5. 불 대수 (Boolean Algebra)

불 대수란, 어떤 명제의 참과 거짓을 이진수 1과 0에 대응시켜 명제와 명제간의 관계를 수학적으로 표현하는 학문이다.

대수학이란?

대수학Algebra은 아래의 요소를 포함한다.

• 다루는 요소 (Boolean, Linear, etc..)
• 연산자
• 공리와 가정 (Axioms and Postulates)

이는 우리가 다루는 요소를 어떻게 다뤄야 할지를 정의하는 학문이기 때문에 중요하다.

Switching Expression vs Schematic Diagram

불 대수를 표현하는 방법으로는 Switching Expression이 사용된다. 잠시 전에 배운 논리 회로와 이를 비교해보자.

각 게이트는 3개의 핀(입출력)을 갖는다. 게이트를 이용한 위 논리 회로에는 총 9개의 signal net과 12개의 핀, 4개의 게이트가 활용되었다.

그러나 Switching Expression을 활용하면 변수 5개와 4개의 연산자를 이용하는 한 줄짜리 수식으로 정리가 된다.

불 대수의 덧셈과 곱셈

불 대수의 덧셈은 OR gate, 곱셈은 AND 게이트에 의해 처리된다. 그 이유는 OR과 AND의 진리표를 보면 직관을 얻을 수 있다.

$a$	$b$	$y$
0	0	0
0	1	1
1	0	1
1	1	1

OR(논리합) 진리표

$a$	$b$	$y$
0	0	0
0	1	0
1	0	0
1	1	1

AND(논리곱) 진리표

 

교환법칙^{Commutative Law}

논리합이나 논리곱에서, 항의 순서를 바꿔도 결과는 같다.

$ A + B = B + A\\
A \cdot B = B \cdot A$

쌍대성 원리^{Duality Principle}

AND를 OR로, OR을 AND로 1을 0으로, 0을 1로 바꿔 만든 방정식을 쌍대라고 한다.
예를들어, $A + B$의 쌍대는 $\overline{A} \cdot \overline{B}$이다.

이때, 어떤 부울식이 참이면, 그 쌍대도 참이다.

결합법칙^{Associative Law}과 분배법칙^{Distributive Law}

논리합과 논리곱에도 결합법칙과 분배법칙이 적용된다.

$ 
A + (B + C) = (A + B) + C\\
A \cdot (B + C) = A\cdot B + A\cdot C
$

드모르간 법칙^{Demorgan law}

$
\text{First Theorem}\\
\overline{A \cdot B} = \overline{A} + \overline{B}\\\\
\text{Second Theorem}\\
\overline{A+B} = \overline{A} \cdot \overline{B}
$

즉, NAND 게이트는 $\overline{A}$와 $\overline{B}$의 OR 연산과, NOR 게이트는 $\overline{A}$와 $\overline{B}$의 AND 연산과 같다는 것이다.

사실 AND와 OR는 같은 구조의 함수이다. 항등원끼리 연산하면 항등원, 이외에는 항등원이 아닌 것이라는 점이 공통점인데, 이때 AND의 항등원은 1(NOT 0)이고 OR의 항등원이 0(NOT 1)일 뿐이다. 두 항에 모두 NOT을 씌워줌으로서 이 항등원을 역전시키므로 두 연산자가 바뀐 것과 같은 효과를 가진다.

A($\overline{A}$)	B($\overline{B}$)	AND($\overline{A} \cdot \overline{B}$)
0(1)	0(1)	0(1)
0(1)	1(0)	0(0)
1(0)	0(1)	0(0)
1(0)	1(0)	1(0)

최소항^Minterm과 최대항^Maxterm

임의의 3가지 변수 $X,Y,Z$를 갖는 함수 $f$가 있다고하자. 이 함수가 가질 수 있는 경우의 수는 $2^3$개이고, 이에 대응하는 출력이 아래와 같다고 보자. 이때, 세 변수 $X, Y, Z$를 논리곱한 값이 Minterm이다.

$X$	$Y$	$Z$	Minterm	$f$
0	0	0	$a'b'c'$	0
0	0	1	$a'b'c$	1
0	1	0	$a'bc'$	0
0	1	1	$a'bc$	1
1	0	0	$ab'c'$	0
1	0	1	$ab'c$	1
1	1	0	$abc'$	1
1	1	1	$abc$	1

이때, 함수 $f$를 곱의 합^{Sum of Product:SOP}로 표현할 수 있다.
$f = m_1 + m_3 + m_5 + m_6 + m_7 = \Sigma m(1,3,5,6,7)$

Maxterm은 세 변수의 합이다. 역시 이를 통해 함수 $f$를 합의 곱^{Product of Sum:POS}로 나타낼 수 있다. 이때, SOP와는 다르게 $f$의 논리값이 0이 나온 것들을 취한다.
$ f = M_0 \cdot M_2 \cdot M_4 = \Pi M(0,2,4)$

이때, minterm과 maxterm은 서로 보수관계에 있는 특징이 있다.

SOP나 POS를 이용해 함수를 표현하는 방식을 Canonical Form이라 한다.

불 대수 정리

Postulate 1	$x + 0 = x$	$ x \cdot 1 = x$
Postulate 2	$x + x' = 1$	$x \cdot x' = 0$
Theorem 1	$x+ x = x$	$x \cdot x = x$
Theorem 2	$x + 1 = 1$	$x \cdot 0 = 0$
Theorem 3. involution	$(x')' = x$
Postulate 3. commutative	$x + y = y + x$	$xy = yx$
Theorem 4. associative	$x + (y + z) = (x + y) + z$	$x(yz) = (xy)z$
Postulate 4. distributive	$x(y + z) = xy + xz$	$x + yz = (x + y)(x + z)$
Theorem 5. DeMorgan	$(x + y)' = x'y'$	$(xy)' = x' + y'$
Theorem 6. absorption	$x + xy = x$	$x(x + y) = x$