Boolean Algebra, Canonical Forms & Logic Minimization

Boolean algebra separates a binary specification from any particular formula or gate network. Its equations establish steady-state input/output equivalence: they do not by themselves predict delay, fan-out, power, metastability, or glitches. Good logic design therefore keeps three questions distinct: what function is required, how that function is represented, and how the chosen representation behaves as a physical circuit.

Abstract Boolean algebra and the two-element model #

An abstract Boolean algebra is a set $B$ with join $\lor$, meet $\land$, complement $\lnot$, least element $0$, and greatest element $1$. The operations form a bounded distributive lattice and every $x\in B$ has a complement:

$$x\lor \lnot x=1,\qquad x\land \lnot x=0.$$

The elements need not be truth values. For example, the subsets of a universe form a Boolean algebra under union, intersection, and set complement. Digital logic normally uses the special two-element algebra $B=\{0,1\}$, with $0$ interpreted as false and $1$ as true. That interpretation is a convention of the model, not an axiom that every abstract Boolean algebra has only two elements.

For $n\geq 1$, an $n$-ary Boolean function is a map

$$f:\{0,1\}^{n}\rightarrow\{0,1\}.$$

There are $2^{2^n}$ such functions: a truth table has $2^n$ rows, and each row's output can independently be 0 or 1. This count includes functions that ignore some formal arguments. A variable $x_i$ is essential for $f$ exactly when two input vectors exist that differ only in coordinate $i$ and produce different outputs. Otherwise $x_i$ is a dummy variable for that function.

Formulas are syntax; functions are behavior #

A Boolean formula is a finite syntax tree built from variables, constants, and operations. Assigning values to its variables evaluates the tree and induces a Boolean function. Different trees can induce the same function:

$$x\lor(x\land y)=x.$$

The left formula contains $y$, but the induced function does not essentially depend on $y$. Two formulas are equivalent when their induced functions agree on every assignment. This distinction matters throughout minimization: the object being preserved is the function, while literals, terms, depth, and gates are costs of a chosen representation.

The same function can also be represented by a truth table, a set of ON-set rows, a decision diagram, a circuit, or one of several algebraic normal forms. None of these representations is the function itself.

DNF, CNF, and their canonical forms #

A literal is $x_i$ or $\lnot x_i$. A disjunctive normal form (DNF), called a sum of products in switching algebra, is an OR of ANDs of literals. A conjunctive normal form (CNF), or product of sums, is an AND of ORs of literals. Ordinary DNF and CNF terms may omit variables.

For an input vector $a=(a_1,\ldots,a_n)$, its minterm contains every variable exactly once and is true at that row alone:

$$m_a(x)=\bigwedge_{i=1}^{n} \begin{cases} x_i,&a_i=1,\\ \lnot x_i,&a_i=0. \end{cases}$$

Its maxterm also contains every variable exactly once and is false at that row alone:

$$M_a(x)=\bigvee_{i=1}^{n} \begin{cases} x_i,&a_i=0,\\ \lnot x_i,&a_i=1. \end{cases}$$

Consequently every Boolean function has canonical expansions

$$f=\bigvee_{a:f(a)=1}m_a \qquad\text{and}\qquad f=\bigwedge_{a:f(a)=0}M_a.$$

The first is the canonical DNF; the second is the canonical CNF. The empty disjunction is $0$, so it represents the constant-zero function, and the empty conjunction is $1$, so it represents the constant-one function. These conventions prevent the constants from becoming exceptions to the theorem.

With variable order $(x,y,z)$ and binary row indices, consider

$$F=\Sigma m(1,3,4,5) =\lnot x\lnot y z\lor\lnot x y z\lor x\lnot y\lnot z\lor x\lnot y z.$$

Its zero rows are $0,2,6,7$, so the same function is $F=\Pi M(0,2,6,7)$. The symbols $\Sigma m$ and $\Pi M$ are unambiguous only after the variable order and row-number convention are stated. Canonical forms are systematic and unique up to term ordering, but they deliberately repeat information and are seldom minimal.

Algebraic normal form over GF(2) #

Another basis treats XOR as addition and AND as multiplication in the field $\mathop{\mathrm{GF}}(2)$. Because $1\oplus1=0$ and a Boolean input satisfies $x_i^2=x_i$, every Boolean function has a unique square-free algebraic normal form (ANF), also called a Zhegalkin polynomial:

$$f(x_1,\ldots,x_n) =\bigoplus_{S\subseteq\{1,\ldots,n\}} a_S\prod_{i\in S}x_i, \qquad a_S\in\{0,1\}.$$

The empty product is 1 and supplies the constant coefficient. If $\mathbf{1}_T$ denotes the input whose 1-coordinates are exactly the set $T$, then the coefficients can be recovered directly from the truth table:

$$a_S=\bigoplus_{T\subseteq S}f(\mathbf{1}_T).$$

