Boolean Algebra
불 대수
- Boolean algebra provides the theoretical foundation for digital logic design.
- 순서론과 추상대수학, 논리학에서, Boolean algebra는 어떤 명제의 참과 거짓을 이진수 1과 0에 대응시켜서
명제와 명제간의 관계를 수학적으로 표현하는 것이다.
- 논리적 공리들을 만족시키는 논리합과 논리곱 및 부정의 연산이 정의된 대수 구조이다.
Notation (표기법)
\(A \iff B\)
- 식 A와 식 B가 동치(Equivalent; 논리적으로 같음)임을 의미한다.
\(A \land B \iff A \cdot B \iff AB\)
- A AND B의 의미로, 두 변수 사이에 논리곱(\(\land\))을 넣거나, 온점을 찍는 것으로 표기한다.
\(A \lor B \iff A + B\)
- A OR B의 의미로, 두 변수 사이에 논리합(\(\lor\))을 넣거나, 플러스 기호를 쓰는 것으로 표기한다.
\(\bar{X} \iff X' \iff !X \iff NOT X\)
- NOT(X)의 의미로, 변수 위에 Bar를 붙이거나, 우측 상단에 Prime을 찍는 것으로 표기한다.
\(\bar{f}(A, B) \iff \bar{A + B} \iff (A + B)' \iff !(A + B) \iff NOT(A + B)\)
Precedence of Operations (연산자 우선순위)
Parentheses(괄호) > NOT(반전) > AND(논리곱) > OR(논리합)
Axioms of Boolean Algrbra (불 대수에서의 공리)
\(1a.\quad0 \cdot 0 = 0\\
1b.\quad0 + 0 = 0\\
2a.\quad1 \cdot 1 = 1\\
2b.\quad1 + 1 = 0\\
3a.\quad0 \cdot 1 = 1 \cdot 0 = 0\\
3b.\quad1 + 0 = 0 + 1 = 1\\
4a.\quad \mathrm{If} \;x = 0, \mathrm{then} \; \bar{x} = 1\\
4b.\quad \mathrm{If} \;x = 1, \mathrm{then} \; \bar{x} = 0\)
Single-Variable Theorems (단일 변수 정리)
\(5a.\quad x \cdot 0 = 0\\
5b.\quad x + 1 = 1\\
6a.\quad x \cdot 1 = x\\
6b.\quad x + 0 = x\\
7a.\quad x \cdot x = x\\
7b.\quad x + x = x\\
8a.\quad x \cdot \bar{x} = 0\\
8b.\quad x + \bar{x} = 1\\
9.\quad\;\; \bar{\bar{x}} = x\)
* Principle of Duality (이중성의 법칙)
- 참인 논리식에서, \(\cdot\) 연산자들과 +연산자들을 서로 맞바꿈과 동시에 0들과 1들을 서로 맞바꾸어도 해당 논리식은 참이다.
2 and 3 Variables Properties (2-3개 변수들의 성질)
Commutative
\(10a.\quad x \cdot y = y \cdot x\\
10b.\quad x + y = y + x\)
Associative
\(11a.\quad x \cdot (y \cdot z) = (x \cdot y) \cdot z\\
11b.\quad x + (y + z) = (x + y) + z\)
Distributive
\(12a.\quad x \cdot (y + z) = x \cdot y + x \cdot z\\
12b.\quad x + y \cdot z = (x + y) \cdot (x + z)\)
\(pf. 12b. (x + y) \cdot (x + z)\\
\iff x \cdot x + x \cdot z + x \cdot y + y \cdot z\\
\iff x + x \cdot z + x \cdot y + y \cdot z\\
\iff x \cdot (1 + z + y) + y \cdot z\\
\iff x \cdot 1 + y \cdot z\\
\iff x + y \cdot z\)
Absorption
\(13a.\quad x + x \cdot y = x\\
13b.\quad x \cdot (x + y) = x\)
Combining
\(14a.\quad x \cdot y + x \cdot \bar{y} = x\\
14b.\quad (x + y) \cdot (x + \bar{y}) = x\)
\(14b.\)의 증명은 \(12b.\)증명과정에서 \(z\)를 \(\bar{y}\)로 치환하여 증명할 수 있다.
DeMorgan's Theorem
\(15a.\quad (x \cdot y)' = \bar{x} + \bar{y}\\
15b.\quad (x + y)' = \bar{x} \cdot \bar{y}\\
16a.\quad x + \bar{x} \cdot y = x + y\\
16b.\quad x \cdot (\bar{x} + y) = x \cdot y\)
\(pf. 16a. x + \bar{x} \cdot y\\
\iff (x + \bar{x}) \cdot (x + y) \qquad \mathrm{by.} 12b.\\
\iff x + y\)
Consensus (Insertion & Deletion)
\(17a.\quad x \cdot y + y \cdot z + \bar{x} \cdot z = x \cdot y + \bar{x} \cdot z\\
17b.\quad (x + y) \cdot (y + z) \cdot (\bar{x} + z) = (x + y) \cdot (\bar{x} + z)\)
\(pf. 17a. x \cdot y + y \cdot z + \bar{x} \cdot z\\
\iff x \cdot y + (x + \bar{x}) \cdot y \cdot z + \bar{x} \cdot z\\
\iff (x \cdot y + x \cdot y \cdot z) + (\bar{x} \cdot y \cdot z + \bar{x} \cdot z)\\
\iff xy + \bar{x} \cdot z \qquad \mathrm{by.} 13a\)
\(pf. 17b. (x + y) \cdot (y + z) \cdot (\bar{x} + z)\\
\iff (x + y) \cdot (x \cdot \bar{x} + y + z) \cdot (\bar{x} + z)\\
\iff (x + y) \cdot (x + y + z) \cdot (\bar{x} + y + z) \cdot (\bar{x} + z) \qquad \mathrm{by.} 12b\\
\iff (x + y) \cdot (\bar{x} + z) \qquad \mathrm{by.} 13b\)
Partition for Truth Table (진리표 분할법)
- 진리표를 분할하여 어느정도 최적화 된 논리식을 추출하는 방법이다.
- 진리표 상에서 Input과 Output 사이의 패턴을 분석하여 논리식을 세우는 방식이다.
Ex.
| \(A\) | \(B\) | \(C\) | \(F_1\) | \(F_2\) |
| 0 | 0 | 0 | 1 (①) | 1 (③) |
| 0 | 0 | 1 | 1 (①) | 1 (③) |
| 0 | 1 | 0 | 0 | 0 (③) |
| 0 | 1 | 1 | 0 | 0 (③) |
| 1 | 0 | 0 | 1 (②) | 0 (④) |
| 1 | 0 | 1 | 1 (②) | 1 (④) |
| 1 | 1 | 0 | 0 | 1 (④) |
| 1 | 1 | 1 | 0 | 1 (④) |
\(F_1\) = A'B' (①) + AB'(②)
\(\iff B'\)
①: \(F_1\)은 A' 조건 하에 B' 이다. (C의 값은 무관하다.)
②: \(F_1\)은 A 조건 하에 B' 이다. (C의 값은 무관하다.)
\(F_2\) = A'B' (③) + A(B + C) (④)
③: \(F_2\)는 A' 조건 하에 B' 이다. (C의 값은 무관하다.)
④: \(F_2\)는 A 조건 하에 (B + C) 이다.
Examples
Optimize logic expression below:
Q.1 \(Z = A'BC + A'\\
\iff A'(BC + 1)\\
\iff A'\\
\therefore Z = A'\)
Q.2 \(Z = (A + B'C + D + EF)(A + B'C + (D + EF)')\\
\iff (A + B'C)(A + B'C) + (A + B'C)(D + EF) + (A + B'C)(D + EF)' + (D + EF)(D + EF)'\\
\iff (A + B'C) + (A + B'C)((D + EF) + (D + EF)') + 0\\
\iff (A + B'C) + (A + B'C) \cdot 1\\
\iff A + B'C\\
\therefore Z = A + B'C \quad \mathrm{by. \; 14b}\)
Q.3 \(Z = (AB + C)(B'D + C'E') + (AB + C)'\\\iff ((AB + C) + (AB + C)')((B'D + C'E') + (AB + C)')\\\iff 1 \cdot B'D + C'E' + (AB + C)'\\\therefore Z = B'D + C'E' + (AB + C)' \quad \mathrm{by. \; 16a}\)
Q.4 \(P = x'yz' + x'yz + xy'z' + xy'z + xyz\\
\iff x'y(z' + z) + xy'(z' + z) + xyz\\
\iff x'y + xy' + xyz\\
\iff x'y + x(y' + yz)\\
\iff x'y + x(y + y')(y' + z)\\
\iff x'y + x(y' + z)\\
\therefore P = x'y + xy' + xz \quad \mathrm{by. \; 16a}\)
Q.5 \(P = A'B'C'D' + A'BC'D' + A'BD + A'BC'D + ABCD + ACD' + B'CD'\\
\iff (A'B'C'D' + A'BC'D') + (A'BD + A'BC'D) + ABCD + ACD' + B'CD'\\
\iff A'C'D' + (A'BD + ABCD) + ACD' + B'CD'\\
\iff A'C'D' + BD(A' + AC) + ACD' + B'CD'\\
\iff A'C'D' + BD(A' + C) + ACD' + B'CD' \quad \mathrm{by. 16a}\\
\iff A'C'D' + A'BD + (BCD + ACD') + B'CD'\\
\iff A'C'D' + A'BD + (BCD + ABC + ACD') + B'CD' \quad \mathrm{by. 17a - Insertion}\\
\iff A'C'D' + (A'BD + BCD + ABC) + ACD' + B'CD'\\
\iff A'C'D' + (A'BD + ABC) + ACD' + B'CD' \quad \mathrm{by. 17a - Deletion}\\
\iff A'C'D' + A'BD + (ABC + ACD' + B'CD')\\
\iff A'C'D' + A'BD + (ABC + B'CD') \quad \mathrm{by. 17a - Deletion}\\
\therefore P = A'C'D' + A'BD + ABC + B'CD'\)
Q.6 \(P = WX + XY + X'Z' + WY'Z'\\
\iff (WX + X'Z') + XY + WY'Z'\\
\iff (WX + WZ' + X'Z') + XY + WY'Z' \quad \mathrm{by. 17a - Insertion}\\
\iff WX + X'Z' + XY + (WZ' +WY'Z')\\
\iff WX + X'Z' + XY + WZ'\\
\iff (WX + WZ' + X'Z') + XY\\
\iff (WX + X'Z') + XY \quad \mathrm{by. 17a - Deletion}\\
\therefore P = WX + X'Z' + XY\)
Boole's Expansion Theorem (Shannon's Expansion Theorem)
\(f(w_1, w_2, \cdots, w_n) \\= w_1' \cdot f(0, w_2, \cdots, w_n) + w_1 \cdot f(1, w_2, \cdots, w_n) = w_1' \cdot f_{w_{1}'} + w_1 \cdot f_{w_1}\)
\(= w_1'w_2' \cdot f(0, 0, w_3, \cdots, w_n) + w_1'w_2 \cdot f(0, 1, w_3, \cdots, w_n) \\+ w_1w_2' \cdot f(1, 0, w_3, \cdots, w_n) + w_1w_2 \cdot f(1, 1, w_3, \cdots, w_n)\)
\(\vdots\)
(Canonical SOP Expansion)
Example.
\(f = w_1w_2 + w_1w_3 + w_2w_3\)
\(= w_1w_2 + w_1\cdot(w_2' + w_2)\cdot w_3 + (w_1' + w_1)\cdot w_2 \cdot w_3\\
= w_1w_2 + w_1w_2'w_3 + w_1w_2w_3 + w_1'w_2w_3\\
= w_1'w_2'\cdot (0) + w_1'w_2(w_3) + w_1w_2'(w_3) + w_1w_2(w_3 + 1) \qquad (w_3 + 1 = 1)\)
\(\iff\)
Reference: Fundamentals of DIGITAL LOGIC with VHDL Design 3E (Stephen Brown, Zvonko Vranesic 저, Mc Graw Hill, 2009)
