Exercise DET-03.03 – Karnaugh maps (Solution)

Prof. Dr. Thorsten Jungmann (last updated 2026-10-19)

Relates to DET-03 Representation and minimization of logic functions

Task

With a Karnaugh map, you minimize a function graphically: loops of ones yield a minimized disjunctive normal form (DNF), loops of zeros a minimized conjunctive normal form (CNF). Draw the map of each function and give the result.

a) Minimize $F_{1} (A, B) = \sum m (0, 1, 3)$ with a Karnaugh map, once with loops of ones and once with loops of zeros.

b) Minimize $F_{2} (A, B, C) = \sum m (0, 2, 4, 5, 6)$ with loops of ones.

c) Minimize $F_{2}$ from b) with loops of zeros. Which of the two results needs fewer gates?

d) Minimize $F_{3} (A, B, C, D) = \sum m (0, 4, 5, 7, 8, 12, 13, 15)$ with loops of ones.

e) Minimize $F_{3}$ from d) with loops of zeros.

f) Draw the Karnaugh map of $F_{4} (A, B, C, D) = \sum m (1, 2, 4, 7, 8, 11, 13, 14)$ . Why does no loop help here? Give a circuit for $F_{4}$ with as few gates as possible.

◀️ Back to the task

Solution

Given

Given explicitly:

a) $F_{1} (A, B) = \sum m (0, 1, 3)$
b) and c) $F_{2} (A, B, C) = \sum m (0, 2, 4, 5, 6)$
d) and e) $F_{3} (A, B, C, D) = \sum m (0, 4, 5, 7, 8, 12, 13, 15)$
f) $F_{4} (A, B, C, D) = \sum m (1, 2, 4, 7, 8, 11, 13, 14)$

Known:

Karnaugh map with two and with three inputs (DET-02)
Arrangement of the Karnaugh map: neighbouring cells differ in exactly one input, also across the edges; the labels show where each input is 1 (DET-03)
Rules for loops of ones and the product term of a loop (DET-03)
Loops of zeros and their sum terms (DET-03)
The chequerboard and XOR (DET-03)
Effort of a circuit: the gates and their inputs (DET-03)

Required

a) the minimized DNF and the minimized CNF of $F_{1}$
b) and d) the minimized DNF of $F_{2}$ and of $F_{3}$
c) and e) the minimized CNF of $F_{2}$ and of $F_{3}$ ; in c), the result that needs fewer gates
f) the Karnaugh map of $F_{4}$ , the reason why no loop helps, and a circuit with as few gates as possible

a) Two inputs

With two inputs, the map has two rows for $A$ and two columns for $B$ (DET-02, 2.6). It contains a 1 in the cells of the minterms 0, 1 and 3 and a 0 in the cell of 2.

Loops of ones (figure): the ones in the cells of 0 and 1 are neighbours in the upper row. There, $A$ is 0, while $B$ changes, so this loop yields $\overline{A}$ . The ones in the cells of 1 and 3 are neighbours in the right column: $B$ is 1, while $A$ changes, so this loop yields $B$ . The cell of 1 lies in both loops; loops may overlap (DET-03, 4.2).

Karnaugh map of F1 with ones in three cells and a zero at the bottom left, with one loop around the two ones of the upper row and one around the two ones of the right column

F_{1} = \overline{A} + B

Loops of zeros (figure): the single zero, in the cell of 2, has no neighbouring zero and forms a loop of one cell. There, $A$ is 1 and $B$ is 0. In a sum term, a variable that is 1 appears negated and a variable that is 0 appears as it is (DET-03, 4.3).

Karnaugh map of F1 with a single loop around the only zero at the bottom left

F_{1} = \overline{A} + B

Both ways yield the same expression: the sum term of a single zero is its maxterm, and nothing is left to unite.

Check with the minterm list: $\overline{A}$ is 1 in rows 0 and 1, $B$ in rows 1 and 3; together, these are rows 0, 1 and 3 ✓

b) Three inputs, loops of ones

With three inputs, the map has two rows for $A$ and four columns for $B$ and $C$ ; in the upper row, the cells contain the minterms 0, 1, 3 and 2, in the lower row 4, 5, 7 and 6 (DET-02, 2.6). The ones of $F_{2}$ form two loops (figure):

The four ones in the first and the last column, in the cells of 0, 4, 2 and 6, form a loop of four, because the first and the last column are neighbours across the edge (DET-03, 4.1). In all four cells, $C$ is 0, while $A$ and $B$ change: the loop yields $\overline{C}$ .
The one in the cell of 5 is a neighbour of the one in the cell of 4 to its left. There, $A$ is 1 and $B$ is 0, while $C$ changes: the loop yields $A \cdot \overline{B}$ . The cell of 4 lies in both loops.

Karnaugh map of F2 for three inputs with a loop of four ones across the left and the right edge and a loop of two ones in the lower row

F_{2} = \overline{C} + A \cdot \overline{B}

Check with the minterm list: $\overline{C}$ is 1 in rows 0, 2, 4 and 6, $A \cdot \overline{B}$ in rows 4 and 5; together, these are rows 0, 2, 4, 5 and 6 ✓

c) Three inputs, loops of zeros

