2Boolean Algebra and Logic Gates 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 IC Chapter 2 Boolean Algebra & Logic Gates 1
Boolean Algebra 1854 George Boole Chapter 2 Boolean Algebra & Logic Gates 2
Duality Principle AND OR, 0 1 ( ) (ex) x+xy = x x(x+y) = x (ex) f = x(y z +yz) f dual of f = x+(y +z )(y+z) therefore, f = x +(y+z)(y +z ) Chapter 2 Boolean Algebra & Logic Gates 3
1. (ex) x+yz = (x+y)(x+z) = xx+xz+xy+yz = x1+xz+xy+yz = x(1+z+y)+yz = x+yz = 2. Chapter 2 Boolean Algebra & Logic Gates 4
) ( 3. Venn Diagram (ex) x+yz = (x+y)(x+z) x x y z y z Chapter 2 Boolean Algebra & Logic Gates 5
Boolean Function : NOT AND OR F 1 = xyz F 2 = x y z+xy z +xy z+xyz +xyz = x y z+xy (z +z)+xy(z +z) = x y z+xy +xy = x y z+x(y +y) = x y z+x = (x +x)(y z+x) = x+y z Chapter 2 Boolean Algebra & Logic Gates 6
Boolean Function F 3 = x y z+x yz+xy z +xy z = x y z+x yz+xy (z +z) = x y z+x yz+xy F 4 = x y z+x yz+xy z +xy z = x y z+x yz+xy (z +z) = x y z+x yz+xy = x z(y +y)+xy = x z+xy Chapter 2 Boolean Algebra & Logic Gates 7
Gate Diagram F = x y z+x yz+xy Chapter 2 Boolean Algebra & Logic Gates 8
Minimization of Boolean Function literal, Literal : prime F 3 = x y z+x yz+xy F 4 = x z+xy : 6 2- AND : 1, 3- AND : 2 3- OR : 1, NOT : 2 Literal: 8 : 5 2- AND : 2, 2- OR : 1, NOT : 2 Literal: 4 Chapter 2 Boolean Algebra & Logic Gates 9
Complement of Boolean Function 1. De Morgan (ex) f 1 = x yz +x y z f 2 = x(y z +yz) f 1 = (x yz +x y z) f 2 = [x(y z +yz)] = (x yz ) (x y z) = x +(y z +yz) = (x+y +z)(x+y+z ) = x +(y z ) (yz) = x +(y+z)(y +z ) 2. Duality (ex) f 1 = x yz +x y z f 2 = x(y z +yz) dual of f 1 = (x +y+z )(x +y +z) dual of f 2 = x+(y +z )(y+z) therefore, f 1 = (x+y +z)(x+y+z ) therefore, f 1 = x +(y+z)(y +z ) Chapter 2 Boolean Algebra & Logic Gates 10
Canonical Form : sum of minterms, product of maxterms n bit2 n, minterm : AND 1 Maxterm : OR 3 0 m i = M i M i = m i Chapter 2 Boolean Algebra & Logic Gates 11
Minterm & Maxterm m 0 m 4 M 0 M 4 m k = M k m 0 +m 4 = M 0 M 4 m 0 +m 4 = (0,4) = (1,2,3,5,6,7) 0,4 1 = 1,2,3,5,6,7 0 M 0 M 4 = (0,4) = (1,2,3,5,6,7) 1,2,3,5,6,7 1 = 0,4 0 Chapter 2 Boolean Algebra & Logic Gates 12
Minterm and Maxterm f 1 = x y z+xy z +xyz = m 1 +m 4 +m 7 = (1,4,7) f 1 = (m 1 +m 4 +m 7 ) = m 1 m 4 m 7 = M 1 M 4 M 7 = (1,4,7) f 1 = x y z +x yz +x yz+xy z+xyz = m 0 +m 2 +m 3 +m 5 +m 6 = (0,2,3,5,6) f 1 = (f 1 ) = (m 0 +m 2 +m 3 +m 5 +m 6 ) = m 0 m 2 m 3 m 5 m 6 = M 0 M 2 M 3 M 5 M 6 = (0,2,3,5,6) Therefore, f 1 = (1,4,7) = (0,2,3,5,6) = x y z+xy z +xyz = (x+y+z)(x+y +z)(x+y +z )(x +y+z )(x +y +z) f 1 = (0,2,3,5,6) = (1,4,7) = x y z +x yz +x yz+xy z+xyz = (x+y+z )(x +y+z)(x +y +z ) Chapter 2 Boolean Algebra & Logic Gates 13
Minterm & Maxterm g = (0,4) = x y z +xy z 0,4 1 1,2,3,5,6,7 0 g = (0,4) = (1,2,3,5,6,7) g = (0,4) = (x+y+z)(x +y+z) = y+xz+x y+y+yz+x z+yx+z = y(x+x +1+z+x)+z(x+x +1)+xy = y+z+xy = y(1+x)+z = y+z 0,4 0 1,2,3,5,6,7 1 g = (0,4) = (1,2,3,5,6,7) Chapter 2 Boolean Algebra & Logic Gates 14
Minterm and Maxterm f 2 = ( ) : sum of minterm = ( ) : product of maxterm f 2 = ( ) : sum of minterm = ( ) : product of maxterm Chapter 2 Boolean Algebra & Logic Gates 15
Sum of Minterm f 1 (A,B,C) = A+B C 1. f 1 = A+B C = A(B+B )+B C(A +A) = AB+AB +A B C+AB C = AB(C+C )+AB (C+C )+A B C+AB C = ABC+ABC +AB C+AB C +A B C+AB C = ABC+ABC +AB C+AB C +A B C = m 7 +m 6 +m 5 +m 4 +m 1 = (1,4,5,6,7) 2. f 1 = m 1 + m 4 +m 5 +m 6 + m 7 = (1,4,5,6,7) Chapter 2 Boolean Algebra & Logic Gates 16
Product of Maxterm f 1 (A,B,C) = A+B C 1. f 1 = A+B C = (A+B )(A+C) = (A+B +CC )(A+C+BB ) = (A+B +C)(A+B +C )(A+C+B)(A+C+B ) = (A+B +C)(A+B +C )(A+B+C)(A+B +C) = (A+B +C)(A+B +C )(A+B+C) = M 2 M 3 M 0 = (0,2,3) 2. f 1 = m 1 + m 4 +m 5 +m 6 + m 7 = (1,4,5,6,7) = (0,2,3) Chapter 2 Boolean Algebra & Logic Gates 17
Sum of Minterm, Product of Maxterm f(x,y,z) = xy+x z f = (1,3,6,7) = x y z+ x yz+ xyz + xyz f = (0,2,4,5) = (x+y+z) (x+y +z) (x +y+z) (x +y+z ) f = (1,3,6,7) = (0,2,4,5) f = (1,3,6,7) f = (0,2,4,5) Chapter 2 Boolean Algebra & Logic Gates 18
Standard Form : sum of products, product of sums Sum of products : (AND) (OR) (ex) f = y +xy+x yz Product of sums : (OR) (AND) (ex) f = x(y +z)(x+y +z) canonical form(sum of minterm, product of maxterm) standard form : (ex) f = (ab+cd)(a b +c d ) = aba b +abc d +a b cd+cdc d = abc d +a b cd Chapter 2 Boolean Algebra & Logic Gates 19
Digital Logic Gates Name Graphic symbol Algebraic function Truth Table AND F = xy 1 1 OR F = x+y 0 0 NOT F = x (inverter) Buffer F = x Chapter 2 Boolean Algebra & Logic Gates 20
Digital Logic Gates Name Graphic symbol Algebraic function Truth Table NAND F = (xy) 1 0 NOR F = (x+y) 0 1 XOR F = x y+xy = x y 1 XNOR F = xy+x y = x y 1 Chapter 2 Boolean Algebra & Logic Gates 21
/ AND, OR, XOR, XNOR : / NAND, NOR : Chapter 2 Boolean Algebra & Logic Gates 22
XOR Gate XOR (odd function) : 1 1 A B C A B C A B C A B C Chapter 2 Boolean Algebra & Logic Gates 23
IC Digital Logic Family RTL (Resistor Transistor Logic) DTL (Diode Transistor Logic) TTL (Transistor Transistor Logic) : ECL (Emitter Coupled Logic) : MOS (Metal Oxide Semiconductor) : CMOS (Complementary Metal Oxide Semiconductor) :, I 2 L (Integrated Injection Logic) : Chapter 2 Boolean Algebra & Logic Gates 24
Positive Logic and Negative Logic Positive logic ( ) Negative logic ( ) Logic Value Signal Value Logic Value Signal Value 1 H 0 L 0 H 1 L Positive logic Positive logic Negative logic Negative logic AND OR AND OR Positive logic AND = Negative logic OR Positive logic OR = Negative logic AND Chapter 2 Boolean Algebra & Logic Gates 25
IC Logic Family Fanout, (Power dissipation) (Propagation delay) (Noise margin) Chapter 2 Boolean Algebra & Logic Gates 26