EECC341 - ShaabanEECC341 - Shaaban#1 Lec # 5 Winter 2001 12-13-2001Switching Algebra: Principle of Duality• Any theorem or identity in switching algebra remainstrue if 0 and 1 are swapped and . and + are swapped.• True because all the duals of all the axioms are true, soduals of all switching-algebra theorems can be provenusing the duals of axioms.• Dual of a logic expression: For a fully parenthesizedlogic expression F(X1, X2, …., Xn, + , . , ’) then the dualexpression, FD, is the same expression with +, . swapped: FD(X1, X2, …., Xn, +, . , ’) = F(X1, X2, …., Xn, . , + , ’)• The generalized DeMorgan’s theorem T14 can be statedas: [F(X1, X2, …., Xn)]’ = FD(X1’, X2’, …., Xn’)EECC341 - ShaabanEECC341 - Shaaban#2 Lec # 5 Winter 2001 12-13-2001Switching Algebra Axioms & Theorems(A1) X = 0 if X ≠≠ 1 (A1’) X = 1 if X ≠≠ 0(A2) If X = 0, then X’ = 1 (A2’) if X = 1, then, X’ = 0(A3) 0 . 0 = 0 (A3’) 1 + 1 = 1(A4) 1 . 1 = 1 (A4’) 0 + 0 = 0(A5) 0 . 1 = 1 . 0 = 0 (A5’) 1 + 0 = 0 + 1 = 1(T1) X + 0 = X (T1’) X . 1 = X (Identities)(T2) X + 1 = 1 (T2’) X . 0 = 0 (Null elements)(T3) X + X = X (T3’) X . X = X (Idempotency)(T4) (X’)’ = X (Involution)(T5) X + X’ = 1 (T5’) X . X’ = 0 (Complements)(T6) X + Y = Y + X (T6’) X . Y = Y . X (Commutativity)(T7) (X + Y) + Z = X + (Y + Z) (T7’) (X . Y) . Z = X . (Y . Z) (Associativity)(T8) X . Y + X . Z = X . (Y + Z) (T8’) (X + Y) . (X + Z) = X + Y . Z (Distributivity)(T9) X + X . Y = X (T9’) X . (X + Y) = X (Covering)(T10) X . Y + X . Y’ = X (T10’) (X + Y) . (X + Y’) = X (Combining)(T11) X . Y + X’. Z + Y . Z = X . Y + X’ . Z(T11’) (X + Y) . ( X’ + Z) . (Y + Z) = (X + Y) . (X’ + Z) (Consensus)(T12) X + X + . . . + X = X (T12’) X . X . . . . . X = X (Generalized idempotency)(T13) (X1 . X2 . . . . . Xn)’ = X1’ + X2’ + . . . + Xn’(T13’) (X1 + X2 + . . . + Xn)’ = X1’ . X2’ . . . . . Xn’ (DeMorgan’s theorems)(T14) [F(X1, X2, . . ., Xn, +, .)]’ = F(X1’, X2’, . . ., Xn’, . , +) (Generalized DeMorgran’s theorem)EECC341 - ShaabanEECC341 - Shaaban#3 Lec # 5 Winter 2001 12-13-2001Logic Expression Algebraic Manipulation ExampleLogic Expression Algebraic Manipulation Example• Prove that the following identity is true using Algebraicexpression Manipulation : (one can also prove it using a truth table) X .Y + X . Z = ((X’ + Y’) . (X’ + Z’))’– Starting from the left hand side of the identity: Let F = X .Y + X . Z A = X . Y B = X . Z Then F = A + B– Using DeMorgan’s theorem T 13 on F: F = A + B = (A’ . B’)’ (1)– Using DeMorgan’s theorem T 13’ on A, B: A = X . Y = (X’ + Y’)’ (2) B = X . Z = (X’ + Z’)’ (3)– Substituting A, B from (2), (3), back in F in (1) gives: F = (A’ . B’)’ = ((X’ + Y’) . (X’ + Z’))’ Which is equal to the right hand side of the identity.EECC341 - ShaabanEECC341 - Shaaban#4 Lec # 5 Winter 2001 12-13-2001Standard Representations of Logic Functions• Truth table for n-variable logic function: Input combinations are arranged in 2n rows in ascending binaryorder, and the output values are written in a column next to the rows.• Practical for functions with a small number of variables.• The general structure of a 3-variable truth table is given by:Row X Y Z F(X,Y,Z) 0 0 0 0 F(0,0,0) 1 0 0 1 F(0,0,1) 2 0 1 0 F(0,1,0) 3 0 1 1 F(0,1,1) 4 1 0 0 F(1,0,0) 5 1 0 1 F(1,0,1) 6 1 1 0 F(1,1,0) 7 1 1 1 F(1,1,1)Truth table for a specific function:Row X Y Z F 0 0 0 0 1 1 0 0 1 0 2 0 1 0 0 3 0 1 1 1 4 1 0 0 1 5 1 0 1 0 6 1 1 0 1 7 1 1 1 1EECC341 - ShaabanEECC341 - Shaaban#5 Lec # 5 Winter 2001 12-13-2001Logic Function Representation Definitions• A literal: is a variable or a complement of a variable Examples: X, Y, X’, Y’• A product term: is a single literal, or a product of two or more literals.Examples: Z’ W.Y.Y X.Y’.Z W’.Y’.Z• A sum-of-products expression: is a logical sum of product terms. Example: Z’ + W.X.Y + X.Y’.Z + W’.Y’.Z• A sum term: is a single literal or logical sum of two or more literals Examples: Z’ W + X + Y X + Y’ + Z W’ + Y’ + Z• A product-of-sums expression: is a logical product of sum terms. Example: Z’. (W + X + Y) . (X + Y’ + Z) . (W’ + Y’ + Z)• A normal term: is a product or sum term in which no variable appearsmore than once Examples of non-normal terms: W.X.X.Y’ W+W+X’+Y X.X’.Y Examples of normal terms: W . X . Y’ W + X’ + YEECC341 - ShaabanEECC341 - Shaaban#6 Lec # 5 Winter 2001 12-13-2001Logic Function Representation Definitions• Minterm An n-variable minterm is a normal product term with n literals. There are 2n such products terms. Example of 4-variable minterms: W.X’.Y’.Z’ W.X.Y’.Z W’.X’.Y.Z’• Maxterm An n-variable maxterm is a normal sum term with n literals. There are 2n such sum terms. Examples of 4-variable maxterms: W’ + X’ + Y + Z’ W + X’ + Y’ + Z W’ + X’ + Y + Z• A minterm can be defined as as product term that is 1 in exactlyone row of the truth table.• A maxterm can similarly be defined as a sum term that is 0 inexactly one row in the truth table.EECC341 - ShaabanEECC341 - Shaaban#7 Lec # 5 Winter 2001 12-13-2001Minterms/Maxterms forA 3-variable function F(X,Y,Z)Row X Y Z F Minterm Maxterm 0 0 0 0 F(0,0,0) X’.Y’.Z’ X + Y + Z 1 0 0 1 F(0,0,1) X’.Y’.Z X + Y + Z’ 2 0 1 0 F(0,1,0) X’.Y.Z’ X + Y’ + Z 3 0 1 1 F(0,1,1) X’.Y.Z X + Y’