lec8-booleanalgebra

1、Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Lec8 Boolean AlgebraLec8 Boolean AlgebraReference: chapter4 - 4.11/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2

2、014OutlineOutline布尔代数，逻辑代数，二值代数布尔代数，逻辑代数，二值代数公理、定理、公式及其运用公理、定理、公式及其运用0、1运算规则运算规则公理（基本定理）公理（基本定理）导出公式：吸收律，冗余项公式等导出公式：吸收律，冗余项公式等基本公式对基本公式对“异或异或”、“同或同或”的适用性的适用性摩根定理和香农定理摩根定理和香农定理变换规则变换规则代入规则代入规则反演规则反演规则对偶规则对偶规则2/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of Ch

3、inaProf. Lin Shuisheng, 2014Logic CircuitsLogic CircuitsCombinational logic circuitOutputs depend only on its current inputsNo feedback loopSequential logic circuitOutputs depend on its current inputs and present statesFeedback loop3/35Digital Logic Design and ApplicationUniversity of Electronic Sci

4、ence and Technology of ChinaProf. Lin Shuisheng, 20144.1 4.1 Switching AlgebraSwitching AlgebraBoolean Algebra formulated by mathematician George Boole in 1854 basic relationships & manipulations for a two-value systemSwitching Algebraadaptation of Boolean Logic to analyze and describe behavior of r

5、elaysClaude Shannon of Bell Labs in 1938this works for all switches (mechanical or electrical)we generally use the terms Boolean Algebra & Switching Algebra interchangeably4/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Boolean

6、 AlgebraBoolean AlgebraWhat is Algebrathe basic set of rules that the elements and operators in a system followthe ability to represent unknowns using variablesthe set of theorems available to manipulate expressionsBooleanwe limit our number set to two values (0, 1)we limit our operators to AND, OR,

7、 INV5/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Fundamentals of Boolean Algebra (1)Fundamentals of Boolean Algebra (1)Axioms (also called Postulates“)minimal set of basic definitions that we assume to be trueall other deriv

8、ations are based on these truthssince we only have two values in our system, we typically define an axiom and then its complement (A1 & A1)6/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014AxiomsAxiomsAxiom #1 Identity”a variable

9、 X can only take on 0 or 1 values(A1) X = 0, if X 1 (A1) X = 1, if X 0Axiom #2 Complement” (Inversion)a prime following a variable denotes an inversion function(A2) if X = 0, then X = 1 (A2) if X = 1, then X = 01XY=XXY=XXY=X7/35Digital Logic Design and ApplicationUniversity of Electronic Science and

10、 Technology of ChinaProf. Lin Shuisheng, 2014AxiomsAxiomsAxiom #3 AND“also called Logical Multiplication“a dot () is used to represent an AND function(A3) 00 = 001 = 0 10 = 011 = 1Axiom #4 OR“also called Logical Addition“a plus (+) is used to represent an OR function(A4) 1+1 = 11+0 = 1 0+1 = 10+0 =

11、08/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014AxiomsAxiomsAxiom #5 “Precedence”(优先级优先级)multiplication precedes additionTry F = 0 + 1 ( 0 + 1 0 )=? = 0 + 1 1 = 09/35Digital Logic Design and ApplicationUniversity of Electronic

12、 Science and Technology of ChinaProf. Lin Shuisheng, 2014TheoremsTheoremsTheorems use our Axioms to formulate more meaningful relationships & manipulationsa theorem is a statement of TRUTHthese theorems can be proved using our Axioms we can prove most theorems using “Perfect Induction“ ( (完全归纳法完全归纳法

13、) )10/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Fundamentals of Boolean Algebra (1)Fundamentals of Boolean Algebra (1)Postulate 1 (Null element): (0-1律律)(a) X + 1 = 1 (b) X 0 = 0Postulate 2 (Existence of 1 and 0 element): (

14、自等律自等律)(a) X + 0 = X (identity for +) (b) X 1 = X (identity for )Postulate 3 (Idempotency): (同一律同一律)(a) X + X = X (b) X X = XPostulate 4 (Involution): (还原律还原律) X =XProperties of 0 and 1 elements :ORANDComplementX + 0 = 0X 0 = 00 = 1X + 1 = 1X 1 = X1 = 011/35Digital Logic Design and ApplicationUniver

15、sity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Fundamentals of Boolean Algebra (2)Fundamentals of Boolean Algebra (2)Postulate 5 (Commutativity): (交换交换律律)(a) X + Y = Y + X (b) X Y = Y XPostulate 6 (Associativity): (结合律结合律)(a) X + (Y + Z) = (X + Y) + Z (b) X (Y Z) = (X Y)

