Visual walkthrough — Quine-McCluskey method

---

Step 0 — What a "minterm" looks like as a corner of a cube

WHAT. We have three input switches, $A$, $B$, $C$. Each can be $0$ (off) or $1$ (on). That gives $2^3=8$ combinations. A minterm is one such combination where the output is 1.

WHY a cube? Because a cube has exactly $8$ corners, and each corner is one $(A,B,C)$ pattern. Distance between two corners along the edges = how many switches you'd have to flip to walk from one to the other. That distance is the Hamming distance — literally "how many bits differ". We will need this idea constantly, so we build it first.

PICTURE. Below, the cube. Each corner is labelled with its 3-bit code $ABC$ and its minterm number. The corners we care about (output $=1$: $0,1,2,5,6,7$) are painted yellow; the two "off" corners ($3,4$) are dim.

---

Step 1 — Why merging = collapsing an edge to its midpoint

WHAT. Take the two corners $000$ ($m0$) and $001$ ($m1$). As terms they are $\bar{A}\bar{B}\bar{C}$ and $\bar{A}\bar{B}C$. Add them: $\underset{\text{corner }000}{\underbrace{\bar{A}\bar{B}\bar{C}}}+\underset{\text{corner }001}{\underbrace{\bar{A}\bar{B}C}}=\bar{A}\bar{B}\underset{=1}{\underbrace{(\bar{C}+C)}}=\bar{A}\bar{B}.$

WHY this is legal. The law $\bar{C}+C=1$ says "$C$ is either 0 or 1 — one of them is always true", so the two terms together don't care about $C$ at all. The $C$ cancels. This is the combining theorem $X\bar{Y}+XY=X$, and it is the only algebra QM uses.

WHAT IT LOOKS LIKE. On the cube, $000$ and $001$ are the ends of one edge. The merged term $\bar{A}\bar{B}$ is that whole edge — a segment covering both corners at once. We record the cancelled variable as a dash: $00\text{-}$.

WHY it must be a single edge. If the two corners differed in two bits (say $000$ and $011$), you'd get $\bar{A}\bar{B}\bar{C}+\bar{A}BC$, and now both $B$ and $C$ change — no single $X+\bar{X}$ forms, nothing cancels. That is why only Hamming-distance-1 pairs merge.

---

Step 2 — Sort the corners by their number of 1s

WHAT. Before merging blindly, we bucket the six live minterms by how many $1$s they contain:

