Lecture 3 EGR 270 Fundamentals of Computer Engineering Reading Assignment Chapter 2 in Logic and Computer Design Fundamentals 4th Edition by Mano Complement of a Function A function F has the exact opposite truth table as function F Example Find truth table for F and for F for the function below F x y z x y Canonical and Standard forms Boolean functions are commonly expressed using the following forms Canonical forms Sum of minterms Product of maxterms Standard forms Sum of products Product of sums 1 Lecture 3 EGR 270 Fundamentals of Computer Engineering Minterm also called a standard product A minterm is a term containing all n variables complemented or uncomplemented ANDed together Example f A B has 4 possible minterms List them Each minterm represents one n bit word where Primed variable 0 Unprimed variable 1 Minterm 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 2 Lecture 3 EGR 270 Fundamentals of Computer Engineering 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 F minterms Example Pick a truth table for some function f x y z and represent f as a sum of minterms Maxterm also called a standard sum A maxterm is a term containing all n variables complemented or uncomplemented ORed together Example f A B has 4 possible maxterms List them 3 Lecture 3 EGR 270 Fundamentals of Computer Engineering Each maxterm represents one n bit word where Primed variable 1 note that this is opposite of the notation used for minterms Unprimed variable 0 Maxterm 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 4 Lecture 3 EGR 270 Fundamentals of Computer Engineering Example Pick a truth table for some function f x y z and represent f as a product of maxterms Relationship between minterms and maxterms Show that and mi M i Mi m i 5 Lecture 3 EGR 270 Fundamentals of Computer Engineering Conversion between forms Since 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 6 Lecture 3 EGR 270 Fundamentals of Computer Engineering Conversion to sum of minterms or product of maxterms forms from other forms Possible approaches include Boolean algebra and truth tables Example Represent each function below as a sum of minterms 1 F A B A 2 F x y z xy z Examples Represent each function below as a product of maxterms 1 F A B A B AB 2 F x y z x y 7 Lecture 3 EGR 270 Fundamentals of Computer Engineering Standard Forms Canonical 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 8 Lecture 3 EGR 270 Fundamentals of Computer Engineering Example Function F A B C has the following truth table Express F in each of the following forms 1 Sum of minterms 2 Product of maxterms 3 Minimal SOP 4 Minimal POS 9 Lecture 3 EGR 270 Fundamentals of Computer Engineering Standard Forms 2 Level Implementations Standard 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 2level implementation Example Implement a POS expression using logic gates to illustrate that it is a 2level implementation 10 Lecture 3 EGR 270 Fundamentals of Computer Engineering Non 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 11 Lecture 3 EGR 270 Fundamentals of Computer Engineering Basic 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 Inputs A B Logic Gate F Output List possible truth tables 6 commonly defined 2 input logic functions gates 1 AND 4 NOR 2 OR 5 XOR Exclusive OR 3 NAND 6 XNOR Exclusive NOR or Equivalence 12 Lecture 3 EGR 270 Fundamentals of Computer Engineering NAND Show logic symbol truth table and logic expressions NOR Show logic symbol truth table and logic expressions 13 Lecture 3 EGR 270 Fundamentals of Computer Engineering XOR Show logic symbol truth table and logic expressions XNOR Show logic symbol truth table and logic expressions 14 Lecture 3 EGR 270 Fundamentals of Computer Engineering Other Logic Symbols 15