Boolean Functions Lecture 5 PDF

Boolean functions Lecture 5 Canonical and standard forms Lecture 5 Prof. Neamat Abdelkader 1  Overview – Canonical F...

Boolean functions Lecture 5 Canonical and standard forms Lecture 5 Prof. Neamat Abdelkader 1  Overview – Canonical Forms ▪ What are Canonical Forms? ▪ Minterms and Maxterms ▪ Index Representation of Minterms and Maxterms ▪ Sum-of-Minterm (SOM) Representations ▪ Product-of-Maxterm (POM) Representations ▪ Representation of Complements of Functions ▪ Conversions between Representations 2 Lecture 5 Prof. Neamat Abdelkader  Example of Algebraic Simplification of Boolean Functions Simplify the function: f(x, y, z)= (x’y’+ z)’+(x z+x y)’ Solution: F= (x+ y) z’+ (x’+z’)(x’+y’) = xz’+yz’+x’. x’+ x’y’+ x’z’ + y’z’ = z’(x+y+x’+y’) + x’ =z’(1+ 1) +x’ = x’ + z’ 3 Lecture 5 Prof. Neamat Abdelkader  Canonical Forms ▪ It is useful to specify Boolean functions in a form that: Allows comparison for equality. Has a correspondence to the truth tables ▪ Canonical Forms in common usage: Sum of Minterms (SOM) Product of Maxterms (POM) 4 Lecture 5 Prof. Neamat Abdelkader  Minterms ▪ Minterms are AND terms with every variable presents in either complemented or uncomplemented form such that its value equals 1 for certain input and equals 0 for all other inputs. ▪ Given that each binary variable may appear normal (e.g., x) or complemented (e.g., x’ ), there are 2n minterms for n variables. ▪ Example: Two variables (X and Y)produce 2 x 2 = 4 combinations: (both normal), (X normal, Y complemented), (X complemented, Y normal), (both complemented) ▪ Thus there are four minterms of two variables. 5 Lecture 5 Prof. Neamat Abdelkader  Maxterms ▪ Maxterms are OR terms with every variable in complemented or uncomplemented form such that its value equals 0 for certain input and equals 1 for all other inputs.. ▪ Given that each binary variable may appear normal (e.g., x) or complemented (e.g., x’),then there are 2n maxterms for n variables. ▪ Example: Two variables (X and Y) produce 2 x 2 = 4 combinations: (both normal), (x normal, y complemented), (x complemented, y normal), (both complemented) 6 Lecture 5 Prof. Neamat Abdelkader  Minterms and Maxterms ▪ Examples: minterms and maxterms of two variables (x, y). X Y Minterm Maxterm 0 0 (m0) X’ Y’ (M0) X+Y 0 1 (m1) X’ Y (M1) X+Y’ 1 0 (m2) X Y’ (M2) X’+Y 1 1 (m3) X Y (M3) X’+Y’ ▪ The index above is important for describing which variables in the terms are complemented and which are uncomplemented. 7 Lecture 5 Prof. Neamat Abdelkader  Purpose of the Index ▪ The index for the minterm or maxterm, expressed as a binary number, is used to determine whether the variable is shown in the complemented form or uncomplemented form. ▪ For Minterms: “1” means the variable is “uncomplemented” and “0” means the variable is “Complemented”. ▪ For Maxterms: “0” means the variable is “ uncomplemented” and “1” means the variable is “Complemented”. 8 Lecture 5 Prof. Neamat Abdelkader  Minterms and Maxterms (cont.) ▪ Minterms and maxterms are designated with a subscript , corresponding to the decimal value of the corresponding binary pattern. ▪ All variables will be present in a minterm or maxterm and will be listed in the same order (usually alphabetically) ▪ Example: For variables a, b, c: Minterms: a b c, a b’ c, a b’ c’ denoted m7, m5, m4 Terms: (a c), b c are not minterms, do not contain all variables Maxterms: (a + b + c), (a’ + b + c) denoted (M0, M4) Terms: (b + a), a c b, and (c + b) are not maxterms. 9 Lecture 5 Prof. Neamat Abdelkader  Minterms and maxterms of three variables (x, y, z) x y z minterms maxterms 0 0 0 x’y’z’ (m0) x + y+ z (M0) 0 0 1 x’y’z (m1) x + y+ z’ (M1) 0 1 0 x’yz’ (m2) x + y’+ z (M2) 0 1 1 x’yz (m3) x + y’+ z’ (M3) 1 0 0 xy’z’ (m4) x’ + y+ z (M4) 1 0 1 xy’z (m5) x’ + y+ z’ (M5) 1 1 0 xyz’ (m6) x’ + y’+ z (M6) 1 1 1 xyz (m7) x’ + y’+ z’ (M7) 10 Lecture 5 Prof. Neamat Abdelkader  Index Examples – Four Variables Index Binary Minterm Maxterm i Pattern mi Mi 0 0000 a’b’c’d’ 1 0001 a’b’c’d a + b + c + d’ 3 0011 5 0101 7 0111 10 1010 ab’cd’ a’+ b + c’+ d 13 1101 15 1111 abcd a’+ b’+ c’+ d’ 11 Lecture 5 Prof. Neamat Abdelkader  Minterm and Maxterm Relationship Review: DeMorgan's Theorem (x. y)’= x’+y’ and (x +y)’ = x’. y’ Two variable examples, for x=1, y= 0, M2= x’+y and m2= x.y’ Thus M2 is the complement of m2 and vice- versa. ▪ Since DeMorgan's Theorem holds for n variables, the above holds for terms of n variables Thus: (mi )’ = Mi 12 Lecture 5 Prof. Neamat Abdelkader  Function Tables for minterms and maxterms ▪ Minterms of Maxterms of 2 variables 2 variables xy m0 m1 m2 m3 x y M0 M1 M2 M3 00 1 0 0 0 00 0 1 1 1 01 0 1 0 0 01 1 0 1 1 10 0 0 1 0 10 1 1 0 1 11 0 0 0 1 11 1 1 1 0 ▪ Each column in the maxterm function table is the complement of the column in the minterm function table since Mi is the complement of mi. 13 Lecture 5 Prof. Neamat Abdelkader  Impelementig functions by minterems and maxterms ▪ In the function tables: Each minterm has one and only one 1 present in the 2n terms corresponding to certain input. All other entries are 0. Each maxterm has one and only one 0 present in the 2n terms All other entries are 1 (a maximum of 1s). ▪ We can implement any function by "ORing" the minterms corresponding to "1" entries in the function table. These are called the minterms of the function. ▪ We can implement any function by "ANDing" the maxterms corresponding to "0" entries in the function table. These are called the maxterms of the function. ▪ This gives us two canonical forms: Sum of Minterms (SOM), Product of Maxterms (POM) 14 Lecture 5 Prof. Neamat Abdelkader  Canonical Sum of Minterms Example: Implement f as a sum of minterms. F=xy+x’yz First expand terms : f=xy(z+z’)+x’yz Then distribute terms: f=xyz+ xyz’+ x’yz= m7 + m6 +m3 Expressed as sum of minterms, deriving T.T. f= ∑m 3, 6, 7 x y z f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 m3 1 0 0 0 1 0 1 0 1 1 0 1 m6 1 1 1 1 m7 15 Lecture 5 Prof. Neamat Abdelkader  Minterm Function Example x y z F1 F2 Minterm example 0 0 0 0 1 0 0 1 1 1 F1(x, y, z)= m1+m3+m7 0 1 0 0 0 F1=X’y’z+ x’yz+ xyz 0 1 1 1 1 1 0 0 0 0 F2(x, y, z) = m0+m1+m3+ m5+m7 1 0 1 0 1 They can be written also 1 1 0 0 0 F1=∑m1,3, 7 1 1 1 1 1 F2=∑m0,1, 3, 5, 7 16 Lecture 5 Prof. Neamat Abdelkader  Another SOM Example From the previous example, we started with: F = A + B C=A(B+B’)(C+C’)+B’C(A+A’) =(AB+AB’)(C+C’)+AB’C+A’B’C=ABC+ABC’+AB’C+AB’C’ +AB’C+A’B’C We ended up with: F = m1+m4+m5+m6+m7, This can be denoted in the formal shorthand: F ( A, B, C ) = m(1,4,5,6,7) Note that we explicitly show the standard variables in order and drop the “m” designators. 17 Lecture 5 Prof. Neamat Abdelkader  Canonical Product of Maxterms Any Boolean Function can be expressed as a Product of Maxterms (POM). For the function table, the maxterms used are the terms – corresponding to the 0's of the function in T.T. For an expression, expand all terms first to explicitly list all – maxterms. Do this by “ORing” terms missing variable v with a term equal to v.v’, and then applying the distributive law. Example: Convert to product of maxterms: – Apply the distributive law: F= x+x’y’ = (x+x’)(x+y’) =x+y’ Add missing variable z: F= x+y’+z.z’= (x+y’+z)(x+y’+z’) Express as POM: f = M2 · M3= ∏M 2,3 18 Lecture 5 Prof. Neamat Abdelkader  Function as POM from Complements of minterms The complement of a function expressed as a sum of minterms is constructed by selecting the minterms missing in the sum-of-minterms canonical forms. Alternatively, the complement of a function expressed by a Sum of Minterms form is simply the Product of Maxterms with the same indices. Example: Given F ( x , y , z ) =  m ( 1 , 3 , 6 , 7 ), F’=∑m 0, 2,4, 5 F =(F’)’=(∑m 0, 2,4, 5)’ = ∏M (0,2,4,5) 19 Lecture 5 Prof. Neamat Abdelkader  Conversion Between Forms The complement of a function expressed as the sum of minterms missing from the original function. This is because the original function is expressed by those minterms which make the function equals to 1, whereas its complement has the value “1” for those minterms of which the function has the value “0”. To convert between sum-of-minterms and product-of- maxterms form (or vice-versa) we follow these steps: Find the minterms related to the 1’s of the function. – Represent function as SOM. Get the maxterms not listed in the SOM expression, – then represent the function as POM and vice versa. 20 Lecture 5 Prof. Neamat Abdelkader  Example: Given F as before: F( x, y, z) = m(1, 3,5,7) Form the Complement: F ( x , y , z ) = m( 0, 2,4,6) Then use the other form with the same indices – then, F( x, y, z ) = M(0, 2,4,6) forms the complement again, giving the other form of the original function: 21 Lecture 5 Prof. Neamat Abdelkader 22 Lecture 5 Prof. Neamat Abdelkader  Standard Forms Standard Sum-of-Products (SOP) form: equations are written as an OR of AND terms Standard Product-of-Sums (POS) form: equations are written as an AND of OR terms Examples: SOP F1=AB+AC’B+ A’B’ POS: F2 = (A’+B’)( A+B+C’) The following “mixed” form is neither SOP nor POS F3=AB+C(BC’+A’C’ )+A’(B+C) nonstandard form 23 Lecture 5 Prof. Neamat Abdelkader  Standard Sum-of-Products (SOP) A Simplification Example: F( A, B, C) = m(1,4,5,6,7) Writing the minterm expression: F = A’ B’ C + A B’ C’ + A B’ C + ABC’ + ABC Simplifying: F=A’B’C+AB’ (C’+C)+AB(C’+C) F=A’B’C+AB’+AB=A’B’C+A=(A’+A)(B’+A)(A+C) F=(A+C)(A+B’)=A+AB’+AC+B’C=A+B’C (SOP) Simplified F contains three literals compared to five minterm. (each term has 3 literals) 24 Lecture 5 Prof. Neamat Abdelkader  AND/OR Two-level Implementation of SOP Expression The two implementations for F are shown below – it is quite apparent which is simpler! A B C A A F B B C A C B F C A B C A B C 25 Lecture 5 Prof. Neamat Abdelkader  Standard Form Implementation The logic diagram of a sum‐of‐products expression consists of a group of AND gates followed by a single OR gate. This configuration pattern is shown in the figure below. Each product term requires an AND gate, except for a term with a single literal. The logic sum is formed with an OR gate whose inputs are the outputs of the AND gates and the single literal. It is assumed that the input variables are directly available and their complements, so inverters are not included in the diagram. This circuit configuration is referred to as a two‐level implementation. SOP (two level AND- OR) The logic diagram of a product- of -sum consists of a group of OR gates followed by a single AND gate. Each sum term requires an OR gate, except for a term with a single literal. The logic product is formed with an AND gate whose inputs are the outputs of the OR gates POS (two level OR- AND) 26 Lecture 5 Prof. Neamat Abdelkader  Non standard forms Three level implementation F3(A, B, C)= AB+ C(D+E) , f3 is nonstandard form function and can be implemented by three level implementation. Canonical form can be simplified to standard form. Non standard forms can be also simplified to standard form and to canonical form. 27 Lecture 5 Prof. Neamat Abdelkader  Implementation of canonical and standard forms SOM and SOP can be implemented as two level AND- OR gates Ex: F1= y’ + x’ y z’ + x y (SOP) POM and POS can be implemented as two level OR – AND gates Ex: F2= x ( y’+ z) (x’ + y + z) (POS) 28 Lecture 5 Prof. Neamat Abdelkader 29 Lecture 5 Prof. Neamat Abdelkader  Three and two level implementation F3(x, y, z)= AB+ C(D+E) , f3 is nonstandard form function. 30 Lecture 5 Prof. Neamat Abdelkader  SOP and POS Observations From the above examples: Canonical Forms (Sum-of-minterms, Product-of- – Maxterms), or other standard forms (SOP, POS) differ in complexity Boolean algebra can be used to manipulate equations – into simpler forms. Simpler equations lead to simpler two-level – implementations Questions: How can we attain a “simplest” expression? – Is there only one minimum cost circuit? – The next part will deal with these issues. – 31 Lecture 5 Prof. Neamat Abdelkader