2.2 Sum of products and product of sums

Why this matters

A truth table says what a circuit must do, but you cannot build from a table directly. Sum of products and product of sums are two mechanical recipes that turn any table into an expression, and so into a circuit, with no cleverness required. They always work, and they are the starting point that every minimization technique improves on.

Learning goals

Write a sum of products from the rows of a truth table where the output is 1.
Write a product of sums from the rows where the output is 0, with every literal in the right polarity.
Convert between the two forms with DeMorgan's law.
Choose the form that needs fewer terms for a given table.
Explain why a canonical form is correct but usually not minimal.

Intuition first

Suppose you must describe an alarm that sounds on some combinations of switches and stays quiet on the others. There are two honest ways to say it. You can list the combinations that sound the alarm: "it rings if the switches are like this, or like this, or like this". Or you can list the combinations that keep it quiet and say "it rings unless the switches are like this, or like this". The first is a sum of products and the second is a product of sums.

Each listed combination needs a test that fires on that combination and no other. For a combination of switches, the test "every switch is the way this row says" is a product: it is 1 only when all of its literals are 1. A listing of such tests joined by OR is 1 as soon as any one test fires. The second way works with sums: a sum is 0 only when all of its literals are 0, so a sum can be built to be 0 on exactly one row, and joining sums by AND gives a function that is 0 on any of those rows.

If you program, a sum of products is a chain of if (row1) ... else if (row2) ... that returns 1 on a match. The analogy breaks in one way: the products are all evaluated at once, by separate gates, not tried in order.

Definition 2.2.1(product term and sum term).

A product term is a product (an AND) of literals, such as $\overline{A}B$ . A sum term is a sum (an OR) of literals, such as $A+\overline{B}$ . A product term that mentions every input variable once is 1 on exactly one row of the truth table. A sum term that mentions every input variable once is 0 on exactly one row.

Definition 2.2.2(sum of products, product of sums).

A sum of products (SoP) is a sum of product terms. A product of sums (PoS) is a product of sum terms. The lecture points out that a sum of products is the disjunctive normal form (DNF) and a product of sums the conjunctive normal form (CNF) of CSE 311.^{F (fact ch02/cse311-forms)} An SoP or PoS in which every term mentions every variable is called canonical, and then each term corresponds to one row of the table.

Reading off the 1-rows

The recipe for a sum of products has two rules. Write one product term for each row where the output is 1. In that term, write a variable plain if the row has a 1 in its column, and with a bar if the row has a 0, so that the term is 1 exactly on that row. Then OR the terms together.

Example 2.2.1(exclusive-or as a sum of products).

Take the exclusive-or of two inputs, with output C. It is 1 when A and B differ. Figure 2.2.1 marks the two rows where C is 1.

Truth table with 2 inputs (A, B) and output C; 4 rows in ascending binary order, A most significant
A	B	C
0	0	0
0	1	1
1	0	1
1	1	0

Figure 2.2.1. The two rows where C is 1 are marked.

In the row where A is 0 and B is 1, the term must be 1 when A is 0 and B is 1, so it is $\overline{A}B$ . In the row where A is 1 and B is 0 it is $A\overline{B}$ . The sum of products is $\overline{A}B + A\overline{B}$ . As a circuit it is two AND gates, each with one inverted input, feeding an OR gate:

Figure 2.2.2. Exclusive-or as a sum of products.

Because each product term is 1 on one row only, the sum is 1 on exactly the rows you listed and 0 on every other row. That is why the recipe cannot go wrong, provided you copy the bars carefully.

Reading off the 0-rows

The recipe for a product of sums is the mirror image, and the mirror image has one catch. Write one sum term for each row where the output is 0. In that term, a variable is written plain if the row has a 0 and with a bar if the row has a 1, so that every literal in the sum is 0 on that row and the sum is 0 there. Then AND the sums together.

The polarity is the opposite of the sum-of-products rule, because now each literal must be 0, not 1, on its row.

Example 2.2.2(the same function as a product of sums).

