Karnaugh map simplification (2,3,4 variables): Exercises

Before we start, a shared vocabulary reminder so no symbol appears un-earned:

Definition The words we will reuse

Minterm $m_{i}$ — one specific input row where the output is 1. The index $i$ is that row's input bits read as a binary number. Example: for $A, B, C$ , input $A = 1, B = 0, C = 1$ is bits $101 = 5$ , so it is $m_{5}$ .
$\sum m (\dots)$ — "sum of these minterms": the output is 1 exactly for the listed indices, 0 everywhere else.
$d (\dots)$ / don't-care ( $\times$ ) — inputs that can never occur (or whose output we don't care about). We are free to pretend each is a 1 or a 0, whichever helps. See Don't-care Conditions.
Literal — one variable in true ( $A$ ) or complemented ( $\overset{ˉ}{A}$ ) form. Fewer literals ⇒ fewer gate inputs ⇒ cheaper circuit. See Logic Gate Minimisation.
Gray order — the labelling 00, 01, 11, 10 where each step flips exactly one bit, so paper-neighbours are true logical neighbours.

The two K-map layouts we use throughout (memorise the cell → minterm mapping):

Level 1 — Recognition

Exercise 1.1

Below is a 3-variable map. Write down the minterm indices that are 1.

$A \ B C$	00	01	11	10
0	1	0	0	1
1	1	0	0	1

Recall Solution 1.1

Read each cell's index from the figure above.

Row $A = 0$ : column 00 → $m_{0}$ (=1), column 10 → $m_{2}$ (=1).
Row $A = 1$ : column 00 → $m_{4}$ (=1), column 10 → $m_{6}$ (=1).

Answer: $F = \sum m (0, 2, 4, 6)$ .

State whether each proposed group is legal. Answer legal/illegal and give the one-word reason. (a) 3 cells in a horizontal row. (b) The 4 corner cells of a 4-variable map. (c) An L-shape of 4 cells. (d) A single lonely 1.

Recall Solution 1.2

(a) Illegal — size 3 is not a power of two.
(b) Legal — wrap-around joins the four corners into a $2 \times 2$ group (top/bottom and left/right edges touch).
(c) Illegal — must be a rectangle, no L-shapes.
(d) Legal — size $1 = 2^{0}$ is a valid group (it just eliminates 0 variables).

Level 2 — Application

Exercise 2.1

Minimise $F (A, B) = \sum m (1, 3)$ on a 2-variable map (rows $A$ , columns $B$ ).

Recall Solution 2.1

Layout: $m_{i}$ index $= 2 A + B$ .

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

$m_{1}$ ( $A 0, B 1$ ) and $m_{3}$ ( $A 1, B 1$ ) fill column $B = 1$ : a group of $2^{1} = 2$ . $n - k = 2 - 1 = 1$ literal. Across the group $A$ varies (drop), $B = 1$ constant. Answer: $F = B$ .

Exercise 2.2

Minimise $F (A, B, C) = \sum m (0, 2, 4, 6)$ (the map from Exercise 1.1).

Recall Solution 2.1... 2.2

All four 1s sit in columns 00 and 10 (the $C = 0$ columns), forming a $2 \times 2$ block of 4. $n - k = 3 - 2 = 1$ literal. $A$ varies, $B$ varies, $C = 0$ constant. Answer: $F = \overset{ˉ}{C}$ . Sanity: minterms $0, 2, 4, 6$ are exactly the even indices — even means the last bit $C = 0$ . ✓

Exercise 2.3

Minimise $F (A, B, C) = \sum m (0, 1, 4, 5)$ .

Recall Solution 2.3

$A \ B C$	00	01	11	10
0	1	1	0	0
1	1	1	0	0

The 1s occupy columns 00 and 01 ( $B = 0$ ) across both rows: a group of 4. $B = 0$ constant; $A$ and $C$ vary. $n - k = 3 - 2 = 1$ . Answer: $F = \overset{ˉ}{B}$ .

Level 3 — Analysis

Exercise 3.1

Minimise $F (A, B, C, D) = \sum m (0, 4, 12, 8)$ . (Hint: think about the edges.)

Recall Solution 3.1

