Quine–McCluskey is a systematic Boolean minimization method that turns the visual grouping idea behind a Karnaugh map into a tabular procedure. It is useful when a map becomes difficult to inspect, especially as the number of variables grows. The method first combines minterms that differ in one bit, repeats that combination process to form larger implicants, and then selects a cover of the required minterms.
This article works through a four-variable function in full. It shows how to group terms by their number of 1-bits, mark combined terms, identify prime implicants, build a coverage chart, and derive a minimum SOP expression. It also calls out common sources of errors: combining terms with different fixed bits, forgetting which variable a dash represents, and assuming every prime implicant belongs in the final answer.
Function and binary rows
Minimize F(A,B,C,D)=Σm(0,1,2,5,6,7,8,9,10,14). There are four inputs, so write each minterm as four bits in the order ABCD. The minterms are: 0=0000, 1=0001, 2=0010, 5=0101, 6=0110, 7=0111, 8=1000, 9=1001, 10=1010, and 14=1110. There are no don't-care inputs in this example, so every implicant must be contained entirely within these ten rows.
Quine–McCluskey begins by grouping the binary rows by how many 1s they contain. The zero-one-count is a convenient way to find possible adjacent pairs: two minterms differing in one bit always have counts that differ by exactly one. The groups are:
| Number of 1s | Minterm | ABCD |
|---|---|---|
| 0 | 0 | 0000 |
| 1 | 1, 2, 8 | 0001, 0010, 1000 |
| 2 | 5, 6, 9, 10 | 0101, 0110, 1001, 1010 |
| 3 | 7, 14 | 0111, 1110 |
To combine two rows, compare their bit strings position by position. They must differ in exactly one position, and every other position must match. Replace the differing bit with a dash. For example, 0000 and 0001 combine as 000-, which represents minterms 0 and 1. The dash means D can be either 0 or 1; the other bits remain fixed. Rows differing in two or more positions cannot be combined in this round.
First combination round
Compare each group with the next group by 1-count. From group 0 and group 1, 0000 combines with 0001 to produce 000-. It also combines with 0010 to produce 00-0, and with 1000 to produce -000. From group 1 and group 2, the valid pairs are 0001 with 0101 (0-01), 0001 with 1001 (-001), 0010 with 0110 (0-10), 0010 with 1010 (-010), 1000 with 1001 (100-), and 1000 with 1010 (10-0).
From group 2 and group 3, 0101 combines with 0111 to form 01-1. 0110 combines with 0111 to form 011-, and 0110 combines with 1110 to form -110. 1010 combines with 1110 to form 1-10. The remaining candidates do not match in every other bit position, so they are not combinable. Record each combined result together with the pair of minterms it covers. Mark both source minterms as combined; an uncombined minterm at the end of all rounds would itself be a prime implicant.
For clarity, the first-round terms and coverage are: 000-={0,1}; 00-0={0,2}; -000={0,8}; 0-01={1,5}; -001={1,9}; 0-10={2,6}; -010={2,10}; 100-={8,9}; 10-0={8,10}; 01-1={5,7}; 011-={6,7}; -110={6,14}; and 1-10={10,14}. A dash always marks one variable position; it is not a wildcard that can move when the term is compared again.
Combine the pairs again
Now combine first-round terms that have dashes in the same position and differ in exactly one of their remaining fixed bits. Their dash pattern must match. For example, 000- and 100- have the dash in the D position and differ only in A; they combine to -00-, covering 0,1,8,9. Likewise, 00-0 and 10-0 combine to -0-0, covering 0,2,8,10. This second round has groups of four minterms.
The complete second round has three distinct valid four-cell patterns. 000- combines with 100- to form -00-, covering 0,1,8,9. 00-0 combines with 10-0 to form -0-0, covering 0,2,8,10. Finally, both 0-10 with 1-10 and -010 with -110 produce the same pattern --10, covering 2,6,10,14. Keep just one copy of --10 in the prime list, while recognizing that it can be reached by two combination paths.
Some plausible pairs cannot be combined. For example, 000- and 00-0 have their dashes in different positions, so they do not represent compatible cubes and cannot produce 00--. The terms 0-01, -001, 01-1, 011-, and 1-10 cannot be expanded further into valid cubes for this on-set, so they remain prime implicants. The complete prime list is determined by tracking every pattern and marking which terms combine at least once, not by selecting only the largest rows you happened to notice.
Collect prime implicants
In this example the prime implicants are:
| Pattern | Covered minterms | Term |
|---|---|---|
| 011- | 6, 7 | A′BC |
| 01-1 | 5, 7 | A′BD |
| 0-01 | 1, 5 | A′C′D |
| -00- | 0, 1, 8, 9 | B′C′ |
| -0-0 | 0, 2, 8, 10 | B′D′ |
| --10 | 2, 6, 10, 14 | CD′ |
To translate a pattern into a product term, retain only the bits that are fixed. A 0 becomes a complemented variable, a 1 becomes an uncomplemented variable, and a dash removes that variable. For -0-0, B=0 and D=0 stay fixed, while A and C vary, so the term is B′D′. The pattern --10 fixes C=1 and D=0, giving CD′. Each term covers 2 to the number-of-dashes minterms: two dashes mean four cells.
Select a minimum cover
Create one chart column for each on-set minterm: 0, 1, 2, 5, 6, 7, 8, 9, 10, and 14. Mark which prime implicants cover each column. Minterm 9 is covered only by -00-, so B′C′ is essential. Minterm 14 is covered only by --10, so CD′ is essential. These two rows cover 0,1,8,9 and 2,6,10,14, leaving minterms 5 and 7 uncovered.
The remaining cells 5 and 7 are covered together by 01-1, which translates to A′BD. Adding this implicant completes the cover. The final expression is F = B′C′ + CD′ + A′BD. The selected groups cover {0,1,8,9}, {2,6,10,14}, and {5,7}. Their union is the complete on-set. No two-row cover is possible: 9 forces B′C′ and 14 forces CD′, but these two forced rows leave 5 and 7. Therefore three terms are necessary and sufficient.
Verify the expression
Check each selected term by its pattern. B′C′ matches minterms 0,1,8,9. CD′ matches 2,6,10,14. A′BD matches 5,7. The union is {0,1,2,5,6,7,8,9,10,14}, precisely the original list. No selected cube includes an unlisted row. This direct coverage verification is faster and safer than expanding a long algebraic expression into a truth table after the fact.
It is also helpful to test the listed zeros. The complement set is {3,4,11,12,13,15}. For m3=0011, B′C′ is false because C=1, CD′ is false because D=1, and A′BD is false because B=0. For m4=0100, B′C′ is false because B=1, CD′ is false because C=0, and A′BD is false because D=0. Spot-check remaining zeros, or evaluate every assignment if implementing the result in software.
The tabulation process and the cover selection are separate. The first phase proves which maximal implicants are available; the second finds a cover. For a deeper explanation of alternative minimum covers, see why different minimum K-map answers can exist. For a visual comparison of manual maps and tabulation, see Quine–McCluskey vs. Karnaugh maps.
Common tabulation errors
- Combining terms with more than one mismatch: only one fixed bit may differ.
- Combining unlike dash patterns: the dash must represent the same variable in both terms.
- Forgetting to reject a cube containing a zero: every covered minterm must be in the on-set or a declared don't-care.
- Dropping source coverage: keep the minterm set attached to each pattern through every round.
- Writing a term from the wrong bit position: state the variable order once and keep it visible.
- Choosing every prime implicant: primes are candidates; a cover may need only a subset.
- Skipping final coverage verification: the selected rows must cover all listed minterms.
One subtlety in tabulation is duplicate patterns produced by different combination paths. If two derivations yield the same dash pattern, keep one copy of the implicant but preserve its full coverage. Duplicate paths are evidence of overlapping cubes, not separate terms. Another subtlety is don't-care treatment: a don't-care may help create a larger implicant, but it is not a required chart column. It can be used for grouping without forcing the final expression to output 1 there.
When to use the method
A four-variable K-map is usually quicker by hand. Quine–McCluskey becomes more attractive when the function is specified as a long list of minterms, when the number of inputs exceeds the comfortable visual range, or when you want a reproducible exact procedure. It is also a useful teaching bridge: every dash pattern corresponds to a K-map group, and the coverage chart corresponds to the final group-selection question.
The exact tabulation algorithm can still grow rapidly. The number of prime implicants may become large, and selecting a minimum cover is computationally difficult in the general case. Larger logic synthesis tools often use heuristic minimizers such as Espresso rather than enumerate every exact cover. Quine–McCluskey is valuable for small functions and transparent examples; it is not a promise that brute-force tabulation scales without limit.
For manual work, label rows by binary pattern, show each combination round, and circle patterns that were never combined again. For an implementation, preserve the source minterms and test the final expression exhaustively for small n. That combination of structured derivation and independent verification makes the answer easier to review and reduces transcription errors.
Practice prompt
Try minimizing H(A,B,C)=Σm(0,1,2,5,6,7). First write three-bit forms and group them by 1-count. Combine adjacent rows, repeat with matching dash positions, then build the prime chart. Before deriving an expression, check whether some minterm appears in exactly one prime row. After selecting a cover, expand each dash pattern to its assignments and compare the union with the original six indices.
Quine–McCluskey is a repeatable form of the same reasoning a K-map encourages: combine adjacent assignments until no more expansion is possible, then choose a complete set of implicants. The method is most reliable when every round records its coverage and the last expression is checked against the original function.