Worked examples — Karnaugh map simplification (2,3,4 variables)

Before anything: a K-map is the truth-table grid where neighbours differ by one variable. A minterm $m_i$ is the row of a truth table whose input bits spell the number $i$ in binary. A literal is a single variable, plain ($A$) or barred ($\bar{A}$ = "NOT A"). Our goal each time: cover every 1 with the fewest, largest power-of-two rectangles, then read off the surviving Sum-of-Products expression.

---

The scenario matrix

Every K-map problem falls into one of these case classes. The examples below are labelled with the cell(s) they cover.

Cell	Case class	Why it's tricky	Covered by
C1	2-variable, ordinary group	smallest map, build the reflex	Ex 1
C2	3-variable, two groups + overlap	when one group isn't enough	Ex 2
C3	4-variable, a quad (2×2 block)	reading 2 surviving literals	Ex 3
C4	Wrap-around edges (torus)	the four-corner group	Ex 4
C5	Degenerate: all 1s	answer is $1$, no literals	Ex 5
C6	Degenerate: all 0s / single 1	answer is $0$, or a full minterm	Ex 5
C7	Don't-cares enlarging a group	treat $\times$ as 1 only if useful	Ex 6
C8	Real-world word problem	translate English → minterms	Ex 7
C9	Exam twist: 0-grouping for POS	grouping 0s gives Product-of-Sums	Ex 8

---

Example 1 — 2-variable, ordinary group (C1)

Forecast: Two 1s sitting together — guess how many literals survive before reading on.

The map. Rows = $A$, columns = $B$ (single-bit labels, so Gray code is trivially satisfied).

$A\backslash B$	0	1
0	0	0
1	1	1

1. Place the 1s. $m2=$ 10 (so $A=1,B=0$), $m3=$ 11 (so $A=1,B=1$). Why this step? Decimals must become $AB$ bit-patterns to know which cells light up.
2. Grab the largest group. Both 1s fill the entire $A=1$ row → a horizontal pair (group of $2^1=2$). Why this step? Bigger group ⇒ more variables cancelled; two is the max here.
3. Read surviving literals. Across the pair $B$ is 0 then 1 → $B$ varies, drop it. $A=1$ in both → stays. Literals $=n-k=2-1=1$. Why this step? The combining theorem $A\bar{B}+AB=A$ deletes the variable that changes.

$\boxed{F=A}$

Recall Verify:

$A\bar{B}+AB=A(\bar{B}+B)=A\cdot 1=A$. And $m2,m3$ are exactly the rows with $A=1$. ✓

---

Example 2 — 3-variable, two overlapping groups (C2)

Forecast: Five 1s — five isn't a power of two, so you'll need more than one group. Guess how many.

$A\backslash BC$	00	01	11	10
0	1	1	1	1
1	0	0	0	1

1. Place the 1s. $m\mathrm{0..}m3$ have $A=0$ → the whole top row. $m6=$ 110 ($A=1,B=1,C=0$) → bottom-right cell. Why? Convert each decimal to $ABC$ to know its cell.
2. First group — the top row (quad of 4). All four top cells → group of $2^2=4$. $B,C$ vary, $A=0$ stays → term $\bar{A}$. Why this step? Always take the largest legal group first; $4-2=2\Rightarrow$ wait, $n-k=3-2=1$ literal.
3. Second group — cover the lonely $m6$. It has no vertical partner ($m2$ above it is already covered, but overlap is allowed!). Pair $m6$ (110) with $m2$ (010) — they sit in the same column 10. This vertical pair: $A$ varies, $B=1$, $C=0$ → term $B\bar{C}$. Why this step? Overlapping into the already-covered $m2$ lets $m6$ join a size-2 group instead of standing alone as a 3-literal minterm.

$\boxed{F=\bar{A}+B\bar{C}}$

Recall Verify:

$\bar{A}$ covers $m0,1,2,3$. $B\bar{C}$ covers rows with $B=1,C=0$: $m2$ (010) and $m6$ (110). Union $=\{0,1,2,3,6\}$. ✓ No 1 missed, no extra minterm added.

---

Example 3 — 4-variable quad, reading two literals (C3)

Forecast: These four cluster into a neat square. Guess the two surviving literals.

$AB\backslash CD$	00	01	11	10
00	0	0	0	0
01	0	1	1	0
11	0	1	1	0
10	0	0	0	0

