2. Two-Level Combinational Logic

1. Logic Functions and Switches
⊙ Axioms of Boolean Algebra
1. B contains at least two elements, a, b, such that a≠b
2. Closure a,b in B,
(i) a + b in B
(ii) a •b in B
3. Commutative Laws: a,b in B,
(i) a + b = b + a
(ii) a •b = b •a
4. Associative Laws: a,b in B,
(i) (a + b) + c = a + (b + c) = a + b + c
(ii) (a • b) • c = a • (b • c) = a • b • c
5. Identities: 0, 1 in B
(i) a + 0 = a
(ii) a •1 = a
6. Distributive Laws:
(i) a + (b •c) = (a + b) •(a + c)
(ii) a •(b + c) = a • b + a •c
7. Complement:
(i) a + a' = 1
(ii) a •a' = 0

⊙ Thm : truth tabel로 표현되는 Boolean function은 Boolean Algebra로 표현될 수 있다.
⊙ NAND, NOR gate는 AND, OR 보다 더 효과적이라, 많이 사용되고, 어떤 Boolean expression도 NAND, NOR, NOT 만으로 구현될 수 있다. 사실, NOT 역시, NAND나 NOR의 input을 묶어 같이 넣어주면 구현가능하다.
⊙ Literal : Boolean expression 에서 한 문자는 하나의 literal 이며, 이는 나중에 wire 개수에 해당한다. literal이 적을 수록 wire가 적게 필요해서 좋다.
(예) Z = AB'C + A'B + A'BC' + B'C : 3 variables, 10 literals

⊙ XOR, XNOR. (내가 초반에 젤 헷갈렸던 것.)
XOR : X or Y but not both ("inequality", "difference")
XNOR : X and Y are the same ("equality", "coincidence")

XOR and XNOR

2. Gate Logic
⊙ Duality : AND ↔ OR, 0s ↔ 1s, literal은 그대로.
► 참이 expression은, 그 dual도 참이다.
(앞의 Boolean Algebra의 Axiom에서 빠진 내용만 보자.)
Simplification Theorems:
9. X •Y + X •Y' = X 9D. (X + Y) • (X + Y') = X
10. X + X •Y = X 10D. X •(X + Y) = X
11. (X + Y') •Y = X •Y 11D. (X •Y') + Y = X + Y
DeMorgan's Law: AND ≡ NOR, OR ≡ NAND, AND/OR ≡ OR/AND
12. (X + Y + Z + ...)' = X' •Y' •Z' •... 12D. (X •Y •Z •...) ' = X' + Y' + Z' + ...
13. {F(X1,X2,...,Xn,0,1,+, •}' = {F(X1',X2',...,Xn',1,0, •,+)}
Duality:
14. (X + Y + Z + ...) = X •Y •Z •... 14D. (X •Y •Z •...) = X + Y + Z + ...
15. {F(X1,X2,...,Xn,0,1,+, •} = {F(X1,X2,...,Xn,1,0, •,+)}
Theorems for Multiplying and Factoring:
16. (X + Y) •(X' + Z) = X •Z + X' •Y
16D. X •Y + X' •Z = (X + Z) •(X' + Y)
Consensus Theorem:
17. (X •Y) + (Y •Z) + (X' •Z) = X •Y + X' •Z
17D. (X + Y) •(Y + Z) •(X' + Z) = (X + Y) •(X' + Z)


⊙ Truth table은 Boolean function의 unique signature이다. 따라서, expression은 여러가지일지라도, truth table은 하나이다.
► Canonical form : Boolean expression의 표준 형식.
(truth table을 그대로 boolean function으로 나타내면 된다.)
► Sum of Product form = minterm (1:A, 0:A')
F = [F 값이 1인 것들의 product를 sum]
F' = [F 값이 0인 것들의 product를 sum]
► Product of Sum = maxterm (1:A', 0:A)
F = [F 값이 0인 것들의 sum을 product]
F' = [F 값이 1인 것들의 sum을 product]

DeMorgan's Law에 의해

3. Two-Level Simplification
⊙ 여기에서의 핵심은, The Uniting Theorem 이다.
A(B'+B) = A
① Boolean Cubes : 4 demensions 이상은 그리기 힘들다.
② Karnaugh Map Method : ~6 demensions
③ CAD Tools : 6 demensions 이상.
(Quine-McCluskey Method)
④ Esspresso Method ( skip )