2.1 조합 시스템
조합 시스템 Combinational System : 클락을 사용하지 않는 디지털 회로
디지털 회로(Digital circuit) : binary 정보를 조작하는 하드웨어 부품
논리 게이트는 논리 함수를 구현한다.
논리 함수 : AND, OR, NOT, XOR, NOR, NAND
Boolean Algebra : 논리 함수를 특정하고 변환하기 위한 수학적 시스템
Level of Abstraction 추상화 레벨
2.2 Logical Operation 논리 연산자
- 기본 연산자
AND ( · )
| x | y | xy |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
OR (+)
| x | y | x+y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
NOT (~)
| x | ~x |
|---|---|
| 0 | 1 |
| 1 | 0 |
XOR (⊕)
| x | y | x⊕y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NAND / (xy)'
| x | y | (xy)' |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR / (x+y)'
| x | y | (x+y)' |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
XNOR (x⊙y)
| x | y | x⊙y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
- 스위치에서의 논리 연산자
AND → 직렬
OR → 병렬
NOT → 기본적으로 닫혀있는 스위치
똑같은 논리 함수에 대해 진리표(truth table), 논리 선도(logic diagram), 논리식(boolean equation)로 표현할 수 있다.
- 논리 선도
2.3 Switching Algebra
- Commutative (교환 법칙)
a + b = b + a
ab = ba
- Associative (결합 법칙)
a + (b + c) = (a + b) + c
a(bc) = (ab)c
- Identity (항등원)
a + 0 = a
0 + a = a
a · 1 = a
1 · a = a
- Null (무효화)
a + 1 = 1
1 + a = 1
a · 0 = 0
0 · a = 0
- Complement (보수)
a + a' = 1
a' + a = 1
a · a' = 0
a' · a = 0
- Idempotency (등멱 법칙)
a + a = a
a · a = a
- Involution (퇴화 법칙)
(a')' = a
- Distributive (분배 법칙)
a(b + c) = ab + ac
a + bc = (a + b)(a + c)
- Adjacency (통합)
ab + ab' = a
(a + b)(a + b') = a
a'b' + ab' + a'b + ab = 1
(a' + b')(a' + b)(a + b')(a + b) = 0
- Simplification (간소화)
a + a'b = a + b
a(a' + b) = ab
- DeMorgan (드 모르간의 법칙)
(a + b)' = a'b'
(ab)' = a' + b'
- Absorption (흡수 법칙)
a + ab = a
a(a + b) = a
증명)
a + ab = a · 1 + ab = a(1 + b) = a · 1 = a
a(a + b) = a + ab = a
- Consensus (컨센서스 법칙)
at1 + a't2 + t1t2 = at1 + a't2
(a + t1)(a' + t2)(t1 + t2) = (a + t1)(a' + t2)
증명)
at₁ + a’t₂ + t₁t₂ =
= at₁ + a’t₂ + 1 · t₁t₂ (identity)
= at₁ + a’t₂ + (a+a’)t₁t₂ (complement)
= at₁ + a’t₂ + at₁t₂ + a’t₁t₂ (distributive)
= at₁ (1+t₂) + a’t₂ (1+t₁) (distribute)
= at₁ · 1 + a’t₂ · 1 (null)
= at₁ + a’t₂
- ab + a'c = (a + c)(a' + b)
증명)
ab + a'c
= (ab + a')(ab + c) (distribute)
= (a + a')(a' + b)(a + c)(b + c) (distribute)
= 1(a' + b)(a + c)(b + c) (complement)
= (a + c)(a' + b) (consensus)
- 표현의 단순화
논리 함수는 최대한 단순하게 표현한다.
AB + A'CD + A'BD + A'CD' + ABCD
= AB + AB(CD) + A'C(D+D') + A'BD (교환 법칙, 분배 법칙)
= AB + A'C + A'BD (흡수 법칙, 보수 법칙)
= B(A + A'D) + A'C (분배 법칙)
= B(A + D) + A'C (간소화)
- 드 모르간 법칙을 통한 보수화
F = wx'y + xy' + wxz
F' = (w'+x+y')(x'+y)(w'+x'+z')
2.4 Canomical Forms 표준 형식
- Minterm
- x,y,z에 대한 minterms
곱으로 나타낸 모든 항
| x y z | Minterms | Notation |
|---|---|---|
| 0 0 0 | x'y'z' | m0 |
| 0 0 1 | x'y'z | m1 |
| 0 1 0 | x'yz' | m2 |
| 0 1 1 | x'yz | m3 |
| 1 0 0 | xy'z' | m4 |
| 1 0 1 | xy'z | m5 |
| 1 1 0 | xyz' | m6 |
| 1 1 1 | xyz | m7 |
F1 = m3 + m5 + m6 + m7 = x'yz + xy'z + xyz' + xyz
→ 1-minterms
F'1 = m0 + m1 + m2 + m4 = x'y'z' + x'y'z + x'yz' + xy'z'
→ 0-minterms
어떤 Boolean 함수라도 1-minterms의 합으로 표현할 수 있다.
ex)
F1 = ∑(3,5,6,7)
F'1 = ∑(0,1,2,4)
ex) F = x + yz
= x(y+y')(z+z')+(x+x')yz
=xyz+xyz'+xy'z+xy'z'+xyz+x'yz
=xyz+x'yz+xyz'+xy'z+xy'z'
=m7 + m3 + m6 + m5 + m4
= ∑(3,4,5,6,7)
- Maxterm
- x,y,z에 대한 maxterms
합으로 나타낸 모든 항
| x y z | Maxterms | Notation |
|---|---|---|
| 0 0 0 | x+y+z | M0 |
| 0 0 1 | x+y+z' | M1 |
| 0 1 0 | x+y'+z | M2 |
| 0 1 1 | x+y'+z' | M3 |
| 1 0 0 | x'+y+z | M4 |
| 1 0 1 | x'+y+z' | M5 |
| 1 1 0 | x'+y'+z | M6 |
| 1 1 1 | x'+y'+z' | M7 |
ex) F1(x,y,z) = x'yz+xy'z+xyz'+xyz
(F1)' = (x+y'+z')(x'+y+z')(x'+y'+z)(x'+y'+z')
= M3M5M6M7
= ∏(3,5,6,7)
F1 = M0M1M2M4
ex) F = x'y'+xz
=(x'y'+x)(x'y'+z)
=(x+x')(x+y')(x'+z)(y'+z)
=(x+y')(x'+z)(y'+z)
=(x+y'+z)(x+y'+z')(x'+y+z)(x'+y'+z)(x+y'+z)(x'+y'+z)
=(x+y'+z)(x+y'+z')(x'+y+z)(x'+y'+z)
=M2M3M4M6
=∏(2,3,4,6)
- Mintern 과 Maxterm은 서로 보수이다.
f = m0+m1+m5+m7 = M2M3M4M6
곱의 합 수식 sum of products(SOP) : 한 개 이상의 곱항들이 OR 연산자로 연결된 것.
합의 곱 수식 product of sums(POS) : 한 개 이상의 합항들이 AND 연산자로 연결된 것