In the same table, the rows where C is 0 are the one where A and B are both 0 and the one where both are 1. Figure 2.2.3 marks them.

Truth table with 2 inputs (A, B) and output C; 4 rows in ascending binary order, A most significant
A	B	C
0	0	0
0	1	1
1	0	1
1	1	0

Figure 2.2.3. The two rows where C is 0 are marked.

For the row of two 0s the sum must be 0 when A and B are both 0, so it is $A + B$ . For the row of two 1s it is $\overline{A} + \overline{B}$ , which is 0 only when A and B are both 1. The product of sums is $(A + B) \cdot (\overline{A} + \overline{B})$ .

This expression is C itself. It is not the complement of C, even though we built it from the rows where C is 0. Each sum is 0 on one of those rows, so the product is 0 there, and it is 1 everywhere else. The table below shows C beside the product of sums and the sum of products from the previous example, with all three columns equal.

Truth table with 2 inputs (A, B) and outputs C, SoP, PoS; 4 rows in ascending binary order, A most significant
A	B	C	$\mathrm{SoP}$	$\mathrm{PoS}$
0	0	0	0	0
0	1	1	1	1
1	0	1	1	1
1	1	0	0	0

Figure 2.2.4. The table of C, its sum of products and its product of sums.

Figure 2.2.5. Exclusive-or as a product of sums.

Why the two forms agree

A product of sums for $C$ is the complement of a sum of products for the complement of $C$ . Rows where $C$ is 0 are the 1-rows of $\overline{C}$ , so the sum of products of $\overline{C}$ is $\overline{A}\,\overline{B} + AB$ . DeMorgan's law turns the complement of that into a product of sums, and the double negation law removes the extra bars:

Step-by-step simplification; each line names the law used to get from the line above
Expression	Law used
$\overline{\overline{A}\,\overline{B} + AB}$
$= \overline{\overline{A}\,\overline{B}} \cdot \overline{AB}$	DeMorgan
$= (\overline{\overline{A}} + \overline{\overline{B}}) \cdot (\overline{A} + \overline{B})$	DeMorgan
$= (A + B) \cdot (\overline{A} + \overline{B})$	Double negation

The first line is the complement of $\overline{C}$ 's sum of products, which is $C$ , and the last line is the product of sums we found above. Section 2.4 studies the DeMorgan steps in detail. For now, take the derivation as the reason the polarity rule is what it is.

A table with several terms

The XOR table is symmetric, which hides mistakes: a product of sums with the polarity reversed gives the same answer there. A less symmetric function exposes them.

Example 2.2.3(a function and its complement as a product).

The function Z is 1 on three rows, each with C equal to 1: where A and B are both 0, where A is 0 and B is 1, and where A is 1 and B is 0. Figure 2.2.6 shows them.

Truth table with 3 inputs (A, B, C) and outputs Z, Zbar; 8 rows in ascending binary order, A most significant
A	B	C	Z	$\mathrm{Zbar}$
0	0	0	0	1
0	0	1	1	0
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	0	1
1	1	1	0	1

Figure 2.2.6. Z is 1 on the three marked rows. The column headed Zbar is the complement of Z, which the text writes with an overbar.

The sum of products has three terms: $\overline{A}\,\overline{B}C + \overline{A}BC + A\overline{B}C$ . Now take the complement. Its 0-rows are the three marked rows, so the recipe for a product of sums gives one sum for each marked row. For the row where A, B and C are 0, 0 and 1, the sum is $A + B + \overline{C}$ , with A and B plain because they are 0 on that row and C barred because it is 1. The other two sums follow the same rule, and the complement of Z is $(A + B + \overline{C}) \cdot (A + \overline{B} + \overline{C}) \cdot (\overline{A} + B + \overline{C})$ . The check below shows that this is exactly the complement of the sum of products.

\overline{\overline{A}\,\overline{B}C + \overline{A}BC + A\overline{B}C}

= (A + B + \overline{C}) \cdot (A + \overline{B} + \overline{C}) \cdot (\overline{A} + B + \overline{C})

It is also what DeMorgan's law gives when you complement the three-term sum directly, with each variable's bar flipped.

