1ECET 331 – Digital Integrated CircuitsChapter 3Boolean Algebra and Combinational LogicECET 331 - Digital Integrated CircuitsObjectiveBooleanExpressionLogicDiagramTruthTableECET 331 - Digital Integrated CircuitsLogic Gate Networkz Two or more logic gates connected togetherz Described by truth table, logic diagram or Boolean expressionECET 331 - Digital Integrated CircuitsLogic Gate NetworkECET 331 - Digital Integrated CircuitsBoolean Expression from Logic Gate Networkz Similar to finding the expression for a single gatez Inputs may be compound expressions that represent outputs from previous gatesECET 331 - Digital Integrated CircuitsBubble-to-Bubble Conventionz Choose gate symbols so that outputs with bubbles connect to inputs with bubblesz Results in a cleaner notation and a clearer idea of the circuit function2ECET 331 - Digital Integrated CircuitsSimplification by Double Inversionz In logic circuits, when two bubbles touch, they cancel outz In Boolean expressions, bars of the same length cancelECET 331 - Digital Integrated CircuitsBubble-to-Bubble / Double Inversion (example)Y = AB+BCS =[P+Q][Q+R]= (P+Q)(Q+R)ECET 331 - Digital Integrated CircuitsOrder of Precedencez Unless otherwise specified, in Boolean expressions AND functions are performed first, followed by ORsExample: Y = A & B + C + Dz To change the order of precedence, use parenthesesExample: Y = A & (B + C + D)ECET 331 - Digital Integrated CircuitsLogic Diagrams from Boolean Expressionsz Called synthesisz Use order of precedence• A bar over a group of variables is the same as having those variables in parenthesesz Create levels of gating based on orders of precedenceECET 331 - Digital Integrated CircuitsLogic Diagrams from Boolean Expressions (example)Synthesize: Y = (A + B)(C + D)(E + F)BACDEFYA + BC + DE + F(C + D)(E+F)ECET 331 - Digital Integrated CircuitsTruth Tables from Logic Diagrams or Boolean Expressionsz Two methods:1) Combine individual truth tables from each gate into a final output truth table2) Develop a Boolean expression and use it to fill in the truth tableWhich is more thorough? Which is more efficient?3ECET 331 - Digital Integrated CircuitsTruth Table (Method 1) ABCA B C (A + B) (A + C) (A + B)(A + C)0 0 0 1 0 00 0 1 1 1 10 1 0 1 0 00 1 1 1 1 11 0 0 1 1 11 0 1 1 1 11 1 0 0 1 01 1 1 0 1 0ECET 331 - Digital Integrated CircuitsCircuit Description Using Boolean Expressionsz Definitions:• A product term is a part of a Boolean expression where one or more true or complement variables are ANDed• A sum term is a part of a Boolean expression where one or more true or complement variables are ORedECET 331 - Digital Integrated CircuitsSOP and POSz A sum-of-products (SOP) is a Boolean expression where several product terms are summed (ORed) togetherExample: Y = AB + CD + ADz A product-of-sums (POS) is a Boolean expression where several sum terms are multiplied (ANDed) togetherExample: P = (A + B)(C + D)(E + F)ECET 331 - Digital Integrated CircuitsMinterms and Maxtermsz Minterm• A product term in a Boolean expression where all possible input variables appear once in true or complemented formExamples: ABC; ABCz Maxterm• A sum term in a Boolean expression where all possible variables appear once in true or complemented formExamples: (A + B + C); (A + B + C)ECET 331 - Digital Integrated CircuitsDeriving a SOP Expression from a Truth Table1) Each line of the truth table with a 1 (HIGH) output represents a product term (a minterm) in the truth table’s Boolean expression2) Write all input variables for each minterm in true or complement form• If an input variable’s value is 0, write it in complement form (with a bar over it)• If an input variable’s value is 1, write it in true form (no bar)3) Combine all minterms as a sum (OR them)ECET 331 - Digital Integrated CircuitsSOP (example)A B C Y0 0 0 10 0 1 00 1 0 00 1 1 11 0 0 11 0 1 01 1 0 01 1 1 0DigitalCircuitABCYApply all possible inputs to fill out truth tableFind Minterms:ABC, ABC, ABC4ECET 331 - Digital Integrated CircuitsBus FormBus Form:A schematic convention in which each variable is available in true or complement form (or double-rail) at any point along a conductorECET 331 - Digital Integrated CircuitsDeriving a POS Expression from a Truth Table1) Each line of the truth table with a 0 (LOW) output represents a sum term (a maxterm) in the truth table’s Boolean expression2) Write all input variables for each maxterm in true or complement form• If a variable’s value is 1, write it in complement form (with a bar over it)• If a variable’s value is 0, write it in true form (no bar)3) Combine all maxterms as a product (AND them)ECET 331 - Digital Integrated CircuitsPOS (example)A B C Y0 0 0 10 0 1 00 1 0 00 1 1 11 0 0 11 0 1 01 1 0 01 1 1 0DigitalCircuitABCYApply all possible inputs to fillout the truth tableFind Maxterms:(A + B + C), (A + B + C), (A + B + C)(A + B + C), (A + B + C) ECET 331 - Digital Integrated CircuitsExercisez Derive the SOP form for an XOR gateECET 331 - Digital Integrated CircuitsTheorems of Boolean Algebraz 24 theoremsz Used to minimize a Boolean expression to reduce the number of logic gates in a networkECET 331 - Digital Integrated CircuitsCommutative Propertyz An operation is commutative if it can be applied to its operands in any order without effecting the resultz AND and OR are commutative• Theorem 1: xy = yx.• Theorem 2: x + y = y + x5ECET 331 - Digital Integrated CircuitsAssociative Propertyz An operation is associative if its operands can be grouped in any order without effecting the resultz AND and OR are associative• Theorem 3: (xy)z = x(yz) = (xz)y• Theorem 4: (x + y) + z = x + (y + z) = (x + z) + yECET 331 - Digital Integrated CircuitsDistributive Property(of Multiplication over Addition)z The property allows us to distribute (multiply through) an AND across several OR functions• Theorem 5: x(y + z) = xy + xz• Theorem 6: (x + y)(w + z) = xw + xz + yw + yzECET 331 - Digital Integrated CircuitsOperations with 1 and 0z Theorem 7: x • 0 = 0z Theorem 8: x + 0 = xz Theorem 9: x ⊕ 0 = xz Theorem 10: x • 1 = xz Theorem 11: x + 1 = 1z Theorem 12: x ⊕ 1 = xECET 331 - Digital Integrated CircuitsOperations with One Variablez The same variable• Theorem 13: x • x = x• Theorem 14: x + x = x• Theorem 15: x ⊕ x = 0z The complement of the variable• Theorem 16: x • x = 0• Theorem 17: x + x = 1• Theorem 18: x