Introduction to the Quine-McCluskey Algorithm

A digital circuit realizes a Boolean function as a network of gates, and every gate costs silicon area, power, and propagation delay. The canonical sum-of-products form of a function — one product term per minterm, all products added together — is always correct but almost never economical: a function of four variables that happens to be true on six input combinations can need six four-input AND gates feeding a six-input OR gate, when a handful of much smaller terms would do exactly the same job. Karnaugh maps solve this by letting a human eye spot adjacent minterms and group them visually, but that grouping step is really just pattern matching on a grid, and grids stop being drawable well before eight or ten variables. The Quine-McCluskey algorithm takes the same underlying idea — two minterms differing in a single bit can be merged into one shorter term — and turns it into an explicit, mechanical procedure that a computer can carry out for any number of variables, first formulated by Quine and put into the tabular shape used today by McCluskey. Every step below is verified numerically against a solver that implements the same procedure, so the tables and expressions can be reproduced directly by entering the same minterms.

Minterms and the Canonical Sum of Products

A Boolean function of \(n\) variables is a map \(f:\{0,1\}^n\to\{0,1\}\). A literal is a variable \(x_i\) or its complement \(\overline{x_i}\), and a minterm is a product (AND) of \(n\) literals, one per variable, chosen so that exactly one input assignment makes the product equal to \(1\). Numbering the variables \(x_0,\dots,x_{n-1}\) and reading an assignment as a binary number gives every minterm an index \(m\in\{0,\dots,2^n-1\}\): the bit at position \(i\) of \(m\) fixes whether \(x_i\) or \(\overline{x_i}\) appears. Any function can be written as the OR of the minterms on which it evaluates to \(1\); this is its canonical sum of products, and the shorthand

\[ f(x_0,\dots,x_{n-1})=\sum m(\dots) \]

lists exactly those minterm indices. Some input combinations may never occur in practice (an invalid sensor reading, an unused binary-coded-decimal digit), and the function's value there is irrelevant; these are written as don't-cares \(d(\dots)\) and may be treated as either \(0\) or \(1\), whichever helps produce a smaller expression. The canonical sum of products already computes the correct function, but it is rarely minimal: the whole point of the algorithm developed here is to replace it with a shorter expression covering the same required minterms, using don't-cares wherever convenient.

The Combining Law

The single algebraic fact underlying the entire method is the combining law

\[ (x_i\wedge A)\vee(\overline{x_i}\wedge A)=A\wedge(x_i\vee\overline{x_i})=A\wedge 1=A, \]

obtained by factoring out the common term \(A\) with the distributive law, then applying the complement law \(x_i\vee\overline{x_i}=1\) and the identity law \(A\wedge 1=A\). It says that if two minterms are identical except for one variable, appearing uncomplemented in one and complemented in the other, their sum collapses to a single, shorter term that no longer mentions that variable at all. Encoding minterms as bit strings and marking the eliminated position with a dash turns this into a purely syntactic rule: two bit strings that agree everywhere except one position, where one has a 0 and the other a 1, merge into a shorter string with a dash at that position, and the same rule applies again to strings that already contain dashes, as long as the dashes line up in the same positions. A term with dashes stops being mergeable once no partner differing in exactly one remaining bit exists; such a term is a prime implicant — a product term that cannot be shortened any further while still implying the function.

Comparing every pair of minterms directly costs \(O(2^{2n})\) comparisons, most of which are wasted, since two bit strings differing in exactly one position must also differ in their number of set bits by exactly one. Grouping minterms by their number of ones and only comparing adjacent groups finds every possible merge without ever comparing a pair that cannot combine, which is exactly what the worked example below does.

Worked Example

Consider a four-variable function specified by

\[ f(x_0,x_1,x_2,x_3)=\sum m(4,8,10,11,12,15)+d(9,14). \]

Writing every minterm and don't-care in binary and sorting by its number of set bits gives the starting table:

Comparing every minterm in each group with every minterm in the next group finds all pairs differing in exactly one bit, and records the merged term with a dash at that position:

