Quine–McCluskey is a tabular way to minimise a Boolean sum of products. Rather than spotting rectangles on a Karnaugh map, it combines binary patterns that differ in one fixed bit, collects prime implicants, and solves a cover problem. Those are separate stages: finding every prime does not mean every prime belongs in the final answer.
The tables below were generated with the site's step-by-step minimisation library. Its cover selection is exact for the small functions used here: it minimises the number of product terms first, then the number of literals. Stable ordering chooses one answer when several covers tie. The existing Karnaugh-map solver remains useful for comparing the same Boolean function visually.
Specify the required ones and don't-cares
Use the variable order A, B, C, D, with A as the most significant bit:
- Required minterms: 4, 8, 10, 11, 12, 15.
- Don't-cares: 9, 14.
- All other input combinations must produce zero.
A don't-care is permission to use either output for that input. It is not another required one. Include it when forming larger implicants, then leave it out of the required columns of the prime chart. The same index cannot be both a required minterm and a don't-care.
The first table groups the union of those two sets by its number of one bits. The notation (d) marks a don't-care. In a pattern, a dash means that variable is absent from the product term; it is not a third input value.
Generate all combining rounds
Two patterns combine only when they have dashes in the same positions and differ in exactly one remaining position. Replace that differing position by a dash. Record both parents as used. Duplicate results can arise by different paths and represent one implicant, not separate choices for the cover.
Combining round 0
| Number of ones | Pattern | Represented indices |
|---|---|---|
| 1 | 0100 | 4 |
| 1 | 1000 | 8 |
| 2 | 1010 | 10 |
| 2 | 1100 | 12 |
| 2 | 1001 | 9 (d) |
| 3 | 1011 | 11 |
| 3 | 1110 | 14 (d) |
| 4 | 1111 | 15 |
| First pattern | Second pattern | Combined pattern |
|---|---|---|
| 0100 | 1100 | -100 |
| 1000 | 1010 | 10-0 |
| 1000 | 1100 | 1-00 |
| 1000 | 1001 | 100- |
| 1010 | 1011 | 101- |
| 1010 | 1110 | 1-10 |
| 1011 | 1111 | 1-11 |
| 1011 | 1001 | 10-1 |
| 1100 | 1110 | 11-0 |
| 1111 | 1110 | 111- |
Every pattern combines, so none becomes a prime in this round.
Combining round 1
| Number of ones | Pattern | Represented indices |
|---|---|---|
| 1 | -100 | 4, 12 |
| 1 | 10-0 | 8, 10 |
| 1 | 1-00 | 8, 12 |
| 1 | 100- | 8, 9 (d) |
| 2 | 101- | 10, 11 |
| 2 | 1-10 | 10, 14 (d) |
| 2 | 10-1 | 9 (d), 11 |
| 2 | 11-0 | 12, 14 (d) |
| 3 | 1-11 | 11, 15 |
| 3 | 111- | 14 (d), 15 |
| First pattern | Second pattern | Combined pattern |
|---|---|---|
| 10-0 | 10-1 | 10-- |
| 10-0 | 11-0 | 1--0 |
| 1-00 | 1-10 | 1--0 |
| 100- | 101- | 10-- |
| 101- | 111- | 1-1- |
| 1-10 | 1-11 | 1-1- |
Uncombined prime patterns: -100.
Combining round 2
| Number of ones | Pattern | Represented indices |
|---|---|---|
| 1 | 10-- | 8, 9 (d), 10, 11 |
| 1 | 1--0 | 8, 10, 12, 14 (d) |
| 2 | 1-1- | 10, 11, 14 (d), 15 |
No pair combines in this round.
Uncombined prime patterns: 10--, 1--0, 1-1-.
Only patterns left uncombined become primes at that round. A used pattern may be useful as an intermediate step, but a larger implicant already contains it. Continue until no new combinations remain; stopping after the first grouping can miss the simplification that matters.
Translate the prime patterns into products
Read bits left to right in the declared variable order. A one means the variable, a zero means its complement, and a dash contributes no literal. An apostrophe denotes Boolean complement here, not a derivative.
| Prime pattern | Product term | All represented indices |
|---|---|---|
| -100 | BC'D' | 4, 12 |
| 10-- | AB' | 8, 9, 10, 11 |
| 1--0 | AD' | 8, 10, 12, 14 |
| 1-1- | AC | 10, 11, 14, 15 |
These primes cover required ones and possibly don't-cares. None covers a required zero. The fact that a prime is valid does not yet prove it is essential, or that the minimum answer must contain it.
Build the prime-implicant chart
Now retain only required minterms as columns. An X means that prime covers the minterm; a dash means it does not.
| Prime | 4 | 8 | 10 | 11 | 12 | 15 |
|---|---|---|---|---|---|---|
| -100 | X | — | — | — | X | — |
| 10-- | — | X | X | X | — | — |
| 1--0 | — | X | X | — | X | — |
| 1-1- | — | — | X | X | — | X |
A prime is essential if some required column has an X in that row and no other row. The generated essentials are -100 (BC'D') and 1-1- (AC). Keep them because otherwise at least one required minterm would be uncovered.
After choosing essentials, cross out every required column they cover. Then solve the remaining cover problem using the other primes. Do not simply select the row with the largest number of X marks: that greedy decision does not always minimise the final expression. The library searches the remaining cover choices exactly.
Read the final minimum cover
The selected patterns are -100, 10--, 1-1-. Converting them to products gives:
F = BC'D' + AB' + AC
This selected cover has 3 product terms and 7 literals. Another cover can have the same cost; the method need not produce a unique printed expression. Compare Boolean behaviour and the stated optimisation criteria rather than assuming different-looking answers must disagree.
A useful final check is to enumerate every input combination. Required minterms must be covered, required zeros must not be covered, and don't-cares may take either value. A truth-table generator can help inspect a translated expression, while the minimiser's unit tests independently check these coverage conditions for this worked example.
What the tabulation method does not promise
Minimum SOP is a particular cost model. It does not automatically minimise a multi-level gate network, delay, switching activity or hazard risk. A circuit may deliberately retain an additional consensus term to avoid a static hazard even though that term is redundant in the Boolean cover.
The exponential part is choosing a cover, not merely writing binary numbers in groups. Large-variable functions can generate many primes. This walkthrough uses a small function so every intermediate row remains inspectable; it is not a promise that hand tabulation scales well to a large industrial design.
Common mistakes in an exam solution
- Reversing the variable order halfway through the calculation. State which variable owns each bit before grouping.
- Combining patterns whose dash positions differ. Matching one-bit counts alone is not sufficient.
- Treating duplicate combinations as distinct prime implicants.
- Calling every uncombined term an essential prime. Primality comes from the combining rounds; essentiality comes from a uniquely covered chart column.
- Adding don't-care columns to the required cover. They may help combine terms without forcing an output of one.
- Stopping after the essential primes without checking the remaining columns.
Keep the required-one set, the don't-care set and the required-zero set distinct all the way through. That separation makes the chart, the final expression and the verification agree.
For a related walkthrough, read Why K-Maps Use Gray Code Order.