Canonical Forms: Sum of Products and Product of Sums
In the previous articles we manipulated Boolean expressions that were already written down. In this one we go the other way: given a truth table, how do you get an expression at all? There are two mechanical procedures, sum of products (SOP) and product of sums (POS), and these are the canonical forms of Boolean algebra. They are like the expanded form of a polynomial: $x^2 + 3x + 2$ is the standard form, $(x+1)(x+2)$ is the factored one. The canonical form is where you start before you simplify.
Every synthesis tool, every Karnaugh map and every minimisation algorithm starts from one of these forms, so they are worth learning properly.
Minterms
A minterm of $n$ variables is a product (AND) term in which every variable appears exactly once, either complemented or not. There are $2^n$ of them, one per row of the truth table, and each one is 1 for exactly one row and 0 for every other.
For two variables:
| Row | $A$ | $B$ | Minterm | Symbol |
|---|---|---|---|---|
| 0 | 0 | 0 | $A’B'$ | $m_0$ |
| 1 | 0 | 1 | $A’B$ | $m_1$ |
| 2 | 1 | 0 | $AB'$ | $m_2$ |
| 3 | 1 | 1 | $AB$ | $m_3$ |
The rule for building the minterm of a row: where the variable is 1 it appears plain, where it is 0 it appears complemented. The subscript is the row number, which is the decimal value of the row’s binary pattern reading $A$ as the most significant bit. Row 5 is binary 101, so $m_5 = AB’C$.
For three variables:
| Row | $A$ | $B$ | $C$ | Minterm | Symbol |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | $A’B’C'$ | $m_0$ |
| 1 | 0 | 0 | 1 | $A’B’C$ | $m_1$ |
| 2 | 0 | 1 | 0 | $A’BC'$ | $m_2$ |
| 3 | 0 | 1 | 1 | $A’BC$ | $m_3$ |
| 4 | 1 | 0 | 0 | $AB’C'$ | $m_4$ |
| 5 | 1 | 0 | 1 | $AB’C$ | $m_5$ |
| 6 | 1 | 1 | 0 | $ABC'$ | $m_6$ |
| 7 | 1 | 1 | 1 | $ABC$ | $m_7$ |
Sum of products: read the 1s
To get the SOP form, take every row where the output is 1, write its minterm, and OR them all together. The function is 1 in a row exactly when that row’s minterm is 1, and each minterm fires for only one row, so the OR of the 1-row minterms is 1 precisely where the function is.
The shorthand $F = \sum m(i, j, k, \ldots)$ lists the row numbers where the output is 1.
Take this function:
| Row | $A$ | $B$ | $C$ | $F$ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 0 |
| 7 | 1 | 1 | 1 | 1 |
The output is 1 in rows 1, 3, 5 and 7, so
$$F = \sum m(1, 3, 5, 7) = A’B’C + A’BC + AB’C + ABC$$
Check row 3, $A = 0, B = 1, C = 1$: the term $A’BC = 1$ and every other term is 0, so $F = 1$.
When a synthesis tool reports that a function has some number of minterms, it is telling you how many rows of the truth table are 1. Its optimisation step then tries to cover those rows with fewer, larger product terms.
Maxterms
A maxterm is a sum (OR) term in which every variable appears exactly once. It is 0 for exactly one row and 1 for all the others.
The rule is the opposite of the minterm rule: where the variable is 0 in the row it appears plain, where it is 1 it appears complemented. This makes sense when you think about it. An OR is 0 only when every literal in it is 0. To make it 0 when $A = 0$ we need the literal $A$; to make it 0 when $A = 1$ we need $A’$.
| Row | $A$ | $B$ | $C$ | Maxterm | Symbol |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | $A+B+C$ | $M_0$ |
| 1 | 0 | 0 | 1 | $A+B+C'$ | $M_1$ |
| 2 | 0 | 1 | 0 | $A+B’+C$ | $M_2$ |
| 3 | 0 | 1 | 1 | $A+B’+C'$ | $M_3$ |
| 4 | 1 | 0 | 0 | $A’+B+C$ | $M_4$ |
| 5 | 1 | 0 | 1 | $A’+B+C'$ | $M_5$ |
| 6 | 1 | 1 | 0 | $A’+B’+C$ | $M_6$ |
| 7 | 1 | 1 | 1 | $A’+B’+C'$ | $M_7$ |
Product of sums: read the 0s
For the POS form, take every row where the output is 0, write its maxterm, and AND them together. Each maxterm is 0 for its own row and 1 elsewhere, so the product is 0 exactly in the 0-rows.
The shorthand $F = \prod M(i, j, k, \ldots)$ lists the row numbers where the output is 0.
For the same function, the output is 0 in rows 0, 2, 4 and 6:
$$F = \prod M(0, 2, 4, 6) = (A+B+C)(A+B’+C)(A’+B+C)(A’+B’+C)$$
Check row 2, $A = 0, B = 1, C = 0$: $M_2 = 0 + 0 + 0 = 0$, and anything AND 0 is 0. Check row 1, which is a 1-row: $M_0 = 0+0+1 = 1$, $M_2 = 0+1+1 = 1$, $M_4 = 1+0+1 = 1$, $M_6 = 1+1+1 = 1$, and the product is 1.
The two forms are complements of each other
The minterm indices in the SOP form and the maxterm indices in the POS form are complementary sets. For three variables, if $F = \sum m(1,3,5,7)$ then $F = \prod M(0,2,4,6)$; together the two lists cover all of rows 0 to 7.
There is also a direct relation between a minterm and the maxterm with the same index:
$$M_i = m_i’$$
For example $m_3 = A’BC$ and $M_3 = A + B’ + C’$, and by De Morgan $(A’BC)’ = A + B’ + C’$.
So converting between the forms is trivial: complement the index set. Given $F = \sum m(1,3,5,7)$, the full index set is ${0,\ldots,7}$, the complement of ${1,3,5,7}$ is ${0,2,4,6}$, so $F = \prod M(0,2,4,6)$. And the complement function swaps the sets: $F’ = \sum m(0,2,4,6) = \prod M(1,3,5,7)$.
Which form to use in practice depends on which list is shorter. A function that is 1 in only two rows has a two-term SOP; a function that is 0 in only two rows has a two-factor POS.
Why canonical forms matter
For synthesis, because every logic minimiser (Espresso, Quine-McCluskey, the Karnaugh map) starts from the list of minterms. When you write assign F = ... the tool converts your expression to canonical form before optimising it.
For equivalence checking, because two expressions with the same minterm set are the same function, and that can be proved without simulating anything. Formal verification tools rely on this.
For documentation, because $\sum m(1,3,5,7)$ is a compact and unambiguous way to state a function.
A full worked example
The function: output 1 when a 3-bit input has an odd number of 1s.
Build the truth table by counting the 1s in each row:
| Row | $A$ | $B$ | $C$ | Number of 1s | $F$ |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 2 | 0 | 1 | 0 | 1 | 1 |
| 3 | 0 | 1 | 1 | 2 | 0 |
| 4 | 1 | 0 | 0 | 1 | 1 |
| 5 | 1 | 0 | 1 | 2 | 0 |
| 6 | 1 | 1 | 0 | 2 | 0 |
| 7 | 1 | 1 | 1 | 3 | 1 |
The on-set (rows where $F = 1$) is ${1, 2, 4, 7}$ and the off-set is ${0, 3, 5, 6}$.
SOP form:
$$F = \sum m(1,2,4,7) = A’B’C + A’BC’ + AB’C’ + ABC$$
POS form:
$$F = \prod M(0,3,5,6) = (A+B+C)(A+B’+C’)(A’+B+C’)(A’+B’+C)$$
Check row 7 in both. SOP: $ABC = 1$, so $F = 1$. POS: $M_0 = 1+1+1 = 1$, $M_3 = 1+0+0 = 1$, $M_5 = 0+1+0 = 1$, $M_6 = 0+0+1 = 1$, product 1. Both agree.
You may recognise this function: it is the 3-input XOR, $A \oplus B \oplus C$. The canonical SOP has four terms and twelve literals; the XOR form is much smaller. That is the point to remember: the canonical form is the starting point of minimisation, not the end.
One mistake to avoid: reading SOP from the 0-rows or POS from the 1-rows. SOP reads the 1s, because you are OR-ing terms that are each 1 in one row. POS reads the 0s, because you are AND-ing terms that are each 0 in one row.
Reference table for three variables
| Row | A | B | C | Minterm $m_i$ | Maxterm $M_i$ |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | $A’B’C'$ | $A+B+C$ |
| 1 | 0 | 0 | 1 | $A’B’C$ | $A+B+C'$ |
| 2 | 0 | 1 | 0 | $A’BC'$ | $A+B’+C$ |
| 3 | 0 | 1 | 1 | $A’BC$ | $A+B’+C'$ |
| 4 | 1 | 0 | 0 | $AB’C'$ | $A’+B+C$ |
| 5 | 1 | 0 | 1 | $AB’C$ | $A’+B+C'$ |
| 6 | 1 | 1 | 0 | $ABC'$ | $A’+B’+C$ |
| 7 | 1 | 1 | 1 | $ABC$ | $A’+B’+C'$ |
Practice Exercise
Problem 1. Write $F(A,B,C) = \sum m(0, 3, 6, 7)$ in full SOP form, and give the POS form.
Solution
$$F = A’B’C’ + A’BC + ABC’ + ABC$$
The complementary index set is ${1,2,4,5}$:
$$F = \prod M(1,2,4,5) = (A+B+C’)(A+B’+C)(A’+B+C)(A’+B+C’)$$
Problem 2. $G(A,B,C) = \prod M(1,4,5,7)$. Write the canonical SOP form.
Solution
The complement of ${1,4,5,7}$ in ${0,\ldots,7}$ is ${0,2,3,6}$, so
$$G = \sum m(0,2,3,6) = A’B’C’ + A’BC’ + A’BC + ABC’$$
Problem 3. How many distinct Boolean functions of three variables are there?
Solution
The truth table has $2^3 = 8$ rows and each output can independently be 0 or 1, so there are $2^8 = 256$ functions. Each one corresponds to a distinct subset of the eight minterms, which is exactly why the canonical form is canonical: there is one for each function.
In the next article we take a canonical expression, which is usually far larger than it needs to be, and simplify it algebraically into something worth building.