Exercise DET-04.01 – Prime implicants

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

Relates to DET-04 Algorithmic minimization of functions with many inputs and hazard analysis

Task

In a Karnaugh map, each loop of ones that cannot be enlarged is a prime implicant of the function. In each function, the first variable has the highest weight.

a) Draw the Karnaugh map of $F_1(A,B,C)=\sum m(1,3,4,5)$, and give all its prime implicants. Which of its ones does only a single prime implicant cover? Which prime implicants are essential, and which are redundant? Give the minimal disjunctive normal form (DNF).

b) Answer the same questions for $F_2(A,B,C,D)=\sum m(5,7,10,11,13,15)$.

c) Draw the Karnaugh map of $F_3(A,B,C,D)=\sum m(4,5,6,7,8,9,13)$, and give all its prime implicants and the essential ones among them. Give a minimal DNF. Is it unique?

Solution

a) prime implicants $\overline{A}\cdot C$, $A\cdot \overline{B}$ and $\overline{B}\cdot C$; only one prime implicant covers the ones of minterms 3 and 4; essential: $\overline{A}\cdot C$ and $A\cdot \overline{B}$; redundant: $\overline{B}\cdot C$; $F_1=\overline{A}\cdot C+A\cdot \overline{B}$
b) prime implicants $B\cdot D$, $A\cdot \overline{B}\cdot C$ and $A\cdot C\cdot D$; only one prime implicant covers the ones of minterms 5, 7, 10 and 13; essential: $B\cdot D$ and $A\cdot \overline{B}\cdot C$; redundant: $A\cdot C\cdot D$; $F_2=B\cdot D+A\cdot \overline{B}\cdot C$
c) prime implicants $\overline{A}\cdot B$, $A\cdot \overline{B}\cdot \overline{C}$, $B\cdot \overline{C}\cdot D$ and $A\cdot \overline{C}\cdot D$; essential: $\overline{A}\cdot B$ and $A\cdot \overline{B}\cdot \overline{C}$; not unique, two minimal DNFs: $F_3=\overline{A}\cdot B+A\cdot \overline{B}\cdot \overline{C}+B\cdot \overline{C}\cdot D$ and $F_3=\overline{A}\cdot B+A\cdot \overline{B}\cdot \overline{C}+A\cdot \overline{C}\cdot D$

▶️ Full worked solution