Prof. Seewhy Lee Presents Ch. 5 Boolean Algebra 정적 평형 Prof. Seewhy Lee Presents

기본 논리식의 표현 방법을 이해할 수 있다. 불 대수의 법칙을 이해하고 복잡한 논리식을 간소화할 수 있다. 논리회로를 논리식으로, 논리식을 논리회로로 표현할 수 있다. 곱의 합(SOP)과 최소항(minterm) 및 합의 곱(POS)과 최대항(maxterm)의 개념을 이해하고 이를 활용할 수 있다.

Contents 기본 논리식의 표현 불 대수 법칙 논리회로의 논리식 변환 논리식의 회로 구성 불 대수식의 표현 형태 불 대수 법칙을 이용한 논리식의 간소화

1. 기본 논리식의 표현

기본적인 불 대수식은 AND, OR, NOT을 이용하여 표현 NOT식은 𝐴 또는 Aˊ 로 표현 완전한 논리식은 입력 항목들의 상태에 따른 출력을 결정하는 식 A=0 and B=1 일 때 출력을 1로 만들려는 경우 출력 논리식 A=0 or B=1 일 때 출력을 1로 만들려는 경우 출력 논리식 (A=0 and B=1) or (A=1 and B=0) 일 때 출력을 1로 만들려는 경우 출력 논리식

1입력 논리식, 2입력 논리식, 3입력 논리식 1입력 논리식 2입력 논리식 3입력 논리식 입력 출력 A F 입력 출력 A B 1 입력 출력 A B F 1 입력 출력 A B C F 1

A=1이거나 (B=0이고 C=1)일 때, 1을 출력하는 논리식 2입력 논리식 예 A=0 또는 B=0일 때, 1을 출력하는 논리식 입력 출력 A B F 1 3입력 논리식 예 A=1이거나 (B=0이고 C=1)일 때, 1을 출력하는 논리식 입력 출력 A B C A=1 1

2. 부울 대수 법칙

불 대수 공리(Boolean Algebra Axioms) P1 A = 0 or A = 1 P2 0 ∙ 0 = 0 P3 1 ∙ 1 = 1 P4 0 + 0 = 0 P5 1 + 1 = 1 P6 1 ∙ 0 = 0 ∙ 1 = 0 P7 1 + 0 = 0 + 1 = 1

불 대수 법칙 기본법칙 1. A+0=0+A=A 2. A·1=1·A=A 3. A+1=1+A=1 4. A·0=0·A=0 7. 8. 9. 교환법칙(commutative law) 10. A+B=B+A 11. AB=BA 결합법칙(associate law) 12. (A + B) + C = A + (B + C) 13. (AB) C = A (BC) 분배법칙(distributive law) 14. A (B + C) = AB + AC 15. A + BC = (A+B)(A+C)

드모르간의 정리(De Morgan's theorem) 16. 17. 흡수 법칙(absorptive law) 18. A + AB = A 19. A(A+B) = A 합의의 정리(consensus theorem) 20. 21. 쌍대성(duality) : 불 대수 공리나 기본 법칙에서 좌우 한 쌍에서 0과 1을 서로 바꾸고 동시에 ‘•’과 ‘+’를 서로 바꾸면 다른 한 쪽이 얻어지는 성질

진리표를 이용한 분배 법칙 A+BC = (A+B)(A+C) 의 증명 좌측식 우측식 B·C A+B·C A+B A+C (A+B)(A+C) 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 동일한 결과

진리표를 이용한 드모르간의 정리 증명 동일한 결과 A B A+B 좌측식 우측식 0 0 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 0 동일한 결과

드모르간 정리의 일반식 3항 드모르간 정리 4항 드모르간 정리 일반식

드모르간의 정리 예제

3. 논리회로의 논리식 변환

원래의 회로에 게이트를 거칠 때마다 게이트의 출력을 적어주면서 한 단계 씩 출력 쪽으로 나아가면 된다. 논리회로 논리식 유도 과정

예 1 예 2

4. 논리식의 회로 구성

AND, OR, NOT을 이용하여 논리식으로부터 회로를 구성 (AND-OR로 구성된 회로) 보수입력 사용 NOT 게이트 사용

논리식의 2가지 기본 형태 AND-OR OR-AND

다단계 논리회로

5. 부울 대수식의 표현 형태

곱의 합(Sum of Product, SOP) 1. 곱의 합과 최소항 곱의 합(Sum of Product, SOP) SOP의 구성은 1 단계는 AND항(곱의 항, product term)으로 구성되고, 2 단계는 OR항(합의 항, sum term)으로 만들어진 논리식

최소항(Minterm) 최소항 : 표준 곱의 항 표준 곱의 항이란 함수에 모든 변수를 포함하고 있음 예: 4변수 A, B, C, D일 때: 최소항의 예 minterm 곱의 합(SOP)의 예 non minterm

진리표로부터 최소항식을 표현하는 방법 입력 출력 A B F 1 1 (A=0 AND B=1) OR (A=1 AND B=0) OR (A=1 AND B=1) 일 때, F = 1이다. 또는 ( AND B=1) OR (A=1 AND ) OR (A=1 AND B=1) 일 때, F = 1이다. 또는 OR OR 일 때, F = 1이다.

2변수 최소항의 표현 방법 A B 최소항 기호 0 0 m0 0 1 m1 1 0 m2 1 1 m3 입력 출력 A B F m0 1 0 0 m0 0 1 m1 1 0 m2 1 1 m3 입력 출력 A B F m0 1 m1 m2 m3

3변수 최소항의 표현 방법 A B C 최소항 기호 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

3변수 최소항의 표현 예 A B C F 최소항 기호 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

4변수 최소항의 표현 방법 A B C D 최소항 기호 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 [Example]

2. 합의 곱과 최대항 합의 곱 구성 : 1 단계는 OR항(합의 항, sum term)으로 구성되고, 2 단계는 AND항(곱의 항, product term)으로 만들어진 논리식. 모든 변수를 포함하는 OR항을 맥스텀(maxterm) 또는 최대항이라 한다. 예: 4변수 A, B, C, D일 때: 최대항의 예 maxterm 합의 곱(POS)의 예 non maxterm

최대항 표형 방법 A B 최대항 기호 0 0 0 1 1 0 1 1 A B C 최대항 기호 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 1 <2변수인 경우> <3변수인 경우>

A B C D 최대항 기호 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 <4변수인 경우>

[Example] 입력 출력 A B F 0 0 0 1 1 0 1 1 1

3. 최소항과 최대항의 관계 최소항은 출력이 1인 항을 SOP로 나타낸 것이고, 최대항은 출력이 0인 항을 POS로 나타낸 것이다. 최소항과 최대항은 상호 보수의 성질을 가진다. A B C F 𝐹 최소항 기호 최대항 관 계 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

최소항을 부정하면 최대항 최대항을 부정하면 최소항

6. 부울 대수법칙을 통한 논리식의 간소화

(1)식을 간소화하는 과정 1) 2) 3) 4)

(1)식을 간소화하는 과정 동일한 항 추가 X+X=X를 이용 동일한 항 추가 X+X=X를 이용

(2)식을 간소화하는 과정 1) 2) 3) 4)

간소화하는 과정 예

2변수로 나타낼 수 있는 모든 경우 2변수로 나타낼 수 있는 모든 경우의 논리식 A B F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 1 2변수로 나타낼 수 있는 모든 경우의 논리식 n개의 입력 변수가 있을 때 진리표의 행의 개수는 2n개이며, 22n개의 서로 다른 함수가 존재 n=2 n=3 n=4

A B F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 1

Thanks for your attention~!! Prof. Seewhy Lee