Quine–McCluskey Visualization | Combine Minterms, Chart the Primes

The idea: a Karnaugh map turned into a table

A Karnaugh map finds the shortest sum of products by eye: neighbouring cells differ in one input, so two touching 1s merge into one shorter term. Past four inputs the map gets hard to read. The Quine–McCluskey method does the same merging with a table that a person or a program can follow step by step, for any number of inputs. It has two halves: first find every prime implicant (a term that cannot grow any bigger), then pick the cheapest set of them that covers every 1.

The method as a pipeline for Σm(3,5,6,7): the minterms 011, 101, 110, 111 are grouped by number of 1s, combined into the pairs -11, 1-1, 11-, which are the prime implicants; the chart marks all three as essential and F = BC + AC + AB — Group, combine until nothing merges, then choose rows from the chart: the majority function becomes BC + AC + AB.

On the canvas the three top panels are the columns of the combining table (single minterms, pairs, quads). Below them are the prime implicant chart and the cover that is picked from it. Press Group by 1s, then Combine once per pass, then Cover.

Step 1: group by the number of 1s

Write each minterm in binary, A as the most significant bit, so m5 with four inputs is 0101. Sort the terms into groups by how many 1s they have. Two terms can only differ in exactly one bit if their counts of 1s differ by exactly one, so from now on a term is only compared with the terms of the next group. That is what makes the method faster than trying every pair. Don't cares (d) go into the table too, because they may help a term grow.

Step 2: combine terms that differ in one bit

Two terms that differ in exactly one bit combine into one term with a dash in that bit: 0101 (A'BC'D) and 0111 (A'BCD) give 01-1 (A'BD). This is the rule XY + XY' = X, the same one a Karnaugh map group uses. Both terms get a tick (✓). The new term goes into the next column, which holds terms of twice the size.

The next pass does the same on that column. Two terms only combine if their dashes are in the same places: -0-0 and -0-1 combine, -0-0 and 0--0 do not. The same bigger term is often formed twice: (0,1) + (8,9) and (0,8) + (1,9) both give -00-. It is kept once (Demo: 4 inputs, duplicates in pass 2). When a pass makes nothing new, the table is done. Every term that never got a tick is a prime implicant.

Left: m5 = 0101 and m7 = 0111 differ only in C and combine into 01-1 = A'BD, both ticked. Right: the quad -00- is formed twice, from the pairs 000- and 100- and from the pairs -000 and -001; the first copy is kept, the second is marked as a duplicate — One bit differs: it becomes a dash and both terms are ticked; a term formed a second time is kept once.

column	term size	dashes	literals (4 inputs)
1	1 minterm	0	4
2	2 minterms	1	3
3	4 minterms	2	2
4	8 minterms	3	1

Step 3: the prime implicant chart

Make a chart with one row per prime implicant and one column per minterm where F = 1. Don't cares get no column: they never have to be covered. Put an X where a prime covers a minterm. A column with a single X can only be covered by that row, so the row is an essential prime implicant and must be in the answer. Take every essential prime and mark the columns it covers.

With the don't cares of Demo: don't cares, Σm(4,8,10,11,12,15) + d(9,14), m4 forces BC'D' and m15 forces AC. Only m8 is left, and AB' and AD' both cover it with 2 literals, so F = BC'D' + AC + AB' (or BC'D' + AC + AD').

Petrick's method and cyclic charts

For the columns the essentials leave open, Petrick's method writes the choice as algebra. Each open column needs at least one of its rows, which is an OR; all columns need that, which is an AND. In Demo: 4 inputs, duplicates in pass 2 the open columns m5 and m7 give P = (P1 + P2)(P2 + P3). Multiplied out, P2 alone is the smallest product, so A'BD is added.

A cyclic chart has no essential prime at all: every column has two or more X. Σm(0,1,2,5,6,7) has six prime implicants of 2 literals each, and every minterm is covered by exactly two of them. Petrick gives two equally small answers, A'B' + BC' + AC and A'C' + B'C + AB (Demo: cyclic chart, Petrick's method).

The 6 by 6 chart of the cyclic function Σm(0,1,2,5,6,7): every column has two X, so no row is essential. Two covers of three rows each are marked: P1, P4, P5 and P2, P3, P6 — No column has a single X, so nothing is essential; two different sets of three rows each cover every column.

Five inputs and beyond

A 5-input function is two 4 × 4 maps stacked, and groups across the two maps are easy to miss. The table does not care: Demo: 5 inputs, past the K-map runs Σm(0,4,8,12,16,17,19,21,23,29,31) through 13 pairs and 3 quads to F = A'D'E' + AB'E + ACE + B'C'D'E', 13 literals instead of 55.

The cost is the catch. A function of n inputs can have about 3ⁿ/n prime implicants, and choosing the cheapest cover is the set cover problem, which is NP-hard. Logic tools for real circuits therefore use heuristics such as Espresso, which reshape a cover step by step instead of listing every prime. Quine–McCluskey is still the exact method they are measured against.

	Karnaugh map	Quine–McCluskey
inputs	up to 4 (5–6 with stacked maps)	any number
finding primes	by eye	by rule, column by column
choosing the cover	by eye	chart, essentials, Petrick
as a program	hard	easy, but exponential in the worst case

See also Truth Tables and Sets for minterms and truth tables, Combinational Logic for the circuits that a minimal SOP turns into, and Multilevel Logic for turning AND–OR into NAND–NAND.

What the page leaves out

Product of sums (working on the 0s), multi-output minimization (sharing primes between several outputs), row and column dominance as a shortcut before Petrick, functions with more than 5 inputs or more than 12 minterms, the cost of real gates (NAND/NOR, fan-in), and heuristic minimizers such as Espresso in detail.