Chapter 10 of 32

Quine-McCluskey Method

Karnaugh maps are wonderful for 3 or 4 variables, workable for 5, and hopeless beyond 6: you cannot reliably spot adjacencies across stacked maps, and a computer cannot "look" at a picture at all. We need a method that is purely mechanical, works for any number of variables, and is guaranteed to find the minimum. That method is the Quine-McCluskey method, also called the tabulation method.

It was developed by the philosopher and logician Willard Van Orman Quine (1952) and extended into a practical tabular procedure by Edward McCluskey (1956). It uses exactly the same ideas as Karnaugh Maps (prime implicants, essential prime implicants, the combining law XY + XY′ = X) and handles don't-cares exactly as in K-Maps with Don't-Care Conditions. The difference is that adjacency is checked by comparing binary strings instead of looking at a map.

The Quine-McCluskey method minimises a Boolean function in two phases: (1) find all prime implicants by repeatedly merging terms that differ in exactly one bit, and (2) choose a minimum set of prime implicants that covers every minterm, using a prime implicant chart.

All tables, prime implicants and final answers in this chapter were generated and checked by computer, and the complete Python program is included below.


The Core Idea

Write minterms in binary. Two terms can merge when they differ in exactly one bit position; that position becomes a dash (–), meaning "this variable is eliminated".

m5 = 0101  (A′BC′D)
m7 = 0111  (A′BCD)
              differ only in C
merged: 01–1  (A′BD)             because A′BC′D + A′BCD = A′BD(C′ + C) = A′BD

Merged terms can merge again if their dashes are in the same positions and the remaining bits differ in exactly one place:

0–01 (m1, m5)  and  1–01 (m9, m13)  →  ––01 (m1, m5, m9, m13) = C′D

A term that can no longer merge with anything is a prime implicant. That is the whole of phase 1.

Why Group by the Number of 1s?

Two binary strings that differ in exactly one bit must have counts of 1s that differ by exactly one. So we sort terms into groups by their number of 1s, and only compare each group with the next group. This cuts down the comparisons enormously and is the "tabular" trick that makes the method practical by hand.

A handy decimal shortcut for column 1: a minterm a in one group merges with a minterm b in the next group exactly when b − a is a power of 2 (1, 2, 4, 8, ...). For example 1 and 5 merge (difference 4), but 1 and 6 do not (difference 5).


