Prof. Seewhy Lee Presents

Presentation on theme: "Prof. Seewhy Lee Presents"— Presentation transcript:

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

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

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

4 1. 기본 논리식의 표현

5 기본적인 불 대수식은 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로 만들려는 경우 출력 논리식

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

7 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

8 2. 부울 대수 법칙

9 불 대수 공리(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 = = 1

10 불 대수 법칙 기본법칙 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)

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

12

13

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

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

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

17 드모르간의 정리 예제

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

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

20 예 1 예 2

21 4. 논리식의 회로 구성

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

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

24 다단계 논리회로

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

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

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

28 진리표로부터 최소항식을 표현하는 방법 입력 출력 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이다.

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

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

31 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

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

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

34 최대항 표형 방법 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변수인 경우>

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

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

37 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

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

39

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

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

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

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

44 간소화하는 과정 예

45 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

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

47 Thanks for your attention~!!
Prof. Seewhy Lee