Chapter 05 부울대수
1. 부울대수 부울대수 (boolean algebra) 를근거로한스위칭이론 (switching theory) 은논리설계에있어서이론적인근거가되는수학적체계. 부울대수 - 부울상수와부울변수로구성, 0과 1의두개값을가짐 - 논리레벨의여러정의 논리 0 False Off Low No Open Switch 논리 1 True On High Yes Closed switch - 부울대수는논리회로의입력및출력의상관관계를표현하는방법 입력의논리레벨에따라출력결정 논리변수표현 :A,B.. 등과같이문자로표현. 값은 A0 또는 B1 등으로표현 부울대수의기본연산 : 논리동작 (logic operation) OR, AND, NOT 논리게이트 : 입력신호에대해기본논리연산 (OR, AND, NOT) 을수행하는디지털회로는다이오드, 트랜지스터, 저항등을사용하여구성 - 부울변수를전자회로에서사용할때실제적인전압레벨 0~0.8 V 논리레벨 (logic level) 0, 2~ 5V 논리레벨 1 로표시, 0.8~2V undefined 값, 논리레벨의전이영역 (transition region) - 2 - 한국기술교육대학교정보기술공학부
- 단일변수에관한정리 부울대수정리 - duality 성립 : 0 <-> 1, <-> - 3 - 한국기술교육대학교정보기술공학부
교환법칙결합법칙 다변수부울대수정리 (9) xy yx (10) x y y x (11) x(yz) (12) x(yz) (xy)z xyz (xy)z xyz 분배법칙 (13a) x (y z) (13b) x yz xy xz (x y)(x z) Absorption (14a) x xy x (14b) x(xy) x (15) x x'y x y Consensus (16a) xyx'zyz xyx'z (16b) (xy)(x'z)(yz) (xy)(x'z) < 사용예 > 컨센서스항 (13b) 역유도 (xy)(xz) xxxzxyyz x(1zy)yz x yz (14a) x xy x (1 y) x 1 x (14b) x(xy) xxxy x xy x (15) xx'y (xx')(xy) 1 (xy) xy ( 정리 13b) (16a) xyx'zyz xyx'zyz(xx') xyx'zxyzx'yz xy(1z) x'z(1y) xy x'z - 4 - 한국기술교육대학교정보기술공학부
드모르강정리 - DeMorgan's theorems는변수의합이나곱의형태를서로바꾸며식을단순화하게한다. (17a) xy x y NOR (17b) x y x y NAND < 정리증명 > < 사용예 > 식 F 를단순화하라. F (A'C)' (BD')' (A')' C' B' (D')' AC' B'D - 드모르강정리로간략화할때전체반전기호가없어지면서 기호는. 로,. 기호는 로변경, 단일변수에대한반전만남을때까지계속 - 5 - 한국기술교육대학교정보기술공학부
드모르강논리게이트 좌변식 : 입력변수 x 와 y 를갖는 NOR 게이트의출력 우변식 : 입력변수 x 와 y 를각각반전한후 AND 의입력 인버트된입력을갖는 AND NOR 연산 좌변식 : 입력 x 와 y 의 NAND 게이트로구성 우변식 : 반전된두입력 x 와 y 를 OR 게이트입력 인버트된입력을갖는 OR 게이트 NAND 연산 - 6 - 한국기술교육대학교정보기술공학부
드모르강의정리예제 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 - 7 - 한국기술교육대학교정보기술공학부
부울함수의표현 부울함수 -2 진수 (0, 1), 연산자 (OR, AND, NOT), 괄호, 등호등을사용하여표현. 부울함수의간소화 - 게이트수 (term) 와게이트의입력이되는변수 (literal) 의수를줄이는것. - 간소화방법 1. 부울함수로표현한다. 2. 부울대수의항등식규칙등으로간소화한다. 3. 회로를구성 - 8 - 한국기술교육대학교정보기술공학부
대수적간소화방법 항 (term) 결합 : 두개의항을결합하여하나의항으로만든다. 항제거 : 항들을제거하기위하여사용되는정리. 문자 (literal) 제거 : 문자들을제거하기위하여사용되는정리. 함수식의의미가변하지않도록주의하며, 적절한항들을함수식에첨가 - 9 - 한국기술교육대학교정보기술공학부
대수적간소화방법 ( 계속 ) 콘센서스 (consensus) 정리 - 부울대수식에있어서콘센서스항을더해도부울대수식은변하지않는다. - 부울표현식을최소화하는데유리하다. consensus 항 xy xz' yz xy(zz')xz'yz xyzxyz'xz'yz yz(x1) y( xz'(y1) yz xz' ( 예 ) F x'y' xz yz' y'z xy x'y' 와 xz의컨센선스는 y'z y'z yz 와 xy 의컨센선스는 xz 컨센선스 y'z와 xz를생략하여간소화한다. F x'y' xy y'z ( 예 ) F (xy)(x'z)(yz) consensus 항 (xy)(x'z) - 10 - 한국기술교육대학교정보기술공학부
부울함수의보수 함수의보수 (complement of a function) 구하는방법 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) z)(xy z z) 각변수를보수화 F' (xyz')(x'yz)(xz') - 11 - 한국기술교육대학교정보기술공학부
부울대수를이용한논리식의간소화 (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 ( xyz xyz) ( x yz x yz) ( xyz xyz) x y x y xz x y x y yz xy( z z) x y( z z) yz( x x) xy 1 x y 1 yz 1 x y x y yz XXX를이용 xyz xyz x yz x yz xyz xyz xyz x yz x yz xyz x yz ( xyz xyz) ( x yz x yz) xyz ( xyz xyz) ( x yz x yz) ( xyz x yz) xy ( z z ) x y ( z z ) xyz xy ( z z ) x y ( z z ) xz ( y y ) xy 1 x y 1 xyz xy 1 x y 1 xz 1 xy x y xyz xy x y xz - 12 - 한국기술교육대학교정보기술공학부
(2) 식을간소화하는과정 (1) x yz xyz x yz x yz xyz (2) x y x y xyz (3) x y x y xz (4) x y x y yz a ab ( a a)( a b) 1 ( a b) a b a ( a b) aa ab 0 ab ab xy x y xyz xy x( y yz) xy x( y y)( y z) xy x 1( y z ) xy x y xz x y 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 - 13 - 한국기술교육대학교정보기술공학부
논리식를간소화하여라. a b c ab c abc a b c a b c ab c abc a b c ( a b c ab c ) abc a b c a c ( b a c abc a b c a ( c bc ) a b c a ( c b )( c c ) a b c a ( c b ) a c ab a b c a c a b c ab c ( a a b ) ab c ( a b ) ab c a c b ab a b c ab c abc a b c a b c a b c ab c abc b c ( a a ) ab ( c c ) b c ab b ) a b c abc a b c 서로다른간소화결과를가져올수있다. - 14 - 한국기술교육대학교정보기술공학부
2. 부울함수표현형식 (1) SOP 형식 ( 곱의합, Sum of Products ) : standard form - 예 : (a) a'bc b'd a'c (b) AB A'BC' C'D' D 2개이상의 AND 항을 OR 각입력은 normal 혹은 inverted 형태로사용 (2) POS 형식 ( 합의곱, Product of sums) : standard form - 예 : (a) (A B' C)(A C) (b) (A B)(C' D)F 2개이상의 OR 항을 AND f abc bd ac (3) minterm 또는 standard product n 개의변수는 0-2 n-1 의값을갖는 2 n 개의 minterm 을가짐각 minterm은모든입력변수 (normal/inverted) 에대하여 AND (4) maxterm 또는 standard sum n 개의변수는 0-2 n-1 의값을갖는 2 n 개의 maxterm 을가짐각 maxterm은모든입력변수 (normal/inverted) 에대하여 OR - 15 - 한국기술교육대학교정보기술공학부
2 변수최소항과최대항표현방법 - minterm : n 개입력변수의 AND term -maxterm: n 개입력변수의 OR term a b 최소항기호 a b 최대항기호 0 0 a b m 0 0 0 a b M 0 0 1 a b m 1 0 1 a b M 1 1 0 a b m 2 1 0 a b M 2 1 1 a b m 3 1 1 a b M 3-16 - 한국기술교육대학교정보기술공학부
3 변수에대한 minterm 과 maxterm 변수최소항최대항함수 x y z 항표시항표시 F 1 F 2 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 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 x y z x y z x y z x y z x y z x y z x y z x y z -minterm 과 maxterm ate 의관계 m j M j m 3 xyz xyz M 3 1 M 0 M 1 0 M 2 0 M 3 1 M 4 0 M 5 0 M 6 1 M 7 0 0 1 0 0 0 0 1 1-17 - 한국기술교육대학교정보기술공학부
3 변수최소항을이용한부울함수표현 x y z f1 f2 000 0 0 1 0 0 0 1 1 1 0 1 0 0 0 011 1 1 0 1 0 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 f ( x, y, z) 1 f ( x, y, z) 1 f ( x, y, z ) m (2, 4, 6) x y z x y z 1 m(0,1, 3, 5, 7) x yz x yz xyz x yz xyz (xyz)(xyz)(xyz) f 2 (x,y,z)? m(2, 4, 6) x y z x y z x y z x y z m(0,1,, 3, 5, 7) x yz x yz xyz x yz xyz - 최소항과최대항과의관계 최소항은출력이 1 인항을 Product(AND) 로나타낸것이고, 최대항은출력이 0인항을 Sum(OR) 로나타낸것이다. 최소항과최대항은반대의성질을가진다. - 18 - 한국기술교육대학교정보기술공학부
4 변수최소항 a b c d 최소항 기호 a b c d 최소항 기호 0 0 0 0 a b c d m 0 1 0 0 0 a b c d m 8 0 0 0 1 a b c d m 1 1 0 0 1 a b c d m 9 0 0 1 0 a b c d m 2 1 0 1 0 a b c d m 10 0 0 1 1 a b c d m 3 1 0 1 1 a b c d m 11 0 1 0 0 a b c d m 4 1 1 0 0 a b c d m 12 0101 0 1 a b c d m 5 1101 1 1 a b c d m 13 0 1 1 0 a b c d m 6 1 1 1 0 a b c d m 14 0 1 1 1 a b c d m 7 1 1 1 1 a b c d m 15 [Example] f ( a, b, c, d ) m (0, 1, 5, 9, 11,1515 ) abcd abcd abcd abcd abcd abcd - 19 - 한국기술교육대학교정보기술공학부
4 변수최대항 a b c d 최대항기호 a b c d 최대항기호 0 0 0 0 a b c d 0 1 0 0 0 0 0 0 1 a b c d M 1 1 0 0 1 0 0 1 0 a b c d M 2 1 0 1 0 0 0 1 1 a b c d M 3 1 0 1 1 0 1 0 0 a b c d M 4 1 1 0 0 0101 0 1 a b c d M 5 1101 1 1 0 1 1 0 a b c d M 6 1 1 1 0 0 1 1 1 a b c d 1 1 1 1 M a b c d 8 M 9 m 7 a b c a b c a b c a b c a b c a b c a b c d d d d d d d M M 10 M 11 M 12 M 13 M 14 M 15-20 - 한국기술교육대학교정보기술공학부
(5) Canonical form 부울함수를 SOM(sum of minterms) 혹은 POM( product of maxterms) 으로표현 (a) sum of minterms f1 x'y' xy' m 0 m 2 2변수 f2 xyz x'y'z xyz' xyz m 1 m 6 m 7 3 변수 f3 a'b'cd a'bc'd ab'cd' abcd' m 3 m 5 m 10 m 14 4변수 f1(x,y) m(0, 2) f2(x,y,z) m(1, 6, 7) f3(a,b,c,d) m(3, 5, 10, 14) (b) product of maxterms f1 (xyz)(xy'z)(x'y'z) M 0 M 2 M 6 f2 (abcd')(ab'cd) (a'bcd') (a'b'cd) M 1 M 4 M 9 M 12 f1(x,y,z) M(0, 2, 6) f2(abcd) f2(a,b,c,d) M(1,4 4, 9, 12) - 21 - 한국기술교육대학교정보기술공학부
[Example] f ( a, b ) ( a b )( a b )( a b ) M 0 M 1 M M (0, 1, 2 ) 2 입력 출력 a b f 0 0 0 0 1 0 1 0 0 1 1 1-22 - 한국기술교육대학교정보기술공학부
다음최대항식에대한진리표로만들고, 논리식을구하라. f ( x, y, z ) M (0, 1, 3, 5, 7 ) x y z f 최대항 기호 0 0 0 0 x y z M 0 0 0 1 0 x y z M 1 0 1 0 1 x y z M 2 011 1 0 x y z M 3 1 0 0 1 x y z M 4 1 0 1 0 x y z M 5 1 1 0 1 x y z M 6 1 1 1 0 x y z 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 ) - 23 - 한국기술교육대학교정보기술공학부
(6) Canonical form 의상호변환 f1 x'y'zxyz'xyz m 1 m 6 m 7 정규함수는 1인항의합 f1' x'y'z' x'yz' x'yz xy'z' xy'z 보수함수는 0 인항의합 f1 (f1')' ( x'y'z' x'yz' x'yz xy'z' xy'z)' (xyz)(xy'z)(xy'z')(x'yz)(x'yz') z)(xy z ) M 0 M 2 M 3 M 4 M 5 x y z f1 f2 f2 m 0 m 2 m 5 m 6 M 1 M 3 M 4 M 7 0 0 0 0 0 1 010 0 0 1 0 1 0 1 정규함수와보수함수는 0 1 1 0 0 SOM과 POM에서각최소항과최대항의 index 가 1 0 0 0 0 서로중복되지않는다. 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0-24 - 한국기술교육대학교정보기술공학부
f ( a, b, c) m(1, 2, 3, 4, 5) abc abc abc abc abc abc abc abc abc abc abc abc abc abc abc ( a b c)( a b c)( a b c)( a b c)( a b c) M (1, 2, 3, 4, 5) f ( a, b, c) m(1, 2, 3, 4, 5) M (0, 6, 7) M ( m (0, 6, 7) M (1, 2, 3, 4, 5) 최소항을부정하면최대항 최대항을부정하면최소항 f ( a, b, c) m(0, 6, 7) abc abc abc abc abc abc abc abc abc ( a b c)( a b c)( a b c) M (0, 6, 7) m(0, 6, 7) 1, 2, 3, 4, 5) f ( a, b, c) M (0, 6, 7) M ( m(1, 2, 3, 4, 5) - 25 - 한국기술교육대학교정보기술공학부
(7) Standard form 과 canonical form 의변환 f1 x y'z 의 POM? (xy')(xz) (xy'zz')(xzyy') (xy'z)(xy'z')(xyz)(xy'z) (xy'z)(xy'z')(xyz) M 0 M 2 M 3 f1 xy'z 의 SOM? x(yy')(zz') (xx')y'z missing 변수추가 xyz xyz' xy'z xy'z' xy'z x'y'z m 7 m 6 m 5 m 4 m 1 f2 (a c')(a b') b) aa ab' ac' c'b' cb a(bb')(cc') ab'(cc') ac'(bb') c'b'(aa') a(bcbc'b'cb'c')ab'cab'c' c cab c... abcabc'ab'cab'c'a'b'c' - 26 - 한국기술교육대학교정보기술공학부
간소화과정예 : canonical form standard form 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 - 27 - 한국기술교육대학교정보기술공학부
예제다음진리표로부터논리식을구하고간소화하여라. a b c f f 000 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 101 1 1 0 1 1 0 0 1 1 1 1 0 1 f ( a, b, c) m(1, 2, 3, 4, 5) abc abc abc abc abc abc abc abc abc abc abc ( a a ) bc ab ( c c ) ab ( c c ) bc ab ab f ( a, b, c) m(0, 6, 7) abc abc abc abc ab( c c) abc ab - 28 - 한국기술교육대학교정보기술공학부
3. 논리회로의논리식변환 원래의회로에게이트를거칠때마다게이트의출력을적어주면서한단계씩출력쪽으로나아가면된다. 논리회로 논리식유도과정 - 29 - 한국기술교육대학교정보기술공학부
논리식유도예 1 a b c b d a c abc bd ac f abcbdac 논리식유도예 2-30 - 한국기술교육대학교정보기술공학부
논리식유도예 3-31 - 한국기술교육대학교정보기술공학부
4. 논리식의회로구성 AND, OR, NOT을이용하여논리식으로부터회로를구성.(AND-OR로혹은 OR-AND 로구성된 2 단회로 ) x y x y yz 보수입력사용 NOT 게이트사용 - 32 - 한국기술교육대학교정보기술공학부
회로예 AND-OR f ( x, y, z) xyz xyz x yz x yz xyz OR- AND f ( x y)( x y z) - 33 - 한국기술교육대학교정보기술공학부
회로예 다단계논리회로 f z wxy v( xz w) - 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 - 한국기술교육대학교정보기술공학부