Exercise DET-04.01 – Prime implicants (Solution)

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?

◀️ Back to the task

---

Solution

Given

Given explicitly:

• a) $F_1(A,B,C)=\sum m(1,3,4,5)$
• b) $F_2(A,B,C,D)=\sum m(5,7,10,11,13,15)$
• c) $F_3(A,B,C,D)=\sum m(4,5,6,7,8,9,13)$
• in each function, the first variable has the highest weight

Known:

• Arrangement of the Karnaugh map: neighbouring cells differ in exactly one input, also across the edges (DET-03)
• Loops of ones and the product term of a loop (DET-03)
• Implicants and prime implicants: a prime implicant is a loop of ones that cannot be enlarged (DET-04)
• Essential and redundant prime implicants, minimal disjunctive normal form (DNF) (DET-04)
• Prime implicants that complete the minimal DNF when the essential ones leave ones uncovered (DET-04)

Required

a) and b) all prime implicants of $F_1$ and of $F_2$, the ones that only a single prime implicant covers, the essential and the redundant prime implicants, and the minimal DNF
c) all prime implicants of $F_3$, the essential ones among them, a minimal DNF and whether it is unique

a) Three inputs

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 four ones of $F_1$ lie in the cells of 1 and 3 in the upper row and of 4 and 5 in the lower row (figure).

Each loop of ones that cannot be enlarged is a prime implicant (DET-04, 1.1). No four ones form a block, so there is no loop of four; three loops of two remain:

• the ones of 1 and 3, neighbours in the upper row: $A$ is 0 and $C$ is 1, while $B$ changes, so the loop yields $\overline{A}\cdot C$
• the ones of 4 and 5, neighbours in the lower row: $A$ is 1 and $B$ is 0, while $C$ changes: $A\cdot \overline{B}$
• the ones of 1 and 5, neighbours in the second column: $B$ is 0 and $C$ is 1, while $A$ changes: $\overline{B}\cdot C$

Now look for ones that only a single prime implicant covers (DET-04, 1.2). The one of minterm 3 lies only in $\overline{A}\cdot C$, the one of minterm 4 only in $A\cdot \overline{B}$; in the figure, these two cells are shaded. Both prime implicants are therefore essential. Together, they cover all four ones. The ones of $\overline{B}\cdot C$, minterms 1 and 5, already lie in them, so $\overline{B}\cdot C$ is redundant and is drawn with dashed lines:

Prime implicant	Minterms	Ones that only it covers	Kind
$\overline{A}\cdot C$	1, 3	3	essential
$A\cdot \overline{B}$	4, 5	4	essential
$\overline{B}\cdot C$	1, 5	–	redundant

The essential prime implicants form the minimal DNF:

$$F_1=\overline{A}\cdot C+A\cdot \overline{B}$$

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

b) Four inputs

With four inputs, the map has $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 six ones of $F_2$ form three loops that cannot be enlarged (figure):

• the ones of 5, 7, 13 and 15, a square in the third and the fourth column of the two middle rows: $B$ and $D$ are 1, while $A$ and $C$ change: $B\cdot D$
• the ones of 11 and 10 in the second column of the two lower rows: $A$ is 1, $B$ is 0 and $C$ is 1, while $D$ changes: $A\cdot \overline{B}\cdot C$
• the ones of 11 and 15 in the third row: $A$, $C$ and $D$ are 1, while $B$ changes: $A\cdot C\cdot D$

The ones of minterms 5, 7 and 13 lie only in $B\cdot D$, the one of minterm 10 only in $A\cdot \overline{B}\cdot C$ (shaded cells): both prime implicants are essential. The ones of $A\cdot C\cdot D$ lie in them as well, minterm 11 in $A\cdot \overline{B}\cdot C$ and minterm 15 in $B\cdot D$, so $A\cdot C\cdot D$ is redundant (DET-04, 1.2):

Prime implicant	Minterms	Ones that only it covers	Kind
$B\cdot D$	5, 7, 13, 15	5, 7, 13	essential
$A\cdot \overline{B}\cdot C$	10, 11	10	essential
$A\cdot C\cdot D$	11, 15	–	redundant

$$F_2=B\cdot D+A\cdot \overline{B}\cdot C$$

Check with the minterm list: $B\cdot D$ is 1 in rows 5, 7, 13 and 15, $A\cdot \overline{B}\cdot C$ in rows 10 and 11; together, these are the six ones of $F_2$ ✓

c) A choice

The seven ones of $F_3$ lie in the cells of 6 and 4 in the first row, 7 and 5 in the second row, 9 and 13 in the third row and 8 in the fourth row (figure). Four loops cannot be enlarged:

• the ones of 4, 5, 6 and 7, a square in the third and the fourth column of the two upper rows: $A$ is 0 and $B$ is 1, while $C$ and $D$ change: $\overline{A}\cdot B$
• the ones of 9 and 8 in the first column of the two lower rows: $A$ is 1, $B$ and $C$ are 0, while $D$ changes: $A\cdot \overline{B}\cdot \overline{C}$
• the ones of 5 and 13 in the fourth column of the two middle rows: $B$ is 1, $C$ is 0 and $D$ is 1, while $A$ changes: $B\cdot \overline{C}\cdot D$
• the ones of 9 and 13 in the third row, neighbours across the left and the right edge: $A$ is 1, $C$ is 0 and $D$ is 1, while $B$ changes: $A\cdot \overline{C}\cdot D$

The ones of minterms 4, 6 and 7 lie only in $\overline{A}\cdot B$, the one of minterm 8 only in $A\cdot \overline{B}\cdot \overline{C}$ (shaded cells): these two prime implicants are essential. Together, they leave the one of minterm 13 uncovered (DET-04, 1.3). Two prime implicants contain it, $B\cdot \overline{C}\cdot D$ and $A\cdot \overline{C}\cdot D$, drawn with dashed lines. Neither of them is essential: each of their ones also lies in another prime implicant. Neither of them is redundant either: minterm 13 lies in no essential prime implicant. In the table, they are therefore of the kind ‘neither’:

Prime implicant	Minterms	Ones that only it covers	Kind
$\overline{A}\cdot B$	4, 5, 6, 7	4, 6, 7	essential
$A\cdot \overline{B}\cdot \overline{C}$	8, 9	8	essential
$B\cdot \overline{C}\cdot D$	5, 13	–	neither
$A\cdot \overline{C}\cdot D$	9, 13	–	neither

Either of the two completes the minimal DNF, and both forms have three product terms with eight literals:

$$\begin{array}{rl}{F}_3& =\overline{A}\cdot B+A\cdot \overline{B}\cdot \overline{C}+B\cdot \overline{C}\cdot D\\ F_3& =\overline{A}\cdot B+A\cdot \overline{B}\cdot \overline{C}+A\cdot \overline{C}\cdot D\end{array}$$

So the minimal DNF of $F_3$ is not unique: there are two of the same size.

Check with the minterm list: $\overline{A}\cdot B$ is 1 in rows 4 to 7 and $A\cdot \overline{B}\cdot \overline{C}$ in rows 8 and 9; $B\cdot \overline{C}\cdot D$ adds row 13 (and row 5 again), $A\cdot \overline{C}\cdot D$ adds row 13 (and row 9 again). Each form is therefore 1 exactly in rows 4, 5, 6, 7, 8, 9 and 13 ✓