1Boolean AlgebraECE 152A – Fall 2006October 3, 2006ECE 152A - Digital Design Principles2Reading Assignment Brown and Vranesic 2 Introduction to Logic Circuits 2.5 Boolean Algebra 2.5.1 The Venn Diagram 2.5.2 Notation and Terminology 2.5.3 Precedence of Operations 2.6 Synthesis Using AND, OR and NOT Gates 2.6.1 Sum-of-Products and Product of Sums Forms2October 3, 2006ECE 152A - Digital Design Principles3Reading Assignment Brown and Vranesic (cont) 2 Introduction to Logic Circuits (cont) 2.7 NAND and NOR Logic Networks 2.8 Design Examples 2.8.1 Three-Way Light Control 2.8.2 Multiplexer CircuitOctober 3, 2006ECE 152A - Digital Design Principles4Reading Assignment Roth 2 Boolean Algebra 2.3 Boolean Expressions and Truth Tables 2.4 Basic Theorems 2.5 Commutative, Associative, and Distributive Laws 2.6 Simplification Theorems 2.7 Multiplying Out and Factoring 2.8 DeMorgan’s Laws3October 3, 2006ECE 152A - Digital Design Principles5Reading Assignment Roth (cont) 3 Boolean Algebra (Continued) 3.1Multiplying Out and Factoring Expressions 3.2 Exclusive-OR and Equivalence Operation 3.3 The Consensus Theorem 3.4 Algebraic Simplification of Switching ExpressionsOctober 3, 2006ECE 152A - Digital Design Principles6Reading Assignment Roth (cont) 4 Applications of Boolean Algebra Minterm and Maxterm Expressions 4.3 Minterm and Maxterm Expansions 7 Multi-Level Gate Circuits NAND and NOR Gates 7.2 NAND and NOR Gates 7.3 Design of Two-Level Circuits Using NAND and NOR Gates 7.5 Circuit Conversion Using Alternative Gate Symbols4October 3, 2006ECE 152A - Digital Design Principles7Boolean Algebra Axioms of Boolean Algebra Axioms 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’ = 0October 3, 2006ECE 152A - Digital Design Principles8Boolean Algebra The 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.”5October 3, 2006ECE 152A - Digital Design Principles9Boolean Algebra Single-Variable Theorems Theorems can be proven with truth tables Truth 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’)’ = XOctober 3, 2006ECE 152A - Digital Design Principles10Boolean Algebra Two- and Three-Variable Properties CommutativeX · Y = Y · X X + Y = Y + X AssociativeX · (Y · Z) = (X · Y) · Z X + (Y + Z) = (X + Y) + Z DistributiveX · (Y + Z) = X · Y + X · Z X + (Y · Z) = (X + Y)·(X + Z)6October 3, 2006ECE 152A - Digital Design Principles11Boolean Algebra Absorption (Simplification)X + X · Y = X X · ( X + Y ) = XYX0101YX01011100XX·YXX+YOctober 3, 2006ECE 152A - Digital Design Principles12Boolean Algebra Combining (Simplification)X · Y + X · Y’ = X (X + Y) · (X + Y’) = XYX0101YX01011100X·YX·Y’XXX+Y’X+Y7October 3, 2006ECE 152A - Digital Design Principles13Boolean Algebra Redundant Coverage (simplification)X + X’ · Y = X + Y X · (X’ + Y) = X · YYX0101YX0101110010XX+YX’·Y XX’+YX·YOctober 3, 2006ECE 152A - Digital Design Principles14Boolean Algebra The Consensus TheoremXY + X’Z + YZ = XY + X’ZYZX00 010111 101111XYX’Z YZ8October 3, 2006ECE 152A - Digital Design Principles15Boolean Algebra DeMorgan’s Theorem(X · Y)’ = X’ + Y’ (X + Y)’ = X’ · Y’YX0101YX010100111100(X·Y)0001(X·Y)’0111X+Y(X+Y)’X’+Y’X’·Y’October 3, 2006ECE 152A - Digital Design Principles16Boolean Expressions Precedence of Operations Order of evaluation 1. NOT 2. AND 3. OR Or forced by parentheses Example: F = ab’c + a’b + a’bc’ + b’c’ a=0, b=0 and c=1 NOT: 011 + 10 + 100 + 10 AND: 0 + 0 + 0 + 0 OR: 09October 3, 2006ECE 152A - Digital Design Principles17Boolean Expressions, Logic Networks, Karnaugh Maps, Truth Tables & Timing Diagrams Derive 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 terms Expression is in Standard Sum-of-Products form i.e., the function is the sum (or logical OR) or the four product (or logical AND) terms The alternative standard form is Product-of-Sums The expression “implies” structure Direct realization with AND, OR and NOT functionsOctober 3, 2006ECE 152A - Digital Design Principles18Boolean Expressions, Logic Networks, Karnaugh Maps, Truth Tables & Timing Diagrams Logic Network F = ab’c + a’b + a’bc’ + b’c’10October 3, 2006ECE 152A - Digital Design Principles19Boolean Expressions, Logic Networks, Karnaugh Maps, Truth Tables & Timing Diagrams Karnaugh Map F = ab’c + a’b + a’bc’ + b’c’bca00 010111 1011111b’c’ab’ca’ba’bc’October 3, 2006ECE 152A - Digital Design Principles20Boolean Expressions, Logic Networks, Karnaugh Maps, Truth Tables & Timing Diagrams Note possible simplification Redundant coverage (eliminates literal) and absorption (eliminates product term)bca00 010111 1011111b’c’ab’a’b11October 3, 2006ECE 152A - Digital Design Principles21Boolean Expressions, Logic Networks, Karnaugh Maps, Truth Tables & Timing Diagrams Truth Table F = ab’c + a’b + a’bc’ + b’c’01110011110110011110101001001000FcbaOctober 3, 2006ECE 152A - Digital Design Principles22Boolean Expressions, Logic Networks, Karnaugh Maps, Truth Tables & Timing Diagrams Timing Diagram (Functional Simulation) F = ab’c + a’b + a’bc’ + b’c’10001111000InputOutput001 010 011 100 101 110 11112October 3, 2006ECE 152A - Digital Design Principles23Minterms and Maxterms