1Boolean AlgebraECE 152A – Summer 2009June 24, 2009ECE 152A - Digital Design Principles2Reading AssignmentBrown and Vranesic2 Introduction to Logic Circuits2.5 Boolean Algebra2.5.1 The Venn Diagram2.5.2 Notation and Terminology2.5.3 Precedence of Operations2.6 Synthesis Using AND, OR and NOT Gates2.6.1 Sum-of-Products and Product of Sums Forms2June 24, 2009ECE 152A - Digital Design Principles3Reading AssignmentBrown and Vranesic (cont)2 Introduction to Logic Circuits (cont)2.7 NAND and NOR Logic Networks2.8 Design Examples2.8.1 Three-Way Light Control2.8.2 Multiplexer CircuitJune 24, 2009ECE 152A - Digital Design Principles4Reading AssignmentRoth2 Boolean Algebra2.3 Boolean Expressions and Truth Tables2.4 Basic Theorems2.5 Commutative, Associative, and Distributive Laws2.6 Simplification Theorems2.7 Multiplying Out and Factoring2.8 DeMorgan’s Laws3June 24, 2009ECE 152A - Digital Design Principles5Reading AssignmentRoth (cont)3 Boolean Algebra (Continued)3.1Multiplying Out and Factoring Expressions3.2 Exclusive-OR and Equivalence Operation3.3 The Consensus Theorem3.4 Algebraic Simplification of Switching ExpressionsJune 24, 2009ECE 152A - Digital Design Principles6Reading AssignmentRoth (cont)4 Applications of Boolean Algebra Minterm and Maxterm Expressions4.3 Minterm and Maxterm Expansions7 Multi-Level Gate Circuits NAND and NOR Gates7.2 NAND and NOR Gates7.3 Design of Two-Level Circuits Using NAND and NOR Gates7.5 Circuit Conversion Using Alternative Gate Symbols4June 24, 2009ECE 152A - Digital Design Principles7Boolean AlgebraAxioms of Boolean AlgebraAxioms generally presented without proof0 · 0 = 0 1 + 1 = 11 · 1 = 1 0 + 0 = 00 · 1 = 1 · 0 = 0 1 + 0 = 0 + 1 = 1if X = 0, then X’ = 1 if X = 1, then X’ = 0June 24, 2009ECE 152A - Digital Design Principles8Boolean AlgebraThe Principle of Dualityfrom Zvi Kohavi, Switching and Finite Automata Theory“We observe that all the preceding properties are grouped in pairs. Within each pair one statement can be obtained from the other by interchanging the OR and AND operations and replacing the constants 0 and 1 by 1 and 0 respectively. Any two statements or theorems which have this property are called dual, and this quality of duality which characterizes switching algebra is known as the principle of duality. It stems from the symmetry of the postulates and definitions of switching algebra with respect to the two operations and the two constants. The implication of the concept of duality is that it is necessary to prove only one of each pair of statements, and its dual is henceforth proved.”5June 24, 2009ECE 152A - Digital Design Principles9Boolean AlgebraSingle-Variable TheoremsTheorems can be proven with truth tablesTruth table proof a.k.a., “Perfect Induction”X · 0 = 0 X + 1 = 1X · 1 = X X + 0 = X X · X = X X + X = XX · X’ = 0 X + X’ = 1(X’)’ = XJune 24, 2009ECE 152A - Digital Design Principles10Boolean AlgebraTwo- and Three-Variable PropertiesCommutativeX · Y = Y · X X + Y = Y + XAssociativeX · (Y · Z) = (X · Y) · Z X + (Y + Z) = (X + Y) + ZDistributiveX · (Y + Z) = X · Y + X · Z X + (Y · Z) = (X + Y)·(X + Z)6June 24, 2009ECE 152A - Digital Design Principles11Boolean AlgebraAbsorption (Simplification)X + X · Y = X X · ( X + Y ) = XYX0 101YX0 1011 10 0XX·YXX+YJune 24, 2009ECE 152A - Digital Design Principles12Boolean AlgebraCombining (Simplification)X · Y + X · Y’ = X (X + Y) · (X + Y’) = XYX0 101YX0 1011 10 0X·YX·Y’XX X+Y’X+Y7June 24, 2009ECE 152A - Digital Design Principles13Boolean AlgebraRedundant Coverage (simplification)X + X’ · Y = X + Y X · (X’ + Y) = X · YYX0 101YX0 1011 10 010XX+YX’·Y XX’+YX·YJune 24, 2009ECE 152A - Digital Design Principles14Boolean AlgebraThe Consensus TheoremXY + X’Z + YZ = XY + X’ZYZX00 010111 101111XYX’Z YZ8June 24, 2009ECE 152A - Digital Design Principles15Boolean AlgebraDeMorgan’s Theorem(X · Y)’ = X’ + Y’ (X + Y)’ = X’ · Y’YX0 101YX0 1010011 11 00(X·Y)0001(X·Y)’0 111X+Y(X+Y)’X’+Y’X’·Y’June 24, 2009ECE 152A - Digital Design Principles16Boolean ExpressionsPrecedence of OperationsOrder of evaluation1. NOT2. AND3. OROr forced by parenthesesExample: F = ab’c + a’b + a’bc’ + b’c’a=0, b=0 and c=1NOT: 011 + 10 + 100 + 10AND: 0 + 0 + 0 + 0OR: 09June 24, 2009ECE 152A - Digital Design Principles17Boolean Expressions, Logic Networks, Karnaugh Maps, Truth Tables & Timing DiagramsDerive Logic Network, Karnaugh Map, Truth Table and Timing Diagram from:F = ab’c + a’b + a’bc’ + b’c’3 variables, 10 literals, 4 product termsExpression is in Standard Sum-of-Products formi.e., the function is the sum (or logical OR) or the four product (or logical AND) termsThe alternative standard form is Product-of-SumsThe expression “implies” structureDirect realization with AND, OR and NOT functionsJune 24, 2009ECE 152A - Digital Design Principles18Boolean Expressions, Logic Networks, Karnaugh Maps, Truth Tables & Timing DiagramsLogic NetworkF = ab’c + a’b + a’bc’ + b’c’10June 24, 2009ECE 152A - Digital Design Principles19Boolean Expressions, Logic Networks, Karnaugh Maps, Truth Tables & Timing DiagramsKarnaugh MapF = ab’c + a’b + a’bc’ + b’c’bca00 010111 1011111b’c’ab’ca’ba’bc’June 24, 2009ECE 152A - Digital Design Principles20Boolean Expressions, Logic Networks, Karnaugh Maps, Truth Tables & Timing DiagramsNote possible simplificationRedundant coverage (eliminates literal) and absorption (eliminates product term)bca00 010111 1011111b’c’ab’a’b11June 24, 2009ECE 152A - Digital Design Principles21Boolean Expressions, Logic Networks, Karnaugh Maps, Truth Tables & Timing DiagramsTruth TableF = ab’c + a’b + a’bc’ + b’c’01110011110110011110101001001000FcbaJune 24, 2009ECE 152A - Digital Design Principles22Boolean Expressions, Logic Networks, Karnaugh Maps, Truth Tables & Timing DiagramsTiming Diagram (Functional Simulation)F = ab’c + a’b + a’bc’ + b’c’100 01 1 11000InputOutput001 010 011 100 101 110 11112June 24, 2009ECE 152A - Digital Design Principles23Minterms and MaxtermsMintermA product term which contains each of the nvariables as factors in either complemented or
View Full Document