Canonical Forms, Minterms, and the Cost of Two-Level Logic

A combinational circuit is specified by a truth table: for each of the $2^n$ input assignments, one output bit. Turning that table into gates requires a notation in which the table’s rows become algebraic terms. The canonical forms do this mechanically, with no insight required, and they establish the baseline against which every minimization technique is measured.

Truth tables as algebraic objects

Fix $n$ input variables. An assignment is a vector in ${0,1}^n$. A literal is a variable or its complement; a product term is a conjunction of literals in which no variable appears twice; a sum term is a disjunction of literals.

A minterm of $n$ variables is a product term containing exactly one literal for each variable. There are $2^n$ minterms, and each is true for exactly one assignment. Write $m_i$ for the minterm true at the assignment whose binary value is $i$. For three variables with $x$ as the most significant bit, $m_5$ corresponds to $101$ and is the term $x \bar y z$.

A maxterm $M_i$ is the sum term containing every variable exactly once, and it is false at exactly the assignment $i$. The maxterm and minterm with the same index are complements: $M_i = \overline{m_i}$.

Any function $f$ can then be written two ways. The canonical sum of products is the OR of the minterms where $f$ is 1:

$$f = \sum_{i ,:, f(i)=1} m_i$$

The canonical product of sums is the AND of the maxterms where $f$ is 0:

$$f = \prod_{i ,:, f(i)=0} M_i$$

Both are correct for every function, and both are unique up to the ordering of terms. That uniqueness is what makes them canonical: two functions are equal exactly when their canonical forms have the same term set.

The mechanical construction is worth stating because it is what a truth-table-to-logic tool does. For each row where the output is 1, write a product of all input variables, using the variable uncomplemented where the row has a 1 and complemented where it has a 0. OR the products together. The dual procedure over the zero rows, with the polarity inverted and the connectives swapped, gives the product of sums.

Why the canonical form is never the answer

A canonical form has one literal per variable per term. For a function of $n$ variables with $k$ ones in its truth table, the sum of products has $n \cdot k$ literals and $k$ product terms. For an 8-input function that is 1 on 200 of 256 rows, that is 1,600 literals — an absurd circuit that a minimized implementation might realize with a few dozen.

The canonical form is still useful in three roles. It is the interchange format between a truth table and a minimization algorithm, because the minterm index set identifies the function exactly. It gives a decision procedure for equivalence: convert both sides to canonical form and compare term sets. And it supplies the starting point for the tabular minimization methods described in two-level minimization, which work by merging adjacent minterms.

The adjacency rule that makes merging possible

Two minterms that differ in exactly one literal are adjacent, and their OR simplifies:

$$x \bar y z + x y z = x z (\bar y + y) = x z$$

The merged term has one fewer literal and covers two assignments. Repeating the merge produces product terms that cover $2^k$ assignments with $n-k$ literals. Such a term is an implicant of $f$: whenever it is true, $f$ is true. A prime implicant is an implicant that cannot be enlarged by dropping a literal without covering an assignment where $f$ is 0.

Two-level minimization is the search for a small set of prime implicants whose union covers every one-row of the truth table. The covering condition is what makes the problem hard: the minimum cover problem is NP-hard in general, which is why exact minimizers are practical only for modest input counts and why synthesis tools use heuristics above that threshold.

Representation	Terms	Literals per term	Total literals, 4-var function with 8 ones
Canonical SOP	8	4	32
Minimized SOP	3	2	6

The table is not a measurement; it is arithmetic on a specific hypothetical function. The point is the order of magnitude: minimization removes a factor of five in literal count here, and literal count is the first-order proxy for area and for the number of transistor stacks in the resulting network.

Literal cost is a proxy, not the objective

Counting literals is the standard cost function in the two-level minimization literature because it correlates with the number of transistors and with the number of inputs to the first-level gates. It is not the same as delay, area, or power in a real standard cell library, and the divergence matters.

