Canonical Forms and Functional Completeness

Every Boolean function has two canonical representations that are unique up to term order: the sum of minterms (canonical SOP) and the product of maxterms (canonical POS). From those forms you can read the truth table directly, and you can ask which gate sets are functionally complete: able to express every Boolean function. NAND alone and NOR alone are complete; AND and OR together are not (no NOT).

The working skills are minterm and maxterm numbering, conversions between SOP and POS, and deciding whether a given gate set is complete (with a short functional-completeness argument).

For $n$ variables $x_1,\ldots,x_n$ ordered left to right:

Relation: $M_i = (m_i)'$ as functions, and $m_i' = M_i$.

If $f=1$ on index set $S$, then

(the sum of those minterms). If $f=0$ on index set $T$, then

(the product of those maxterms). The two sets partition $\{0,\ldots,2^n-1\}$: $T$ is the complement of $S$.

Notation: $f(x,y,z)=\sum m(1,2,5)=\prod M(0,3,4,6,7)$.

With $S$ the 1-rows of $f$ and $\bar S$ the 0-rows:

The dual row follows from $f^d(x) = f'(x')$: complementing all inputs maps row $i$ to row $2^n - 1 - i$. For $f = \sum m(1, 2, 5)$ with $n = 3$: $f' = \sum m(0, 3, 4, 6, 7) = \prod M(1, 2, 5)$ and $f^d = \prod M(6, 5, 2) = \sum m(0, 1, 3, 4, 7)$.

Different count: minterms covered by a product term. A product of $k$ literals over $n$ variables covers $2^{n-k}$ minterms. So $f(x, y, z) = x + y'z$ expands to $x \to m(4, 5, 6, 7)$ and $y'z \to m(1, 5)$, giving $\sum m(1, 4, 5, 6, 7)$: 5 minterms, not 6, because $m_5$ is shared. The number of functions of $n$ variables with exactly $k$ minterms is $\binom{2^n}{k}$.

A sum of products that is not necessarily minterms (some products omit variables) is an ordinary SOP. A product of sums that is not necessarily maxterms is an ordinary POS. Minimization seeks short SOP or POS forms; they are not unique, unlike the canonical ones.

A set of Boolean operators is functionally complete (universal) if every Boolean function of any arity can be written using only operators from that set (and constants, or without constants, depending on the precise definition used in the question; this note allows composing the gates and using the input variables, and asks separately whether constants are needed).

IMPERATIVE RULE. To show incompleteness, name an invariant preserved by the set (for example monotonicity for $\{\text{AND},\text{OR}\}$, or linearity over $\mathrm{GF}(2)$ for $\{\text{XOR}\}$) that some target function violates (NOT is not monotone; AND is not linear).

Number rows 0 to $2^n-1$ in binary order of $(x_1\ldots x_n)$. Every row where $f=1$ contributes its minterm. That list is the canonical SOP.

Complement the minterm list to get the maxterm list (the rows where $f=0$), then write $\prod M_i$. Alternatively: take the SOP of $f'$, then apply De Morgan once.

