The Quine-McCluskey method
The tabular way to minimise a boolean function: the same answer a Karnaugh map gives, reached by merging binary codes in a table instead of spotting rectangles in a picture. It works for any number of variables, which is why it is the algorithm behind the minimisers on this site.
What the method does
A sum of products lists one product term per minterm, which is correct but wasteful: any two minterms that differ in a single variable can be replaced by one term without that variable, since AB'C + ABC = AC. The Quine-McCluskey method, published by Willard Quine in 1952 and refined by Edward McCluskey in 1956, is that one rule applied exhaustively and then a second step that picks the fewest of the resulting terms. It has two halves:
- Find every prime implicant. Write the minterms in binary, merge any pair that differs in one bit into a term with a dash there, and repeat on the merged terms until nothing merges. Whatever never merged is a prime implicant: a product term that cannot be made any shorter.
- Choose a minimal cover. Draw a chart of primes against minterms. A prime that is the only cover of some minterm is essential and goes straight into the answer. The leftover minterms are covered by the smallest set of remaining primes, found with Petrick's method.
A Karnaugh map does both halves at once by eye, and for four variables or fewer that is faster. Past five, and for anything a program has to do, the table wins: it never gets harder to read, only longer.
A worked example
Every table below is computed from the function in these boxes. The default is a classic textbook example, f(A, B, C, D) = Σm(4, 8, 10, 11, 12, 15) + d(9, 14), chosen because it needs every step of the method. Change it and the whole worked example changes with it.
f(A, B, C, D) = Σm(4, 8, 10, 11, 12, 15) + d(9, 14) gives BC'D' + AC + AB'
Step 1: group the minterms by their number of 1s
Write every minterm and don't care in 4 bit binary and sort them into groups by how many 1s they contain. Two codes can only differ in exactly one bit if their counts of 1s differ by exactly one, so from now on only neighbouring groups ever need comparing. The don't cares join in here: a don't care may help form a larger term, and only later, in the chart, is it excused from being covered.
| 1s | Minterm | A | B | C | D | Merged? |
|---|---|---|---|---|---|---|
| 1 | m4 | 0 | 1 | 0 | 0 | ✓ |
| m8 | 1 | 0 | 0 | 0 | ✓ | |
| 2 | m9d | 1 | 0 | 0 | 1 | ✓ |
| m10 | 1 | 0 | 1 | 0 | ✓ | |
| m12 | 1 | 1 | 0 | 0 | ✓ | |
| 3 | m11 | 1 | 0 | 1 | 1 | ✓ |
| m14d | 1 | 1 | 1 | 0 | ✓ | |
| 4 | m15 | 1 | 1 | 1 | 1 | ✓ |
A small d marks a don't care. A tick means the code merged with another in the next step.
Step 2: merge pairs that differ in one bit
Compare each code in a group with every code in the group below it. When two differ in a single bit, write them as one term with a dash in that position and tick both originals: the tick means the term has been absorbed into something larger, so it cannot be prime. Then do the same to the new column, merging only terms whose dashes are in the same place, until a pass produces nothing. Anything left unticked at any stage is a prime implicant. This function takes 2 merging passes and produces 4 prime implicants.
| 1s | Minterms | A | B | C | D | Merged? |
|---|---|---|---|---|---|---|
| 1 | 4,12 | – | 1 | 0 | 0 | prime |
| 8,9 | 1 | 0 | 0 | – | ✓ | |
| 8,10 | 1 | 0 | – | 0 | ✓ | |
| 8,12 | 1 | – | 0 | 0 | ✓ | |
| 2 | 9,11 | 1 | 0 | – | 1 | ✓ |
| 10,11 | 1 | 0 | 1 | – | ✓ | |
| 10,14 | 1 | – | 1 | 0 | ✓ | |
| 12,14 | 1 | 1 | – | 0 | ✓ | |
| 3 | 11,15 | 1 | – | 1 | 1 | ✓ |
| 14,15 | 1 | 1 | 1 | – | ✓ |
| 1s | Minterms | A | B | C | D | Merged? |
|---|---|---|---|---|---|---|
| 1 | 8,9,10,11 | 1 | 0 | – | – | prime |
| 8,10,12,14 | 1 | – | – | 0 | prime | |
| 2 | 10,11,14,15 | 1 | – | 1 | – | prime |
A dash means the variable has dropped out. Reading the dashes back gives the product terms:
- –100 is BC'D'
- 10–– is AB'
- 1––0 is AD'
- 1–1– is AC
Step 3: the prime implicant chart
One row per prime implicant, one column per minterm, and a mark wherever the prime covers the minterm. The don't cares get no column: they were allowed to help build the primes, but nothing is obliged to cover them. The question the chart answers is which rows, taken together, put a mark in every column.
| Prime | Term | m4 | m8 | m10 | m11 | m12 | m15 |
|---|---|---|---|---|---|---|---|
| –100 | BC'D' | × | × | ||||
| 10–– | AB' | × | × | × | |||
| 1––0 | AD' | × | × | × | |||
| 1–1– | AC | × | × | × |
A mark in a circle is the only one in its column, which makes its row essential. Highlighted rows are the ones in the final answer; struck-through columns are covered by an essential prime.
Step 4: take the essential prime implicants
A column with a single mark can only be covered by that one row, so the row is essential and must appear in any minimal expression. Here 2 primes are essential: BC'D', AC. Cross off every column they cover, and one minterm is still uncovered: m8.
Step 5: cover what is left
For each uncovered minterm, write the sum of the primes that could cover it, then multiply those sums together and expand. Every product in the result is a valid cover; the shortest, with the fewest literals if two tie, is the minimal choice. That is Petrick's method, and it is just the distributive law with X + XY = X applied as you go.
Expanding gives 2 equally short covers, so the function has 2 minimal forms:
- BC'D' + AC + AB' shown above
- BC'D' + AC + AD'
Minimal sum of products f = BC'D' + AC + AB' 3 terms, down from 6 minterms
See the same function as a Karnaugh map: the groups it circles are a minimal cover of the same primes, chosen greedily, so it can pick a different one when two covers tie.
Karnaugh map or Quine-McCluskey?
| Karnaugh map | Quine-McCluskey | |
|---|---|---|
| How adjacency is found | By eye: Gray code ordering puts neighbours next to each other | By comparison: two codes that differ in one bit |
| Comfortable size | Up to 4 variables by hand, 5 or 6 with the solver here | Any number; the table just gets longer |
| Suits a program | Poorly: it is a visual method | Well: it is a list of mechanical steps |
| Result | The same minimal sum of products; the circled groups are the chosen prime implicants | |
| Cost for large functions | Impractical | Exponential in the worst case; real tools use heuristics such as Espresso |
The boolean algebra calculator on this site finds the primes this way for whatever expression you type, up to eight variables, then picks the cover greedily rather than with Petrick's method, and the Karnaugh map solver draws the primes it chooses as rectangles. The simplification examples reach the same answers by algebra, one law at a time.
Questions about the Quine-McCluskey method
What is the Quine-McCluskey method?
A procedure for finding a minimal sum of products for a boolean function. It lists the minterms in binary, repeatedly merges pairs that differ in one bit into terms with a dash in that position, keeps the terms that can no longer merge as prime implicants, and then chooses the fewest of those primes that between them cover every minterm. It gives the same answer as a Karnaugh map, but as a table rather than a picture, so it works for any number of variables and can be run by a computer.
When should you use Quine-McCluskey instead of a Karnaugh map?
When there are more than about five variables, when the function is given as a list of minterm numbers rather than a drawing, or when the minimisation has to be done by a program. A Karnaugh map is faster by hand for four variables or fewer because adjacency is visible; the tabular method is the same search done mechanically, so it does not get harder to read as the function grows, only longer.
What is a prime implicant?
An implicant is a product term that is 1 only where the function is 1 (or a don't care), so it can safely be part of a sum of products for it. A prime implicant is an implicant that cannot be made any larger: removing any literal from it would make it cover a 0. In the tabulation, the primes are exactly the rows that never got ticked, because nothing would merge with them.
What is an essential prime implicant?
A prime implicant that is the only one covering some minterm. That minterm has to be covered by something, and nothing else can do it, so every minimal expression must contain that prime. Finding the essentials first is what makes the chart manageable: the columns they cover are crossed off, and only the leftover minterms need a choice.
What is Petrick's method?
A systematic way to choose which of the non-essential primes to keep. For every minterm still uncovered, write a sum of the primes that cover it; multiply all those sums together; expand and simplify with X + XY = X. Each product term in the result is a valid cover, and the shortest ones, with the fewest literals as a tiebreak, are the minimal answers. When two products tie there are two equally good expressions, and either is correct.
How are don't cares handled in Quine-McCluskey?
They go into the tabulation as if they were 1s, so they can help form larger primes, but they are left out of the prime implicant chart, so nothing is obliged to cover them. That is exactly how a Karnaugh map treats an X: circle it when it enlarges a group, ignore it otherwise.
Why is the method rarely used for large functions?
The number of prime implicants can grow exponentially with the number of variables, and choosing a minimal cover from them is an NP-hard problem, so the exact method becomes slow past a dozen or so variables. Synthesis tools use heuristic minimisers descended from Espresso instead, which give a near-minimal answer quickly. For anything you would do by hand, Quine-McCluskey is exact and fast enough.