Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 57 · Simplification

The Quine-McCluskey Method

Minimize Boolean functions with the Quine-McCluskey tabular method: group minterms, find prime implicants, use the chart, and run a full Python implementation.

Karnaugh maps are wonderful for three or four variables, but they have two limits. Past five or six variables the picture becomes unmanageable, and even on a four-variable map a tired human can miss a group. The Quine-McCluskey method (also called the tabular method) does the same job with a table and a fixed procedure. Because it is a procedure, a computer can run it, and it gives the same answer every time.

You will walk through the method by hand-sized steps, see why each step is correct, and then run a complete Python implementation that finds prime implicants, picks a cover, and checks the result against the truth table.

The one idea behind it

A K-map groups cells that differ in a single variable. Quine-McCluskey does exactly the same thing with binary strings. Two product terms that differ in exactly one position can be merged, because of the law X·A + X·A′ = X. For example 0110 (A′BCD′) and 0111 (A′BCD) merge into 011-, where the dash means "this variable no longer matters".

Repeat the merge on the merged terms. A term that can no longer be merged with anything is a prime implicant: a product term that implies the function and cannot be made shorter. The final answer is built only from prime implicants, which is the same rule you used with K-map groups.

Step 1: list and group minterms

Write each minterm (and each don't-care, if there are any) in binary. Then group them by the number of 1s. Only terms from neighboring groups can differ in exactly one bit, so this grouping saves you from comparing every pair.

Step 2: merge neighbors until nothing merges

Compare every term in one group with every term in the next group. If they differ in one bit, write the merged term (with a dash) in the next column and mark both originals as "used". Dashes must line up: 01-1 can only merge with another term that has its dash in the same place. Repeat on each new column. Every term that never got marked is a prime implicant.

The method in four moves

List Write minterms and don't-cares in binary.
Group Sort by the number of 1s.
Merge Combine terms that differ in one bit.
Cover Pick the fewest primes that hit every minterm.
1 / 2

The program below runs steps 1 and 2 on a four-variable function with minterms 0, 1, 2, 5, 6, 7, 8, 9, 10 and 14. It prints each column grouped by the number of 1s (a dash counts as 0 for grouping), then lists the prime implicants. The helper combine stores a term as a pair: the bit values and a mask that marks the dashes.

Python Find the prime implicants

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Column 0 holds the ten minterms. Column 1 has thirteen merged pairs, and column 2 has only three terms: -00-, -0-0 and --10. Those three are quads (two dashes), so each covers four minterms. The pairs that never merged further, 0-01, 01-1 and 011-, join them. Six prime implicants in total.

A nice detail in the code: diff & (diff - 1) == 0 is the classic test for "exactly one bit set", so it accepts a merge only when the two values differ in exactly one position. You met this trick in bit tricks.

Step 3: the prime implicant chart

The prime implicants cover the function, but you rarely need all of them. Build a chart with the prime implicants as rows and the original minterms as columns (never the don't-cares: you are not required to cover those). Mark a cell when the prime implicant covers the minterm.

  • A column with exactly one mark is a minterm that only one prime implicant can cover. That implicant is essential and must be in the answer. In the example, minterm 14 is covered only by --10 (CD′) and minterm 9 only by -00- (B′C′).
  • Cross out every minterm the essential implicants already cover. In the example this leaves minterms 5 and 7.
  • Choose the cheapest set of remaining implicants that covers what is left. Here 01-1 (A′BD) covers both 5 and 7 at once.

The result is F = B′C′ + CD′ + A′BD. Cheapest usually means fewest terms first, then fewest literals.

When no implicant is essential, or essentials leave a messy remainder, the choice is a small covering puzzle. Petrick's method solves it exactly by writing the coverage as a Boolean expression and multiplying it out. For small functions, trying combinations of increasing size (as the program below does) is simpler and just as correct.

The full algorithm in Python

This second program adds the chart, the essential-implicant rule and a search for the cheapest remaining cover. It also takes don't-cares: they are fed into the merging (so groups can grow bigger) but left out of the chart. At the end show verifies the answer by testing every input that is not a don't-care.

Python Minimize with a prime implicant chart

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Three things to notice in the output.

  1. The first function reproduces the hand result, B′C′ + CD′ + A′BD, with the two essential implicants flagged.
  2. In the second function the don't-cares 9 and 14 let AB′ and AC grow to cover more. Without 14 as a don't-care, the term AC could not be used at all, because it covers minterm 14.
  3. The third function has no essential prime implicant. Every minterm is covered by two implicants, forming a cycle. Two different covers cost the same: A′B′ + BC′ + AC and A′C′ + B′C + AB. Either is correct, and the program simply reports the first it finds. This is called a cyclic function, and it is exactly the case where Petrick's method earns its keep.

When K-maps stop working, and when this stops too

For five variables a K-map needs two layers and for six variables four, and spotting groups across layers is slow and error-prone. For seven or more variables it is not practical. Quine-McCluskey handles any number of variables in principle, but the number of minterms and prime implicants can grow exponentially, and the covering step is NP-hard in the worst case. Real design tools therefore use heuristic minimizers such as Espresso, which trade a guarantee of the absolute minimum for speed. The ideas, though, are the ones you just ran: merge neighbors, keep primes, cover the minterms.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. Which two terms can be merged in the first column of the method?

    Terms merge only when they differ in exactly one bit. 0101 and 0111 differ in the third bit, so they merge into 01-1.
  2. 2. What does a dash in a term such as 1-01 mean?

    A dash marks a variable that appeared in both complemented and uncomplemented form among the merged minterms, so it dropped out of the product term.
  3. 3. In the prime implicant chart, how do you find an essential prime implicant?

    If a minterm is covered by only one prime implicant, that implicant has to be in every valid cover, so it is essential.
  4. 4. Why are don't-cares left out of the chart's columns but included when merging?

    A don't-care may be treated as 0 or 1, whichever helps, so it can enlarge groups. Nothing forces the final circuit to cover it, so it is not a required column.
  5. 5. Why do real tools use heuristics such as Espresso instead of exact Quine-McCluskey for large functions?

    The prime implicant count can grow exponentially and exact covering is NP-hard, so large designs trade a guaranteed minimum for speed.

Summary

  • Quine-McCluskey is the K-map idea as a table: merge terms that differ in one bit, and write a dash for the dropped variable.
  • Group by the number of 1s so only neighboring groups need comparing.
  • Terms that cannot merge any further are the prime implicants.
  • Build a chart of primes against the original minterms; essential primes (the only cover of a minterm) are mandatory.
  • Don't-cares help the merging but are not required columns.
  • Cyclic charts have no essential primes and need Petrick's method or a search; large problems use heuristics such as Espresso.

Next: Half Adders and Full Adders.