Place them using the 4-var map ( $m = 8 A + 4 B + 2 C + D$ , rows $A B$ , cols $C D$ ):

$A B \ C D$	00	01	11	10
00	1	0	0	0
01	1	0	0	0
11	1	0	0	0
10	1	0	0	0

All four 1s fill column CD=00: a vertical group of 4. Rows $A B$ run through all values (both $A$ and $B$ vary), while $C = 0, D = 0$ stay fixed. $n - k = 4 - 2 = 2$ literals. Answer: $F = \overset{ˉ}{C} \overset{ˉ}{D}$ .

Exercise 3.2

Minimise $F (A, B, C, D) = \sum m (0, 2, 8, 10)$ — the four corners.

Recall Solution 3.2

$A B \ C D$	00	10
00	1	1
01	0	0
11	0	0
10	1	1

The four 1s are the map's corners. By wrap-around, top row $\leftrightarrow$ bottom row and left column $\leftrightarrow$ right column, so the corners form one $2 \times 2$ group of 4 (see the red loop in the figure). Inside it: $A$ varies (rows 00 vs 10), $C$ varies (cols 00 vs 10). Constant: $B = 0$ , $D = 0$ . $n - k = 4 - 2 = 2$ . Answer: $F = \overset{ˉ}{B} \overset{ˉ}{D}$ .

Exercise 3.3

Minimise $F (A, B, C, D) = \sum m (5, 7, 13, 15)$ .

Recall Solution 3.3

$A B \ C D$	01	11
00	0	0
01	1	1
11	1	1
10	0	0

The 1s form a $2 \times 2$ block in rows 01,11 and columns 01,11. Rows: $B = 1$ in both (constant), $A$ varies. Columns: $D = 1$ in both (constant), $C$ varies. Constant: $B = 1$ , $D = 1$ . $n - k = 4 - 2 = 2$ . Answer: $F = B D$ .

Level 4 — Synthesis

Exercise 4.1

