5 불대수 Http://RAIC.kunsn..kr
2 학습목표 마스터제목스타일편집 기본논리식의표현방법을알아본다. 불대수의법칙을알아본다. 논리회로를논리식으로논리식을논리회로로표현하는방법을알아본다. 곱의합 (SOP) 과합의곱 (POS), 최소항 (minterm) 과최대항 (mxterm) 에대해알아본다. 01. 기본논리식의표현 02. 불대수법칙 03. 논리회로의논리식변환 04. 논리식의회로구성 05. 불대수식의표현형태 06. 불대수법칙을이용한논리식의간소화
01 기본논리식의표현 3 Boole 연산 (Boolen Opertion) Boole 연산이란각 gte 의연산을변수를사용하여편리하게표현한다. 기호학 (Symbology) -. 변수와변수표현은대문자사용 -. 단일변수또는몇개의변수의함수는 1 또는 0 값중하나이다. -. Boole 대수에서 2진숫자는디지털논리회로내에생기는두개의레벨로표현하기위하여활용됨. 즉, 2진에서 1은 HIGH 레벨로 0은 LOW 레벨로표현
01 기본논리식의표현 4 기본적인불대수식은 AND, OR, NOT을이용하여표현 AND 식은곱셈의형식으로표현하고, OR 식은덧셈의형식으로표현 NOT 식은 X 또는 X ' 로표현 완전한논리식은입력항목들의상태에따른출력을결정하는식 X0 nd Y1 일때출력을 1 로만들려는경우출력논리식 F XY X0 or Y1 일때출력을 1 로만들려는경우출력논리식 (X0 nd Y1) or (X1 nd Y0) 일때출력을 1 로만들려는경우출력논리식 F X Y F XY XY
01 기본논리식의표현 5 1. NOT 2. AND 입력변수를 A, 출력변수를 X 라하면 입력변수를 A 와 B, 출력변수를 X 라하면 A X A X A A B XAB X AB A0, B0: XAB0 00 A0, B1: XAB0 10 A1, B0: XAB1 00 A1, B1: XAB1 11 : 2 개의입력이모두 HIGH 일때만 HIGH 가됨 [ 그림 1] Inverter 기능에대한 Boole 식 X ABC X ABCD A B C XABC A B C D XABCD [ 그림 2] AND 기능에대한 Boole 식
01 기본논리식의표현 6 3. OR 입력변수를 A,B, 출력변수를 X 라하면 X A B A B XAB A0, B0: XAB000 A0, B1: XAB011 A1, B0: XAB101 A1, B1: XAB111 : 2 개의입력이모두 LOW 이면출력이 LOW 가됨 X A B C X A B C D A B C XABC A B C D XABCD [ 그림 3] OR 기능에대한 Boole 식
01 기본논리식의표현 7 4. NAND X AB : 2 개의입력변수 A, B 를먼저 AND 하고, Br 를명시하여보수를취함 A 0, B 0 : X A B 0 0 0 1 A 0, B 1: X A B 0 1 0 1 A 1, B 0 : X A B 1 0 0 1 A 1, B 1: X A B 1 1 1 0 5. NOR X A B : 2 개의입력변수 A, B 를먼저 AND 하고, Br 를명시하여보수를취함 A 0, B 0 : X A 0, B 1: X A 1, B 0 : X A 1, B 1: X A B 0 0 0 1 A B 0 1 1 0 A B 1 0 1 0 A B 1 1 1 0
8 마스터제목스타일편집 01 기본논리식의표현 1 입력논리식, 2 입력논리식, 3 입력논리식 1 입력논리식 2 입력논리식 3 입력논리식 입력 출력 입력 출력 입력 출력 X F X Y F X Y Z F 0 F X 0 0 F X Y 0 0 0 F X Y Z 1 F X 0 1 F X Y 0 0 1 F X Y Z 1 0 F X Y 0 1 0 F X Y Z 1 1 F X Y 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 F X Y Z F X Y Z F X Y Z F X Y Z F X Y Z
01 기본논리식의표현 2 입력논리식예 입력 출력 X Y F 0 0 1 0 1 1 1 0 1 1 1 0 F X Y 3입력논리식예 F X YZ 입력 출력 X Y Z X1 Y Z YZ X YZ 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 X0 또는 Y0 일때, 1 을출력하는논리식 X1 이거나 (Y0 이고 Z1) 일때, 1 을출력하는논리식 9
02 불대수법칙 10 불대수공리 (boolen Postultes) P1 X 0 or X 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
02 불대수법칙 11 불대수기본법칙 1. X00XX 2. X 11 XX 3. X11X1 4. X 00 X0 5. XXX 6. X XX 7. X X 1 8. X X 0 9. X X 교환법칙 (ommuttive lw) 10. XYYX 11. XYYX 결합법칙 (ssoite lw) 12. (X Y) Z X (Y Z) 13. (XY) Z X (YZ) 분배법칙 (distributive lw) 14. X (Y Z) XY XZ 15. X YZ (XY)(XZ)
02 불대수법칙 12 드모르간의정리 (De Morgn's theorem) 16. X Y X Y 17. XY X Y 흡수법칙 (bsorptive lw) 18. X XY X 19. X(XY) X 합의의정리 (onsensus theorem) 20. XY YZ XZ XY XZ 21. ( X Y )( Y Z)( X Z) ( X Y )( X Z)
13 교환법칙 (Commuttive Lws) <2 개의변수에대한가산의교환법칙 > <2 개의변수에대한승산의교환법칙 > A B B A AB BA A B AB B A BA A B AB B A BA [ 가산의교환법칙의예 ] [ 승산의교환법칙의예 ]
14 결합법칙 (Assoitive Lws) <3 개의변수에대한가산의결합법칙 > A ( B C) ( A B) C A B C BC ABC A B C AB ABC [ 가산의결합법칙의예 ] <3개의변수에대한승산의결합법칙 > A ( BC) ( AB) C A B C BC ABC A B C AB ABC [ 승산의결합법칙의예 ]
15 분배법칙 (Distributive Lws) <3 개의변수에대한분배법칙 > A ( B C) AB AC B C A (BC) XA(BC) X A B A C AB AC XABAC X [ 분배법칙의예 ]
02 불대수법칙 16 진리표를이용한분배법칙 X YZ (XY)(XZ) 의증명 X Y Z 좌측식우측식 Y Z XY Z XY XZ (XY)(XZ) 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 동일한결과
02 불대수법칙 17 드모르간의정리증명 X Y XY 좌측식우측식 X Y X Y XY 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 동일한결과 드모르간의일반식 X 1 X 2 X n X 1 X 2 X n X X 1 2 X n X 1 X 2 X n
18 마스터제목스타일편집 02 불대수법칙 합의의정리증명 입력 XY YZ XZ XY X Y Z XY YZ XZ XY YZ XZ XY XZ XY XZ 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 1 1 0 1 1 0 1 XZ 동일한결과
02 불대수법칙 19 드모르간의정리예제 X Y Z ( X Y ) Z ( X Y ) Z X Z Y Z W X YZ W X YZ ( W X ) YZ WYZ XYZ ( A B) C D E F ( A B) C D E F ( A B C D) E F ( A B C D) E F A B E F C E F D E F AB( CD EF)( AB CD) AB ( CD EF) ( AB CD) AB ( CD EF) AB CD AB ( C D)( E F) ABCD AB CE CF DE DF ABCD
20 마스터제목스타일편집 03 논리회로의논리식변환 원래의회로에게이트를거칠때마다게이트의출력을적어주면서한단계 씩출력쪽으로나아가면된다. 논리회로 논리식유도과정 Y Z Y Z YZ (YZ)WX W X X Y F W X X Y WX XY F (YZ)WXXY
21 마스터제목스타일편집 03 논리회로의논리식변환 b b 예 1 b d f b d bd f bd b b 예 2 b d f b d bd f () (bd)()
22 마스터제목스타일편집 03 논리회로의논리식변환 B C A F 예 3 B C A BC A (BC)A F (BC)AABC C ABC
04 논리식의회로구성 23 AND, OR, NOT 을이용하여논리식으로부터회로를구성.(AND-OR 로구성된회로 ) x y x y yz 보수입력사용 NOT 게이트사용 x y xy x y x xy x y y z xy yz f xyxyyz z y xy yz f xyxyyz
24 마스터제목스타일편집 04 논리식의회로구성 x y z x y z AND-OR x y z x y z f f ( x, y, z) xyz xyz x yz x yz xyz x y z OR-AND x y x y z f f ( x y)( x y z)
04 논리식의회로구성 25 다단계논리회로 x z w v y xz xzw wxy (xzw)v f f z wxy v( xz w)
26 마스터제목스타일편집 05 불대수식의표현형태 1. 곱의합과최소항 곱의합 (Sum of Produt, SOP) SOP의구성은 1 단계는 AND항 ( 곱의항, produt term) 으로구성되고, 2 단계는 OR항 ( 합의항, sum term) 으로만들어진논리식. b b d f f bd 최소항 (Minterm) 최소항 : 표준곱의항 표준곱의항이란함수에모든변수를포함하고있음. W XY Z WXYZ minterm W XY W X Z Non minterm
05 불대수식의표현형태 27 진리표로부터최소항식을표현하는방법 입력 출력 b f 0 0 0 0 1 1 1 0 1 1 1 1 (0 AND b1) OR (1 AND b0) OR (1 AND b1) 일때, f 1이다. 또는 ( 1AND b1) OR (1 AND b 1) OR (1 AND b1) 일때, f 1이다. 또는 b 1 OR b 1 OR b 1 일때, f 1이다. f b b b
05 불대수식의표현형태 28 2 변수최소항의표현방법 b 최소항 기호 0 0 b m 0 0 1 b m 1 1 0 b m 2 1 1 b m 3 f (, b) b b b m1 m2 m m(1, 2, 3) 3
05 불대수식의표현형태 29 3 변수최소항의표현방법 b 최소항기호 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 b m 0 m 1 m 2 m 3 m 4 m 5 m 6 m 7
05 불대수식의표현형태 3 변수최소항의표현방법 x y z f 최소항기호 0 0 0 1 x y z 0 0 1 1 x y z 0 1 0 0 x y z 0 1 1 1 x y z 1 0 0 0 x y z 1 0 1 1 x y z 1 1 0 0 x y z 1 1 1 1 x y z m 0 m 1 m 2 m 3 m 4 m 5 m 6 m 7 f ( x, y, z) m( 0, 1, 3, 5, 7) x yz x yz xyz f ( x, y, z) m(2, 4, 6) xyz x yz xyz x yz xyz f ( x, y, z) m(0,1, 3, 5, 7) x yz x yz xyz x yz xyz f ( x, y, z) m(2, 4, 6) x y z x y z x y z f ( x, y, z) m(2, 4, 6) x y z x y z x y z m(0,1, 3, 5, 7) x yz x yz xyz x yz xyz 30
05 불대수식의표현형태 31 예제 5-1 다음진리표를이용하여 f 와 f 를최소항식으로나타내어라. b f f 0 0 0 0 1 f (, b, ) m(1, 2, 3, 4, 5) 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 f (, b, ) m(0, 6, 7) 1 1 0 0 1 1 1 1 0 1
05 불대수식의표현형태 32 4 변수최소항의표현방법 b d 최소항기호 b d 최소항기호 m 0 0 0 0 0 d 1 0 0 0 0 0 0 1 d m 1 1 0 0 1 0 0 1 0 d m 2 1 0 1 0 0 0 1 1 d m 3 1 0 1 1 0 1 0 0 d m 4 1 1 0 0 0 1 0 1 d m 5 1 1 0 1 0 1 1 0 d m 6 1 1 1 0 0 1 1 1 d m 7 1 1 1 1 d d d d d d d d m 8 m 9 m 10 m 11 m 12 m 13 m 14 m 15 [Exmple] f (, b,, d) m(0, 1, 5, 9, 11,15) d d d d d d
33 마스터제목스타일편집 05 불대수식의표현형태 2. 합의곱과최대항 합의곱구성 : 1 단계는 OR 항 ( 합의항, sum term) 으로구성되고, 2 단계는 AND 항 ( 곱의항, produt term) 으로만들어진논리식. 모든변수를포함하는 OR 항을맥스텀 (mxterm) 또는최대항이라한다. 최대항의예 w x y w x y z z 합의곱의예 ( w x)( w y) w ( w y) w w x ( w x y z)( w x y z)
05 불대수식의표현형태 34 최대항표현방법 b 최대항 기호 0 0 0 1 1 0 1 1 b b b b M 0 M 1 M 2 2 변수인경우 M 3 b 최대항기호 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 b b b b b b b b 3 변수인경우 M 0 M 1 M 2 M 3 M 4 M 5 M 6 M 7
05 불대수식의표현형태 35 b d 최대항기호 b d 최대항기호 0 0 0 0 b d M 0 1 0 0 0 0 0 0 1 b d M 1 1 0 0 1 0 0 1 0 b d M 2 1 0 1 0 0 0 1 1 b d M 3 1 0 1 1 0 1 0 0 b d M 4 1 1 0 0 0 1 0 1 b d M 5 1 1 0 1 0 1 1 0 b d M 6 1 1 1 0 0 1 1 1 b d 1 1 1 1 M 7 b d b d b d b d b d b d b d b d M 8 M 9 M 10 M 11 M 12 M 13 M 14 M 15 4 변수인경우
05 불대수식의표현형태 36 [Exmple] f (, b) ( b)( b)( M 0 M1 M 2 M (0,1, 2) b) 입력 출력 b f 0 0 0 0 1 0 1 0 0 1 1 1
05 불대수식의표현형태 37 예제 5-2 다음최대항식을진리표로만들어보고, 논리식을구해보아라. f ( x, y, z) M (0,1, 3, 5, 7) x y z f 최대항기호 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 x y z x y x y x y x y x y x y x y z z z z z z z M 0 M 1 M 2 M 3 M 4 M 5 M 6 M 7 f ( x, y, z) M (0,1, 3, 5, 7) ( x y z)( x y z)( x y z)( x y z)( x y z)
05 불대수식의표현형태 38 3. 최소항과최대항과의관계 최소항은출력이 1 인항을 SOP 로나타낸것이고, 최대항은출력이 0 인항을 POS 로나타낸것이다. 최소항과최대항은반대의성질을가진다. b f f 최소항기호최대항기호관계 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 0 1 m 0 m 1 m 2 m 3 m 4 m 5 m 6 m 7 b M 0 b b b b b b b M 1 M 2 M 3 M 4 M 5 M 6 M 7 M 0 m 0 M 1 m 1 M 2 m 2 M 3 m 3 M 4 m 4 M 5 m 5 M 6 m 6 M 7 m 7
39 7) 6, (0, 7) 6, (0, 5) 4, 3, 2, (1, 5) 4, 3, 2, (1, ),, ( m M M m b f 5) 4, 3, 2, (1, ) )( )( )( )( ( 5) 4, 3, 2, (1, ),, ( M b b b b b m b f 7) 6, (0, ) )( )( ( 7) 6, (0, ),, ( M b b b m b f 5) 4, 3, 2, (1, 5) 4, 3, 2, (1, 7) 6, (0, 7) 6, (0, ),, ( m M M m b f 최소항을부정하면최대항최대항을부정하면최소항 05 불대수식의표현형태
06 불대수법칙을이용한논리식의간소화 40 (1) 식을간소화하는과정 (1) x yz xyz x yz x yz xyz xyz xyz x yz x yz xyz xyz (2) (3) (4) x y x y xyz x y x y xz x y x y yz ( xyz xyz) ( x yz x yz) ( xyz xyz) xy( z z) x y( z z) yz( x x) xy 1 x y 1 xy x y yz yz 1 XXX 를이용 xyz xyz x yz x yz xyz ( xyz xyz) ( x yz x yz) xy( z z) x y( z z) xyz xy 1 x y 1 xyz xy x y xyz xyz xyz xyz x yz x yz xyz x yz ( xyz xyz) ( x yz x yz) ( xyz x yz) xy( z z) x y( z z) xz( y y) xy 1 x y 1 xy x y xz xz 1 XXX 를이용
41 마스터제목스타일편집 06 불대수법칙을이용한논리식의간소화 (2) 식을간소화하는과정 (1) x yz xyz x yz x yz xyz (2) x y x y xyz (3) x y x y xz b ( )( b) 1 ( b) b (4) x y x y yz ( b) b 0 b b xy x y xyz xy x( y yz) xy x( y y)( y z) xy x 1( y z) xy x y xz xy x y xyz y( x xz) x y y( x x)( x z) x y y 1( x z) x y xy yz x y
06 불대수법칙을이용한논리식의간소화 42 예제 5-3 논리식 b 를간소화하여라. ( ) ( b b) ( b) ( b)( ) ( b) b b ( b) b ( b) b b b b( ) b( ) b b
43 마스터제목스타일편집 06 불대수법칙을이용한논리식의간소화 간소화하는과정예 f ( x, y, z) m(0,1, 3, 5, 7) x yz x yz xyz x yz xyz x y( z z) xz( y y) xz( y x y xz xz x y z( x x) x y z y) f ( x, y, z) m(0,1, 3, 5, 7) m(2, 4, 6) xyz x yz xyz yz( x x) xz( y y) yz xz
06 불대수법칙을이용한논리식의간소화 예제 5-4 다음진리표를보고논리식을구하고간소화하여라. b f f 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 0 1 f (, b, ) m(1, 2, 3, 4, 5) ( ) b b( ) b( ) b b b f (, b, ) m(0, 6, 7) b( ) b 44
06 불대수법칙을이용한논리식의간소화 2 변수로나타낼수있는모든경우 b f 0 f 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 f 10 f 11 f 12 f 13 f 14 f 15 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 변수로나타낼수있는모든경우의논리식 f 0 0 f b 1 f 2 b f 3 f b f b 4 f 5 b f 6 b b 7 8 f 9 b b f 10 b f 11 b 12 f 13 b f 14 b f 15 1 f b f n개의입력변수가있을때진리표의행의개수는 2 개이며, 2 개의서로다른함 수가존재. n2 2 2 2 2 16 n3 2 8 2 2 256 n4 2 16 2 65536 n 2 n 45
06 불대수법칙을이용한논리식의간소화 46 b f 0 f 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 f 10 f 11 f 12 f 13 f 14 f 15 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 f b b ( b b) 3 f b b ( ) b b 5 f b b b b b b b b b b b ( ) b ( b b) b 7 f b b ( ) b b 10 f b b b b b b b b b b b b 11 f b b ( b b) 12 f b b b b b b b b 13 f b b b b b b b b 14
47