Which form is shorter

A canonical sum of products has one term for each 1-row and a canonical product of sums has one sum for each 0-row. For $n$ inputs there are $2^n$ rows, so the two counts always add up to $2^n$ . If the table has few 1s, the sum of products is short. If it has few 0s, the product of sums is short.

Example 2.2.4(two 0-rows out of eight).

The function H is 0 on only two rows: where A, B and C are 0, 1 and 1, and where they are 1, 0 and 0.

Truth table with 3 inputs (A, B, C) and outputs H, S, P; 8 rows in ascending binary order, A most significant
A	B	C	H	S	P
0	0	0	1	1	1
0	0	1	1	1	1
0	1	0	1	1	1
0	1	1	0	0	0
1	0	0	0	0	0
1	0	1	1	1	1
1	1	0	1	1	1
1	1	1	1	1	1

Figure 2.2.7. H is 0 on the two marked rows. S is its sum of products and P its product of sums.

The sum of products needs six terms, one for each 1-row: $\overline{A}\,\overline{B}\,\overline{C} +$ $\overline{A}\,\overline{B}C +$ $\overline{A}B\overline{C} +$ $A\overline{B}C +$ $AB\overline{C} +$ $ABC$ . The product of sums needs two sums: $(A + \overline{B} + \overline{C}) \cdot (\overline{A} + B + C)$ . The columns S and P in Figure 2.2.7 are the two forms, and both agree with H on every row.

Two levels of logic

Both forms give a circuit with two levels of gates: a first level that forms the terms, and a second level that combines them. An SoP circuit has an AND level then one OR gate, and a PoS circuit has an OR level then one AND gate, as in the two figures above, with inverters or input bubbles to make the barred literals.

Two-level circuits are easy to read and always possible, but a canonical form is rarely the cheapest. Z, for example, equals $\overline{A}C + \overline{B}C$ , which has two terms of two literals each instead of three terms of three literals. Finding the cheap form is what the next section and Chapter 3 are about.

Course conventions

How CSE 369 writes this

The vocabulary is SoP and PoS, with the "on set" being the rows where the output is 1 and the "off set" the rows where it is 0. NOT is an overbar. A PoS is built from the off set by writing each variable plain where the row has a 0, and a SoP from the on set by writing each variable plain where the row has a 1. Truth-table rows go in ascending binary order with the first-listed input as the most significant bit.

Pitfalls

Common pitfall

Using the sum-of-products polarity in a product of sums. In a sum term, a variable is plain where the row has a 0 and barred where it has a 1. On a symmetric table such as exclusive-or the mistake can go unnoticed, so test your PoS on a row.
Reading a product of sums built from the 0-rows as the complement of the function. Each sum is 0 on a 0-row, so the product is 0 there and equals the function itself.
Using the 1-rows for a product of sums, or the 0-rows for a sum of products. Reading the wrong kind of row with a recipe gives the complement of the function you wanted.
Leaving out a row, or writing a bar on the wrong letter while copying it. Count the terms: a canonical form has one term for each row of the kind you are reading off.
Assuming a canonical form is minimal. It is correct and mechanical, but usually bigger than it has to be.

Check your understanding

Take the quiz (4 questions)

Exercises

Exercise 2.2.1

The function G is 1 exactly when A and B are equal. Write a sum of products and a product of sums for it.

Hint

List the rows where G is 1 for the first, and the rows where G is 0 for the second. Check the polarity rule for each recipe.

Solution

G is 1 on the rows where A and B are both 0 and where they are both 1. Those rows give the terms $\overline{A}\,\overline{B}$ and $AB$ , so the sum of products is $\overline{A}\,\overline{B} + AB$ .

G is 0 on the other two rows, where A and B differ. For the row where A is 0 and B is 1 the sum is $A + \overline{B}$ , plain A because A is 0 and barred B because B is 1. For the row where A is 1 and B is 0 the sum is $\overline{A} + B$ . The product of sums is $(A + \overline{B}) \cdot (\overline{A} + B)$ . Compare it with the product of sums for the exclusive-or: each sum here is the complement of one of the exclusive-or's product terms, because G is 0 exactly where the exclusive-or is 1. The check $\overline{A}\,\overline{B} +$ $AB$ $= (A + \overline{B}) \cdot (\overline{A} + B)$ confirms they are equal.