1. Place the 1s. $m5=$0101, $m7=$0111, $m13=$1101, $m15=$1111. They occupy rows $AB=01,11$ and columns $CD=01,11$. Why? Bit-patterns pin each cell — see the red $2\times 2$ block in the figure.
2. Grab the $2\times 2$ quad. Four cells, power of two, rectangular → legal group of $2^2=4$. Why this step? $n-k=4-2=2$ literals — bigger than any pair we could take.
3. Read the constants. Across the block: $A$ is $0$ then $1$ → drop. $C$ is $0$ then $1$ → drop. $B=1$ everywhere → stays. $D=1$ everywhere → stays. Why this step? Only variables constant across the whole group survive.

$\boxed{F=BD}$

Recall Verify:

$BD$ means $B=1,D=1$: minterms $\{5,7,13,15\}$ exactly (0101,0111,1101,1111). ✓

---

Example 4 — wrap-around four corners (C4)

Forecast: These sit in the four corners of the map. On flat paper they look scattered — on a donut they touch. Guess the group.

$AB\backslash CD$	00	01	11	10
00	1	0	0	1
01	0	0	0	0
11	0	0	0	0
10	1	0	0	1

1. Place the 1s. $m0=$0000, $m2=$0010, $m8=$1000, $m10=$1010 — the four corner cells. Why? Corners are $CD\in \{00,10\}$ (left & right edges) crossed with $AB\in \{00,10\}$ (top & bottom edges).
2. Wrap the edges. Left edge $CD=00$ touches right edge $CD=10$; top row $AB=00$ touches bottom row $AB=10$. All four corners become one $2\times 2$ group of 4 on the torus (green loops in the figure). Why this step? The map is a donut — opposite edges are adjacent, so this is a legal quad, not four singletons.
3. Read constants. $A$: $0,1$ vary → drop. $C$: $0,1$ vary → drop. $B=0$ in all four → stays as $\bar{B}$. $D=0$ in all four → stays as $\bar{D}$. Why? $n-k=4-2=2$ literals, the two constants.

$\boxed{F=\bar{B}\bar{D}}$

Recall Verify:

$\bar{B}\bar{D}$: $B=0,D=0$ → -0-0 → minterms $\{0,2,8,10\}$ (0000,0010,1000,1010). ✓

---

Example 5 — degenerate maps: all-1s and single-1 (C5, C6)

Forecast: What's the simplest possible answer, and the least simplifiable? Guess before reading.

Part (a) — all 1s.

1. One group of 16. Every cell is 1 → the whole map is a single legal group of $2^4=16$. Why? $n-k=4-4=0$ literals — nothing survives.
2. Read. Every variable takes both values inside the group → all four dropped.

$\boxed{F=1}$

Part (b) — single 1.

1. No partner exists. $m9$ has no adjacent 1, so the largest group is size $2^0=1$. Why? Grouping needs a neighbouring 1; there is none.
2. Read the full minterm. $9=$1001 → $A=1,B=0,C=0,D=1$. Nothing cancels; $n-k=4-0=4$ literals.

$\boxed{G=A\bar{B}\bar{C}D}$

(If instead the map were all 0s, no 1 exists to cover, so $F=0$ — the empty function.)

Recall Verify:

(a) $A+\bar{A}$-style collapse of the whole table gives constant $1$. (b) 1001 is decimal $8+1=9$, and $A\bar{B}\bar{C}D$ selects exactly that one row. ✓

---

Example 6 — don't-cares that pay off (C7)

Forecast: Three $\times$ cells are offered. Which do you accept? Guess.

$AB\backslash CD$	00	01	11	10
00	d	1	1	0
01	0	0	0	0
11	0	0	d	0
10	d	1	1	0

1. Place required 1s and don't-cares. $1=$0001,$3=$0011,$9=$1001,$11=$1011. Don't-cares $0=$0000,$8=$1000,$15=$1111. Why? We must cover the 1s; the $\times$ are optional 1s.
2. Build the biggest group using $\times 0$ and $\times 8$. Columns $CD=00$ and $CD=01$ in rows $AB=00,10$ give cells $\{0,1,8,9\}$. Treating $\times 0,\times 8$ as 1 makes a quad. Constants: $B=0$, $D$? $D$ varies (0,1) → drop; $C=0$ stays. So this quad = $\bar{B}\bar{C}$. It covers required $m1,m9$. Why this step? Accepting the two free $\times$ turns lonely 1s into a size-4 group ($4-2=2$ literals).
3. Cover remaining $m3,m11$. Cells $\{1,3,9,11\}$ (columns $CD=01,11$, rows $AB=00,10$) form a quad: $B=0$, $D=1$, $A$ & $C$ vary → $\bar{B}D$. Why? Another size-4 group grabs $m3,m11$ (and re-covers $m1,m9$ — overlap is free).
4. Ignore $\times 15$. It never enlarged a needed group, so we treat it as 0. Why? Never invent a term just to cover a don't-care.