Build the map for $F (A, B, C, D) = \sum m (1, 3, 7, 11, 15) + d (0, 2, 5)$ and find the minimal SOP. (This is the parent note's Example 3 — reproduce it and justify every choice.)

Recall Solution 4.1

$A B \ C D$	00	01	11	10
00	d	1	1	d
01	0	d	1	0
11	0	0	1	0
10	0	0	1	0

Group A — column CD=11 (cells $m_{3}, m_{7}, m_{15}, m_{11}$ ): all real 1s, size 4. Rows vary, $C = 1, D = 1$ constant → term $C D$ . Group B — row AB=00 (cells $m_{0} (d), m_{1}, m_{3}, m_{2} (d)$ ): treat the two don't-cares as 1 to make a size-4 group. $A = 0, B = 0$ constant, $C D$ vary → term $\overset{ˉ}{A} \overset{ˉ}{B}$ . Every real 1 ( $1, 3, 7, 11, 15$ ) is now covered. The don't-care at $m_{5}$ was not needed, so we leave it 0 (no extra term). Answer: $F = C D + \overset{ˉ}{A} \overset{ˉ}{B}$ .

Exercise 4.2

Design a majority function: $F = 1$ when at least two of $A, B, C$ are 1. Write its minterms, map it, minimise.

Recall Solution 4.2

"At least two 1s" out of 3 inputs → minterms with two or three 1s: $011 = 3, 101 = 5, 110 = 6, 111 = 7$ . So $F = \sum m (3, 5, 6, 7)$ .

$A \ B C$	00	01	11	10
0	0	0	1	0
1	0	1	1	1

Three pairs (each size 2, overlapping on $m_{7}$ ):

$m_{3}, m_{7}$ (column 11): $B = 1, C = 1$ , $A$ varies → $B C$ .
$m_{5}, m_{7}$ (row $A = 1$ , cols 01,11): $A = 1, C = 1$ , $B$ varies → $A C$ .
$m_{6}, m_{7}$ (row $A = 1$ , cols 11,10): $A = 1, B = 1$ , $C$ varies → $A B$ .

No size-4 group exists (the 1s don't form a rectangle of 4). Overlap on $m_{7}$ is legal and lets each pair be full. Answer: $F = A B + B C + A C$ — the classic majority/"carry-out" expression.

Level 5 — Mastery

Exercise 5.1

Minimise $F (A, B, C, D) = \sum m (0, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13)$ . Choose the fewest, largest groups and defend that the cover is minimal.

Recall Solution 5.1

$A B \ C D$	00	01	11	10
00	1	1	1	1
01	1	1	0	0
11	1	1	0	0
10	1	1	1	1

Group A — columns CD=00,01 (all four rows, size 8): $D = 0$ constant, everything else varies. $n - k = 4 - 3 = 1$ → term $\overset{ˉ}{D}$ . Group B — rows AB=00,10 (top+bottom edges wrap, all four columns, size 8): $B = 0$ constant. $n - k = 4 - 3 = 1$ → term $\overset{ˉ}{B}$ . Every 1 is covered by A or B; the two remaining 0-heavy cells ( $m_{7}, m_{15}$ region) stay 0. Answer: $F = \overset{ˉ}{D} + \overset{ˉ}{B}$ . Minimality: only two 1-cells that lie in row 01/11 and columns 11/10 are 0, and every 1 falls into one of two maximal size-8 groups — you cannot do better than two 1-literal terms.

Exercise 5.2

A 4-variable function is 1 exactly when the input, read as a number $0 - 15$ , is odd. Give the minimal SOP and the gate count.

Recall Solution 5.2

"Odd" ⇔ last bit $D = 1$ . Odd indices: $1, 3, 5, 7, 9, 11, 13, 15$ .

$A B \ C D$	01	11
00	1	1
01	1	1
11	1	1
10	1	1

Columns 01 and 11 ( $D = 1$ ) across all four rows form a size-8 group. $A, B, C$ all vary; $D = 1$ constant. Answer: $F = D$ . Gate count: zero gates — the output is just the wire $D$ . That is the cheapest circuit possible, and it's why "odd detector = lowest bit" is a hardware one-liner.

Exercise 5.3

$F (A, B, C, D) = \sum m (1, 3, 5, 7, 9)$ . Find the minimal SOP and identify which single group is essential (covers a 1 no other group can).

Recall Solution 5.3

$A B \ C D$	01	11
00	1	1
01	1	1
11	0	0
10	1	0

Group A — rows 00,01, columns 01,11 ( $m_{1}, m_{3}, m_{5}, m_{7}$ ), size 4: $A = 0, D = 1$ constant → term $\overset{ˉ}{A} D$ . Group B — cover $m_{9}$ ( $1001$ ). Its only same-one-bit neighbour that is a 1 is $m_{1}$ ( $0001$ ), so pair them: column 01, rows 00,10 → $B = 0, C = 0, D = 1$ → term $\overset{ˉ}{B} \overset{ˉ}{C} D$ . $m_{9}$ can be covered only by Group B, so Group B is essential. Answer: $F = \overset{ˉ}{A} D + \overset{ˉ}{B} \overset{ˉ}{C} D$ . Cross-check with Quine-McCluskey Method would list the same two prime implicants, with $\overset{ˉ}{B} \overset{ˉ}{C} D$ flagged essential for $m_{9}$ .

Active Recall

Recall What survives in the product term for a group?

Only the variables that are constant across the whole group; every variable that takes both 0 and 1 is dropped (combining theorem).

Recall A size-8 group in a 4-variable map → how many literals?

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

Recall When may you leave a don't-care as 0?

Whenever it is not needed to enlarge a group you already require — never add a term just to cover it.

Recall What makes a group "essential"?

It covers at least one 1 that no other legal group can cover.

Connections

Parent: K-map simplification — the theory these drills exercise.
Boolean Algebra Laws — $X Y + X \overset{ˉ}{Y} = X$ powers every reduction.
Sum of Products and Product of Sums — all answers are minimal SOP.
Truth Tables — the raw form each $\sum m$ comes from.
Logic Gate Minimisation — fewer literals ⇒ fewer gates (Exercises 5.2, 5.3).
Quine-McCluskey Method — cross-check for essential implicants.
Don't-care Conditions — the flexibility used in Exercises 4.1.

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