This is the Möbius transform on the subset lattice; applying the same XOR transform again recovers the truth table. It also proves uniqueness: the $2^n$ square-free monomials form a basis for the $2^n$-dimensional vector space of Boolean truth tables over $\mathop{\mathrm{GF}}(2)$.

For the previous example,

$$F=z\oplus x\oplus xz\oplus xy.$$

ANF exposes algebraic degree and XOR structure that DNF can hide. For instance,

$$x\lor y=x\oplus y\oplus xy.$$

Functions whose ANF has degree at most one have the form $a_0\oplus a_1x_1\oplus\cdots\oplus a_nx_n$. They are affine; the narrower word linear is appropriate only when $a_0=0$.

Functional completeness and Post's five obstructions #

A gate basis is useful only if composition can express the required functions. Start with a family $\Gamma$ of Boolean functions, allow projections such as $(x_1,\ldots,x_n)\mapsto x_i$, and repeatedly substitute outputs of functions into inputs of other functions. The resulting composition-closed family is the clone generated by $\Gamma$. The basis is functionally complete when this clone contains every Boolean function.

Post's 1921 paper developed the truth-table and metalogical setting. At the opening of Section 26 of his 1941 monograph, he states that there are exactly five immediately subcomplete closed systems and gives the corresponding generator criterion. Modern clone theory supplies the composition-and-maximal-clone framework; a modern five-class account presents the obstructions as the following maximal proper Boolean classes:

The table uses the common symbols $S$ for the self-dual clone and $L$ for the affine clone. Gonda writes these two classes as SF and $A$; this is only a notation change.

Every proper Boolean clone is contained in at least one of these five. Therefore the exact completeness criterion is

$$\Gamma\text{ is functionally complete} \iff \Gamma\nsubseteq T_0,\quad \Gamma\nsubseteq T_1,\quad \Gamma\nsubseteq M,\quad \Gamma\nsubseteq S,\quad \Gamma\nsubseteq L.$$

In words: for each of the five classes, at least one generator must lie outside it. The same generator may escape several classes, and different generators may supply different witnesses. Escaping all five is not merely a useful heuristic; it is both necessary and sufficient.

NAND and NOR are universal bases #

The Post criterion proves completeness abstractly; explicit identities show how synthesis works. Define NAND and NOR by

$$x\uparrow y=\lnot(x\land y), \qquad x\downarrow y=\lnot(x\lor y).$$

NAND alone constructs NOT, AND, and OR:

$$\lnot x=x\uparrow x,$$

$$x\land y=(x\uparrow y)\uparrow(x\uparrow y), \qquad x\lor y=(x\uparrow x)\uparrow(y\uparrow y).$$

NOR has the dual constructions:

$$\lnot x=x\downarrow x,$$

$$x\lor y=(x\downarrow y)\downarrow(x\downarrow y), \qquad x\land y=(x\downarrow x)\downarrow(y\downarrow y).$$

Since NOT, AND, and OR can express every canonical DNF or CNF, either $\{\uparrow\}$ or $\{\downarrow\}$ is a universal basis. Universality says that an implementation exists; it says nothing about whether the resulting gate count, depth, delay, or power is acceptable.

Implicants are cubes in the input space #

For two-level sum-of-products minimization, partition the input rows into an ON-set where the output must be 1, an OFF-set where it must be 0, and optionally a don't-care set where either output is allowed. A product term can be written as a cube over $\{0,1,-\}$: a dash means that coordinate is unconstrained. For example, the cube $0{-}1$ denotes $\lnot x\land z$ and covers both $001$ and $011$.

A cube is an implicant of a fully specified function when every row it covers lies in the ON-set. With don't-cares, a usable implicant may cover rows in $\mathrm{ON}\cup\mathrm{DC}$ but no row in the OFF-set, and it must cover at least one required ON row.

• A prime implicant is an implicant from which no fixed literal can be removed without covering an OFF row. Geometrically, it is a maximal legal cube.
• An essential prime implicant covers at least one ON minterm that no other prime implicant covers. Every valid SOP cover must select it.

Prime does not mean globally optimal. Prime implicants are the maximal-cube, literal-irreducible candidates; a prime may still be redundant in a selected cover. Selecting a minimum-cost subset of the primes is a separate covering problem.

Quine–McCluskey: generate primes, then solve the cover #

The Quine–McCluskey method makes both phases explicit:

1. List the ON and don't-care minterms as bit strings and group them by number of 1s.
2. Combine terms that have the same dash positions and differ in exactly one remaining fixed coordinate, replacing that coordinate with a dash. Mark both parents as combined and deduplicate identical results.
3. Repeat on the new cubes. Retain every generated cube through all combination rounds, including a cube that currently covers only don't-care rows: it may still combine with an ON-containing cube to remove another literal. Every cube left uncombined in an iteration is a prime candidate. Only after all rounds, discard final candidates that cover no required ON row.
4. Build a prime-implicant chart whose columns are required ON minterms only. Don't-care rows helped form larger primes but do not require coverage.
5. Select essential primes, remove the ON columns they cover, and solve the remaining set-cover problem exactly, for example with Petrick's method or branch-and-bound.

