Exercise DET-03.01 – Normal forms

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

Solution

a) $F_1(A,B)=\sum m(0,2,3)=\prod M(1)$; canonical DNF: $F_1=\overline{A}\cdot \overline{B}+A\cdot \overline{B}+A\cdot B$; canonical CNF: $F_1=A+\overline{B}$
b) a 1 in rows 1, 4 and 6, a 0 in the five other rows; $F_2=\overline{A}\cdot \overline{B}\cdot C+A\cdot \overline{B}\cdot \overline{C}+A\cdot B\cdot \overline{C}$
c) $F_3(A,B,C)=\sum m(1,2,3,4,6,7)$; $F_3=\left(A+B+C\right)\cdot \left(\overline{A}+B+\overline{C}\right)$; two OR gates with three inputs, an AND gate with two inputs and inverters for $A$ and $C$
d) $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)$; the canonical CNF needs fewer gates, five instead of 13: $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)$

▶️ Full worked solution