Truth table with 2 inputs (A, B) and output G; 4 rows in ascending binary order, A most significant
A	B	G
0	0	1
0	1	0
1	0	0
1	1	1

Figure 2.2.8. The table of G with the rows where G is 0 marked.

Tags: Warm-upTruth tablesBoolean algebra

Exercise 2.2.2

A function is 0 when A, B and C are 0, 1 and 1, or 1, 0 and 0, and 1 on every other row. Which form would you use to build it, a sum of products or a product of sums? Write it, and say how many terms the other form would need.

Hint

Count the 0-rows and the 1-rows. Each canonical term corresponds to one row of the kind you are reading off.

Solution

There are two 0-rows and six 1-rows, so the product of sums is much shorter. For the row 011 the sum is $A + \overline{B} + \overline{C}$ , with A plain because it is 0 and B and C barred because they are 1. For the row 100 it is $\overline{A} + B + C$ . The product is $(A + \overline{B} + \overline{C}) \cdot (\overline{A} + B + C)$ , which is the function H of the example. The sum of products would need six terms of three literals each.

Tags: StandardTruth tablesBoolean algebra

Exercise 2.2.3

The function W equals $\overline{A}B + AC$ . Use DeMorgan's law to write the complement of W as a product of sums, one law per line.

Hint

The complement of a sum is the product of the complements. Apply it once to the outer sum, then to each product, then remove double bars.

Solution

Each line follows from the one above it by the named law.

Step-by-step simplification; each line names the law used to get from the line above
Expression	Law used
$\overline{\overline{A}B + AC}$
$= \overline{\overline{A}B} \cdot \overline{AC}$	DeMorgan
$= (\overline{\overline{A}} + \overline{B}) \cdot (\overline{A} + \overline{C})$	DeMorgan
$= (A + \overline{B}) \cdot (\overline{A} + \overline{C})$	Double negation

The answer is $(A + \overline{B}) \cdot (\overline{A} + \overline{C})$ . It is not canonical, because each sum leaves out one variable, but it is a product of sums for the complement of W.

Tags: StandardBoolean algebra

Exercise 2.2.4

The complement of Z from the examples is the canonical product of sums $(A + B + \overline{C}) \cdot (A + \overline{B} + \overline{C}) \cdot (\overline{A} + B + \overline{C})$ . Simplify it step by step to a sum of two terms, naming each law.

Hint

Group the sums that share two of their literals. The OR form of the distributive law pulls a shared part out of two sums.

Solution

The first two sums differ only in B, so they combine first. The result then combines with the third sum. Each line follows from the one above by the law beside it.

Step-by-step simplification; each line names the law used to get from the line above
Expression	Law used
$(A + B + \overline{C}) \cdot (A + \overline{B} + \overline{C}) \cdot (\overline{A} + B + \overline{C})$
$= (A + \overline{C} + B) \cdot (A + \overline{C} + \overline{B}) \cdot (\overline{A} + \overline{C} + B)$	Commutative
$= (A + \overline{C} + B\overline{B}) \cdot (\overline{A} + \overline{C} + B)$	Distributive
$= (A + \overline{C} + 0) \cdot (\overline{A} + \overline{C} + B)$	Complement
$= (A + \overline{C}) \cdot (\overline{A} + \overline{C} + B)$	Identity
$= (\overline{C} + A) \cdot (\overline{C} + \overline{A} + B)$	Commutative
$= \overline{C} + A \cdot (\overline{A} + B)$	Distributive
$= \overline{C} + AB$	Absorption

The result is $\overline{C} + AB$ , a sum of two terms, and the complement of that is Z: $\overline{\overline{C} + AB} = \overline{A}C + \overline{B}C$ .

Tags: ChallengeBoolean algebra