Why NAND-NAND equals AND-OR. $f = P_1 + P_2 + \cdots + P_k = \big(P_1' P_2' \cdots P_k'\big)'$ by De Morgan, and each $P_j'$ is a NAND of the literals of $P_j$. So a two-level NAND-NAND circuit realizes an SOP with the AND-OR levels replaced using NAND gates; the SOP is minimal only if it was minimized under the stated cost model, and this conversion alone does not prove gate-count optimality. Dually, NOR-NOR realizes a POS. A single literal entering the second level directly must be complemented.

Taking any of AND, OR, NAND, NOR at each of the two levels gives 16 forms. Eight are degenerate: they collapse to a single gate. AND-AND and OR-OR are trivial; NAND-NOR and NOR-NAND collapse by De Morgan, for example $\big((ab)' + (cd)'\big)' = abcd$. The other eight compute an SOP or POS:

Read AND-NOR as $(P_1 + \cdots + P_k)'$, an AND-OR-INVERT that gives the complement of an SOP, which equals a POS of the complemented function. NOR-OR and OR-NAND use complemented literals at the first level.

The 4-NAND XOR is $t = (xy)'$, then $\big((x t)'(y t)'\big)'$. No circuit of fewer two-input NAND gates computes XOR; the counts in the table are minimum over all circuits, not only over two-level forms.

The constructive check is sufficient but not necessary: sets such as $\{\to, 0\}$ and $\{\text{XOR}, \text{AND}, 1\}$ are complete without containing NAND, NOR or NOT directly. The exact test is Post's criteria below.

Algorithm costs, not gate delays. Use unit-cost indexed row lookup, word comparison and amortised constant-time output append; an index/loop word must hold $2^n$. Inputs and output buffers are excluded from workspace. MINTERM-LIST reads all $2^n$ rows: $\Theta(2^n)$ time in best, average and worst cases, $O(1)$ working words, and $\Theta(1+|S|)$ output-list words. With iterative literal emission, CANONICAL-SOP takes $\Theta(1+n|S|)$ time and output tokens in every case, and $O(1)$ workspace beyond the input/output. Empty $S$ emits constant 0; for $n=0$, the sole selected zero-variable minterm emits constant 1. For IS-COMPLETE-BY-NAND-BUILD, precomputed membership flags for the fixed named basis make time and auxiliary space $\Theta(1)$ in all cases, excluding the input and Boolean result. If gates arrive as an unsorted list of $g$ word-sized tags, first building those flags takes $\Theta(g+1)$ time and $O(1)$ words. These are representation-specific software costs, not arbitrary-precision or circuit-latency claims.

Uniqueness. Canonical SOP is unique because each minterm corresponds to exactly one 1 in the truth table. Canonical POS is unique for the same reason on the 0s.

Post's criteria. Emil Post showed that a set $F$ of Boolean functions (with composition and the input variables freely available, constants only if they are in $F$) is functionally complete if and only if, for each of the five classes below, $F$ contains at least one function outside that class. Each class is closed under composition, so a set lying inside one class can never leave it; that is the incompleteness argument.

Applying the test. Mark, for each function in the set, which classes it falls outside; the set is complete when every column has a mark.

A completeness question names a gate set (sometimes with constants 0 and 1 allowed) and asks if it is complete. Two steps settle it: try to construct NOT and either AND or OR; if that fails, find the class that contains every member of the set.

Rows: $001, 010, 101$. Canonical SOP: $x'y'z + x'yz' + xy'z$. Zeros at $0,3,4,6,7$, so POS: $M_0 M_3 M_4 M_6 M_7$, that is $(x+y+z)(x+y'+z')(x'+y+z)(x'+y'+z)(x'+y'+z')$.

$x \uparrow x = (xx)' = x'$.

Any expression using only AND and OR is monotone: flipping an input from 0 to 1 never flips the output from 1 to 0. NOT is not monotone, so it cannot be expressed.

For $n=4$ there are 16 minterms $m_0..m_{15}$. A function with $k$ ones has exactly $k$ minterms in its canonical SOP.

$f(a, b, c) = ab + c'$. The term $ab$ covers $m_6, m_7$; $c'$ covers $m_0, m_2, m_4, m_6$. So $f = \sum m(0, 2, 4, 6, 7) = \prod M(1, 3, 5)$, that is $f = (a + b + c')(a + b' + c')(a' + b + c')$. The complement is $f' = \sum m(1, 3, 5) = a'c + b'c$.

Check the five classes. $f(0,0,0) = 1$: outside $T_0$. $f(1,1,1) = 0$: outside $T_1$. $f$ is not monotone (raising $z$ from 0 to 1 at $x = 1, y = 0$ lowers the output from 1 to 0). It is not affine (it contains the product $x'y$). Self-dual? At $x = y = z = 0$ the value is 1, and at the complement input $(1, 1, 1)$ it is 0, which is consistent; but at $(0, 1, 1)$ the value is 1 and at $(1, 0, 0)$ it is also 1, so $f$ is not self-dual. All five marks: complete. Constructively, $f(x, x, x) = x'$ (since $x'x = 0$), and NOT together with $f(x, y, 1) = x'y$ gives AND.

Common misconceptions.