5 불대수 IT CookBook, 디지털논리회로
- 2 - 학습목표 기본논리식의표현방법을알아본다. 불대수의법칙을알아본다. 논리회로를논리식으로논리식을논리회로로표현하는방법을알아본다. 곱의합 (SOP) 과합의곱 (POS), 최소항 (minterm) 과최대항 (mxterm) 에대해알아본다. 01. 기본논리식의표현 02. 불대수법칙 03. 논리회로의논리식변환 04. 논리식의회로구성 05. 불대수식의표현형태 06. 불대수법칙을이용한논리식의간소화
01 기본논리식의표현 - 3 - 기본적인불대수식은 AND, OR, NOT을이용하여표현 AND 식은곱셈의형식으로표현하고, OR 식은덧셈의형식으로표현 NOT 식은 X 또는 X ' 로표현 완전한논리식은입력항목들의상태에따른출력을결정하는식 X=0 n Y=1 일때출력을 1 로만들려는경우출력논리식 F XY X=0 or Y=1 일때출력을 1 로만들려는경우출력논리식 F X Y (X=0 n Y=1) or (X=1 n Y=0) 일때출력을 1 로만들려는경우출력논리식 F XY XY
- 4-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 1 1 F F X Y X Y 0 1 0 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 F X Y Z
01 기본논리식의표현 2 입력논리식예 입력 출력 X Y F 0 0 1 0 1 1 1 0 1 1 1 0 3 입력논리식예 F 입력 출력 X Y Z X=1 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 F X YZ - 5 - X Y X=0 또는 Y=0 일때, 1 을출력하는논리식 X=1 이거나 (Y=0 이고 Z=1) 일때, 1 을출력하는논리식
02 불대수법칙 - 6 - 불대수공리 (oolen 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 불대수법칙 불대수기본법칙 1. X+0=0+X=X 2. X 1=1 X=X 3. X+1=1+X=1 4. X 0=0 X=0 5. X+X=X 6. X X=X 7. X X 1 8. X X 0 9. X X 교환법칙 (ommuttive lw) 10. X+Y=Y+X 11. XY=YX 결합법칙 (ssoite lw) 12. (X + Y) + Z = X + (Y + Z) 13. (XY) Z = X (YZ) 분배법칙 (istriutive lw) 14. X (Y + Z) = XY + XZ 15. X + YZ = (X+Y)(X+Z) 드모르간의정리 (De Morgn's theorem) 16. X Y X Y 17. XY X 흡수법칙 (sorptive lw) 18. X + XY = X 19. X(X+Y) = X 합의의정리 (onsensus theorem) 20. XY YZ XZ XY XZ 21. - 7 - Y ( X Y )( Y Z)( X Z) ( X Y )( X Z)
02 불대수법칙 - 8 - 진리표를이용한분배법칙 X + YZ = (X+Y)(X+Z) 의증명 X Y Z 좌측식우측식 Y Z X+Y Z X+Y X+Z (X+Y)(X+Z) 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 불대수법칙 - 9 - 드모르간의정리증명 X Y X+Y 좌측식우측식 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 X 1 X 2 X n X 1 X 2 X n 1 X 2 X n X 1 X 2 X n
- 10-02 불대수법칙 합의의정리증명 입력 XY YZ X Y Z XY YZ XZ XY YZ X Z XY 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 XY XZ XZ XY X Z 동일한결과
02 불대수법칙 - 11 - 드모르간의정리예제 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
- 12-03 논리회로의논리식변환 원래의회로에게이트를거칠때마다게이트의출력을적어주면서한단계씩출력쪽으로나아가면된다. 논리회로 논리식유도과정 Y Z Y Z Y+Z (Y+Z)WX W X X Y F W X X Y WX XY F (Y+Z)WX+XY
- 13-03 논리회로의논리식변환 예 1 ++ ++ 예 2 + + (++) (+)(+)
- 14-03 논리회로의논리식변환 B C A F 예 3 B C A B+C A (B+C)A F (B+C)A+ABC C ABC
04 논리식의회로구성 - 15 - AND, OR, NOT 을이용하여논리식으로부터회로를구성.(AND-OR 로구성된회로 ) x x z 보수입력사용 NOT 게이트사용 x x x x x x z x z x+x+z z x z x+x+z
- 16-04 논리식의회로구성 x z x z AND-OR x z x z ( x,, z) xz xz xz xz xz x z OR-AND x x z ( x )( x z)
04 논리식의회로구성 - 17 - 다단계논리회로 x z w v xz xz+w wx (xz+w)v z wx v( xz w)
05 불대수식의표현형태 - 18-1. 곱의합과최소항 곱의합 (Sum o Prout, SOP) SOP의구성은 1 단계는 AND항 ( 곱의항, prout term) 으로구성되고, 2 단계는 OR항 ( 합의항, sum term) 으로만들어진논리식. 최소항 (Minterm) 최소항 : 표준곱의항 표준곱의항이란함수에모든변수를포함하고있음. W XY Z WXYZ minterm W XY W X Z Non minterm
05 불대수식의표현형태 - 19 - 진리표로부터최소항식을표현하는방법 입력 출력 0 0 0 0 1 1 1 0 1 1 1 1 (=0 AND =1) OR (=1 AND =0) OR (=1 AND =1) 일때, = 1 이다. 또는 ( 1AND =1) OR (=1 AND 1) OR (=1 AND =1) 일때, = 1이다. 또는 1 OR 1 OR 1 일때, = 1이다.
05 불대수식의표현형태 - 20-2 변수최소항의표현방법 최소항 기호 0 0 m 0 0 1 m 1 1 0 m 2 1 1 m 3 (, ) m1 m2 m m(1, 2, 3) 3
05 불대수식의표현형태 - 21-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
05 불대수식의표현형태 3 변수최소항의표현방법 x z 최소항기호 0 0 0 1 x z 0 0 1 1 x z 0 1 0 0 x z 0 1 1 1 x z 1 0 0 0 x z 1 0 1 1 x z 1 1 0 0 x z 1 1 1 1 x z m 0 m 1 m 2 m 3 m 4 m 5 m 6 m 7 ( x,, z) m( 0, 1, 3, 5, 7) x z x z xz ( x,, z) m(2, 4, 6) xz x z xz x z xz ( x,, z) m(0,1, 3, 5, 7) xz xz xz xz xz ( x,, z) m(2, 4, 6) x z x z x z ( x,, z) m(2, 4, 6) x z x z x z m(0,1, 3, 5, 7) x z x z xz - 22 - x z xz
- 23-05 불대수식의표현형태 예제 5-1 다음진리표를이용하여 와 를최소항식으로나타내어라. 0 0 0 0 1 (,, ) m(1, 2, 3, 4, 5) 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 (,, ) m(0, 6, 7) 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 0 1
05 불대수식의표현형태 - 24-4 변수최소항의표현방법 최소항기호 최소항기호 m 0 0 0 0 0 1 0 0 0 0 0 0 1 m 1 1 0 0 1 0 0 1 0 m 2 1 0 1 0 0 0 1 1 m 3 1 0 1 1 0 1 0 0 m 4 1 1 0 0 0 1 0 1 m 5 1 1 0 1 0 1 1 0 m 6 1 1 1 0 0 1 1 1 m 7 1 1 1 1 m 8 m 9 m 10 m 11 m 12 m 13 m 14 m 15 [Exmple] (,,, ) m(0,1, 5, 9, 11,15)
05 불대수식의표현형태 - 25-2. 합의곱과최대항 합의곱구성 : 1 단계는 OR 항 ( 합의항, sum term) 으로구성되고, 2 단계는 AND 항 ( 곱의항, prout term) 으로만들어진논리식. 모든변수를포함하는 OR 항을맥스텀 (mxterm) 또는최대항이라한다. 최대항의예 w w x x z z 합의곱의예 ( w x)( w ) w( w ) w w x ( w x z)( w x z)
05 불대수식의표현형태 - 26 - 최대항표현방법 최대항기호 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 3변수인경우 M 0 M 1 M 2 M 3 M 4 M 5 M 6 M 7
- 27 - 최대항기호 최대항기호 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 M 0 M 1 M 2 M 3 M 4 M 5 M 6 M 7 M 8 M 9 M 10 M 11 M 12 M 13 M 14 M 15 4 변수인경우 05 불대수식의표현형태
05 불대수식의표현형태 - 28 - [Exmple] (, ) ( )( )( ) M 0 M1 M 2 M (0, 1, 2) 입력 출력 0 0 0 0 1 0 1 0 0 1 1 1
05 불대수식의표현형태 - 29 - 예제 5-2 다음최대항식을진리표로만들어보고, 논리식을구해보아라. ( x,, z) M(0,1, 3, 5, 7) x z 최대항기호 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 z x z x z x z x z x z x z x z M 0 M 1 M 2 M 3 M 4 M 5 M 6 M 7 ( x,, z) M (0,1, 3, 5, 7) ( x z)( x z)( x z)( x z)( x z)
05 불대수식의표현형태 - 30-3. 최소항과최대항과의관계 최소항은출력이 1 인항을 SOP 로나타낸것이고, 최대항은출력이 0 인항을 POS 로나타낸것이다. 최소항과최대항은반대의성질을가진다. 최소항기호최대항기호관계 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 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
- 31-7) 6, (0, 7) 6, (0, 5) 4, 3, 2, (1, 5) 4, 3, 2, (1, ),, ( m M M m 5) 4, 3, 2, (1, ) )( )( )( )( ( 5) 4, 3, 2, (1, ),, ( M m 7) 6, (0, ) )( )( ( 7) 6, (0, ),, ( M m 5) 4, 3, 2, (1, 5) 4, 3, 2, (1, 7) 6, (0, 7) 6, (0, ),, ( m M M m 최소항을부정하면최대항최대항을부정하면최소항 05 불대수식의표현형태
06 불대수법칙을이용한논리식의간소화 - 32 - (1) 식을간소화하는과정 (1) xz xz xz xz xz xz xz x z x z xz xz (2) (3) (4) x x x x xz x xz x z ( xz xz) ( x z x z) ( xz xz) x( z z) x ( z z) z( x x) x 1 x 1 x x z z1 X+X=X 를이용 xz xz x z x z xz ( xz xz) ( x z x z) x( z z) x ( z z) xz x 1 x 1 xz x x xz xz xz xz x z x z xz x z ( xz xz) ( x z x z) ( xz x z) x( z z) x ( z z) xz( ) x 1 x 1 x x xz xz1 X+X=X 를이용
- 33-06 불대수법칙을이용한논리식의간소화 (2) 식을간소화하는과정 (1) xz xz xz xz xz (2) x x xz (3) x x xz ( )( ) 1( ) (4) x x z ( ) 0 x x xz x x( z) x x( )( z) x x 1( z) x x xz x x xz ( x xz) x ( x x)( x z) x 1( x z) x x z x
- 34 - 예제 5-3 논리식를간소화하여라. ) ( ) ( ) ( ) )( ( ) ( ) ( ) ( ) ( ) ( 06 불대수법칙을이용한논리식의간소화
- 35-06 불대수법칙을이용한논리식의간소화 간소화하는과정예 ( x,, z) m(0,1, 3, 5, 7) x z x z xz x z xz x ( z z) xz( ) xz( x xz xz x z( x x) x z ) ( x,, z) m(0,1, 3, 5, 7) m(2, 4, 6) xz x z xz z( x x) xz( ) z xz
- 36-06 불대수법칙을이용한논리식의간소화 예제 5-4 다음진리표를보고논리식을구하고간소화하여라. 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(1, 2, 3, 4, 5) ( ) ( ) ( ) (,, ) m(0, 6, 7) ( )
06 불대수법칙을이용한논리식의간소화 2 변수로나타낼수있는모든경우 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 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 변수로나타낼수있는모든경우의논리식 0 0 1 2 3 4 5 6 8-37 - 7 9 10 11 12 13 14 15 1 n n개의입력변수가있을때진리표의행의개수는 2 개이며, 2 개의서로다른함수가존재. 2 n=2 2 2 2 16 n=3 2 3 8 2 2 256 n=4 2 4 16 2 65536 2 n
06 불대수법칙을이용한논리식의간소화 - 38-0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 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 3 ( ) 5 7 ( ) ( ) ( ) 10 ( ) 11 12 13 ( ) 14
5 장불대수끝