Bucket (#1s)	Minterms	Codes
0	$0$	$000$
1	$1,2$	$001,010$
2	$5,6$	$101,110$
3	$7$	$111$

WHY bucket at all? A single-edge neighbour has exactly one more or one fewer $1$. So its Hamming-1 partner can only live in the bucket next door. Sorting this way means we never waste time comparing two corners that could never merge — and we can never accidentally merge a distance-2 pair.

PICTURE. The same cube, now drawn as stacked levels: level 0 at the bottom (no 1s), climbing to level 3 at the top. Every cube edge connects two adjacent levels — which is exactly why only neighbouring buckets can be joined.

---

Step 3 — Merge every legal edge (size-2 groups)

WHAT. Compare each corner with every corner in the next-higher bucket; keep the pairs that differ in one bit. Every corner that gets used is ticked (✓) — a ticked corner is not prime on its own.

Merged pair	Code	Cancelled	Term
$0,1$	$00\text{-}$	$C$	$\bar{A}\bar{B}$
$0,2$	$0\text{-}0$	$B$	$\bar{A}\bar{C}$
$1,5$	$\text{-}01$	$A$	$\bar{B}C$
$2,6$	$\text{-}10$	$A$	$B\bar{C}$
$5,7$	$1\text{-}1$	$B$	$AC$
$6,7$	$11\text{-}$	$C$	$AB$

WHY every corner ends up ticked. Each of $0,1,2,5,6,7$ appears in at least one pair, so all six get a ✓. Nothing survives alone.

WHAT IT LOOKS LIKE. Each merged pair is a highlighted edge on the cube. Six edges light up — these six edges are our six candidate patterns so far.

---

Step 4 — Try to merge the edges (size-4 groups)

WHAT. Two size-2 terms merge into a size-4 term only if they (i) have their dash in the same position and (ii) differ in exactly one of the remaining bits. Scan the six edges:

• $00\text{-}$ and $11\text{-}$ share a dash in $C$ — but they differ in two bits ($A$ and $B$). ✗
• $\text{-}01$ and $\text{-}10$ share a dash in $A$ — differ in two bits ($B$ and $C$). ✗
• Every other pair fails the "same dash position" test outright.

RESULT: nothing merges. No size-4 group exists.

WHY this matters. Because nothing merged, every size-2 edge from Step 3 was never ticked at this level → all six are prime implicants (PIs): maximal edges that can't grow into a face.

WHAT IT LOOKS LIKE. A face of the cube would be a $2\times 2$ square of four corners. Below we show why no face forms: the lit edges are scattered — no four of them box in a complete square face.

---

Step 5 — The Prime Implicant chart: who is forced in?

WHAT. Build a grid: one row per PI, one column per minterm. Put a mark where a PI covers that minterm. Then read each column top-to-bottom.

PI	0	1	2	5	6	7
$\bar{A}\bar{B}(0,1)$	✗	✗
$\bar{A}\bar{C}(0,2)$	✗		✗
$\bar{B}C(1,5)$		✗		✗
$B\bar{C}(2,6)$			✗		✗
$AC(5,7)$				✗		✗
$AB(6,7)$					✗	✗

WHY columns, not rows? An essential PI is one that is the only mark in some column — that minterm has no other cover, so that PI must be chosen. Scanning columns is how you spot "no choice here".

The awkward truth for this function. Look at every column: each minterm is covered by two PIs. So there are no essential PIs — no column is forced! We must instead pick a minimal cover by hand (this is where Petrick's method takes over in the general case).

WHAT IT LOOKS LIKE. Below, the chart with each column highlighted; because every column has two ✗'s, the graph of "PI covers minterm" is a ring — the classic cyclic chart.

---

Step 6 — Choose a minimal cover

WHAT. We need every column ($0,1,2,5,6,7$) marked, using as few rows as possible. Try: $f=\underset{0,1}{\underbrace{\bar{A}\bar{B}}}+\underset{5,7}{\underbrace{AC}}+\underset{2,6}{\underbrace{B\bar{C}}}.$

WHY these three. Check the union of what they cover: $\{0,1\}\cup \{5,7\}\cup \{2,6\}=\{0,1,2,5,6,7\}=\text{all six.}✓$ Three PIs, six literals — you cannot do it in two rows (two edges cover at most four corners, we have six). So three is minimal.

WHAT IT LOOKS LIKE. Three chosen edges on the cube, coloured, together touching all six lit corners with none left orphaned.

---

The one-picture summary

The whole journey on one cube: raw yellow corners → single edges (the only legal merges) → try for faces (none form) → pick three edges that blanket every lit corner. That last picture is the formula $\bar{A}\bar{B}+AC+B\bar{C}$.

Recall Feynman: retell the walkthrough

Picture a little cube. Its eight corners are the eight ways three switches can be set. We paint the corners where the machine should output "yes" — six of them here. Two corners joined by one edge differ in just one switch, and by the rule "a switch is either on or off, so it can't matter" we can glue those two corners into the whole edge — a shorter description. We sort corners into shelves by how many switches are on, because glue-able corners always sit on next-door shelves. We glue every legal edge: six edges appear. Then we try to glue edges into flat square faces — but here none of the edges line up into a square, so all six edges are as big as they get. Finally we make a checklist: which edges touch which corners? Normally some corner is only touched by one edge, forcing that edge into the answer — but this function is stubborn, every corner has two options, so we just pick the smallest handful of edges that together touch all six corners. Three edges do it, and reading those three edges back out gives the shortest recipe: $\bar{A}\bar{B}+AC+B\bar{C}$.

Recall Quick self-test

Why can't $000$ and $011$ be glued? ::: They differ in two bits ($B$ and $C$); no single $X+\bar{X}$ cancels, so no edge joins them. What made this chart "cyclic"? ::: Every column had two ✗'s — no minterm is covered by a lone PI, so there are no essential PIs. How many corners can one edge cover, and how many corners must we cover here? ::: One edge covers 2 corners; we must cover 6, so we need at least 3 edges — the minimal cover.

---

Connections

• Parent: the full algorithm
• Karnaugh Maps — the same edge-gluing, seen as a grid instead of a cube
• Sum of Products (SOP) — the output form we minimize to
• Boolean Algebra Laws — home of the combining theorem $X+\bar{X}=1$
• Prime Implicants and Petrick's Method — how to resolve the cyclic chart in Step 5
• Logic Gate Minimization — turning the minimal SOP into fewer gates