Exercise DET-03.01 – Normal forms (Solution)

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

Relates to DET-03 Representation and minimization of logic functions

Task

A logic function can be written in several equivalent forms: as a truth table, as a minterm list or a maxterm list, and as a canonical disjunctive normal form (DNF) or a canonical conjunctive normal form (CNF). In this exercise, you switch between these forms. In each function, the first variable has the highest weight, as in the truth tables of the lesson.

a) The function $F_1(A,B)$ has the following truth table. Give its minterm list, its maxterm list, its canonical DNF and its canonical CNF.

Row	$A$	$B$	$F_1$
0	0	0	1
1	0	1	0
2	1	0	1
3	1	1	1

b) Set up the truth table of $F_2(A,B,C)=\sum m(1,4,6)$, and give its canonical DNF.

c) Give the minterm list and the canonical CNF of $F_3(A,B,C)=\prod M(0,5)$, and draw the two-level circuit of the canonical CNF.

d) The function $F_4(A,B,C,D)$ has the following truth table. Give its minterm list and its maxterm list. Which of the two canonical normal forms needs fewer gates? Write that normal form down.

Row	$A$	$B$	$C$	$D$	$F_4$
0	0	0	0	0	1
1	0	0	0	1	0
2	0	0	1	0	1
3	0	0	1	1	1
4	0	1	0	0	1
5	0	1	0	1	1
6	0	1	1	0	0
7	0	1	1	1	1
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	0
12	1	1	0	0	0
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	1

◀️ Back to the task

---

Solution

Given

Given explicitly:

• a) the truth table of $F_1(A,B)$
• b) $F_2(A,B,C)=\sum m(1,4,6)$
• c) $F_3(A,B,C)=\prod M(0,5)$
• d) the truth table of $F_4(A,B,C,D)$

Known:

• Minterms and the canonical DNF (DET-03, DET-03)
• Maxterms and the canonical CNF (DET-03, DET-03)
• Minterm and maxterm lists (DET-03)
• Truth table in the order of a binary count (DET-02)
• Effort of a circuit: the gates and their inputs (DET-03)

Required

a) the minterm list, the maxterm list, the canonical DNF and the canonical CNF of $F_1$
b) the truth table and the canonical DNF of $F_2$
c) the minterm list, the canonical CNF and the two-level circuit of $F_3$
d) the minterm list and the maxterm list of $F_4$, and the canonical normal form with fewer gates

a) Two inputs

The minterm list names the rows with $F_1=1$, the maxterm list the rows with $F_1=0$ (DET-03, 2.5). Here, $F_1$ is 0 only in row 1:

$$F_1(A,B)=\sum m(0,2,3)=\prod M(1)$$

For the canonical DNF, you need the minterm of each row with $F_1=1$. A variable that is 0 in the row appears negated, a variable that is 1 appears as it is (DET-03, 2.1):

Row	$A$	$B$	$F_1$	Minterm
0	0	0	1	$\overline{A}\cdot \overline{B}$
2	1	0	1	$A\cdot \overline{B}$
3	1	1	1	$A\cdot B$

In row 0, both inputs are 0, so both appear negated; in row 2, only $B$ is 0; in row 3, neither. The OR of the three minterms is the canonical DNF (DET-03, 2.2):

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

For the canonical CNF, you need the maxterm of each row with $F_1=0$. Here, the rule is reversed: a variable that is 1 in the row appears negated, a variable that is 0 appears as it is (DET-03, 2.3). The only zero lies in row 1, with $A=0$ and $B=1$. Its maxterm alone is the canonical CNF (DET-03, 2.4):

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

With a single zero, the canonical CNF needs only an OR gate with two inputs and an inverter, while the canonical DNF needs three AND gates and an OR gate.

Check in row 1, the only zero of $F_1$. For $A=0$ and $B=1$:

$$A+\overline{B}=0+\overline{1}=0+0=0$$

In every other row, $A=1$ or $B=0$, and the sum is 1 ✓

b) From the minterm list to the canonical DNF

The minterm list names the rows in which $F_2=1$: rows 1, 4 and 6. In the five other rows, $F_2=0$. With three inputs, the truth table has $2^3=8$ rows, in the order of a binary count (DET-02, 2.2). The last column shows the minterm of each row with $F_2=1$ (DET-03, 2.1):