For $F=\Sigma m(1,3,4,5)$, the initial minterms are $001$, $011$, $100$, and $101$. Pairwise combinations produce three primes:

$$\mathtt{-01}=\lnot y z,\qquad \mathtt{10-}=x\lnot y,\qquad \mathtt{0-1}=\lnot x z.$$

Minterm $m_3$ is covered only by $\mathtt{0-1}$, while $m_4$ is covered only by $\mathtt{10-}$. Those two essential primes already cover the whole ON-set, so $\mathtt{-01}$ is redundant and

$$F=x\lnot y\lor\lnot xz.$$

The word minimum needs an explicit cost contract. In this example, use the lexicographic objective

$$C(P)=\left(\text{number of product terms in }P,\ \text{total number of literals in }P\right),$$

and minimize $C$ among all valid two-level SOP covers of the required ON-set under the stated don't-care contract. A weighted cell-area model, a maximum-fan-in limit, shared inversions, or a delay objective can choose a different cover. Prime generation can itself be exponential, and the residual chart is a set-cover problem; the method is exact, not inherently cheap.

Karnaugh and Veitch maps #

Veitch and Karnaugh diagrams encode the same Boolean-cube adjacency idea: neighboring cells must differ in exactly one input bit. The common Karnaugh layout labels rows and columns in Gray-code order so that geometric rectangles correspond to implicants. For the running example:

The upper cells in columns 01 and 11 form $\lnot xz$; the lower cells in columns 00 and 01 form $x\lnot y$. A legal group:

• contains $2^k$ cells for some $k$;
• contains only ON or chosen don't-care cells, never an OFF cell;
• is rectangular in the map's wrapped topology; and
• contributes the literals whose coordinates remain fixed across the group.

The left and right edges are adjacent, as are the top and bottom edges. In a four-variable map the four corners are therefore one rectangular group. This wrap is not a drawing trick: it is the adjacency of vertices in the Boolean hypercube.

A don't-care cell may be treated as 1 when it enlarges a useful group or as 0 when it does not; different groups may simply ignore it. The final circuit chooses some concrete output on that row, so the don't-care assumption is safe only while the environment truly permits either value.

Karnaugh maps work well for human inspection of a small number of variables. Quine–McCluskey preserves the same cube operations in a tabular algorithm, but exact methods still scale poorly; industrial synthesis uses more sophisticated exact or heuristic procedures and optimizes beyond a single two-level expression.

Boolean minimum is not circuit minimum #

Algebraic identities such as absorption and De Morgan's laws preserve the function:

$$x\lor(x\land y)=x, \qquad \lnot(x\land y)=\lnot x\lor\lnot y.$$

They do not define a unique hardware cost. A minimum-literal SOP can be worse after technology mapping than a factored multilevel network; factoring can reduce gate count yet increase depth, fan-out, reconvergent paths, or critical delay. A universal NAND-only realization can likewise be larger than a mixed-gate realization. The cost function must match the available cells and the physical objective.

Hazards are a separate boundary. Consider

$$F=A B\lor\lnot A C.$$

When $B=C=1$ and $A$ changes, the ideal function remains 1. Unequal delays through the two $A$ paths can nevertheless make both product terms temporarily 0, producing a static-1 hazard. In a two-level AND–OR implementation under the single-input-change model, adding the consensus term $BC$ closes the adjacent ON transition:

$$F=A B\lor\lnot A C\lor BC.$$

The consensus term is redundant in steady-state Boolean algebra and may make the SOP more expensive, yet it supplies temporal overlap. A later multilevel rewrite or technology mapper can reintroduce a hazard, so hazard freedom must be checked on the implemented topology and delay model, not inferred from the source expression alone.

Synchronous sampling often masks a combinational glitch when every path settles before the receiving clock edge. That protection does not automatically apply to asynchronous controls, clocks, latches, analog enables, clock-domain crossings, or external interfaces.

A disciplined design flow #

1. State the legal input space and specify ON, OFF, and don't-care rows. Treat every don't-care as an environmental contract.
2. Fix variable order and derive a truth table or another executable specification.
3. Choose a representation that exposes the needed structure: canonical DNF/CNF for row-level traceability, ANF for XOR and degree, or cubes for two-level minimization.
4. Declare the cost model before claiming a minimum. For an exact SOP, generate primes and solve the covering phase rather than relying on greedy grouping.
5. Map the selected function into the actual gate or cell library, accounting for fan-in, inversions, sharing, depth, load, and power.
6. Verify functional equivalence over all legal inputs, then verify hazards and timing against the implemented network and its operating assumptions.

The truth table is the behavioral contract, minimization chooses a representation under a cost model, and circuit verification checks the physical consequences. Conflating those layers is the source of most “algebraically correct but electrically wrong” logic designs.