Skip to content
BetterDL

Quine–McCluskey method

Also called: Quine-McCluskey method, Quine-McCluskey, tabulation method, tabular method, QM method

A step-by-step tabular algorithm that finds all prime implicants by combining minterms in rounds, then picks a minimal cover. It works for any number of variables.

The Quine–McCluskey method is algebraic simplification turned into a mechanical procedure, so it works for any number of variables and can be run by a computer.

Stage 1: find every prime implicant.

  1. Write each minterm (and don't-care) in binary. Group them by how many 1s they have; only neighboring groups can differ in exactly one bit.
  2. Compare every term in one group with every term in the next. If two differ in exactly one bit, combine them, putting a dash there, and tick both.
  3. Repeat with the new dashed terms. Two terms combine only if their dashes are in the same places.
  4. Any term never ticked is a prime implicant.

Stage 2: choose a minimal cover. Make a chart of which primes cover which minterms (not the don't-cares). Take the essential ones first, then add the cheapest primes for the minterms left.

It does exactly what a karnaugh map does by eye, but without relying on pattern-spotting. In practice, large problems use faster heuristic tools, built on the same ideas.

Worked example

Example

A small run

Minimize F(A, B, C) = Σm(0, 1, 2, 5, 7).

  1. 1.

    Group by number of 1s: {0: 000}, {1: 001, 2: 010}, {5: 101}, {7: 111}.

  2. 2.

    Round 1: 0 + 1 → 00-, 0 + 2 → 0-0, 1 + 5 → -01, 5 + 7 → 1-1. Every minterm is ticked.

  3. 3.

    Round 2: no two of these have their dashes in the same place, so nothing combines. The primes are , , and .

  4. 4.

    Cover: row 2 is only in and row 7 only in , so both are essential. They cover 0, 2, 5 and 7.

  5. 5.

    Row 1 still needs a prime: or . Either works, so F has two minimal SOPs, such as .

Common mistakes

  • Comparing terms in groups that are not neighbors. Their 1-counts differ by two or more, so they can't be adjacent.

  • Combining dashed terms whose dashes are in different positions.

  • Including every prime in the answer instead of solving the cover.

Practice Quine–McCluskey method

Interactive questions with instant feedback and a worked solution for every wrong answer.

Learn it step by step

Quine–McCluskey method is taught in Boolean Simplification and Karnaugh Maps.