Karnaugh map simplification (2,3,4 variables)

WHAT is a K-map?

WHY Gray code and not binary order? If we labelled columns 00, 01, 10, 11, then columns 01 and 10 (adjacent on paper) differ in two bits — grouping them would be a lie. Gray code order 00, 01, 11, 10 guarantees every neighbour (including wrap-around edges) differs in one bit, which is the whole point.

WHY does grouping work? (Derive from first principles)

The only Boolean law we need is the combining theorem: $XY + X\bar{Y} = X(Y+\bar{Y}) = X\cdot 1 = X$

Now generalise. If a group of $1$ s covers all combinations of $k$ variables while the other $n-k$ variables stay fixed, repeated application of the combining theorem eliminates all $k$ varying variables:

Group of $2^1=2$ cells → eliminates 1 variable.
Group of $2^2=4$ cells → eliminates 2 variables.
Group of $2^3=8$ cells → eliminates 3 variables.

Rules for a legal group (all must hold):

Contains only 1s (and don't-cares if it helps).
Size is a power of two: $1, 2, 4, 8, 16$ .
Shape is a rectangle (or square) — no diagonals, no L-shapes.
Edges wrap around (left↔right, top↔bottom) — the map is a torus.
Groups may overlap; use overlap if it makes a group bigger.
Cover every 1 at least once, using the fewest, largest groups.

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

HOW to build each map

2-variable ( $A,B$ )

$2\times2$ grid. Rows = $A$ , columns = $B$ .

3-variable ( $A,B,C$ )

$2\times4$ grid. Rows = $A$ (0,1), columns = $BC$ in Gray order 00,01,11,10.

4-variable ( $A,B,C,D$ )

$4\times4$ grid. Rows = $AB$ Gray 00,01,11,10, columns = $CD$ Gray 00,01,11,10.

Cell numbering uses the minterm index $m_i$ where $i$ is the decimal value of the input bits.

Worked Example 1 — 3 variables

$F(A,B,C) = \sum m(1,3,5,7)$ — i.e. output 1 for minterms 1,3,5,7.

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

Step 1 — place the 1s. Minterms 1(001),3(011),5(101),7(111). Why this step? These decimals convert to the $ABC$ pattern that names each cell.

Step 2 — find the largest group. All four 1s form a $2\times2$ block in columns 01 and 11. Why this step? Bigger group ⇒ more variables eliminated.

Step 3 — read the surviving literals. Across this group: $A$ takes both 0 and 1 (varies → drop), $B$ takes both 0 and 1 (drop), $C = 1$ in every cell (stays). Why this step? $n-k = 3-2 = 1$ literal survives, and it's the one constant across the group.

$\boxed{F = C}$

Sanity check: $m1,3,5,7$ are exactly the minterms with $C=1$ .

Worked Example 2 — 4 variables

$F(A,B,C,D) = \sum m(0,1,2,3,8,9,10,11)$

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

Step 1 — plot. Row 00 (AB=00) and row 10 (AB=10) are all 1. Why? Minterms 0–3 → AB=00; 8–11 → AB=10.

Step 2 — group with wrap-around. Rows 00 and 10 are the top and bottom edges, which are adjacent by wrap. Together they form a group of $8$ cells (a $2\times4$ block on the torus). Why this step? Edge wrap is legal; grabbing 8 cells eliminates 3 variables ( $4-3=1$ ).

Step 3 — read literals. In this group $C,D$ both vary (drop), $A$ varies between the two rows (drop)... check: row 00 has $A=0$ , row 10 has $A=1$ → $A$ varies, drop. $B=0$ in both rows → stays. $\boxed{F = \bar{B}}$

Worked Example 3 — Don't-cares ( $\times$ )

$F(A,B,C,D) = \sum m(1,3,7,11,15) + d(0,2,5)$

Don't-cares can be treated as 1 or 0, whichever gives a bigger group.

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

Step 1 — the CD=11 column (m3,7,15,11) is all 1 → group of 4 → term $CD$ ( $C=1,D=1$ , rows vary). Why? $4-2=2$ literals, both constant across the column.

Step 2 — grab row 00 using don't-cares. Cells 0(d),1(1),3(1),2(d): making all four =1 gives a group of 4 in row 00 → $\bar A\bar B$ ( $A=0,B=0$ ; CD varies). Why? Don't-cares 0 and 2 are free 1s that let us build a size-4 group instead of a lonely pair.

$\boxed{F = CD + \bar{A}\bar{B}}$ We simply ignore the don't-cares (5) we didn't need — they don't force any extra term.

Common mistakes

Active Recall

Recall Why must K-map rows/columns use Gray code?

So physically adjacent cells differ in exactly one variable, making the combining theorem $XY+X\bar Y = X$ valid for neighbours.

Recall A group of 8 cells in a 4-variable map gives how many literals?

$n-k = 4-3 = 1$ literal.

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

As 1 if it enlarges a group, otherwise as 0 (ignore it). Never require a term just to cover a don't-care.

Recall Why is a group of 3 illegal?

Cancellation only works for powers of two; a size-3 group can't be reduced to a single product term.

Recall Feynman: explain to a 12-year-old

Imagine a sticker chart on a fridge shaped like a donut. You put a star where the answer is "yes". If two stars sit right next to each other, it means one thing (say, whether the light was on) didn't matter — the answer was yes either way — so you cross that thing off your rule. The bigger the block of stars you can circle (2, 4, 8...), the more stuff you cross off, and the shorter and simpler your rule becomes. That short rule is a cheaper circuit.

Connections

Boolean Algebra Laws — the combining theorem $XY+X\bar Y=X$ is the engine.
Sum of Products and Product of Sums — K-map outputs minimal SOP (0-grouping gives POS).
Truth Tables — the raw data a K-map rearranges.
Logic Gate Minimisation — fewer literals ⇒ fewer gates ⇒ cheaper hardware.
Quine-McCluskey Method — tabular alternative when variables > 4.
Don't-care Conditions — flexible cells used to enlarge groups.

Flashcards

What rearrangement does a K-map perform on a truth table?

Places outputs in a grid so adjacent cells differ by exactly one variable (Gray-code labelling).

Which Boolean theorem justifies grouping?

The combining theorem

XY+X\bar Y = X

Literals produced by a group of

2^k

ones in an

n

-var map?

n-k

literals.

Legal K-map group sizes?

Powers of two: 1, 2, 4, 8, 16.

Why is Gray code order used instead of straight binary?

So neighbouring cells differ by only one bit, keeping adjacency valid.

Can K-map groups overlap?

Yes, if overlapping makes a group larger.

How are the map's edges treated?

They wrap around (torus) — left↔right and top↔bottom are adjacent.

How is a don't-care handled?

As 1 if it enlarges a group, otherwise ignored (treated as 0).

F=\sum m(1,3,5,7)

for

A,B,C

simplifies to?

F=C

Why can't you group 3 cells?

Cancellation only collapses powers-of-two groups; 3 has no clean reduction.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, truth table ek lambi list hoti hai jismein har input combination ke liye output likha hota hai. K-map basically usi list ko ek smart grid mein rearrange karta hai — is tarah ki do bagal wale (adjacent) cells sirf ek hi variable mein differ karein. Isi liye rows aur columns ko Gray code order (00, 01, 11, 10) mein likhte hain, warna 01 aur 10 do bits mein change ho jaate aur grouping galat ho jaati.

Core idea ek chhote se Boolean rule par tika hai: $XY + X\bar Y = X$ . Matlab agar output "yes" hai chahe $Y$ 0 ho ya 1 (jab tak $X$ hai), to $Y$ ka koi matlab nahi — usko hata do. K-map mein jab aap adjacent 1s ka group banate ho, to jo variable us group mein 0 aur 1 dono banta hai wo cancel ho jaata hai. Group jitna bada (2, 4, 8 — hamesha power of two), utne zyada variable delete, utna chhota aur sasta circuit. Formula yaad rakho: literals $= n - k$ , jahan group ka size $2^k$ hai.

Practical rules simple hain: sirf 1s (ya zaroorat ho to don't-cares) lelo, rectangle shape rakho, edges wrap karte hain (map ek donut jaisa), overlap allowed hai agar group bada banta ho, aur hamesha sabse bada legal group pehle pakdo. Don't-care ( $\times$ ) ko 1 maano agar group bada ho raha ho, warna ignore. Yeh technique isliye important hai kyunki kam gates matlab kam cost, kam power, aur kam delay — exam mein bhi aur real hardware design mein bhi.

Karnaugh map simplification (2,3,4 variables)

WHAT is a K-map?

WHY does grouping work? (Derive from first principles)

HOW to build each map

2-variable ( $A,B$ )

3-variable ( $A,B,C$ )

4-variable ( $A,B,C,D$ )

Worked Example 1 — 3 variables

Worked Example 2 — 4 variables

Worked Example 3 — Don't-cares ( $\times$ )

Common mistakes

Active Recall

Connections

Flashcards

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Boolean Algebra & Logic Gates

Connections