Row	$A$	$B$	$C$	$F_2$	Minterm
0	0	0	0	0
1	0	0	1	1	$\overline{A}\cdot \overline{B}\cdot C$
2	0	1	0	0
3	0	1	1	0
4	1	0	0	1	$A\cdot \overline{B}\cdot \overline{C}$
5	1	0	1	0
6	1	1	0	1	$A\cdot B\cdot \overline{C}$
7	1	1	1	0

The OR of the three minterms is the canonical DNF (DET-03, 2.2):

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

Check in row 4, where $F_2$ must be 1. For $A=1$, $B=0$ and $C=0$, only the second minterm is 1:

$$\overline{1}\cdot \overline{0}\cdot 0+1\cdot \overline{0}\cdot \overline{0}+1\cdot 0\cdot \overline{0}=0+1+0=1$$

The 1 comes from the minterm of row 4 alone, as the minterm list demands ✓

c) From the maxterm list to the canonical CNF

Every row number appears in exactly one of the two lists (DET-03, 2.5). The maxterm list names rows 0 and 5, so $F_3=1$ in the six other rows:

$$F_3(A,B,C)=\prod M(0,5)=\sum m(1,2,3,4,6,7)$$

In a maxterm, a variable that is 1 in the row appears negated, a variable that is 0 appears as it is (DET-03, 2.3):

Row	$A$	$B$	$C$	$F_3$	Maxterm
0	0	0	0	0	$A+B+C$
5	1	0	1	0	$\overline{A}+B+\overline{C}$

The AND of the two maxterms is the canonical CNF (DET-03, 2.4):

$$F_3=\left(A+B+C\right)\cdot \left(\overline{A}+B+\overline{C}\right)$$

The circuit has two levels: an OR gate with three inputs for each maxterm and an AND gate with two inputs that combines them (DET-03, 2.4). Two inverters provide $\overline{A}$ and $\overline{C}$; $B$ only appears as it is (figure).

Check in the two rows of the maxterm list, where $F_3$ must be 0. For $A=0$, $B=0$ and $C=0$, the first maxterm is 0:

$$(0+0+0)\cdot (\overline{0}+0+\overline{0})=0\cdot 1=0$$

For $A=1$, $B=0$ and $C=1$, the second maxterm is 0:

$$(1+0+1)\cdot (\overline{1}+0+\overline{1})=1\cdot 0=0$$

In every other row, both maxterms are 1, and so is their AND ✓

d) Four inputs: the shorter canonical normal form

$F_4$ has 12 ones and four zeros, the zeros in rows 1, 6, 11 and 12 (DET-03, 2.5):

$$\begin{array}{rl}{F}_4(A,B,C,D)& =\sum m(0,2,3,4,5,7,8,9,10,13,14,15)\\ & =\prod M(1,6,11,12)\end{array}$$

The canonical DNF needs a minterm for each of the 12 ones, the canonical CNF a maxterm for each of the four zeros. Counted as in the lesson (DET-03, 3.1), with four inverters in both cases:

Canonical normal form	AND gates	OR gates	Gate inputs
DNF	12	1	60
CNF	1	4	20

The canonical CNF needs five gates instead of 13: with few zeros, the CNF is the shorter canonical form, with few ones the DNF (DET-03, 2.5). Its maxterms, one for each zero (DET-03, 2.3):

Row	$A$	$B$	$C$	$D$	$F_4$	Maxterm
1	0	0	0	1	0	$A+B+C+\overline{D}$
6	0	1	1	0	0	$A+\overline{B}+\overline{C}+D$
11	1	0	1	1	0	$\overline{A}+B+\overline{C}+\overline{D}$
12	1	1	0	0	0	$\overline{A}+\overline{B}+C+D$

$$\begin{array}{rl}{F}_4& =\left(A+B+C+\overline{D}\right)\cdot \left(A+\overline{B}+\overline{C}+D\right)\\ & \cdot \left(\overline{A}+B+\overline{C}+\overline{D}\right)\cdot \left(\overline{A}+\overline{B}+C+D\right)\end{array}$$

Check in row 6, where $F_4$ must be 0. For $A=0$, $B=1$, $C=1$ and $D=0$, the second maxterm is 0:

$$A+\overline{B}+\overline{C}+D=0+\overline{1}+\overline{1}+0=0$$

and so is the whole AND. Together, the two lists contain $12+4=16$ row numbers, each of them once ✓