Karnaugh map simplification (2,3,4 variables): Visual walkthrough

Step 1 — What a single output cell even is

WHAT. We start with nothing but a rule that says "yes" or "no". Suppose we have two switches, and we call them $A$ and $B$ . Each switch is either off (we write $0$ ) or on (we write $1$ ). A cell is one little box that answers: "for this exact setting of the switches, is the light on?"

WHY. Before we can talk about neighbouring cells, we must agree what one cell means. A cell is one row of a truth table — one input combination and its single output.

PICTURE. Look at the figure: four possible switch settings, four boxes. The box for $A = 1, B = 0$ is highlighted. Its label $A \overset{ˉ}{B}$ reads: " $A$ is on, $B$ is off." The bar over $B$ means "not $B$ ", i.e. $B = 0$ .

Figure — Karnaugh map simplification (2,3,4 variables)

Step 2 — Laying the four cells so neighbours differ by one switch

WHAT. We arrange the four boxes in a $2 \times 2$ grid. The left–right position is set by $B$ , the top–bottom position by $A$ .

WHY. We want a picture where walking one step changes exactly one switch. If moving right flipped two switches at once, "these two boxes are neighbours" would be a lie. So we deliberately choose the layout that keeps every step a one-switch step.

PICTURE. In the grid, walk from the box $\overset{ˉ}{A} \overset{ˉ}{B}$ (top-left) one step right to $\overset{ˉ}{A} B$ . Only $B$ changed — $A$ stayed $0$ . That single-bit-change ordering is called Gray code. The colour of each border shows which switch flipped when you entered it.

Step 3 — The one law that makes deletion legal

WHAT. Take two neighbours that are both 1, and that differ only in $B$ . Their two products are $X B$ and $X \overset{ˉ}{B}$ , where $X$ is everything they share (here $X = A$ ). We add them (OR them, written $+$ ): $X B + X \overset{ˉ}{B} .$

WHY. We use the OR $+$ because "the output is 1 in this cell or that cell". We are about to prove those two terms collapse to one shorter term. This is the engine — the combining theorem.

PICTURE. Read each symbol where it sits: $shared part X B = 1 B + shared part X B = 0 \overset{ˉ}{B} = X = 1, always (B + \overset{ˉ}{B}) = X \cdot 1 = X .$ The middle piece $B + \overset{ˉ}{B}$ is " $B$ is on or off" — which is always true, so it equals $1$ . Multiplying by $1$ changes nothing, so $B$ vanishes. The figure shades the two cells and draws an arrow: two boxes → one label $X$ .

Step 4 — A group of 2 deletes 1 variable (worked live)

WHAT. Concretely: in our $2 \times 2$ map, put $1$ in $A \overset{ˉ}{B}$ and $1$ in $A B$ — the whole bottom row.

WHY. These two share $A = 1$ and differ only in $B$ . By Step 3, $A B + A \overset{ˉ}{B} = A$ . We see the deletion instead of computing it.

PICTURE. Circle the bottom row. Across the circle, $B$ shows both $0$ and $1$ (so $B$ dies), while $A = 1$ everywhere (so $A$ lives). Surviving term: $A$ .

Step 5 — Growing to 3 variables and a group of 4

WHAT. Add a third switch $C$ . Now $2^{3} = 8$ cells, drawn as a $2 \times 4$ grid: rows = $A$ , columns = $B C$ in Gray order $00, 01, 11, 10$ .

WHY. With more variables, bigger blocks become possible, and each doubling deletes one more variable. We test the $n - k$ rule on a group of $4$ .

PICTURE. Shade the columns $B C = 01$ and $B C = 11$ across both rows — a $2 \times 2$ block of four 1s (this is exactly parent Example 1, $F = \sum m (1, 3, 5, 7)$ ). Inside the block: $A$ takes both values (die), $B$ takes both values (die), but $C = 1$ in every one of the four cells (live). So $F = C$ . Check: $4 - 2 = 2$ literals gone, $1$ left. ✔

Step 6 — The edges wrap: the map is a donut

WHAT. In the $2 \times 4$ column order $00, 01, 11, 10$ , look at the first column $00$ and the last column $10$ . Their labels differ only in $B$ ( $00$ vs $10$ : $C$ is $0$ in both, $B$ flips). So they are neighbours even though they sit at opposite ends of the paper.