The Procedure

  1. List all minterms and don't-cares in binary, grouped by the number of 1s.

  2. Compare every term in group i with every term in group i + 1. If they differ in one bit, write the merged term in the next column and tick (✓) both parents.

  3. Repeat on the new column (dashes must line up) until no more merges are possible. Remove duplicate terms.

  4. Every term never ticked is a prime implicant.

  5. Draw the prime implicant chart: one row per PI, one column per required minterm (not don't-cares).

  6. Pick the essential PIs: any column with a single X identifies one.

  7. Remove the covered columns. Cover what remains using dominance rules or Petrick's method, choosing the cheapest option.


Worked Example 1: Full Tabulation

Minimise F(A, B, C, D) = Σm(0, 1, 2, 5, 6, 7, 8, 9, 10, 14).

Column 1: Minterms Grouped by Number of 1s

Group  Minterm  ABCD
  0       0     0000  ✓
-------------------------
  1       1     0001  ✓
          2     0010  ✓
          8     1000  ✓
-------------------------
  2       5     0101  ✓
          6     0110  ✓
          9     1001  ✓
         10     1010  ✓
-------------------------
  3       7     0111  ✓
         14     1110  ✓

Column 2: Pairs

Compare group 0 with group 1, group 1 with group 2, and group 2 with group 3:

Group  Minterms  ABCD
  0      0,1     000–  ✓
         0,2     00–0  ✓
         0,8     –000  ✓
-------------------------
  1      1,5     0–01      ← cannot merge further: PI
         1,9     –001  ✓
         2,6     0–10  ✓
         2,10    –010  ✓
         8,9     100–  ✓
         8,10    10–0  ✓
-------------------------
  2      5,7     01–1      ← PI
         6,7     011–      ← PI
         6,14    –110  ✓
         10,14   1–10  ✓

Every minterm in column 1 merged with something, so all are ticked. In column 2, the pairs (1,5), (5,7) and (6,7) find no partner with matching dashes, so they are prime implicants.

Column 3: Quads

Group  Minterms     ABCD
  0    0,1,8,9      –00–     from (0,1)+(8,9), also from (0,8)+(1,9)
       0,2,8,10     –0–0     from (0,2)+(8,10), also from (0,8)+(2,10)
-------------------------
  1    2,6,10,14    ––10     from (2,6)+(10,14), also from (2,10)+(6,14)

Each quad appears twice (two different ways of pairing); we keep one copy. No two quads can merge (their dashes are in different places), so all three are prime implicants.

The Prime Implicants

Label

Pattern

Term

Covers

P1

–00–

B′C′

0, 1, 8, 9

P2

–0–0

B′D′

0, 2, 8, 10

P3

––10

CD′

2, 6, 10, 14

P4

0–01

A′C′D

1, 5

P5

01–1

A′BD

5, 7

P6

011–

A′BC

6, 7

To read a pattern: 1 → plain variable, 0 → complemented variable, – → variable dropped.

The Prime Implicant Chart

PI

0

1

2

5

6

7

8

9

10

14

P1 B′C′

X

X

X

X

P2 B′D′

X

X

X

X

P3 CD′

X

X

X

X

P4 A′C′D

X

X

P5 A′BD

X

X

P6 A′BC

X

X

Step 1: Essential Prime Implicants

  • Column 9 has a single X, in row P1, so P1 = B′C′ is essential.

  • Column 14 has a single X, in row P3, so P3 = CD′ is essential.

Together they cover minterms 0, 1, 2, 6, 8, 9, 10, 14. Only 5 and 7 remain.

Step 2: The Reduced Chart and Dominance

PI

5

7

P2 B′D′

P4 A′C′D

X

P5 A′BD

X

X

P6 A′BC

X

P2 covers nothing that is left, so it is dropped. Row P5 dominates rows P4 and P6: it covers everything they cover, at the same cost (3 literals each). So we keep P5 and drop P4 and P6. P5 alone covers 5 and 7.

F = B′C′ + CD′ + A′BD          (3 terms, 7 literals)

Notice that B′D′ is a perfectly good prime implicant (a 4-cell group on the K-map) but does not appear in the answer, exactly like the redundant centre square in Karnaugh Maps.

Dominance Rules in General

Rule

Statement

Action

Row dominance

PI row R1 covers every remaining minterm that R2 covers, and R1 costs no more than R2

Delete row R2

Column dominance

Every PI that covers minterm column c1 also covers column c2 (c2 has all the X positions of c1, and possibly more)

Delete column c2: covering c1 automatically covers c2

After deleting rows or columns, new essential PIs may appear ("secondary essential" PIs). Repeat until the chart is empty or no rule applies. If no rule applies, the chart is cyclic, and we use Petrick's method.


Worked Example 2: With Don't-Cares

Minimise F(A, B, C, D) = Σm(4, 8, 10, 11, 12, 15) + d(9, 14).

In phase 1, don't-cares are included as if they were 1s, because they may help form larger groups:

Column 1                Column 2                  Column 3
g1   4   0100 ✓         4,12    –100   PI         8,9,10,11     10––   PI
     8   1000 ✓         8,9     100–  ✓           8,10,12,14    1––0   PI
g2   9   1001 ✓         8,10    10–0  ✓           10,11,14,15   1–1–   PI
    10   1010 ✓         8,12    1–00  ✓
    12   1100 ✓         9,11    10–1  ✓
g3  11   1011 ✓         10,11   101–  ✓
    14   1110 ✓         10,14   1–10  ✓
g4  15   1111 ✓         12,14   11–0  ✓
                        11,15   1–11  ✓
                        14,15   111–  ✓

Prime implicants: BC′D′ (4, 12), AB′ (8, 9, 10, 11), AD′ (8, 10, 12, 14), AC (10, 11, 14, 15).

In phase 2, the chart has columns for the required minterms only (4, 8, 10, 11, 12, 15). Don't-cares 9 and 14 do not need to be covered:

PI

4

8

10

11

12

15

BC′D′

X

X

AB′

X

X

X

AD′

X

X

X

AC

X

X

X

  • Column 4 → BC′D′ is essential (also covers 12).

  • Column 15 → AC is essential (also covers 10 and 11).

  • Only 8 is left, and AB′ and AD′ both cover it at the same cost.

F = BC′D′ + AC + AB′      or      F = BC′D′ + AC + AD′      (each 3 terms, 7 literals)

Petrick's Method for Cyclic Charts

Sometimes no essential PI exists and no dominance rule helps. Stanley Petrick (1956) turned the covering problem into Boolean algebra: write, for each minterm, the OR of the PIs that cover it, AND all of these together, and multiply out. Each product term of the result is a complete cover.

Worked Example 3

F(A, B, C) = Σm(0, 1, 2, 5, 6, 7), the cyclic function from Karnaugh Maps. Phase 1 gives six prime implicants, all pairs:

a = A′B′ (0, 1)    b = A′C′ (0, 2)    c = B′C (1, 5)
d = BC′  (2, 6)    e = AC   (5, 7)    f = AB  (6, 7)

Every minterm is covered by exactly two PIs, so there is no essential PI. Petrick's expression says "m0 must be covered (a or b) AND m1 must be covered (a or c) AND ...":

P = (a + b)(a + c)(b + d)(c + e)(d + f)(e + f)
     m0      m1      m2      m5      m6      m7

Use (X + Y)(X + Z) = X + YZ on pairs sharing a letter:
(a + b)(a + c) = a + bc
(b + d)(d + f) = d + bf
(c + e)(e + f) = e + cf

P = (a + bc)(d + bf)(e + cf)
  = (ad + abf + bcd + bcf)(e + cf)
  = ade + acdf + abef + abcf + bcde + bcdf + bcef + bcf
  = ade + bcf + abef + acdf + bcde          absorption: bcf absorbs abcf, bcdf, bcef

Each product is a valid cover. The cheapest ones use 3 PIs:

ade → F = A′B′ + BC′ + AC
bcf → F = A′C′ + B′C + AB

Both are minimal (3 terms, 6 literals), matching the two answers we found on the K-map. Petrick's method is exact, but the product can explode in size for large charts, so it is used only on the small cyclic core left after essential PIs and dominance.


A Complete Program

Because every step is mechanical, Quine-McCluskey is easy to program. This Python implementation finds the prime implicants, the essential ones, and then the cheapest set of remaining PIs by trying all small combinations (a brute-force version of Petrick's method, fine for textbook-size problems):

from itertools import combinations

def combine(a, b):
    """Merge two patterns like '0101' and '0111' into '01-1', or return None."""
    diff = [i for i in range(len(a)) if a[i] != b[i]]
    if len(diff) == 1 and a[diff[0]] != '-' and b[diff[0]] != '-':
        i = diff[0]
        return a[:i] + '-' + a[i + 1:]
    return None

def prime_implicants(n, minterms, dontcares):
    # Each entry: pattern -> set of minterms it covers
    current = {format(m, f'0{n}b'): {m} for m in minterms + dontcares}
    primes = {}
    while current:
        merged, used = {}, set()
        for a, b in combinations(current, 2):
            if abs(a.count('1') - b.count('1')) != 1:
                continue                      # only neighbouring groups can merge
            c = combine(a, b)
            if c:
                merged[c] = current[a] | current[b]
                used.update([a, b])
        for p, cov in current.items():
            if p not in used:
                primes[p] = cov               # could not be merged: prime
        current = merged
    return primes

def to_term(p, names='ABCDEFGH'):
    t = ''.join(v + ("'" if bit == '0' else '') for v, bit in zip(names, p) if bit != '-')
    return t or '1'

def minimise(n, minterms, dontcares=()):
    minterms, dontcares = list(minterms), list(dontcares)
    primes = prime_implicants(n, minterms, dontcares)
    print("Prime implicants:")
    for p, cov in sorted(primes.items(), key=lambda x: sorted(x[1])):
        print(f"  {p}  {to_term(p):6} covers {sorted(cov)}")

    # Essential PIs: the only PI covering some required minterm
    essential = set()
    for m in minterms:
        covering = [p for p in primes if m in primes[p]]
        if len(covering) == 1:
            essential.add(covering[0])
    print("Essential:", ', '.join(to_term(p) for p in sorted(essential)) or 'none')

    left = set(minterms) - set().union(*(primes[p] for p in essential))
    others = [p for p in primes if p not in essential]
    # Smallest set of remaining PIs that covers what is left (fewest terms, then literals)
    best = []
    for k in range(0, len(others) + 1):
        for extra in combinations(others, k):
            if left <= set().union(set(), *(primes[p] for p in extra)):
                best.append(extra)
        if best:
            break
    cost = lambda ex: sum(len(p) - p.count('-') for p in ex)
    low = min(cost(ex) for ex in best)
    for ex in best:
        if cost(ex) == low:
            terms = sorted(essential) + list(ex)
            print("Minimal SOP: F =", ' + '.join(to_term(p) for p in terms))

print("== F(A,B,C,D) = sum m(0,1,2,5,6,7,8,9,10,14)")
minimise(4, [0, 1, 2, 5, 6, 7, 8, 9, 10, 14])
print("\n== F(A,B,C,D) = sum m(4,8,10,11,12,15) + d(9,14)")
minimise(4, [4, 8, 10, 11, 12, 15], [9, 14])
print("\n== F(A,B,C) = sum m(0,1,2,5,6,7)")
minimise(3, [0, 1, 2, 5, 6, 7])

Output:

== F(A,B,C,D) = sum m(0,1,2,5,6,7,8,9,10,14)
Prime implicants:
  -00-  B'C'   covers [0, 1, 8, 9]
  -0-0  B'D'   covers [0, 2, 8, 10]
  0-01  A'C'D  covers [1, 5]
  --10  CD'    covers [2, 6, 10, 14]
  01-1  A'BD   covers [5, 7]
  011-  A'BC   covers [6, 7]
Essential: CD', B'C'
Minimal SOP: F = CD' + B'C' + A'BD

== F(A,B,C,D) = sum m(4,8,10,11,12,15) + d(9,14)
Prime implicants:
  -100  BC'D'  covers [4, 12]
  10--  AB'    covers [8, 9, 10, 11]
  1--0  AD'    covers [8, 10, 12, 14]
  1-1-  AC     covers [10, 11, 14, 15]
Essential: BC'D', AC
Minimal SOP: F = BC'D' + AC + AB'
Minimal SOP: F = BC'D' + AC + AD'

== F(A,B,C) = sum m(0,1,2,5,6,7)
Prime implicants:
  00-  A'B'   covers [0, 1]
  0-0  A'C'   covers [0, 2]
  -01  B'C    covers [1, 5]
  -10  BC'    covers [2, 6]
  1-1  AC     covers [5, 7]
  11-  AB     covers [6, 7]
Essential: none
Minimal SOP: F = A'B' + BC' + AC
Minimal SOP: F = A'C' + B'C + AB

The program reproduces all three worked examples, including both minimal answers for Examples 2 and 3. Note that the essential PIs are printed in the order of their binary patterns, which is why CD′ appears before B′C′.


K-Map vs Quine-McCluskey

Aspect

Karnaugh map

Quine-McCluskey

Nature

Graphical, relies on pattern spotting

Tabular, purely mechanical

Practical size

Up to 4–5 (at most 6) variables

Any number in principle (limited by time and memory)

Finds all prime implicants?

Only if you spot them all

Yes, guaranteed

Suitable for computers?

No

Yes

Speed by hand

Fast

Slow and error-prone for large problems

Don't-cares

Use X cells when helpful

Include in phase 1, exclude from the chart

Limits of Exact Minimisation

Quine-McCluskey always finds a minimum two-level SOP, but it does not scale. A function of n variables can have a very large number of prime implicants (it grows exponentially with n; there are 3n possible patterns over {0, 1, –}), and the covering step is the set cover problem, which is NP-hard. For this reason, real logic-synthesis tools use heuristic minimisers such as Espresso (developed by Robert Brayton and colleagues at IBM and UC Berkeley in the 1980s), which find near-minimal answers quickly without listing every prime implicant. Modern synthesis tools also go beyond two levels to multi-level logic. Quine-McCluskey remains the reference algorithm that defines what "minimal" means and the one examined in GATE and university papers.


Common Mistakes

  • Comparing non-adjacent groups. Only groups whose 1-counts differ by exactly one can merge.

  • Merging terms with dashes in different positions. 0–01 and 01–1 cannot merge, even though they differ in "two places only".

  • Forgetting to tick both parents. An unticked term is taken as a prime implicant, so a missed tick adds a false PI.

  • Keeping duplicate quads. The same term is produced by different pairings; list it once.

  • Putting don't-cares in the chart. They are used in phase 1 but are not columns in phase 2.

  • Stopping after essential PIs. Check whether any required minterms remain uncovered.

  • Applying row dominance without comparing cost. A dominating row with more literals is not automatically better.


Interview and GATE-Style Questions

Q1. Can minterms 3 (0011) and 12 (1100) be combined in the first step?

No. They are in the same group (two 1s each) and differ in all four bits. Only terms that differ in exactly one bit can merge.

Q2. Can 01–1 and 0–01 be merged?

No. Their dashes are in different positions, so they do not represent cubes of the same shape. Only terms with dashes in identical positions and exactly one other differing bit can merge.

Q3. How are don't-care terms handled in the Quine-McCluskey method?

They are included in the tabulation (phase 1) so they can help form larger prime implicants, but they are left out of the prime implicant chart (phase 2) because they do not need to be covered.

Q4. For F(A, B, C, D) = Σm(0, 1, 2, 5, 6, 7, 8, 9, 10, 14), how many prime implicants and essential prime implicants are there?

Six prime implicants (B′C′, B′D′, CD′, A′C′D, A′BD, A′BC) and two essential ones (B′C′ and CD′). The minimal SOP is B′C′ + CD′ + A′BD.

Q5. What is Petrick's method used for?

Finding all minimum covers of a prime implicant chart, especially a cyclic one with no essential PIs. It writes the covering condition as a product of sums of PIs, multiplies it out into SOP, and picks the product terms with the fewest PIs (and literals).

Q6. Why does nobody use plain Quine-McCluskey for a 32-input function?

The number of prime implicants can grow exponentially with the number of variables, and choosing the minimum cover is NP-hard (set cover). Heuristic tools such as Espresso are used instead.

Q7. In column 1, minterm 6 is in group 2. Which minterms of group 3 can it combine with, among 7, 11, 13, 14?

Using the decimal rule (difference must be a power of 2): 7 − 6 = 1 ✓ and 14 − 6 = 8 ✓. 11 − 6 = 5 and 13 − 6 = 7 are not powers of 2. So 6 combines with 7 (011–) and 14 (–110).


Summary

  • Quine-McCluskey is the tabular, computer-friendly version of K-map minimisation and works for any number of variables.

  • Phase 1: group minterms and don't-cares by number of 1s, merge neighbouring groups that differ in one bit, repeat with matching dashes; unticked terms are prime implicants.

  • Phase 2: build the PI chart over required minterms only, select essential PIs (single-X columns), then reduce with row and column dominance.

  • For cyclic charts, Petrick's method multiplies out the covering condition to list every minimal solution.

  • The method is exact but exponential; industrial tools use heuristics such as Espresso.

  • With minimisation complete, the next chapter, Combinational Circuit Design, puts it to work: from a word problem to a truth table, to a minimal expression, to a gate-level circuit.