Boolean Function Forms

Canonical forms and Standard forms in Digital Electronics

1. Canonical forms and Standard forms

2. Duality principle If the binary operators and the identity elements are interchanged , it is called the duality principle. Switching algebra. Two –valued Boolean algebra called Switching algebra.

3. Difference between Boolean function and Boolean Expression Boolean algebra deals with binary variables and logic operation. A  Boolean Function  is described by an algebraic expression called  Boolean expression  which consists of binary variables, the constants 0 and 1, and the logic operation symbols. Consider the following example.

4. Difference Between Canonical Form and Standard Form Canonical forms are not usually minimal . Minimization of Boolean expression is needed to simplify the Boolean expression and thus reduce the circuitry complexity as it uses less number of gates to produce same output that can by taken by long canonical expression. Eg : X’Y’Z’ + X’Y’Z + X’YZ’ In contrast, Standard form is a simplified version of Canonical form. NOTE Canonical SOP (Sum of Minterms) and POS (Product of Maxterm) is the derivation/expansion of Boolean Expression.

5. Forms (NOT Unique) Standard forms are “ like” canonical forms, except that not all variables need appear in the individual product (SOP) or sum (POS) terms. Example: f 1 ( a,b,c ) = a’b’c + bc ’ + ac’ is a standard sum-of-products form f 1 ( a,b,c ) = ( a+b+c )•( b’+c ’)•( a’+c ’) is a standard product-of-sums form. 2019/12/19 Boolean Algebra PJF - 5

6. Minterm and Maxterm A minterm is a product (AND) of all variables in the function, in direct or complemented form. (Standard product) X’Y’Z’ , X’Y’Z , X’YZ’ A maxterm is a sum (OR) of all the variables in the function, in direct or complemented form. (Standard sum) X’+Y’+Z’ , X’+Y’+Z , X’+Y+Z’

7. Minterms & Maxterms for 2 variables (Derivation of Boolean function from Truth Table) x y Index Minterm Maxterm m = x’ y’ M = x + y 1 1 m 1 = x’ y M 1 = x + y’ 1 2 m 2 = x y’ M 2 = x’ + y 1 1 3 m 3 = x y M 3 = x’ + y’ The minterm m i should evaluate to 1 for each combination of x and y. (1) The maxterm is the complement of the minterm (0)

8. Purpose of the Index Minterms and Maxterms are designated with an index The index number corresponds to a binary pattern The index for the minterm or maxterm, expressed as a binary number, is used to determine whether the variable is shown in the true or complemented form For Minterms: ‘1’ means the variable is “Not Complemented” and ‘0’ means the variable is “Complemented”. For Maxterms: ‘0’ means the variable is “Not Complemented” and ‘1’ means the variable is “Complemented”.

9. Boolean Function Expression form Standard Form Sum of Product Product of Sum Canonical Form Sum of Minterms Sum of Maxterms

10. Standard Forms Boolean functions can generally be expressed in the form of a Sum of Products (SOP) or in the form of a Product of Sums (POS). The SOP and POS forms are Standard forms for representing Boolean functions.

11. Sum of Products Expressions (SOP) Any SOP expression can be implemented in 2-levels of gates. The first level consists of a number of AND gates which equals the number of product terms in the expression. Each AND gate implements one of the product terms in the expression. The second level consists of a SINGLE OR gate whose number of inputs equals the number of product terms in the expression. Two-Level Implementations of Standard Forms

12. Example : Implement the following SOP function F = XZ + Y`Z + X`YZ

13. Product of Sums Expression (POS) Any POS expression can be implemented in 2-levels of gates. The first level consists of a number of OR gates which equals the number of sum terms in the expression. Each gate implements one of the sum terms in the expression. The second level consists of a AND gate whose number of inputs equals the number of sum terms.

14. Example : Implement the following POS function F = (X+Z )(Y`+Z)(X`+Y+Z )

15. Canonical form Sum of Minterm X’Y’Z’ + X’Y’Z + X’YZ’ Product of Maxterm (X’+Y’+Z’ )(X’+Y’+Z) ( X’+Y+Z’)

16. Canonical forms -Definition Boolean function that is expressed as a sum of minterms or as a product of maxterms is said to be in its “ canonical form”. It mainly involves in two Boolean terms, “minterms” and “maxterms”.

17. Shorthand: ∑ and ∏ f 1 ( a,b,c ) = ∑ m (1,2,4,6), where ∑ indicates that this is a sum-of-products form, and m(1,2,4,6) indicates that the minterms to be included are m 1 , m 2 , m 4 , and m 6 . f 1 ( a,b,c ) = ∏ M(0,3,5,7), where ∏ indicates that this is a product-of-sums form, and M(0,3,5,7) indicates that the maxterms to be included are M , M 3 , M 5 , and M 7 . Since m j = M j ’ for any j , ∑ m(1,2,4,6) = ∏ M(0,3,5,7) = f 1 ( a,b,c ) 2019/12/19 Boolean Algebra PJF - 17

18. Definitions Literal: variable Product term: literals connected by • Sum term: literals connected by + Minterm : a product term in which all the variables appear exactly once, either complemented or uncomplemented Maxterm : a sum term in which all the variables appear exactly once, either complemented or uncomplemented 2019/12/19 Boolean Algebra PJF - 19

19. Minimization of Boolean Expression (Contd…) Two method can by applied to reduce the Boolean expression – Algebraic Using Karnaugh Map (K-Map).

20. Minimization of Boolean Expression ( Contd…) Algebraic Method - The different Boolean rules and theorems are used to simplify the Boolean expression in this method.