The zeros of $F_{2}$ lie in the cells of 1, 3 and 7 (figure). The cells of 1 and 3 are neighbours in the upper row: $A$ is 0 and $C$ is 1, while $B$ changes, so the sum term is $A + \overline{C}$ . The cells of 3 and 7 are neighbours in the third column: $B$ is 1 and $C$ is 1, while $A$ changes, so the sum term is $\overline{B} + \overline{C}$ (DET-03, 4.3). The cell of 3 lies in both loops.

Karnaugh map of F2 for three inputs with a loop around the two zeros in the middle of the upper row and a loop around the two zeros of the third column

F_{2} = (A + \overline{C}) \cdot (\overline{B} + \overline{C})

Counted as in the lesson (DET-03, 3.1):

Minimized form	AND gates	OR gates	Gate inputs	Inverters
DNF of b)	1	1	4	2
CNF of c)	1	2	6	2

The DNF of b) needs fewer gates: two gates with four gate inputs instead of three gates with six. Both forms need inverters for $B$ and $C$ .

Check: the CNF is 0 where one of its sum terms is 0. $A + \overline{C}$ is 0 in rows 1 and 3, $\overline{B} + \overline{C}$ in rows 3 and 7; together, these are rows 1, 3 and 7, the zeros of $F_{2}$ ✓

d) Four inputs, loops of ones

With four inputs, the map has four rows and four columns: $A$ on the left of the rows and $D$ on the right of them, $B$ above and $C$ below the columns. Row by row, the cells contain the minterms 0, 2, 6 and 4; 1, 3, 7 and 5; 9, 11, 15 and 13; 8, 10, 14 and 12 (DET-03, 4.1). The ones of $F_{3}$ form two loops (figure):

The four corners hold the minterms 0, 4, 8 and 12. Each corner is a neighbour of the corner in its row and of the corner in its column, so the four corners form a loop of four. In all four cells, $C$ and $D$ are 0, while $A$ and $B$ change: the loop yields $\overline{C} \cdot \overline{D}$ .
The minterms 5, 7, 13 and 15 form a square in the third and the fourth column of the two middle rows. There, $B$ and $D$ are 1, while $A$ and $C$ change: the loop yields $B \cdot D$ .

The fourth column, with the minterms 4, 5, 13 and 12, would also form a loop of four ones. All its ones already lie in the two other loops, so it is not needed and is left out (DET-03, 4.2).

Karnaugh map of F3 for four inputs with a loop that connects the ones in the four corners and a loop around a square of four ones on the right of the two middle rows

F_{3} = \overline{C} \cdot \overline{D} + B \cdot D

Check with the minterm list: $\overline{C} \cdot \overline{D}$ is 1 in rows 0, 4, 8 and 12, $B \cdot D$ in rows 5, 7, 13 and 15; together, these are the eight ones of $F_{3}$ ✓

e) Four inputs, loops of zeros

The zeros of $F_{3}$ form two loops of four (figure):

The zeros in the cells of 1, 3, 9 and 11 form a square in the first and the second column of the two middle rows. There, $B$ is 0 and $D$ is 1, so the sum term is $B + \overline{D}$ .
The zeros in the cells of 2, 6, 10 and 14 lie in the second and the third column of the top and the bottom row. The top and the bottom row are neighbours across the edge, so the four cells form a loop. There, $C$ is 1 and $D$ is 0, so the sum term is $\overline{C} + D$ (DET-03, 4.3).

Karnaugh map of F3 for four inputs with a loop around a square of four zeros on the left of the two middle rows and a loop that connects four zeros of the top and the bottom row across the edge

F_{3} = (B + \overline{D}) \cdot (\overline{C} + D)

Check: $B + \overline{D}$ is 0 in rows 1, 3, 9 and 11, $\overline{C} + D$ in rows 2, 6, 10 and 14; together, these are the eight zeros of $F_{3}$ ✓

f) The chequerboard

In the map of $F_{4}$ , the ones and zeros alternate like the squares of a chequerboard (figure). $F_{4}$ is 1 exactly in the rows with an odd number of ones among $A$ , $B$ , $C$ and $D$ : rows 1, 2, 4 and 8 contain a single 1, rows 7, 11, 13 and 14 contain three. Neighbouring cells differ in exactly one input, and a change of a single input always turns an odd number of ones into an even one, or vice versa. Every neighbour of a one is therefore a zero, and no loop can unite two cells: the minimized DNF would be the canonical one, with eight minterms of four literals each (DET-03, 4.5).

The chequerboard reveals XOR (DET-03, 4.5). An XOR gate delivers a 1 if its two inputs differ, that is, if an odd number of them is 1. One XOR gate combines $A$ and $B$ , a second one $C$ and $D$ ; each delivers a 1 if an odd number of its two inputs is 1. A third XOR gate delivers a 1 if exactly one of the two pairs contains an odd number of ones, and this is the case exactly if an odd number of all four inputs is 1:

F_{4} = A \oplus B \oplus C \oplus D = (A \oplus B) \oplus (C \oplus D)

Karnaugh map of F4 with ones and zeros arranged like a chequerboard and without loops, above a circuit of three XOR gates with the output F4 that combines A and B, C and D and then both results

Three XOR gates with two inputs replace eight AND gates with four inputs, an OR gate with eight inputs and four inverters.

Check in row 7, with $A = 0$ , $B = 1$ , $C = 1$ and $D = 1$ :

(0 \oplus 1) \oplus (1 \oplus 1) = 1 \oplus 0 = 1

Row 7 is in the minterm list ✓

Wattsinside