None of these ten size-2 terms can merge with each other unless their dashes already line up in the same position. Grouping them by dash position and repeating the comparison finds three more merges, each combining two size-2 terms into a size-4 term with two dashes:

None of these three terms shares both dash positions with another, so none merges any further: together with the earlier −100 term (covering {4,12}, which never found a partner to merge with), the process halts with exactly four prime implicants:

The Prime Implicant Chart and Essential Prime Implicants

Don't-cares were useful for finding larger groups, but the function is only required to equal \(1\) on the actual minterms 4, 8, 10, 11, 12 and 15, so only those columns need to be covered from here on. Marking which prime implicant covers which required minterm gives the prime implicant chart:

A column with only a single mark means that minterm can only be covered by that one prime implicant, which therefore must appear in every minimal expression — an essential prime implicant. Minterm 4 is covered only by \(P_0\), and minterm 15 only by \(P_3\), so both are essential. Together they already cover {4,10,11,12,15}, leaving only minterm 8 unaccounted for; both \(P_1\) and \(P_2\) cover it at equal cost, so either may be picked. Choosing \(P_1\) gives the minimal expression

\[ f=(\overline{x_0}\wedge\overline{x_1}\wedge x_2)\vee(\overline{x_2}\wedge x_3)\vee(x_1\wedge x_3), \]

three terms and seven literals in total, down from six terms and twenty-four literals in the canonical sum of products.

Petrick's Method

Essential prime implicants are not guaranteed to exist at all. The function

\[ f(x_0,x_1,x_2)=\sum m(0,1,2,5,6,7) \]

is the standard textbook example for this: grouping and merging its minterms produces six prime implicants, and every one of them shares its minterms evenly with a neighbor, so the chart has no single-mark column at all.

Petrick's method handles exactly this case by turning the chart into a Boolean satisfaction problem: for every column, form the OR of the prime implicants ticked in it, then AND those clauses together into a single expression \(P\) that is true precisely when every column is covered by at least one selected prime implicant,

\[ P=(Q_0\vee Q_1)(Q_0\vee Q_2)(Q_1\vee Q_3)(Q_2\vee Q_4)(Q_3\vee Q_5)(Q_4\vee Q_5). \]

Multiplying this product of sums out into a sum of products, and repeatedly applying the absorption law \(X\vee(X\wedge Y)=X\) to discard redundant terms, leaves two equally short products of three prime implicants each: \(\{Q_0,Q_3,Q_4\}\) and \(\{Q_1,Q_2,Q_5\}\). Both cover every required minterm, and both spend six literals, so either is a valid minimal solution; taking the first gives

\[ f=(\overline{x_1}\wedge\overline{x_2})\vee(\overline{x_0}\wedge x_1)\vee(x_0\wedge x_2). \]

Note that Petrick's method solves a set-cover problem, and expanding the product of sums can itself blow up combinatorially on larger charts — the chart itself is cheap to build, but choosing the cheapest cover from it is, in the worst case, exactly as hard as the general problem it represents.

Extending Quine-McCluskey for XOR Logic

The combining law only ever removes one literal at a time, which works well for functions built mostly out of AND, OR and NOT gates, but produces disappointing results for functions whose natural building block is exclusive-or. Take the three-variable odd-parity function

\[ f(x_0,x_1,x_2)=\sum m(1,2,4,7), \]

true whenever an odd number of its inputs are \(1\). None of its four minterms differ from one another in only a single bit, so ordinary Quine-McCluskey cannot merge any of them at all, and the minimal sum of products is the full canonical form with four terms and twelve literals,

\[ f=(x_0\wedge\overline{x_1}\wedge\overline{x_2})\vee(\overline{x_0}\wedge x_1\wedge\overline{x_2})\vee(\overline{x_0}\wedge\overline{x_1}\wedge x_2)\vee(x_0\wedge x_1\wedge x_2), \]