16、Z ZPostulate 7 (Distributivity): (分配律分配律)(a) X + (Y Z) = (X + Y) (X + Z)(b) X (Y + Z) = X Y + X Z ZPostulate 8 (Existence of complement): (互补律互补律)(a) X+X =1 (b) X X =0 Normally is omitted.12/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuis

17、heng, 2014Validate theorems using truth tableValidate theorems using truth tableX+YZ = (X+Y)(X+Z)X Y ZYZX+YX+ZG(X,Y,Z)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10100000000000000011111111111111111111111F(X,Y,Z)Proofs by exhaustion: Let variables assume all possible values and show validity of result in

18、all casesusing truth table13/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014NotesNotesNO index of variable XXX X3NO division if XY=YZ X=Z ? NO subtraction if X+Y=X+Z Y=Z ?X=1, Y=0, Z=0XY=XZ=0, X ZX=1, Y=0, Z=1错！错！错！错！14/35Digita

19、l Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Multi-Variable TheoremsMulti-Variable TheoremsTheorem 1 “Covering” (吸收律吸收律) X + XY = X X(X+Y) = X Examples:(X + Y) + (X + Y)Z = X + YAB(AB + BC) = ABTheorem 2 “Combining” (组合律组合律) XY + XY =

20、 X (X+Y)(X+Y) = XExamples:ABC + ABC = AC(W + X + Y + Z)(W + X + Y + Z)(W + X + Y + Z)(W + X + Y + Z)= (W + X + Y)(W + X + Y + Z)(W + X + Y + Z)= (W + X + Y)(W + X + Y)= W + X15/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Mult

21、i-Variable TheoremsMulti-Variable TheoremsTheorem 3(a) X + X Y = X + Y(b) X(X + Y) = XYExamples:B + ABCD = B + ACD(X + Y)(X + Y) + Z) = (X + Y)ZTheorem 4(a) XY + XYZ = XY + XZ(b) (X + Y)(X + Y + Z) = (X + Y)(X + Z)Examples:wy + wxy + wxyz + wxz = wy + wxy + wxy + wxz= wy + wy + wxz= w + wxz= w(xy +

22、z)(w + xy + z) = (xy + z)(w + xy)16/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Prove： XY + XZ + YZ = XY + XZYZ = 1YZ = (X+X)YZXY + XZ + (X+X)YZ= XY + XZ + XYZ +XYZ= XY(1+Z) + XZ(1+Y)= XY + XZXY + XZ + YZ= XY + XZ (X+Y)(X+Z)(

23、Y+Z) = (X+Y) (X+Z)Theorem 5 “ConsensusConsensus” ( (一致性定律一致性定律, ,冗余项公式冗余项公式) )17/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014ExamplesAB + ACD + BCD(a + b)(a + c)(b + c)ABC + AD + BD + CD18/35= AB + ACD= (a + b)(a + c)= ABC +

24、(A + B)D + CD= ABC + (AB)D + CD= ABC + (AB)D= ABC + (A + B)D= ABC + AD + BDDigital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Theorem 6 (DeMorgans Theorem)complement of a logic expression(a) (X + Y) = X Y(b) (XY) = X + YGeneralized De

