불 대수 (2)

1. Dulity (쌍대성)

Duality(쌍대성)이란 어떤 수학적 구조를 뒤집어서 구성한 것을 나타낸다. 이 때 만약 A가 성립했다면 A의 쌍대인 B도 성립한다는 것이 바로 Duality(쌍대성)이다.

 

---

Boolean Algebra의 쌍대 조건

 

AND는 OR로, 0은 1로

바꾸면 쌍대 수식이 된다.

 

---

 

예를 들면 $X + 0 = X$라는 명제가 참이면 $+$(OR)은 $\cdot$(AND)로, 0은 1로 바꾸면$X \cdot 1 = X$이 되고 이 명제 역시 반드시 참이 된다. 이를 진리표로 다시 확인해보자. 만일 하나의 입력이 0이고, 나머지 입력이 X(0 or 1)이라면, OR 연산의 출력은 X 자기 자신이 된다.

 

A	B	OR
0	0	0
0	1	1
1	0	1
1	1	1

 

진리표를 통해 위 수식이 참임을 보였다. 이에 대한 쌍대 수식 $X \cdot 1 = X$을 보자. 마찬가지로 하나의 입력이 1이고, 나머지 입력이 X(0 or 1)이라면 AND연산의 출력은 역시 자기 자신이 된다.

 

A	B	AND
0	0	0
0	1	0
1	0	0
1	1	1

 

이러한 성질이 Boolean Algebra의 쌍대성이다. 이를 통해서 Boolean Algebra의 공리(Axioms)들을 추출해보자.

 

2. Axioms (공리)

Boolean Algebra의 공리들을 나열한다. 우측의 공리들은 좌측의 공리들의 쌍대이다. 때문에 공리를 외워야한다면 좌측의 공리 (X OR 0, 1, X, X' → X, 1, X, 1)만 외우고 우측 공리들은 쌍대성으로 만들어내면 된다. (쌍대성을 이용하면 X AND 1, 0, X, X' = X, 0, X, 0가 된다)

 

$X + 0 = X$ (OR 항등원 = 0)	$X \cdot 1 = X$ (AND 항등원 = 1)
$X + 1 = 1$ (1과 OR연산 = 반드시 1)	$X \cdot 0 = 0$ (0과 AND연산 = 반드시 0)
$X + X = X$ (멱등 정리 = 여러번 연산해도 그대로)	$X \cdot X = X$ (멱등 정리 = 여러번 연산해도 그대로)
$X + X' = 1$ (자기자신과 NOT과의 OR = 반드시 1)	$X \cdot X' = 0$ (자기자신과 NOT과의 AND = 반드시 0)
$(X')' = X$ (누승 정리, NOT 2n번 = 원본)

 

3. 중요한 법칙 3가지

 

---

1) 교환법칙 :

 

$X + Y = Y + X$

 

$X \cdot Y = Y \cdot X$

 

---

2) 결합법칙 :

 

$(X + Y) + Z = X + (Y + Z) = X + Y + Z$

 

$(X \cdot Y) \cdot Z = X \cdot (Y \cdot Z) = X \cdot Y \cdot Z$

 

◎ 결합법칙의 의의 : 2개의 게이트를 1개로 줄일 수 있다.

 

 

---

3) 분배법칙 : 

 

$X \cdot (Y+Z) = XY + XZ$

 

$X + (YZ) = (X + Y)(X + Z)$

→ 덧셈 분배는 일반 대수에서는 

안되지만 불대수에서는 가능하다.

 

---

 

4. 드모르간의 법칙

논리학에서 매우 중요한 법칙이다. 설명은 아래 그림으로 설명을 대체한다.

 

[그림] 드모르간의 법칙

 

5. 간략화 기법

(1) 위에서 언급한 많은 법칙을 사용하는 방법 : 너무 비효율적이다.

(2) 진리표를 거쳐서 간략화 하는 방법 (카르노맵, Q-M 방식)

 

(1)은 너무 비효율적이다. 때문에 우리는 (2) 방법만 공부한다.

 

6. Reference