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布爾代數(shù)，邏輯代數(shù)，二值代數(shù)布爾代數(shù)，邏輯代數(shù)，二值代數(shù)公理、定理、公式及其運(yùn)用公理、定理、公式及其運(yùn)用0、1運(yùn)算規(guī)則運(yùn)算規(guī)則公理（基本定理）公理（基本定理）導(dǎo)出公式：吸收律，冗余項(xiàng)公式等導(dǎo)出公式：吸收律，冗余項(xiàng)公式等基本公式對(duì)基本公式對(duì)“異或異或”、“同或同或”的適用性的適用性摩根定理和香農(nóng)定理摩根定理和香農(nóng)定理變換規(guī)則變換規(guī)則代入規(guī)則代入規(guī)則反演規(guī)則反演規(guī)則對(duì)偶規(guī)則對(duì)偶規(guī)則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”(優(yōu)先級(jí)優(yōu)先級(jí))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): (結(jié)合律結(jié)合律)(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): (互補(bǔ)律互補(bǔ)律)(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錯(cuò)！錯(cuò)！錯(cuò)！錯(cuò)！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” ( (一致性定律一致性定律, ,冗余項(xiàng)公式冗余項(xiàng)公式) )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等效電路符號(hào)等效電路符號(hào)或或邏輯門(mén)符號(hào)邏輯門(mén)符號(hào)等效符號(hào)等效符號(hào)

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) 因果互換關(guān)系因果互

28、換關(guān)系 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的個(gè)數(shù)是奇數(shù)的個(gè)數(shù)是奇數(shù)0 變量為變量為1的個(gè)數(shù)是偶數(shù)的個(gè)數(shù)是偶數(shù)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)因果互換關(guān)系因果互換關(guān)系 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的個(gè)數(shù)是偶數(shù)的個(gè)數(shù)是偶數(shù)0 變量為變量為0的個(gè)數(shù)是奇數(shù)的個(gè)數(shù)是奇數(shù)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、香農(nóng)展開(kāi)定理香農(nóng)展開(kāi)定理)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óng)展開(kāi)定理主要用于證明等式或展開(kāi)函數(shù)香農(nóng)展開(kāi)定理主要用于證明等式或展開(kāi)函數(shù)將函數(shù)展開(kāi)一次可以使函數(shù)內(nèi)部的變量數(shù)從將函數(shù)展開(kāi)一次可以使函數(shù)內(nèi)部的變量數(shù)從n n個(gè)減少到個(gè)減少到n-1n-1個(gè)個(gè)對(duì)上述的公式、定理要熟記，做到對(duì)上述的公式、定理要熟記，做到舉一反三舉一反三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 (代入規(guī)則代入規(guī)則)：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 (反演規(guī)則反演規(guī)則) ：ANDOR，0 1，complementing all variablesKeep

37、the operation order of the original function (保持運(yùn)算優(yōu)先級(jí)）保持運(yùn)算優(yōu)先級(jí)）Do NOT change the prime ( ) over multi-variables (不屬于單個(gè)變量上的反號(hào)應(yīng)保留不變不屬于單個(gè)變量上的反號(hào)應(yīng)保留不變)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 （對(duì)偶定理（對(duì)偶定理） 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錯(cuò)！錯(cuò)！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