Exercise DET-03.03 – Karnaugh maps

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.

Solution

a) loops of ones: $F_1=\overline{A}+B$, from two loops of two; loops of zeros: $F_1=\overline{A}+B$, from a loop around the single zero
b) $F_2=\overline{C}+A\cdot \overline{B}$: a loop of four across the left and the right edge and a loop of two
c) $F_2=\left(A+\overline{C}\right)\cdot \left(\overline{B}+\overline{C}\right)$; the DNF of b) needs fewer gates: two gates with four gate inputs instead of three gates with six
d) $F_3=\overline{C}\cdot \overline{D}+B\cdot D$: a loop around the four corners and a square of four
e) $F_3=\left(B+\overline{D}\right)\cdot \left(\overline{C}+D\right)$: a square of four and a loop of four across the top and the bottom edge
f) a chequerboard: no two ones are neighbours, because a change of a single input always changes $F_4$; $F_4=A\oplus B\oplus C\oplus D$ with three XOR gates with two inputs

▶️ Full worked solution