L9: Product of Sums & Sum of Products

Let’s practice Boolean algebra!

Objective
Practice usage of theorems 5-17 of Boolean algebra.

Additional Materials & Formats
Check Box for the most up-to-date versions of this lecture’s materials.

Before the Lecture

Required Textbook Reading:

• 2.6.1 (Sum-of-Products and Product-of-Sums Forms)

Optional Supplemental Instruction:

• Neso Academy videos:
  • Sum of Products (SOP) Form - Part 1
  • Sum of Products (SOP) Form - Part 2
  • Product of Sums (POS) - Part 1
  • Product of Sums (POS) - Part 2
  • SOP and POS Form Examples
• Boolean Function Representation: SOP and POS Form | Minterms and Maxterms Explained – All About Electronics on YouTube

Circuit Synthesis

We want to convert our truth tables into logical formulas, and we want to convert those logical formulas into a format that is easy to synthesize as logic gates. One way to do that is by writing in Product-of-Sums (PoS) or Sum-of-Products (SoP) form.

Minterms and Maxterms

Minterms and maxterms are building blocks used to write Boolean functions directly from a truth table.

• A minterm is a product (AND) that includes every variable exactly once; for a given input combination, include a variable uncomplemented when that variable is 1 and complemented when it is 0. Each minterm is true for only the single input combination that matches it.
• A maxterm is a sum (OR) that includes every variable exactly once; for a given input combination, include a variable uncomplemented when that variable is 0 and complemented when it is 1. Each maxterm is false for only the single input combination that matches it.

Indexing convention used below: treat ($x_1 x_2 x_3$) as a 3-bit binary number with A as the most-significant bit, so index = $4 x_1 + 2 x_2 + 1 x_3$.

Example truth table ($x_1 x_2 x_3$), with the minterm and maxterm for each row:

Sum-of-Products

A Sum-of-Products (SOP) expression is a sum (OR) of one or more product (AND) terms. Each product term can include one or more literals (variables or their complements). SOP is a convenient form for synthesis because each product term maps directly to an AND gate and the outer OR maps to an OR gate.

Canonical SOP (also called the minterm expansion) is a special SOP where every product term is a minterm. Each product contains every variable exactly once (either complemented or uncomplemented). To form the canonical SOP from a truth table:

• List the row indices where the function output = 1.
• For each such row, write the corresponding minterm (use variable for 1, variable’ for 0).
• OR all those minterms together. This is the canonical (full) SOP and is often written using summation notation, e.g. $f(A,B,C) = \sum m(1,3,5)$.

The canonical SOP is guaranteed to represent the function exactly; it can be simplified (Boolean algebra, Karnaugh map, or etc.) to a smaller SOP that may omit some variables in product terms.

Example: SOP with 3 variables

SOP: $f(x_1,x_2,x_3) = \sum m(1,3,5) = \overline{x_1},\overline{x_2},x_3 + \overline{x_1},x_2,x_3 + x_1,\overline{x_2},x_3$.

Product-of-Sums

A Product-of-Sums (POS) expression is a product (AND) of one or more sum (OR) terms. Each sum term can include one or more literals (variables or their complements). POS is convenient for synthesis because each sum term maps to an OR gate and the outer product maps to an AND gate.

Canonical POS (also called the maxterm expansion) is a special POS where every sum term is a maxterm. Each maxterm contains every variable exactly once (either uncomplemented or complemented). To form the canonical POS from a truth table:

• List the row indices where the function output = 0.
• For each such row, write the corresponding maxterm (use a variable uncomplemented when that variable is 0 in the row, and complemented when it is 1).
• AND all those maxterms together. This is the canonical (full) POS and is often written using product notation, e.g. $f(A,B,C) = \prod M(0,2,4)$.

The canonical POS exactly represents the function; it can be simplified (Boolean algebra, Karnaugh map, etc.) to a smaller POS that may omit some variables in sum terms.

Example: POS with 3 variables

Using the same function as the SOP example (where $f=1$ at indices 1, 3, 5), the zeros occur at indices 0, 2, 4, 6, 7. We thus calculate the maxterms at those indices:

The canonical POS is the product of the corresponding maxterms:

$f(x_1,x_2,x_3) = Π M(0,2,4,6,7) \newline = (x_1 + x_2 + x_3) (x_1 + \overline{x_2} + x_3) (\overline{x_1} + x_2 + x_3) (\overline{x_1} + \overline{x_2} + x_3) (\overline{x_1} + \overline{x_2} + \overline{x_3}) $

As with SOP, this canonical POS can be simplified using Boolean algebra or Karnaugh maps to get a more compact POS suitable for implementation.

Quick Cheat Sheet

• Minterm (canonical product term): an AND of every variable, where each variable appears uncomplemented if it is 1 in a particular input row, and complemented if it is 0. A minterm is 1 for exactly one input combination.

• Maxterm (canonical sum term): an OR of every variable, where each variable appears uncomplemented if it is 0 in a particular input row, and complemented if it is 1. A maxterm is 0 for exactly one input combination.

• Sum of Products (SOP): OR of minterms (canonical SOP uses every minterm corresponding to output = 1). Canonical SOP contains every variable in each product term.

• Product of Sums (POS): AND of maxterms (canonical POS uses every maxterm corresponding to output = 0). Canonical POS contains every variable in each sum term.

Quick conversion method:

1. From a truth table, list the row indices where output = 1 (for SOP) or = 0 (for POS).
2. Write the canonical minterm for each 1 row (use variable for 1, variable’ for 0) and OR them.
3. Or write the canonical maxterm for each 0 row (use variable for 0, variable’ for 1) and AND them.
4. Optionally simplify the canonical form using Boolean algebra or Karnaugh maps.