Truth Tables and Normal Forms

Truth Tables

A truth table exhaustively lists every possible combination of input values and the corresponding output of a Boolean function. For a function of $n$ variables, the truth table has $2^n$ rows. The rows are conventionally listed in binary counting order (0 to $2^n - 1$), though other orderings (e.g., Gray code) are sometimes used for specific purposes.

Example: The function $f(x, y, z) = x + y \cdot z$ has the following truth table:

x	y	z	$y \cdot z$	$f = x + y \cdot z$
0	0	0	0	0
0	0	1	0	0
0	1	0	0	0
0	1	1	1	1
1	0	0	0	1
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Minterms

A minterm of $n$ Boolean variables is a product (AND) term that includes every variable exactly once, in either complemented or uncomplemented form. For $n$ variables there are $2^n$ possible minterms.

Notation: $m_i$ denotes the minterm corresponding to row $i$ of the truth table. For a function of 3 variables ($x$, $y$, $z$), with $x$ as the most significant bit:

i	x	y	z	Minterm $m_i$
0	0	0	0	$\bar{x} \cdot \bar{y} \cdot \bar{z}$
1	0	0	1	$\bar{x} \cdot \bar{y} \cdot z$
2	0	1	0	$\bar{x} \cdot y \cdot \bar{z}$
3	0	1	1	$\bar{x} \cdot y \cdot z$
4	1	0	0	$x \cdot \bar{y} \cdot \bar{z}$
5	1	0	1	$x \cdot \bar{y} \cdot z$
6	1	1	0	$x \cdot y \cdot \bar{z}$
7	1	1	1	$x \cdot y \cdot z$

A minterm $m_i$ is TRUE (equals 1) for exactly one input combination: the combination corresponding to row $i$. Note that $y \cdot z$ is NOT a minterm for a 3-variable function because it omits $x$; it is simply a product term.

Disjunctive Normal Form (DNF)

The Disjunctive Normal Form (DNF), also called Sum of Products (SOP) form, expresses a Boolean function as the OR (sum, disjunction) of its minterms. Specifically:

$f = \sum m_i \quad \text{for all } i \text{ where } f = 1$

Using $\Sigma$ notation for brevity: $f = \Sigma(3, 4, 5, 6, 7)$ means the OR of minterms $m_3$, $m_4$, $m_5$, $m_6$, $m_7$.

For the example function $f = x + y \cdot z$ above, the rows where $f = 1$ are 3, 4, 5, 6, 7. The DNF is:

$f = \bar{x} \cdot y \cdot z + x \cdot \bar{y} \cdot \bar{z} + x \cdot \bar{y} \cdot z + x \cdot y \cdot \bar{z} + x \cdot y \cdot z$

DNF has the property that it is canonical: every Boolean function has exactly one DNF representation (up to reordering of minterms). This uniqueness makes DNF useful for comparing functions.

Note on terminology: The term “Sum of Products” (SOP) is often used more broadly to describe any expression that is an OR of AND terms, even if those AND terms are not minterms. For example, $f = x + y \cdot z$ is in SOP form but is NOT in DNF because the terms $x$ and $y \cdot z$ are not minterms (they omit some variables). When we want to be precise, DNF refers specifically to the OR-of-minterms form.

Maxterms

A maxterm of $n$ Boolean variables is a sum (OR) term that includes every variable exactly once, in either complemented or uncomplemented form.

Notation: $M_i$ denotes the maxterm corresponding to row $i$. The rule for constructing maxterms from the truth table: for row $i$, if the variable is 0, use the uncomplemented form; if the variable is 1, use the complemented form. (This is the opposite of the minterm rule.)

For 3 variables:

i	x	y	z	Maxterm $M_i$
0	0	0	0	$x + y + z$
1	0	0	1	$x + y + \bar{z}$
2	0	1	0	$x + \bar{y} + z$
3	0	1	1	$x + \bar{y} + \bar{z}$
4	1	0	0	$\bar{x} + y + z$
5	1	0	1	$\bar{x} + y + \bar{z}$
6	1	1	0	$\bar{x} + \bar{y} + z$
7	1	1	1	$\bar{x} + \bar{y} + \bar{z}$

A maxterm $M_i$ is FALSE (equals 0) for exactly one input combination (row $i$) and is TRUE for all others.

Conjunctive Normal Form (CNF)

The Conjunctive Normal Form (CNF), also called Product of Sums (POS) form, expresses a Boolean function as the AND (product, conjunction) of its maxterms:

$f = \prod M_i \quad \text{for all } i \text{ where } f = 0$

Using $\Pi$ notation: $f = \Pi(0, 1, 2)$ means the AND of maxterms $M_0$, $M_1$, $M_2$.

For the example function $f = x + y \cdot z$, the rows where $f = 0$ are 0, 1, 2. The CNF is:

$f = (x + y + z) \cdot (x + y + \bar{z}) \cdot (x + \bar{y} + z)$

CNF is also canonical: every Boolean function has a unique CNF representation.

Relationship Between DNF and CNF

The maxterm $M_i$ is the complement of the minterm $m_i$, and vice versa:

$M_i = \overline{m_i}$ $m_i = \overline{M_i}$

This can be verified: the minterm $\bar{x} \cdot y \cdot z$ is TRUE only for row 3; its complement is FALSE only for row 3, which is exactly the behaviour of maxterm $M_3 = x + \bar{y} + \bar{z}$. Indeed, by De Morgan: $\overline{\bar{x} \cdot y \cdot z} = x + \bar{y} + \bar{z} = M_3$.

The DNF and CNF of the same function are related by:

$\text{DNF of } f = \text{complement of CNF of } \bar{f}$ $\text{CNF of } f = \text{complement of DNF of } \bar{f}$

Worked Example: Deriving DNF and CNF for $f = \bar{a} \cdot d + \bar{b} \cdot c + \bar{a} \cdot \bar{b} \cdot \bar{c} \cdot d$

This is a 4-variable function $f(a, b, c, d)$. We will build its full truth table and derive both normal forms.

Step 1: Build the Truth Table

For 4 variables there are $2^4 = 16$ rows. We list $a$, $b$, $c$, $d$ in counting order and evaluate the three terms and their OR.

Row	a	b	c	d	$\bar{a} \cdot d$	$\bar{b} \cdot c$	$\bar{a} \cdot \bar{b} \cdot \bar{c} \cdot d$	$f$
0	0	0	0	0	0	0	0	0
1	0	0	0	1	1	0	1	1
2	0	0	1	0	0	1	0	1
3	0	0	1	1	1	1	0	1
4	0	1	0	0	0	0	0	0
5	0	1	0	1	1	0	0	1
6	0	1	1	0	0	0	0	0
7	0	1	1	1	1	0	0	1
8	1	0	0	0	0	0	0	0
9	1	0	0	1	0	0	0	0
10	1	0	1	0	0	1	0	1
11	1	0	1	1	0	1	0	1
12	1	1	0	0	0	0	0	0
13	1	1	0	1	0	0	0	0
14	1	1	1	0	0	0	0	0
15	1	1	1	1	0	0	0	0

Step 2: DNF from $f = 1$ rows

Rows where $f = 1$: 1, 2, 3, 5, 7, 10, 11.

Writing the minterms (using $a$ as MSB, $d$ as LSB):

$m_1 = \bar{a} \cdot \bar{b} \cdot \bar{c} \cdot d$ $m_2 = \bar{a} \cdot \bar{b} \cdot c \cdot \bar{d}$ $m_3 = \bar{a} \cdot \bar{b} \cdot c \cdot d$ $m_5 = \bar{a} \cdot b \cdot \bar{c} \cdot d$ $m_7 = \bar{a} \cdot b \cdot c \cdot d$ $m_{10} = a \cdot \bar{b} \cdot c \cdot \bar{d}$ $m_{11} = a \cdot \bar{b} \cdot c \cdot d$

So the DNF is:

$f = \bar{a}\bar{b}\bar{c}d + \bar{a}\bar{b}c\bar{d} + \bar{a}\bar{b}cd + \bar{a}b\bar{c}d + \bar{a}bcd + a\bar{b}c\bar{d} + a\bar{b}cd$

Or in compact notation: $f = \Sigma(1, 2, 3, 5, 7, 10, 11)$.

Step 3: CNF from $f = 0$ rows

Rows where $f = 0$: 0, 4, 6, 8, 9, 12, 13, 14, 15.

Writing the maxterms:

For each row, variables that are 0 appear uncomplemented; variables that are 1 appear complemented.

Row	a	b	c	d	Maxterm
0	0	0	0	0	$a + b + c + d$
4	0	1	0	0	$a + \bar{b} + c + d$
6	0	1	1	0	$a + \bar{b} + \bar{c} + d$
8	1	0	0	0	$\bar{a} + b + c + d$
9	1	0	0	1	$\bar{a} + b + c + \bar{d}$
12	1	1	0	0	$\bar{a} + \bar{b} + c + d$
13	1	1	0	1	$\bar{a} + \bar{b} + c + \bar{d}$
14	1	1	1	0	$\bar{a} + \bar{b} + \bar{c} + d$
15	1	1	1	1	$\bar{a} + \bar{b} + \bar{c} + \bar{d}$

So the CNF is:

$f = (a + b + c + d) \cdot (a + \bar{b} + c + d) \cdot (a + \bar{b} + \bar{c} + d) \cdot (\bar{a} + b + c + d) \cdot (\bar{a} + b + c + \bar{d}) \cdot (\bar{a} + \bar{b} + c + d) \cdot (\bar{a} + \bar{b} + c + \bar{d}) \cdot (\bar{a} + \bar{b} + \bar{c} + d) \cdot (\bar{a} + \bar{b} + \bar{c} + \bar{d})$

Or in compact notation: $f = \Pi(0, 4, 6, 8, 9, 12, 13, 14, 15)$.

Observation

The DNF has 7 minterms and the CNF has 9 maxterms. Neither is simplified; both are canonical and unique. The function has more zeros than ones, so DNF is more compact in this case. For implementation, we would simplify from either form (see Karnaugh Maps).

Non-Canonical SOP and POS

In practice we rarely use the full DNF/CNF for implementation because they are not simplified. Instead we use:

• SOP (Sum of Products): any OR of AND terms, not necessarily minterms. E.g., $f = \bar{a} \cdot d + \bar{b} \cdot c + \bar{a} \cdot \bar{b} \cdot \bar{c} \cdot d$ is SOP but not DNF.
• POS (Product of Sums): any AND of OR terms, not necessarily maxterms.

The minimisation techniques covered in the following notes take the canonical forms and produce simplified SOP or POS expressions.

Summary

Property	DNF (SOP of minterms)	CNF (POS of maxterms)
Form	OR of ANDs	AND of ORs
Terms are	Minterms (all vars, ANDed)	Maxterms (all vars, ORed)
Canonical?	Yes (unique)	Yes (unique)
Constructed from rows where	$f = 1$	$f = 0$
Compact notation	$\Sigma(\text{row indices of 1s})$	$\Pi(\text{row indices of 0s})$
Minimised?	No	No