Two shapes of expression
Almost every expression you will minimize has one of two shapes:
- Sum of products (SOP): AND terms, ORed together — AB + AC + BC. In hardware: a column of AND gates feeding one OR gate.
- Product of sums (POS): OR terms, ANDed together — (A + B)(A + C). In hardware: a column of OR gates feeding one AND gate.
Both are two-level circuits: a signal passes through at most two gates (not counting inverters on the inputs). Two levels means fast, and it means the cost is easy to count: the number of terms is the number of first-level gates, and the number of literals is the number of gate inputs.
Canonical SOP: OR the minterms
From lesson 1, the majority function is M = Σm(3, 5, 6, 7). Each minterm is 1 on exactly one row, so ORing the four minterms gives an expression that is 1 on exactly those four rows:
M = ABC + ABC + ABC + ABC
This is the canonical SOP (also called the standard or minterm expansion). “Canonical” means every term contains every variable, so there is exactly one such expression for a given function. Two functions are equal if and only if their canonical forms are equal.
Canonical POS: AND the maxterms
Each maxterm is 0 on exactly one row, so ANDing the maxterms of the 0-rows gives an expression that is 0 on exactly those rows. For M = ΠM(0, 1, 2, 4):
M = (A + B + C)(A + B + C)(A + B + C)(A + B + C)
Canonical is correct, not small
The canonical SOP of the majority function needs four 3-input AND gates and a 4-input OR gate: 12 literals. But the same function can be written as
M = AB + AC + BC
which needs three 2-input AND gates and a 3-input OR gate: 6 literals. Check it against the truth table: the expression is 1 exactly when at least two inputs are 1. Same function, half the hardware.
| Form | Terms | Literals |
|---|---|---|
| Canonical SOP ABC + ABC + ABC + ABC | 4 | 12 |
| Minimal SOP AB + AC + BC | 3 | 6 |
What “minimal” means on this site. A minimal SOP has the fewest terms possible, and among expressions with that many terms, the fewest literals. A function can have more than one minimal SOP; they all cost the same.
Going back: expanding to canonical form
To find the minterms of a non-canonical expression, put back the missing variables. A term that is missing a variable X covers both the X = 0 and the X = 1 case, because X + X = 1:
AB = AB(C + C) = ABC + ABC → rows 7 and 6
A term with k missing variables covers 2k rows. Hold on to that idea: minimization is this process run backwards — finding big groups of rows that one short term can cover.
The truth table converter does this expansion for any expression: it shows the table, the Σm and ΠM lists, both canonical forms and the minimal forms.
Check yourself
- Write the canonical SOP of F(A, B, C) = Σm(1, 4, 7).
Show answer
F = ABC + ABC + ABC (rows 001, 100, 111). - Which rows does the term BC cover in a three-variable function A B C?
Show answer
A is missing, so it covers two rows: ABC = row 1 and ABC = row 5. - Expand F = A + BC to a minterm list.
Show answer
A covers every row with A = 1: 4, 5, 6, 7. BC covers 1 and 5. Together: F = Σm(1, 4, 5, 6, 7). Row 5 is covered twice, which is fine: 1 + 1 = 1. - A function of 4 variables has 11 minterms. How many maxterms does its canonical POS have?
Show answer
16 − 11 = 5.