$\boxed{F=\bar{B}\bar{C}+\bar{B}D}$

Recall Verify:

$\bar{B}\bar{C}$ ($B=0,C=0$) = $\{0,1,8,9\}$. $\bar{B}D$ ($B=0,D=1$) = $\{1,3,9,11\}$. Union of the required part = $\{1,3,9,11\}$ ✓ (all required covered), and never forces $m15$. ✓

---

Example 7 — real-world word problem (C8)

Forecast: Guess the final expression before formalising.

1. Assign variables & minterms. Order bits $DWM$. Siren $S=1$ when $M=1$ or ($D=1$ and $W=1$). Why? Translate the English conditions into a truth table.

$D$	$W$	$M$	dec	$S$
0	0	0	0	0
0	0	1	1	1
0	1	0	2	0
0	1	1	3	1
1	0	0	4	0
1	0	1	5	1
1	1	0	6	1
1	1	1	7	1

So $S=\sum m(1,3,5,6,7)$.

$D\backslash WM$	00	01	11	10
0	0	1	1	0
1	0	1	1	1

2. Group the $M=1$ column-pair. Columns $WM=01$ and $WM=11$ (all four rows) → quad. $D,W$ vary, $M=1$ stays → term $M$. Why? Largest group; captures "motion always fires."
3. Group the remaining $m6$. $m6=$110 pairs with $m7=$111 (column pair $WM=10,11$, row $D=1$): $M$ varies, $D=1$, $W=1$ → term $DW$. Why? Overlap into $m7$ lets $m6$ join a size-2 group, matching "both door and window."

$\boxed{S=M+DW}$

Recall Verify:

$M$ covers $\{1,3,5,7\}$; $DW$ covers $\{6,7\}$. Union $=\{1,3,5,6,7\}$ ✓ — exactly the siren rows, and it reads as English: "motion, or door-and-window." ✓

---

Example 8 — exam twist: group the 0s for POS (C9)

Forecast: Twelve 1s is a mess to group. There are only four 0s. Guess the POS.

The 0s are at $m9,11,13,15$ (1001,1011,1101,1111) — i.e. $A=1,D=1$.

$AB\backslash CD$	00	01	11	10
00	1	1	1	1
01	1	1	1	1
11	1	0	0	1
10	1	0	0	1

1. Group the 0s instead of the 1s. The four 0s form a $2\times 2$ quad (rows $AB=11,10$, cols $CD=01,11$). Why this step? Fewer 0s than 1s → grouping them is faster; this is the SOP↔POS duality.
2. Read the 0-group as a product (this is $\bar{F}$). Constants: $A=1$, $D=1$ (B, C vary). So $\bar{F}=AD$. Why? Grouping 0s gives the SOP of the complement $\bar{F}$.
3. Complement to get POS of $F$. By DeMorgan: $F=\overline{AD}=\bar{A}+\bar{D}$. Why? $\overline{X\cdot Y}=\bar{X}+\bar{Y}$ turns the product-of-complement into a sum — a single POS clause.

$\boxed{F=\bar{A}+\bar{D}}$

Recall Verify:

$F=0$ only when $\bar{A}+\bar{D}=0$, i.e. $A=1$ and $D=1$ → minterms $\{9,11,13,15\}$. Those are exactly the missing minterms, so all 12 listed are 1. ✓

---

Active Recall

Recall When five 1s appear, why can't one group cover them?

$5$ is not a power of two; you must use two (or more) overlapping power-of-two groups (Ex 2).

Recall A single isolated 1 in a 4-var map gives how many literals?

$n-k=4-0=4$ — the full minterm survives (Ex 5b).

Recall Why group the 0s in Example 8?

There were only four 0s vs twelve 1s; grouping the smaller set gives $\bar{F}$, then DeMorgan yields the minimal POS.

---

Connections

• Parent: K-map simplification — the rules these examples exercise.
• Boolean Algebra Laws — DeMorgan powered the POS twist (Ex 8).
• Sum of Products and Product of Sums — SOP from 1-groups, POS from 0-groups.
• Truth Tables — Ex 7 built minterms straight from one.
• Don't-care Conditions — Ex 6's optional cells.
• Logic Gate Minimisation — every dropped literal is a saved gate input.
• Quine-McCluskey Method — the systematic fallback beyond 4 variables.