even though the function is exactly \(x_0\oplus x_1\oplus x_2\), a single three-literal term once exclusive-or is allowed as a primitive. Turton (1996) closes this gap with a second combining law, built the same way as the first one but starting from the algebraic definitions of exclusive-or and exclusive-nor,

\[ x_i\oplus x_j:=(x_i\wedge\overline{x_j})\vee(\overline{x_i}\wedge x_j),\qquad x_i\odot x_j:=(x_i\wedge x_j)\vee(\overline{x_i}\wedge\overline{x_j}). \]

Reading these definitions from right to left gives the extended rule: if two minterms agree everywhere except two positions \(i,j\), and in one minterm \(x_i,x_j\) point the same way as \(x_i,x_j\) point in a plain AND term while in the other they are both flipped — \(x_i\wedge x_j\) in one, \(\overline{x_i}\wedge \overline{x_j}\) in the other — the OR of the two collapses to \(A\wedge(x_i\odot x_j)\); if instead one minterm has \(x_i\wedge\overline{x_j}\) and the other \(\overline{x_i}\wedge x_j\), it collapses to \(A\wedge(x_i\oplus x_j)\). Either way, two literals are replaced by one exclusive-or (or exclusive-nor) group spanning both variables, instead of the single dash that ordinary merging would need a matching third minterm to justify. Since an already-formed exclusive-or group is itself just an algebraic block, the same rule applies again one level up, treating that block the way a single literal was treated before — which is exactly how larger parity terms emerge from repeated rounds of merging, mirroring how repeated dash-merging builds up larger AND terms in the classic algorithm.

The smallest case is a half-adder sum, \(f(x_0,x_1)=\sum m(1,2)\). The two minterms \(x_0\wedge \overline{x_1}\) (index 1) and \(\overline{x_0}\wedge x_1\) (index 2) differ in exactly both positions with opposite orientation, so they merge directly into

\[ f=x_0\oplus x_1. \]

For the odd-parity function above, the first round pairs minterm 1 (\(x_0\wedge\overline{x_1}\wedge \overline{x_2}\)) with minterm 2 (\(\overline{x_0}\wedge x_1\wedge\overline{x_2}\)), which agree on \(\overline{x_2}\) and merge into \(\overline{x_2}\wedge(x_0\oplus x_1)\); symmetrically, minterm 4 (\(\overline{x_0}\wedge\overline{x_1}\wedge x_2\)) and minterm 7 (\(x_0\wedge x_1\wedge x_2\)) agree on \(x_2\) and merge into \(x_2\wedge(x_0\odot x_1)\). These two new terms now differ in both their fixed literal (\(\overline{x_2}\) versus \(x_2\)) and their exclusive-or block (\(x_0\oplus x_1\) versus \(x_0\odot x_1\), which is the complement of \(x_0\oplus x_1\)), which is exactly the pattern the extended rule looks for one level up, so the second round merges them into the single term

\[ f=x_0\oplus x_1\oplus x_2, \]

matching the four-term, twelve-literal standard-mode result term for term against a single three-literal exclusive-or chain. Because every exclusive-or group the extended rule discovers is only ever added as an extra candidate term into the same essential-prime-implicant and Petrick's-method covering step used by the classic algorithm, allowing exclusive-or grouping can never make the final expression larger than standard mode alone would find — only equal or smaller. Coverage still has to be checked exactly as before: essential-prime-implicant selection and Petrick's method both apply unchanged, they simply operate over a mixture of plain AND terms and exclusive-or groups instead of AND terms alone. The solver implements both modes side by side, so a function can be minimized with or without exclusive-or grouping and the two results compared directly.

Disjoint XOR Decomposition

Parity merging still has a structural limit: every XOR block it produces is affine, meaning that its arguments are literals or previously merged parity blocks. A mixed expression such as

\[ f(a,b,c)=a\oplus(b\vee c) \]

does not fit that form. Expanding it into minterms and minimizing only products therefore hides the simpler nested structure. It can be recovered directly from the truth table by asking whether the variables can be partitioned into two disjoint sets, denoted by vectors \(X\) and \(Y\), such that

