Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 151Complement of a FunctionA function F’ has the exact opposite truth table as function F.Reading Assignment: Chapter 2 in Logic and Computer Design Fundamentals, 4th Edition by Mano Canonical and Standard formsBoolean functions are commonly expressed using the following forms:• Canonical forms:» Sum of minterms» Product of maxterms• Standard forms:» Sum of products» Product of sumsF x y z x y    Example: Find truth table for F and for F’ for the function below.Lecture #3 EGR 270 – Fundamentals of Computer Engineering2Example: f(A,B) has 4 possible minterms. List them.Minterm – (also called a standard product) A minterm is a term containing all n variables (complemented or uncomplemented) ANDed together.Each minterm represents one n-bit word where:Primed variable  0Unprimed variable  1Minterm designation: for function f(x,y,z) the input combination 000 represents minterm x’y’z’ and is designated m0.Example: Show all 8 possible minterms and the shorthand designations for f(x, y, z).Lecture #3 EGR 270 – Fundamentals of Computer Engineering3Example: Pick a truth table for some function f(x,y,z) and represent f as a sum of minterms.Key Point: A Boolean function F may be represented by a sum (ORed together) of its minterms. They represent the input combinations needed to yield F = 1. So minterms represent the 1’s in the truth table for F.Maxterm – (also called a standard sum) A maxterm is a term containing all n variables (complemented or uncomplemented) ORed together.F (minterms)Example: f(A,B) has 4 possible maxterms. List them.Lecture #3 EGR 270 – Fundamentals of Computer Engineering4Each maxterm represents one n-bit word where:Primed variable  1 (note that this is opposite of the notation used for minterms)Unprimed variable  0Maxterm designation: for function f(x,y,z) the input combination 000 represents maxterm (x + y + z) and is designated M0.Example: Show all 8 possible maxterms and the shorthand designations for f(x, y, z).Key Point: A Boolean function F may be represented by a product (ANDed together) of its maxterms. They represent the input combinations needed to yield F = 0. So maxterms represent the 0’s in the truth table for F.F (max terms) Lecture #3 EGR 270 – Fundamentals of Computer Engineering5Relationship between minterms and maxtermsShow that and Example: Pick a truth table for some function f(x,y,z) and represent f as a product of maxterms.i im M i iM m Lecture #3 EGR 270 – Fundamentals of Computer Engineering6Conversion between formsSince minterms represent where F = 1 and maxterms represent where F = 0, all terms are either minterms or maxterms. So if F is expressed as a sum of minterms, then F is a product of the maxterms (the terms that were not minterms). So it is simple to convert between forms.Example: Convert to the other canonical form 1. F(A, B) = (0, 1) 2. F(x, y, z) = (0, 1) 3. F(x, y, z) = (4, 5, 6) 4. F(a, b, c, d, e) = (0-4, 8, 13-18)Lecture #3 EGR 270 – Fundamentals of Computer Engineering7Conversion to sum of minterms or product of maxterms forms from other formsPossible approaches include Boolean algebra and truth tables.Example: Represent each function below as a sum of minterms:1. F(A, B) = A2. F(x, y, z) = xy + zExamples: Represent each function below as a product of maxterms:1. F(A, B) = A’B + AB’2. F(x, y, z) = x’ + y’Lecture #3 EGR 270 – Fundamentals of Computer Engineering8Standard FormsCanonical forms are not minimized and are not useful for many circuit implementations.Standard forms are more useful. Functions are typically minimized into one of the two standard forms:1. Sum of Products (SOP) : F = sum of ANDed terms (but not necessarily minterms)2. Product of Sums (POS) : F = product of ORed terms (but not necessarily maxterms)Example: List several examples of SOP expressions.Function SOP ? Sum of minterms?Example: List several examples of POS expressions.Function POS ? Product of maxterms?Lecture #3 EGR 270 – Fundamentals of Computer Engineering9Example: Function F(A,B,C) has the following truth table. Express F in each of the following forms:1. Sum of minterms2. Product of maxterms3. Minimal SOP4. Minimal POSLecture #3 EGR 270 – Fundamentals of Computer Engineering10Standard Forms: 2-Level ImplementationsStandard forms are referred to as “2-level implementations” because they can be implemented with two levels gates (and thus only two gate delays). Note that this does not include initial inverters. Example: Implement a SOP expression using logic gates to illustrate that it is a 2-level implementation.Example: Implement a POS expression using logic gates to illustrate that it is a 2-level implementation.Lecture #3 EGR 270 – Fundamentals of Computer Engineering11Non-standard forms:4 commonly used forms have been covered (sum of minterms, product of maxterms, SOP, and POS). These forms will be used commonly throughout the course. There are, however, other forms. Example: List examples of non-standard expressions and implement at least one of them using logic gates.Lecture #3 EGR 270 – Fundamentals of Computer Engineering12Basic functions/gates and their truth tables:We have previously defined two functions with two or more inputs: AND and OR.How many possible 2-input logic functions could be defined (consider the diagram shown below)?How many correspond to actual gates (commercially available)?List possible truth tables:Inputs: A B F (Output) Logic Gate 6 commonly defined 2-input logic functions/gates: 1. AND 4. NOR2. OR 5. XOR (Exclusive-OR)3. NAND 6. XNOR (Exclusive-NOR or Equivalence)Lecture #3 EGR 270 – Fundamentals of Computer Engineering13NAND: Show logic symbol, truth table, and logic expressions:NOR: Show logic symbol, truth table, and logic expressions:Lecture #3 EGR 270 – Fundamentals of Computer Engineering14XOR: Show logic symbol, truth table, and logic expressions:XNOR: Show logic symbol, truth table, and logic expressions:Lecture #3 EGR 270 – Fundamentals of Computer Engineering15Other Logic Symbols:Lecture #3 EGR 270 – Fundamentals of Computer