Quine–McCluskey Reducer

Type a minterm list and (optional) don’t-cares for up to 6 variables. The reducer walks all three stages live: iteration columns with combine ticks, the prime-implicant chart with essentials highlighted, and the chosen minimum SOP cover.

VariablesMintermsDon't-cares

Step 1 — Tabular grouping (2 iterations)

Each iteration column holds implicants of a fixed size. Column 1 lists the original minterms (1 cell each); column 2 holds pairs (2 cells); column 3 holds quads (4 cells); in general column k+1 holds 2^k cells. A check (✓) means the row combined into a larger group that round and so does not survive as a prime implicant.

Column 1 · 1 minterm each

0·	0000	✓

1·	0001	✓
1·	0010	✓

2·	0101	✓
2·	0110	✓

3·	0111	✓

6 rows · varCount=4

Column 2 · pairs · 2 minterms each

0·	000X	PI
0·	00X0	PI

1·	0X01	PI
1·	0X10	PI

2·	01X1	PI
2·	011X	PI

6 rows · varCount=4

Step 2 — Prime-implicant chart

Rows are prime implicants from Step 1. Columns are the original minterms. An × marks where a PI covers a minterm. Highlighted rows are essential (uniquely cover at least one minterm).

PI (pattern)	Term	m0	m1	m2	m5	m6	m7
000X	A'B'C'essential	×	×	·	·	·	·
00X0	A'B'D'	×	·	×	·	·	·
0X01	A'C'D	·	×	·	×	·	·
0X10	A'CD'essential	·	·	×	·	×	·
01X1	A'BDessential	·	·	·	×	·	×
011X	A'BC	·	·	·	·	×	×

Step 3 — Minimum SOP

F = A'B'C' + A'CD' + A'BD

3 terms, total 9 literals.

Quine–McCluskey algorithm

The Quine–McCluskey (QM) method is a tabular alternative to K-maps that scales to any number of variables. It is the basis of commercial logic synthesis tools and guaranteed to find the minimum SOP expression.

Three-stage process

Group minterms by their count of 1-bits (popcount).
Merge pairs from adjacent groups that differ by exactly one bit — producing prime implicants. Repeat until no more merges are possible.
Cover table: select the minimum set of prime implicants that covers every minterm. Essential PIs (covering a minterm no other PI covers) must be chosen first.

When to use QM vs K-map

K-maps are faster for 4 variables or fewer. QM handles 5+ variables where K-maps become unwieldy, and is the only systematic method for programmatic (computer-aided) minimisation.

Learn more → Karnaugh Maps — Learn

Quick experiments

Watch two terms merge. Enter minterms 0 and 1 of a 3-variable function. They differ only in the last bit, so they combine into 00– and one variable disappears. That single step is the whole algorithm, repeated.
Group by the number of ones. Terms can only combine if they differ in exactly one bit, which means their one-counts differ by exactly one. Sorting into groups by one-count is what makes the search efficient rather than exhaustive.
Spot an essential prime implicant. In the coverage chart, find a column with a single tick. The implicant owning that tick is essential — no other term covers that minterm, so it must be in the answer.
Go past what a K-map can handle. Enter a 5- or 6-variable function. A K-map becomes unreadable here, but the tabular method keeps working — which is why synthesis tools use this family of algorithms.
Let don't-cares shrink the result. Add a few don't-care terms. They can join groups to enlarge implicants but need no coverage of their own, so they often remove a literal for free.

Formula reference

Terms combine when they differ in one bit: $A B + A \bar{B} = A$
The differing variable is replaced by a dash.
Literals after combining: $\ell = n - k$
Merging 2^k terms removes k variables from an n-variable product.
Function as a sum of minterms: $F = \sum m(\ldots) + \sum d(\ldots)$
d terms are don't-cares: usable in groups, but not required to be covered.
Cover condition: $F = \sum_{i \in \text{cover}} P_i$
The chosen prime implicants must cover every required minterm.

Symbol	Meaning	Unit
$n$	Number of variables	—
$P_i$	Prime implicant	—
$m$	Minterm the function must cover	—
$d$	Don't-care term	—

Common mistakes

Combining terms that differ in more than one bit.
Only a single-bit difference cancels a variable. 0011 and 0000 differ in two positions and cannot merge directly — they need an intermediate term at each step.
Stopping at the prime implicants.
Finding prime implicants is only half the method. The coverage chart then selects a minimal subset; listing every prime implicant gives a correct but far from minimal expression.
Requiring don't-cares to be covered.
Don't-cares may join groups to enlarge them, but they never need covering themselves. Insisting on covering them adds terms that buy nothing.
Assuming the minimal cover is unique.
Once essential implicants are removed, what remains is a set-covering problem that can have several equally minimal answers. A different tool may return a different — equally valid — expression.
Comparing terms across non-adjacent groups.
Only groups whose one-counts differ by exactly one can produce a merge. Comparing every pair still works but wastes most of the effort, which defeats the point of the tabular arrangement.

Frequently asked questions

What is the Quine-McCluskey algorithm?

It is a tabular method for minimising Boolean functions. It repeatedly combines terms that differ in one bit to find prime implicants, then uses a coverage chart to pick the smallest set that covers every minterm.

Why use Quine-McCluskey instead of a Karnaugh map?

K-maps rely on spotting adjacency by eye and become impractical beyond four or five variables. Quine-McCluskey is a mechanical procedure that works for any number of variables and can be programmed, which is why synthesis tools use this family of methods.

What is a prime implicant?

A prime implicant is a product term that cannot be combined with any other term to remove a further variable. It corresponds to a maximal group on a K-map — one that cannot be made any larger.

What makes a prime implicant essential?

A prime implicant is essential when it is the only one covering some particular minterm. Essential prime implicants must appear in the final expression, because without them that minterm would go uncovered.

Does Quine-McCluskey always give the simplest expression?

It always finds the complete set of prime implicants, but choosing the minimum cover from them is a set-covering problem. When no essential implicants resolve it, several minimal solutions of equal cost may exist and one is picked arbitrarily.