A term with four literals in a sum of products is a four-input AND in the abstract. In static CMOS that becomes a NAND with four series n-channel devices in the pull-down and four parallel p-channel devices in the pull-up, which is slow, tall, and wide. A minimized expression with fewer literals may still be slower than a larger expression factored into gates of fan-in two or three. As the transistor-level structure shows, delay through a series stack grows faster than the stack height, so a five-literal product term is disproportionately expensive.

There is also the inversion cost. Canonical sums of products map naturally to AND-OR networks, but CMOS prefers NAND and NOR. A sum of products becomes a NAND-NAND structure by De Morgan: the OR of products equals the NAND of the NANDs of the products. That transformation is free in the sense that it adds no logic depth, because a NAND is the natural inverting AND. A product of sums becomes a NOR-NOR structure with the same reasoning. Since NOR gates are the weaker form in CMOS, sums of products are generally the preferred starting point even when a product of sums has fewer literals.

Algebraic manipulation beyond the canonical form

Canonical forms are a normal form, not a design method. Real expressions are manipulated with identities that change the structure without changing the function, and the useful ones are few.

Idempotence and absorption: $x + x = x$, $x + xy = x$, $x(x+y) = x$. The second identity is the one that removes redundant terms produced by canonical expansion.

Consensus: $xy + \bar x z + yz = xy + \bar x z$. The term $yz$ is redundant in the presence of the other two, because any assignment making $yz$ true also makes one of the others true. This theorem is the algebraic counterpart of the hazard-elimination rule discussed in combinational hazards, where the same term is deliberately added rather than removed, to hold an output steady during a transition.

Shannon expansion: $f(x, y, \ldots) = x \cdot f(1, y, \ldots) + \bar x \cdot f(0, y, \ldots)$. This decomposes a function on one variable into two cofactors. Iterating it produces a binary decision diagram, and stopping after a few levels produces the multiplexer-based implementation described in mux-based logic and Shannon decomposition.

De Morgan: $\overline{x + y} = \bar x \bar y$ and $\overline{xy} = \bar x + \bar y$. This is what lets a designer choose between an AND-OR and a NAND-NAND realization without changing the function.

A short script makes the canonical construction concrete and gives a way to check a hand-derived expression.

from itertools import product


def canonical_sop(variables, ones):
    """Build a sum-of-products string from the set of true minterm indices."""
    terms = []
    for index in sorted(ones):
        bits = [(index >> (len(variables) - 1 - i)) & 1 for i in range(len(variables))]
        literals = [v if b else "~" + v for v, b in zip(variables, bits)]
        terms.append("(" + " & ".join(literals) + ")")
    return " | ".join(terms) if terms else "0"


def evaluate(variables, ones, assignment):
    """Evaluate the function at one assignment, by table lookup."""
    index = 0
    for name in variables:
        index = (index << 1) | assignment[name]
    return int(index in ones)


vars3 = ["x", "y", "z"]
ones = {1, 3, 5, 7}          # 001, 011, 101, 111: true whenever z is 1
print(canonical_sop(vars3, ones))
for a in product((0, 1), repeat=3):
    print(a, evaluate(vars3, ones, dict(zip(vars3, a))))

The function defined by ones = {1, 3, 5, 7} is true exactly on the assignments $001$, $011$, $101$, $111$ — that is, whenever $z = 1$. The canonical form prints four three-literal terms, and the obvious minimization collapses them to the single literal $z$. That gap between four terms and one is the entire motivation for minimization.

Where the abstraction stops being exact

The Boolean algebra described here is a model with specific assumptions: every wire carries a well-defined 0 or 1, every gate’s output settles before the next gate reads it, and no two sources drive the same node. Each assumption has a failure mode that belongs to a different article.

Wires that are not driven settle at whatever the previous charge left behind, which is why unconnected inputs are a design error rather than a don’t-care. Two gates driving one node produce a contention current and an indeterminate level. And a gate whose inputs change at different times can produce an output that is momentarily wrong even though the steady-state function is correct — the hazard problem. The algebra says nothing about any of this because it has no notion of time.

What the algebra does give is a normal form that makes equivalence decidable and a cost measure that makes optimization a well-posed problem. Both are prerequisites for everything that follows.