ECE 331 Digital System Design Standard Forms for Boolean Expressions (Lecture #4) Standard Forms for Boolean Expressions Sum-of-Products (SOP) Derived from the Truth table for a function by considering those rows for which F = 1.

The logical sum (OR) of product (AND) terms. Realized using an AND-OR circuit. Product-of-Sums (POS) Derived from the Truth table for a function by considering those rows for which F = 0.

The logical product (AND) of sum (OR) terms. Realized using an OR-AND circuit. ECE 301 - Digital Electronics 2 In Mathematical Terms Disjunctive Normal Form (DNF)

Literals within each term are ANDed Terms are Ored Analogous to Sum-of-Products (SOP) Conjunctive Normal Form (CNF) Literals within each term are Ored

Terms are ANDed Analogous to Product-of-Sums (POS) ECE 301 - Digital Electronics 3 Sum-of-Products (SOP) ECE 301 - Digital Electronics 4 Minterms

A minterm, for a function of n variables, is a product term in which each of the n variables appears once. Each variable in the minterm may appear in its complemented or uncomplemented form. For a given row in the Truth table, the corresponding minterm is formed by For all n variables in the function F.

Including variable xi, if xi = 1 Including the complement of xi, if xi = 0 ECE 301 - Digital Electronics 5 Minterms ECE 301 - Digital Electronics 6 Sum-of-Products

Any function F can be represented by a sum of minterms, where each minterm is ANDed with the corresponding value of the output for F. F = (mi . fi) Denotes the logical sum operation where mi is a minterm

and fi is the corresponding functional output Only the minterms for which fi = 1 appear in the expression for function F. F = (mi) = m(i) ECE 301 - Digital Electronics shorthand notation 7

Sum-of-Products The Canonical Sum-of-Products for function F is the Sum-of-Products expression in which each product term is a minterm. The expression is unique However, it is not necessarily the lowest-cost

Synthesis process Determine the Canonical Sum-of-Products Use Boolean Algebra (and K-maps) to find an optimal, functionally equivalent, expression. ECE 301 - Digital Electronics 8 Sum-of-Products AND sum

Y' + X'YZ' + XY X.Y AND OR product term Product Term = Logical ANDing of literals Sum = Logical ORing of product terms ECE 301 - Digital Electronics 9

Sum-of-Products Use the Distributive Laws to multiply out a Boolean expression. Results in the Sum-of-Products (SOP) form. F = (A + B).(C + D).(E) F = (A.C + A.D + B.C + B.D).(E) F = A.C.E + A.D.E + B.C.E + B.D.E not in SOP form Product terms are of single variables

H = A.B.(C + D) + ABE ECE 301 - Digital Electronics 10 Product-of-Sums (POS) ECE 301 - Digital Electronics 11 Maxterms

A Maxterm, for a function of n variables, is a sum term in which each of the n variables appears once. Each variable in the Maxterm may appear in its complemented or uncomplemented form. For a given row in the Truth table, the corresponding Maxterm is formed by Including the variable xi, if xi = 0 Including the complement of xi, if xi = 1 ECE 301 - Digital Electronics

12 Maxterms ECE 301 - Digital Electronics 13 Product-of-Sums Any function F can be represented by a product of Maxterms, where each Maxterm is ANDed with the complement of the corresponding value of the output for F.

F = (Mi . f 'i) Denotes the logical product operation where Mi is a Maxterm and f 'i is the complement of the corresponding functional output

Only the Maxterms for which fi = 0 appear in the expression for function F. F = (Mi) = M(i) ECE 301 - Digital Electronics shorthand notation 14 Product-of-Sums The Canonical Product-of-Sums for function F is the Product-of-Sums expression in which

each sum term is a Maxterm. The expression is unique However, it is not necessarily the lowest-cost Synthesis process Determine the Canonical Product-of-Sums Use Boolean Algebra (and K-maps) to find an

optimal, functionally equivalent, expression. ECE 301 - Digital Electronics 15 Product-of-Sums OR product term X.(Y' + Z).(X' + Y + Z) X' + Y + Z AND sum term

OR Sum Term = Logical ORing of variables Product = Logical ANDing of sum terms ECE 301 - Digital Electronics 16 Product-of-Sums Use the Distributive Laws to factor a Boolean expression. Results in the Product-of-Sums (POS) form. F = V.W.Y + V.W.Z + V.X.Y + V.X.Z F = (V).(W.Y + W.Z + X.Y + X.Z)

F = (V).(W + X).(Y + Z) not in POS form Sum terms are of single variables H = (A+B).(C+D+E) + CE ECE 301 - Digital Electronics 17 SOP and POS

Any function F may be implemented as either a Sumof-Products (SOP) expression or a Product-of-Sums (POS) expression. Both forms of the function F can be realized using logic gates that implement the basic logic operations. However, the two logic circuits realized for the function F do not necessarily have the same cost. Objective: minimize the cost of the designed circuit Compare the cost of the SOP realization with that of the POS realization ECE 301 - Digital Electronics

18 Converting between SOP and POS The sum-of-products (SOP) form of a Boolean expression can be converted to its corresponding product-of-sums (POS) form by factoring the Boolean expression. The product-of-sums (POS) form of a Boolean expression can be converted to its corresponding sum-of-products (SOP) form by multiplying out the Boolean expression. ECE 301 - Digital Electronics

19 Dual The dual of a Boolean expression is formed by changing AND to OR, OR to AND, 0 to 1, and 1 to 0. Alternately, it can be determined by complementing the entire Boolean expression, and then complementing each of the literals. The SOP and POS are duals of one another.

ECE 301 - Digital Electronics 20 Logic Circuit Implementations ECE 301 - Digital Electronics 21 Student Exercise: Draw the AND-OR circuits for the following Sum-of-Products (SOP) expressions: 1. F1 = A'B + AC' + B'C 2. F2 = ABD + BCD' + AB'C' + B'CD ECE 301 - Digital Electronics

22 Student Exercise: Draw the OR-AND circuits for the following Product-of-Sums (POS) expressions: 1. F1 = (A+B').(A'+C).(B+C') 2. F2 = (A+B+D).(B'+C+D').(A'+B+C).(B+C'+D) ECE 301 - Digital Electronics 23 Summary of Logic Functions ECE 301 - Digital Electronics

24 ECE 301 - Digital Electronics 25 Representing Logic Levels (using voltages) ECE 301 - Digital Electronics 26 Signal Levels and Logic Levels ECE 301 - Digital Electronics

27 Signal Levels and Logic Levels ECE 301 - Digital Electronics 28 Signal Levels in Logic Gates ECE 301 - Digital Electronics 29