\[ f(X,Y)=g(X)\oplus h(Y). \]

This decomposition exists if and only if every rectangle of the truth-table matrix anchored at the all-zero assignment has even parity:

\[ f(X,Y)\oplus f(X,0)\oplus f(0,Y)\oplus f(0,0)=0 \qquad\text{for all }X,Y. \]

Necessity follows by substituting \(f=g\oplus h\): each of \(g(X)\), \(g(0)\), \(h(Y)\), and \(h(0)\) occurs twice and cancels under XOR. The condition is also sufficient, not merely a filter. Define

\[ g(X):=f(X,0),\qquad h(Y):=f(0,Y)\oplus f(0,0). \]

Rearranging the rectangle identity then gives \(f(X,Y)=g(X)\oplus h(Y)\) for every assignment, so the two smaller truth tables provide the factors constructively. For \(f(a,b,c)=a\oplus(b\vee c)\), choose \(X=\{a\}\) and \(Y=\{b,c\}\). The restrictions are

\[ g(a)=f(a,0,0)=a,\qquad h(b,c)=f(0,b,c)\oplus f(0,0,0)=b\vee c, \]

which recovers the three-literal expression immediately. The solver checks all \(2^{n-1}-1\) distinct nontrivial variable partitions, applies the rectangle test to each one, and recursively minimizes the two factors. A decomposition replaces the Quine-McCluskey cover only when it uses fewer literals, or the same number of literals with fewer operations.

The test requires a fully specified truth table. With don't-care entries, a missing corner can be assigned in several ways and the rectangle identity becomes a completion problem rather than a direct equality, so this extra pass is deliberately skipped. The partition test itself targets disjoint-support decomposition; a second identity handles useful decompositions whose XOR operands share variables.

Shannon XOR Decomposition

Choose one variable called the selector, and let the two cofactors be the truth tables obtained by fixing it to zero and one:

\[ f_0=f\vert_{x=0},\qquad f_1=f\vert_{x=1},\qquad \Delta=f_0\oplus f_1. \]

The function can then be reconstructed with XOR rather than the usual sum-of-products form:

\[ f=f_0\oplus(x\wedge\Delta). \]

For zero, the second term vanishes and the result is exactly \(f_0\). For one, it becomes \(f_0\oplus(f_0\oplus f_1)=f_1\). Unlike the disjoint-support test, this identity permits variables from \(f_0\) to occur again inside \(\Delta\). Consider the two-to-one multiplexer

\[ f(a,b,c)=(a\wedge c)\vee(b\wedge\overline c). \]

Choosing \(c\) as the selector gives \(f_0=b\), \(f_1=a\), and \(\Delta=a\oplus b\), hence

\[ f=b\oplus\bigl(c\wedge(a\oplus b)\bigr). \]

The solver tries this construction for every possible selector in addition to checking disjoint partitions, and recursively minimizes the resulting cofactors. It retains a decomposition only when it uses fewer literals, or the same number of literals with fewer Boolean operations; a NOT gate counts as an operation in that comparison.

Explore Interactively

The widget below runs the same solver used throughout the examples above, right on this page. Enter a function as a truth table or a minterm list, and it shows every merging round, the resulting prime implicants, and the covering step as they happen.

References

• Quine1952W. V. Quine, "The Problem of Simplifying Truth Functions," The American Mathematical Monthly, vol. 59, no. 8, pp. 521–531, 1952.
• McCluskey1956E. J. McCluskey, "Minimization of Boolean Functions," Bell System Technical Journal, vol. 35, no. 6, pp. 1417–1444, 1956.
• Petrick1956S. R. Petrick, "A Direct Determination of the Irredundant Forms of a Boolean Function from the Set of Prime Implicants," Air Force Cambridge Research Center, Technical Report AFCRC-TR-56-110, 1956.
• Turton1996B. C. H. Turton, "Extending Quine-McCluskey for Exclusive-Or Logic Synthesis," IEEE Transactions on Education, vol. 39, no. 1, pp. 81–85, 1996.