WHY. Gray code's promise (Step 2) must hold including the ends — otherwise the "one-switch-per-step" rule breaks at the border. Bending the strip into a ring makes the ends touch, so the promise holds everywhere.

PICTURE. The figure rolls the strip into a loop and shows column $00$ meeting column $10$ . Left↔right edges touch (and for a $4 \times 4$ map, top↔bottom too). This is why the parent could grab the top and bottom rows as one block of 8.

Step 7 — The degenerate cases (never let the reader get stuck)

WHAT. Four boundary situations, each shown as its own tiny map.

WHY. A derivation is only trustworthy if it survives the extremes. We list every one so no scenario surprises you.

PICTURE. From left to right in the figure:

All cells 0 → no groups, $F = 0$ . The light is never on.
All cells 1 → one giant block of $2^{n}$ , $k = n$ , so $n - n = 0$ literals: $F = 1$ . Every variable irrelevant.
A lonely single 1 ( $2^{0}$ , $k = 0$ ): $n - 0 = n$ literals — nothing cancels, you keep the full minterm.
A group of 3 — illegal. Cancellation only works in powers of two ( $1, 2, 4, 8, 16$ ); three cells have no clean collapse. Fix: overlap into a 4th existing 1 to reach a block of 4.

Step 8 — Don't-cares: free stars that let blocks grow

WHAT. A don't-care ( $\times$ or $d$ ) is a cell whose output we genuinely never observe. We are free to pretend it is $1$ or $0$ — whichever makes a bigger block.

WHY. Bigger block ⇒ fewer literals (Step 4). A $d$ next to a real $1$ can turn a lonely pair into a legal size-4 group at zero cost — because we never have to justify that term for the $d$ 's sake.

PICTURE. Parent Example 3: the $C D = 11$ column is four real 1s → term $C D$ . Then row $A B = 00$ holds $1, 1$ plus two don't-cares at the ends; painting the $d$ s as $1$ completes a block of 4 → term $\overset{ˉ}{A} \overset{ˉ}{B}$ . The unused $d$ (minterm 5) we simply paint $0$ and ignore. Result: $F = C D + \overset{ˉ}{A} \overset{ˉ}{B}$ .

Recall How do you treat a don't-care?

As $1$ only if it enlarges a group; otherwise as $0$ (ignore). Never invent a term just to cover a $d$ . See Don't-care Conditions.

The one-picture summary

Everything on one map. A truth table is reshaped so neighbours differ by one switch (Gray code, Step 2). A pair of adjacent 1s deletes the switch that flipped (combining theorem, Step 3). Doubling the block deletes one more switch ( $n - k$ , Steps 4–5). Edges wrap (Step 6). Odd sizes and empty/full maps are special (Step 7). Don't-cares grow blocks for free (Step 8). Fewer literals ⇒ fewer gates ⇒ cheaper circuit — the whole point of Logic Gate Minimisation.

Recall Feynman: the whole walkthrough in plain words

Picture a donut-shaped sticker chart. You put a star wherever the answer is "yes". You laid the chart out so that stepping to any next-door square flips exactly one switch — even around the back of the donut. Now, if two next-door squares both have stars and they differ only in whether switch $B$ was on, then $B$ didn't matter — cross it off. Circle bigger blocks of stars (2, then 4, then 8) and you cross off more switches each time, shrinking your rule. Empty chart means "never on"; full chart means "always on"; a lone star keeps its full description; and you can never circle an odd number like 3. Some squares are "I don't care" — treat them as stars only when doing so lets you circle a bigger block. What's left after all the crossing-off is the shortest possible rule, which is the cheapest possible circuit.

Connections

Karnaugh map simplification (2,3,4 variables) — the parent result this page derives.
Boolean Algebra Laws — the combining theorem $X B + X \overset{ˉ}{B} = X$ (Step 3) is the engine.
Truth Tables — the raw list a K-map rearranges (Step 1).
Sum of Products and Product of Sums — grouping 1s yields minimal SOP.
Logic Gate Minimisation — fewer literals ⇒ cheaper hardware (summary).
Don't-care Conditions — the free stars of Step 8.
Quine-McCluskey Method — the tabular version for more than 4 variables.