5 장부울대수
5.1 부울대수 ã 부울대수 (oolen lger) 를근거로한스위칭이론 (swithing theory) 은논리설계에있어서이론적인근거가되는수학적체계. ã 부울대수 - 부울상수와부울변수로구성, 0과 1의두개값을가짐 - 논리레벨의여러정의 논리 0 Flse Off Low No Open Swith 논리 1 True On High Yes Closed swith - 부울대수는논리회로의입력및출력의상관관계를표현하는방법 ã ã 입력의논리레벨에따라출력결정 논리변수표현 : A, B.. 등과같이문자로표현. 값은 A0 또는 B1 등으로표현 부울대수의기본연산 : 논리동작 (logi opertion) OR, AND, NOT 논리게이트 : 입력신호에대해기본논리연산 (OR, AND, NOT) 을수행하는디지털회로는다이오드, 트랜지스터, 저항등을사용하여구성 - 부울변수를전자회로에서사용할때실제적인전압레벨 0~0.8 V 논리레벨 (logi level) 0, 2~ 5V 논리레벨 1 로표시, 0.8~2V undefined 값, 논리레벨의전이영역 (trnsition region) 2
ã 1 입력논리식, 2 입력논리식, 3 입력논리식 입력 출력 X F 0 1 F X F X 1입력논리식 입력 출력 X Y F 0 0 0 1 1 0 1 1 2 입력논리식 F X Y F X Y F X Y F X Y 입력 출력 X Y Z F 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 입력논리식 F X Y Z F X Y Z F X Y Z F X Y Z F X Y Z F X Y Z F X Y Z F X Y Z 3
v 2 입력논리식예 입력 출력 X Y F 0 0 1 0 1 1 1 0 1 1 1 0 v 3 입력논리식예 F X YZ F X Y 입력 출력 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 을출력하는논리식 4
5.2 부울대수정리 Ý 단일변수에관한정리 ( 공리 ) Ý dulity 성립 : 0 <-> 1, <-> 5
다변수부울대수정리 교환법칙 (9) xy yx (10) x y y x 결합법칙 (11) x(yz) (12) x(yz) (xy)z xyz z (xy)z xyz 분배법칙 (13) x (y z) (13) x yz xy xz (x y)(x z) Asorption (14) x xy x (14) x(xy) x (15) x x'y x y Consensus (16) xyx'zyz xyx'z (16) (xy)(x'z)(yz) (xy)(x'z) < 사용예 > 컨센서스항 (13) 역유도 (xy)(xz) xxxzxyyz x(1zy)yz x yz (14) x xy x (1 y) x 1 x (14) x(xy) xxxy x xy x (15) xx'y (xx')(xy) 1 (xy) xy ( 정리 13) (16) xyx'zyz xyx'zyz(xx') xyx'zxyzx'yz xy(1z) x'z(1y) xy x'z 6
Ý 드모르강정리 DeMorgn's theorems 는변수의합이나곱의형태를서로바꾸며식을단순화하게한다. (17) xy x y (17) x y x y NOR NAND < 정리증명 > < 사용예 > 식 F 를단순화하라. F (A'C)' (BD')' (A')' C' B' (D')' AC' B'D Ý 드모르강정리로간략화할때전체반전기호가없어지면서 기호는. 로,. 기호는 로변경, 단일변수에대한반전만남을때까지계속 7
드모르강논리게이트 좌변식 : 입력변수 x 와 y 를갖는 NOR 게이트의출력 우변식 : 입력변수 x 와 y 를각각반전한후 AND 의입력 인버트된입력을갖는 AND NOR 연산 좌변식 : 입력 x 와 y 의 NAND 게이트로구성 우변식 : 반전된두입력 x 와 y 를 OR 게이트입력 인버트된입력을갖는 OR 게이트 NAND 연산 8
ã 드모르강의정리예제 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 9
5.3 논리회로의논리식변환 v 회로에서게이트를거칠때마다게이트의출력을적어주면서한단계씩출력쪽으로나아가면된다. 논리회로 논리식유도과정 10
논리식의회로구성 v AND, OR, NOT 을이용하여논리식으로부터회로구성 x y x y yz AND-OR 보수입력사용 f ( x y)( x y z) f z wxy v( xz w) NOT 게이트사용 다단계논리회로 OR- AND 11
ã ã 부울함수의표현 Ý 5.4 부울함수 2 진수 (0, 1), 연산자 (OR, AND, NOT), 괄호, 등호등을사용하여표현. 부울함수의간소화 Ý Ý 게이트수 (term) 와게이트의입력이되는변수 (literl) 의수를줄이는것. 간소화방법 1. 부울함수로표현한다. 2. 부울대수의항등식규칙등으로간소화한다. 3. 회로를구성 12
대수적간소화방법 ã 항 (term) 결합 : 두개의항을결합하여하나의항으로만든다. ã 항제거 : 항들을제거하기위하여사용되는정리. ã 문자 (literl) 제거 : 문자들을제거하기위하여사용되는정리. ã 함수식의의미가변하지않도록주의하며, 적절한항들을함수식에첨가 13
ã 콘센서스 (onsensus) 정리 Ý onsensus 항 부울대수식에있어서콘센서스항을더해도부울대수식은변하지않는다. Ý 부울표현식을최소화하는데유리하다. xy xz' yz xy(zz')xz'yz xyzxyz'xz'yz yz(x1) xz'(y1) yz xz' ( 예 ) F x'y' xz yz' y'z xy x'y' 와 xz 의컨센선스는 y'z y'z 와 xy 의컨센선스는 xz 컨센선스 y'z 와 xz 를생략하여간소화한다. F x'y' xy y'z ( 예 ) F (xy)(x'z)(yz) (xy)(x'z) onsensus 항 14
부울함수의보수 ã 함수의보수 (omplement of funtion) 구하는방법 1. 부울함수 F 값에서 1 은 0 으로, 0 은 1 로바꾸어서구할수있다. 2. 드모르강정리를이용하여 AND 연산자는 OR 연산자로, OR 연산자는 AND 연산자로서로바꾸고, 각변수의값도 1 이면 0 으로, 0 이면 1 로바꾸어구할수있다. 3. 연산자들의쌍대를구한후각변수의값에보수를취하면된다. 함수의쌍대는 AND 연산자와 OR 연산자를상호교환하고, 1 과 0 을바꾸어구할수있다. F x'y'z xy'z' x'z 의보수함수 F'? (2) à F' (xyz')(x'yz)(xz') (3) à F 의쌍대 (x'y'z)(xy'z')(x'z) 각변수를보수화 F' (xyz')(x'yz)(xz') 15
5.5 부울함수의정형과표준형 ã 논리곱 (AND 게이트 ), 논리합 (OR 게이트 ) 로나타냄. ã ã 최소항또는표준곱 (stndrd produt) Ý 2개의변수 와 에대해서는 4가지조합 (' ', ', ', ) 이가능하며, AND연산의항으로표시 최대항또는표준합 (stndrd sum) Ý 2 변수최소항 2 변수최대항 2 개의변수 x 와 y 에대해서는 4 개의조합 (,, ', '') 이가능하며, OR 연산의항으로표시 ã 변수의값이 0 일때는 ( ', r) 기호로하고, 1 일때는붙이지않는다. 입력 출력 f 0 0 0 0 1 1 1 0 1 1 1 1 진리표로부터최소항식표현법 Þ f 16
부울함수표현형식 (1) SOP 형식 ( 곱의합, Sum of Produts ) : stndrd form - 예 : () ABC A'BC' () AB A'BC' C'D' D 2개이상의 AND 항을 ORing > AND 결과들을 OR 입력각입력은 norml 혹은 inverted 형태로사용입력변수의개수가가변 (2) POS 형식 ( 합의곱, Produt of sums) : stndrd form - 예 : () (A B' C)(A C) () (A B)(C' D)F 2개이상의 OR 항을 ANDing 입력변수의개수가가변 (3) minterm 또는 stndrd produt n개의변수는 0-2 n-1 의값을갖는 2 n 개의 minterm을가짐각 minterm은모든입력변수 (norml/inverted) 에대하여 AND (4) mxterm 또는 stndrd sum n개의변수는 0-2 n-1 의값을갖는 2 n 개의 mxterm을가짐각 mxterm은모든입력변수 (norml/inverted) 에대하여 OR 17
최소항 (minterm) q 2 변수최소항의표현방법 최소항 기호 0 0 m 0 0 1 m 1 1 0 m 2 1 1 m 3 f (, ) m1 m2 m åm(1, 2, 3) 3 q3 변수최소항의표현방법 최소항기호 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 m 0 m 1 m 2 m 3 m 4 m 5 m 6 m 7 18
ã 3 변수최소항의표현방법 x y z f 최소항기호 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 x y z x y z x y z x y z x y z x y z x y z 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 x yz xyz f ( x, y, z) å m(2, 4, 6) xyz xyz x yz xyz f ( x, y, z) å m(0,1, 3, 5, 7) f ( x, y, z) å x yz m(2, 4, 6) x yz x y z xyz x yz x y z x xyz y z f ( x, y, z) å å m(2, 4, 6) x y z m(0,1, 3, 5, 7) x y z x yz x y z x yz xyz x yz xyz 19
예제 5-1 다음진리표를이용하여 f 와 f 를최소항식으로나타내어라. 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 (,, ) å m(1, 2, 3, 4, 5) f (,, ) å m (0, 6, 7 ) 20
ã 4 변수최소항의표현방법 d 최소항기호 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 사용예 f (,,, d) å m(0, 1, 5, 9, 11,15) d d d d d d 21
ã 최대항표현방법 최대항 (mxterm) 최대항기호 0 0 0 1 1 0 1 1 2 변수 M 0 M 1 M 2 M 3 최대항기호 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 M 0 M 1 M 2 M 3 M 4 M 5 M 6 M 7 3 변수 22
4변수최대항 d 최대항기호 d 최대항기호 0 0 0 0 d M 0 1 0 0 0 d 0 0 0 1 d M 1 1 0 0 1 d 0 0 1 0 d M 2 1 0 1 0 d 0 0 1 1 d M 3 1 0 1 1 d 0 1 0 0 d M 4 1 1 0 0 d 0 1 0 1 d M 5 1 1 0 1 d 0 1 1 0 d M 6 1 1 1 0 d 0 1 1 1 d M 7 1 1 1 1 d M 8 M 9 M 10 M 11 M 12 M 13 M 14 M 15 23
최소항과최대항과의관계 v 최소항은출력이 1 인항을 SOP 로나타낸것이고, 최대항은출력이 0 인항을 POS 로나타낸것이다. v 최소항과최대항은상호보수의성질을가진다. Ý minterm 과 mxterm 의관계 m j M j m 3 M 3 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 m7 M 0 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 24
(5) Cnonil form ã 부울함수를 SOM(sum of minterms) 혹은 POM( produt of mxterms) 로표현 () sum of minterms f1 x'y' xy' m 0 m 2 f2 x'y'z xyz' xyz m 1 m 6 m 7 f3 ''d ''d 'd' d' m 3 m 5 m 10 m 14 f1(x,y) m(0, 2) f2(x,y,z) m(1, 6, 7) f3(,,,d) m(3, 5, 10, 14) () produt of mxterms f1 (xyz)(xy'z)(x'y'z) M 0 M 2 M 6 f2 (d')('d) ('d') (''d) M 1 M 4 M 9 M 12 f1(x,y,z) M(0, 2, 6) f2(,,,d) M(1,4, 9, 12) 25
(6) Cnonil form 의상호변환 f1 x'y'zxyz'xyz m 1 m 6 m 7 f1' x'y'z' x'yz' x'yz xy'z' xy'z f1 (f1')' ( x'y'z' x'yz' x'yz xy'z' xy'z)' (xyz)(xy'z)(xy'z')(x'yz)(x'yz') M 0 M 2 M 3 M 4 M 5 f2 m 0 m 2 m 5 m 6 0 0 0 0 1 x y z f1 f2 M 1 M 3 M 4 M 7 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 0 26
(7) Stndrd form 과 nonil form 의변환 f1 x y'z (xy')(xz) (xy'zz')(xzyy') (xy'z)(xy'z')(xyz)(xy'z) (xy'z)(xy'z')(xyz) M 0 M 2 M 3 ; POM f1 xy'z x(yy')(zz') (xx')y'z xyz xyz' xy'z xy'z' xy'z x'y'z m 7 m 6 m 5 m 4 m 1 ; SOM f2 ( ')( ') ' ' '' (')(') '(') '(') ''(') ('''')'''... ''''''' 27
예제 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 x y z x y 1 1 1 0 x y z z M 0 M 1 x y z M 2 x y x y x y x y z z z z 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) 28
å Õ Õ å 7) 6, (0, 7) 6, (0, 5) 4, 3, 2, (1, 5) 4, 3, 2, (1, ),, ( m M M m f Õ å 5) 4, 3, 2, (1, ) )( )( )( )( ( 5) 4, 3, 2, (1, ),, ( M m f Þ 최소항을부정하면최대항최대항을부정하면최소항 Õ å ) 7 6, (0, 7) 6, 0, M ( m Õ å 7) 6, (0, ) )( )( ( 7) 6, (0, ),, ( M m f å Õ Õ å 5) 4, 3, 2, (1, 5) 4, 3, 2, (1, 7) 6, (0, 7) 6, (0, ),, ( m M M m f Þ 29
5.6 부울대수법칙을이용한논리식의간소화 ã (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 yz 1 xy x y yz 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 를이용 30
ã (2) 식을간소화하는과정 (1) x yz xyz x yz x yz xyz (2) x y x y xyz (3) x y x y xz ( )( ) 1 ( ) (4) x y x y yz ( ) 0 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 31
예제 5-3 논리식를간소화하여라. ) ( ) )( ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( 32
ã 간소화하는과정예 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 y) x y xz xz x y z( x x) x y z 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 33
예제 5-4 다음진리표를보고논리식을구하고간소화하여라. 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 (,, ) å m(1, 2, 3, 4, 5) ( ) ( ) ( ) f (,, ) å m(0, 6, 7) ( ) 34
ã 논리식의간소화효과 Z ABC AB' (A'C')' ABC AB'(AC) ABCAB'AB'C AB'(1C)ABC AB' ABC A(B'BC) A(B'B)(B'C) A(B'C) AB' AC 35
ã 2 변수로나타낼수있는모든함수의경우 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 변수로나타낼수있는모든경우의함수논리식 f0 0 f 부울함수의종류 1 f 2 f 3 f 4 f 5 f 6 f 8 f f f 9 f 10 f 11 12 f 13 f 14 f 15 1 n개의입력변수가있을때진리표의행의개수는2 개이며, 2 개의서로다른함 수가존재. n2 2 2 2 2 16 n3 2 8 2 2 256 n4 2 16 2 65536 n 2 n 7 36