25、Morgans Theorem(a) (a + b + z) = ab z (b) (ab z) = a + b + zExamples:(a + bc) = (a + (bc)= a(bc)= a(b + c)= ab + acNote: (a + bc) ab + c19/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Examples(a(b + c) + ab)= (ab + ac + ab)= (

26、b + ac)= b(ac)= b(a + c)(a(b + z(x + a) = a + (b + z(x + a)= a + b (z(x + a)= a + b (z + (x + a)= a + b (z + x(a)= a + b (z + xa)= a + b (z + x)20/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 201421等效电路符号等效电路符号或或逻辑门符号逻辑门符号等效符号等效符号

27、或非或非与与与非与非反相器反相器缓冲器缓冲器)B(A)B)(ABA)B(A)(AB)ABBAB)(ABA(AB)Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Theorem forTheorem for XORXOR (异或异或)Commutative：X Y = Y XAssociative：X (Y Z) = (X Y) ZDistributive：X(Y Z) = (XY) (XZ) 因果互换关系因果互

28、换关系 X Y=Z X Z=Y Y Z=X X Y Z W=0 0 X Y Z=W22/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Theorem forTheorem for XORXOR (异或异或)Variable and Constant - X X=0 X X=1 X 0=X X 1=XMulti-variable - the result depends on the total numbe

29、r of “1”X0 X1 Xn = 1 变量为变量为1的个数是奇数的个数是奇数0 变量为变量为1的个数是偶数的个数是偶数23/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Theorem for XNORTheorem for XNOR (同或同或)Commutative：X Y = Y X Associative：X (Y Z) = (X Y) ZNO Distributive：X(Y Z) (XY)

30、 (XZ)因果互换关系因果互换关系 X Y=Z X Z=Y Y Z=X24/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Theorem forTheorem for XNORXNOR (同或同或)Variable and Constant -X X=1 X X=0 X 1=X X 0=XMulti-variable - the result depends on the total number of

31、“0”X0 X1 Xn = 1 变量为变量为0的个数是偶数的个数是偶数0 变量为变量为0的个数是奇数的个数是奇数25/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014XOR vs. XNORXOR vs. XNORA B = A B A B = A BA B = A B A B = A BEven variables XOR and XNOR- opposite X Y = (X Y) X Y Z W =

32、(X Y Z W) Odd variables XOR and XNOR - equal X Y Z = X Y Z26/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Shannon TheoremShannon TheoremGeneralized idempotency (广义同一律广义同一律)X + X + + X = X X X X = XShannons expansion theorems (

33、香农展开定理香农展开定理)12n12n12nF(X ,X ,X )X F(1,X ,X )X F(0,X ,X )12n12n12nF(X ,X ,X )XF(0,X ,X ) XF(1,X ,X )香农展开定理主要用于证明等式或展开函数香农展开定理主要用于证明等式或展开函数将函数展开一次可以使函数内部的变量数从将函数展开一次可以使函数内部的变量数从n n个减少到个减少到n-1n-1个个对上述的公式、定理要熟记，做到对上述的公式、定理要熟记，做到举一反三举一反三27/35Digital Logic Design and ApplicationUniversity of Electronic S

34、cience and Technology of ChinaProf. Lin Shuisheng, 2014Prove: XW + XZ + ZW + XYZW = XW + XZXW + XZ + ZW + XYZW = X ( 1W + 1Z + ZW + 1YZW ) + X ( 0W + 0Z + ZW + 0YZW )= X ( W + ZW + YZW ) + X ( Z + ZW )= XW( 1 + Z + YZ ) + XZ( 1 + W )= XW + XZExample for Shannon theorem28/35Digital Logic Design and A

35、pplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014(X+Y) + (X+Y) = 1Example1: X+X = 1Example2: XY + XY = X(X+Y)(X(Y+Z) + (X+Y)(X(Y+Z) = (X+Y)Substitution Rule (代入规则代入规则)：Any theorem or identity with variable X in switching algebra remains true if substituting

36、all X with another variable or logic expression. Rule 1 - substitutionRule 1 - substitution29/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Complement of a logic expression (反演规则反演规则) ：ANDOR，0 1，complementing all variablesKeep

37、the operation order of the original function (保持运算优先级）保持运算优先级）Do NOT change the prime ( ) over multi-variables (不属于单个变量上的反号应保留不变不属于单个变量上的反号应保留不变)Ex1：Perform the complement expressions F1 = X (Y + Z) + Z W F2 = (X Y) + Z W EF1 = ( X+ Y Z )( Z+W ) = XZ + XW + YZ + Y Z W = X Z + X W + Y ZF2 = (X+Y ) (

38、Z+W+E )Rule 2 - complementRule 2 - complement30/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Prove： (XY + XZ) XY + XZ + YZ = XY + XZ=(X+Y)(X+Z)=XX +XZ + XY + YZ=XZ + XY =XZ + XY + YZEx2：Prove (XY + XZ) = XY + XZ31/35Digital Lo

39、gic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Rule 3 - Duality Rule 3 - Duality （对偶定理（对偶定理） Dual of a logic expressionFD(X1 , X2 , , Xn , + , , )= F(X1 , X2 , , Xn , , + , )ANDOR；0 1Keep the operation order of the original function Princip

40、le of DualityIf a logic equation is true, then its duality remains true. X + X Y = XX X + Y = XX + Y = XX ( X + Y ) = X错！错！32/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2014Application of dualityApplication of dualityProve： X+YZ = (X+Y)(X+Z)X(Y+Z)XY+XZEx：Perform the dualities. F1 = X + Y (Z + W) F2 = ( X(Y+Z) + (Z+W) )F1D = X(Y+Z W)F2D= (X+Y Z ) ( Z W)33/35Digital Logic Design and ApplicationUniversity of Electronic Science and Technology of ChinaProf. Lin Shuisheng, 2