Quine–McCluskey method: meaning and examples

The Quine–McCluskey method is a tabular procedure for simplifying a Boolean function: list the minterms in binary, merge pairs that differ in one bit until no merge remains, and the survivors are the prime implicants; a cover table then selects among them.

Willard Quine described the method and Edward McCluskey made it a table-driven algorithm. The first phase groups minterms by their number of 1 bits and repeatedly combines entries from adjacent groups that differ in exactly one position, writing a dash where the bit was dropped; anything never combined is a prime implicant. The second phase builds a chart of prime implicants against minterms, takes the essential ones, and chooses the rest. Unlike a Karnaugh map it needs no picture, so it works for any number of variables, at a cost that grows quickly.

The artefact is the textbook example Σm(A, B, C, D; 0, 1, 2, 5, 6, 7, 8, 9, 10, 14). The canonical sum of products has 10 terms and 40 literals, as the converter's expansion shows. The engine's map, which reaches the same prime implicants by rectangles, counts 6 and derives the cover (NOT A AND B AND D) OR (NOT B AND NOT C) OR (C AND NOT D) from the groups 5 and 7, then 0, 1, 8 and 9, then 2, 6, 10 and 14: three terms in place of ten, equivalent on every assignment.

Quine–McCluskey is the basis of the prime-implicant method in synthesis tools and of the converter's prime-implicant fallback. It is exact, which is its strength and its limit: the number of prime implicants can grow exponentially, which is why large designs use heuristic tools instead. The term is confused with the Karnaugh map, which finds the same prime implicants by eye, and “the result” is sometimes assumed to be the only shortest form, which neither method promises.

Example

f := Σm(A, B, C, D; 0, 1, 2, 5, 6, 7, 8, 9, 10, 14) · output

Exact checks

Always true (tautology)? No Counterexample: A = F, B = F, C = T, D = T · Exhaustively checked and solver cross-checked · 4 rows

Always false (contradiction)? No Counterexample: A = F, B = F, C = F, D = F · Exhaustively checked and solver cross-checked · 1 rows

Can be true? Yes Example assignment: A = F, B = F, C = F, D = F · Exhaustively checked and solver cross-checked · 1 rows

Truth table (16 rows)

Quine–McCluskey method: meaning and examples
#	A	B	C	D	f
0	FALSE	FALSE	FALSE	FALSE	TRUE
1	FALSE	FALSE	FALSE	TRUE	TRUE
2	FALSE	FALSE	TRUE	FALSE	TRUE
3	FALSE	FALSE	TRUE	TRUE	FALSE
4	FALSE	TRUE	FALSE	FALSE	FALSE
5	FALSE	TRUE	FALSE	TRUE	TRUE
6	FALSE	TRUE	TRUE	FALSE	TRUE
7	FALSE	TRUE	TRUE	TRUE	TRUE
8	TRUE	FALSE	FALSE	FALSE	TRUE
9	TRUE	FALSE	FALSE	TRUE	TRUE
10	TRUE	FALSE	TRUE	FALSE	TRUE
11	TRUE	FALSE	TRUE	TRUE	FALSE
12	TRUE	TRUE	FALSE	FALSE	FALSE
13	TRUE	TRUE	FALSE	TRUE	FALSE
14	TRUE	TRUE	TRUE	FALSE	TRUE
15	TRUE	TRUE	TRUE	TRUE	FALSE

Plain-language reading

Beginnerf is true exactly when the truth-table row of (A, B, C, D) is one of the rows 0, 1, 2, 5, 6, 7, 8, 9, 10, and 14.
In every other case, f is false.
About the operators:
- Σm lists the truth-table rows (minterms) where the formula is true. Rows are numbered from 0 with the first listed input as the most significant bit.

Intermediatef is true exactly when the truth-table row of (A, B, C, D) is one of the rows 0, 1, 2, 5, 6, 7, 8, 9, 10, and 14.
In every other case, f is false.

Advancedf is true exactly when the truth-table row of (A, B, C, D) is one of the rows 0, 1, 2, 5, 6, 7, 8, 9, 10, and 14 [canonical sum of minterms (DNF)].
In every other case, f is false.
Formal notation: Σm(A, B, C, D; 0, 1, 2, 5, 6, 7, 8, 9, 10, 14)

Karnaugh map

AB \ CD

1m0

1m1

0m3

1m2

0m4

1m5

1m7

1m6

0m12

0m13

0m15

1m14

1m8

1m9

0m11

1m10

cells m5, m7NOT A AND B AND D
cells m0, m1, m8, m9NOT B AND NOT C
cells m2, m6, m10, m14C AND NOT D

(NOT A AND B AND D) OR (NOT B AND NOT C) OR (C AND NOT D) · Derived (NOT A AND B AND D) OR (NOT B AND NOT C) OR (C AND NOT D). Exactly equivalent on every assignment.

Normal forms

Conjunctive normal form (CNF)

(A OR B OR NOT C OR NOT D) AND (A OR NOT B OR C OR D) AND (NOT A OR B OR NOT C OR NOT D) AND (NOT A OR NOT B OR C OR D) AND (NOT A OR NOT B OR C OR NOT D) AND (NOT A OR NOT B OR NOT C OR NOT D)

6 clauses, 24 literals · complete · Minterm expansion ×1

Disjunctive normal form (DNF)

(A AND B AND C AND NOT D) OR (A AND NOT B AND C AND NOT D) OR (A AND NOT B AND NOT C AND D) OR (A AND NOT B AND NOT C AND NOT D) OR (NOT A AND B AND C AND D) OR (NOT A AND B AND C AND NOT D) OR (NOT A AND B AND NOT C AND D) OR (NOT A AND NOT B AND C AND NOT D) OR (NOT A AND NOT B AND NOT C AND D) OR (NOT A AND NOT B AND NOT C AND NOT D)

10 terms, 40 literals · complete · Minterm expansion ×1

The common slip

Stopping after the merge phase. The list of prime implicants is not the answer; the cover table is where redundant ones are dropped. On this page 6 prime implicants were found and 3 were needed, and the other 3 are correct terms that add nothing.

Questions

When does Quine–McCluskey beat a Karnaugh map?

Beyond four variables, where a map stops being readable, and whenever the work must be done by a program rather than by eye. For up to four variables the two find the same prime implicants, as this page's map shows; the comparison page sets them side by side.

Glossary

Generated from the Tangibool engine, semantics tangibool-semantics/1, engine 1.0.0, build 2026-11-07. Every table, map, simplification and verdict on these pages was computed by the Tangibool engine when the site was built, and every claim was re-checked by the same exact checker the app uses. Limits are stated where they apply. © 2026 Foreranger LTD.