4.2 Boolean Identities, DeMorgan & Sum-of-Products

Theory: Boolean Identities, DeMorgan & Sum-of-Products

Every gate in a circuit costs money, space, power and delay. Two different-looking Boolean expressions can describe exactly the same function (the same truth table), and the shorter one gives a cheaper, faster circuit. This page shows how to evaluate a Boolean function, the algebraic laws (identities) used to rewrite it, DeMorgan’s law for complements, and how to read a function straight off a truth table in canonical sum-of-products form (Null & Lobur, Ch. 3).

Notation: complement is written with a prime, $x'$ (the overbar $\overline{x}$ in the textbook means the same).

Boolean Functions and Rules of Precedence

A Boolean function combines variables with operators, e.g. $F(x, y, z) = xz' + y$. To read an expression correctly you need the precedence rules, highest first:

Priority	Operator	Analogy
1 (highest)	NOT ($'$)	like a minus sign attached to a number
2	AND (product)	like multiplication
3 (lowest)	OR (sum)	like addition

Parentheses override precedence. So $xz' + y$ means $(x \cdot (z')) + y$, not $x \cdot (z + y)'$.

A prime applies only to what it is directly attached to. $xy'$ complements only $y$; $(xy)'$ complements the whole product. These are different functions.

Evaluating a Function with a Truth Table

Procedure:

1. List all $2^n$ input rows.
2. Add one column for each sub-expression, in precedence order (NOTs first, then products, then the final sum).
3. Fill each column from the columns before it.

Mini-example (lecture function)

$F(x, y, z) = xz' + y$:

$x$	$y$	$z$	$z'$	$xz'$	$F = xz' + y$
0	0	0	1	0	0
0	0	1	0	0	0
0	1	0	1	0	1
0	1	1	0	0	1
1	0	0	1	1	1
1	0	1	0	0	0
1	1	0	1	1	1
1	1	1	0	0	1

Boolean Identities

Most identities come in pairs: an AND (product) form and an OR (sum) form. Each is obtained from the other by swapping AND with OR and 0 with 1 (this is called duality).

Group 1: identities with constants and a single variable

Identity	AND form	OR form
Identity law	$1x = x$	$0 + x = x$
Null (dominance) law	$0x = 0$	$1 + x = 1$
Idempotent law	$xx = x$	$x + x = x$
Inverse law	$xx' = 0$	$x + x' = 1$

Group 2: laws that look like ordinary algebra

Identity	AND form	OR form
Commutative law	$xy = yx$	$x + y = y + x$
Associative law	$(xy)z = x(yz)$	$(x+y)+z = x+(y+z)$
Distributive law	$x + yz = (x+y)(x+z)$	$x(y+z) = xy + xz$

Group 3: laws with no ordinary-algebra equivalent

Identity	AND form	OR form
Absorption law	$x(x+y) = x$	$x + xy = x$
DeMorgan’s law	$(xy)' = x' + y'$	$(x+y)' = x'y'$
Double complement law	$(x')' = x$

The distributive law works both ways in Boolean algebra: AND distributes over OR (as in ordinary algebra) and OR distributes over AND: $x + yz = (x+y)(x+z)$. The second one has no counterpart with numbers, but it is often the key step in a simplification.

Mini-example

Absorption from the other laws: $x + xy = x \cdot 1 + xy$ (Identity) $= x(1 + y)$ (Distributive) $= x \cdot 1$ (Null) $= x$ (Identity).

DeMorgan’s Law

$$(xy)' = x' + y' \qquad\qquad (x+y)' = x'y'$$

In words: the complement of a product is the sum of the complements, and the complement of a sum is the product of the complements. Proof by truth table:

$x$	$y$	$(xy)'$	$x' + y'$	$(x+y)'$	$x'y'$
0	0	1	1	1	1
0	1	1	1	0	0
1	0	1	1	0	0
1	1	0	0	0	0

Why it matters: sometimes it is more economical to build the complement of a function and invert the result at the end, and DeMorgan is how you move between the two forms. It is also what turns AND/OR circuits into NAND-only or NOR-only circuits.

Extended DeMorgan: Complementing a Whole Function

DeMorgan extends to any number of variables: $(x_1 x_2 \cdots x_n)' = x_1' + x_2' + \cdots + x_n'$ and $(x_1 + \cdots + x_n)' = x_1' \cdots x_n'$.

Recipe for the complement $F'$ of any expression:

1. Replace each variable by its complement ($x \to x'$, $x' \to x$).
2. Change every AND to OR and every OR to AND.
3. Keep the grouping: put parentheses around what used to be each product term, so the structure is preserved.

Mini-example (lecture)

$F(x,y,z) = xy + x'z + yz'$.

$$\begin{aligned} F' &= \big(xy + x'z + yz'\big)' \\ &= (xy)'\,(x'z)'\,(yz')' && \text{DeMorgan (OR form, 3 terms)} \\ &= (x' + y')\,(x + z')\,(y' + z) && \text{DeMorgan (AND form) on each, Double complement} \end{aligned}$$

Simplifying with Identities

Procedure:

1. Remove complements of whole groups with DeMorgan.
2. Multiply out (Distributive) or factor (Distributive in reverse) to expose patterns like $y + y'$ or $yy'$.
3. Replace $y + y' = 1$, $yy' = 0$ (Inverse), then clean up with Identity, Null, Idempotent and Absorption.
4. Cite the law used at each step. Check the final answer with a truth table if unsure.

Useful patterns to recognise immediately:

Pattern	Result	Laws
$xy + xy'$	$x$	Distributive, Inverse, Identity
$(x+y)(x+y')$	$x$	Distributive ($x + yy'$), Inverse, Identity
$x + x'y$	$x + y$	Distributive ($(x+x')(x+y)$), Inverse, Identity
$x(x' + y)$	$xy$	Distributive, Inverse, Identity
$xy + x'z + yz$	$xy + x'z$	consensus (see Worked Example 4)

Mini-example

$x + x'y = (x + x')(x + y)$ (Distributive, OR over AND) $= 1 \cdot (x + y)$ (Inverse) $= x + y$ (Identity).

Canonical Sum-of-Products (SOP) from a Truth Table

A sum-of-products is an OR of AND terms, e.g. $xy' + yz$. A truth table converts directly into one:

Procedure (canonical SOP):

1. Look only at the rows where $F = 1$.
2. For each such row write a product term containing every variable: the variable itself if it is 1 in that row, its complement if it is 0. (Such a term is a minterm; it is 1 in exactly that row.)
3. OR all these terms together.

The result is the canonical sum-of-products form. It is correct but usually not the simplest; simplify it afterwards with identities or a Karnaugh map.

Minterm shorthand: number each row by its binary value ($x y z = 101$ is row 5) and write $F = \Sigma m(\ldots)$ listing the rows where $F = 1$.

Mini-example (lecture)

For $F = xz' + y$ (table above), $F = 1$ in rows $010, 011, 100, 110, 111$:

$$F = x'yz' + x'yz + xy'z' + xyz' + xyz = \Sigma m(2, 3, 4, 6, 7)$$

Product-of-sums (POS) is the dual form. Use the rows where $F = 0$; for each, write a sum term (a maxterm) with the variable complemented if it is 1 in that row and uncomplemented if it is 0; AND the terms. For $F = xz' + y$ the 0-rows are $000, 001, 101$: $F = (x + y + z)(x + y + z')(x' + y + z') = \Pi M(0, 1, 5)$. Each maxterm is 0 in exactly its own row.

---

Worked Examples

Exercise 1

Construct the truth table for $F(x, y, z) = x'y + xz'$, showing every intermediate column, and give $F$ in $\Sigma m$ notation.

Show solution ↓Hide solution ↑

Solution

Precedence: first the NOTs ($x'$, $z'$), then the two products, then the OR.

row	$x$	$y$	$z$	$x'$	$z'$	$x'y$	$xz'$	$F = x'y + xz'$
0	0	0	0	1	1	0	0	0
1	0	0	1	1	0	0	0	0
2	0	1	0	1	1	1	0	1
3	0	1	1	1	0	1	0	1
4	1	0	0	0	1	0	1	1
5	1	0	1	0	0	0	0	0
6	1	1	0	0	1	0	1	1
7	1	1	1	0	0	0	0	0

$F = \Sigma m(2, 3, 4, 6)$, i.e. canonical SOP $F = x'yz' + x'yz + xy'z' + xyz'$.

Sanity check: $x'y$ should be 1 exactly when $x = 0, y = 1$ (rows 2, 3) ✓; $xz'$ exactly when $x = 1, z = 0$ (rows 4, 6) ✓.

Exercise 2

Use extended DeMorgan to find the complement of:

(a) $F(x, y, z) = xy + x'z + yz'$

(b) $G(x, y, z) = x(y' + z) + x'yz'$

Verify each answer with a truth table.

Show solution ↓Hide solution ↑

Solution

(a) Complement each variable, swap AND ↔ OR, keep each old product grouped:

$$F' = (x' + y')(x + z')(y' + z)$$

(b) Work from the outside in. $G$ is a sum of two terms, so $G'$ is the product of their complements:

$$\begin{aligned} G' &= \big(x(y'+z)\big)' \cdot (x'yz')' && \text{DeMorgan (OR form)} \\ &= \big(x' + (y'+z)'\big)\,(x + y' + z) && \text{DeMorgan (AND form), Double complement} \\ &= (x' + yz')\,(x + y' + z) && \text{DeMorgan on } (y'+z)' \end{aligned}$$

Verification (a complement must be 1 exactly where the original is 0):

$xyz$	$F$	$(x'+y')(x+z')(y'+z)$	$G$	$(x'+yz')(x+y'+z)$
000	0	1	0	1
001	1	0	0	1
010	1	0	1	0
011	1	0	0	1
100	0	1	1	0
101	0	1	1	0
110	1	0	0	1
111	1	0	1	0

Row by row, each complement column is the opposite of its function ✓. (Spot-check row $001$ of (b): $G = 0\cdot(1+1) + 1\cdot0\cdot0 = 0$; $G' = (1 + 0)(0 + 1 + 1) = 1$ ✓.)

Exercise 3

(Lecture example) Simplify $F(x, y, z) = (x + y)(x + y')(xz')'$, citing the identity used at every step.

Show solution ↓Hide solution ↑

Solution

$$\begin{aligned} F &= (x + y)(x + y')(xz')' \\ &= (x + y)(x + y')(x' + z) && \text{DeMorgan, Double complement} \\ &= (xx + xy' + xy + yy')(x' + z) && \text{Distributive (multiply out)} \\ &= (x + x(y' + y) + yy')(x' + z) && \text{Idempotent } (xx = x)\text{, Distributive (factor } x) \\ &= (x + x\cdot 1 + 0)(x' + z) && \text{Inverse } (y'+y = 1,\ yy' = 0) \\ &= (x + x)(x' + z) && \text{Identity } (x\cdot1 = x,\ \ldots + 0) \\ &= x(x' + z) && \text{Idempotent } (x + x = x) \\ &= xx' + xz && \text{Distributive} \\ &= 0 + xz && \text{Inverse} \\ &= xz && \text{Identity} \end{aligned}$$

Shortcut: the first two factors are the pattern $(x + y)(x + y') = x + yy' = x + 0 = x$ (Distributive AND form, Inverse, Identity), giving $x(x' + z) = xz$ immediately.

Check by truth table ($xyz$ from 000 to 111): $F$ = $0,0,0,0,0,1,0,1$ and $xz$ = $0,0,0,0,0,1,0,1$ ✓. A circuit with 3 OR/AND gates and inverters reduces to a single AND gate.

Exercise 4

Prove the consensus theorem $xy + x'z + yz = xy + x'z$ using identities.

Show solution ↓Hide solution ↑

Solution

The trick is to multiply the redundant term $yz$ by $1 = x + x'$ so it splits into pieces that can be absorbed.

$$\begin{aligned} xy + x'z + yz &= xy + x'z + yz\cdot 1 && \text{Identity} \\ &= xy + x'z + yz(x + x') && \text{Inverse} \\ &= xy + x'z + xyz + x'yz && \text{Distributive, Commutative} \\ &= (xy + xyz) + (x'z + x'yz) && \text{Commutative, Associative} \\ &= xy(1 + z) + x'z(1 + y) && \text{Distributive (factor)} \\ &= xy\cdot 1 + x'z \cdot 1 && \text{Null law } (1 + z = 1) \\ &= xy + x'z && \text{Identity} \end{aligned}$$

Intuition: if $yz = 1$ then $y = z = 1$; whichever value $x$ has, either $xy$ (when $x = 1$) or $x'z$ (when $x = 0$) is already 1. So $yz$ never contributes anything new.

Truth table check: both sides give $0,1,0,1,0,0,1,1$ for $xyz = 000 \ldots 111$ ✓.

Exercise 5

$F(x, y, z) = \Sigma m(0, 2, 4, 5, 6)$.

(a) Write the canonical sum-of-products and the canonical product-of-sums.

(b) Simplify $F$ algebraically.

Show solution ↓Hide solution ↑

Solution

(a) Translate each row number to binary ($x y z$):

row	$xyz$	$F$	minterm (if $F=1$)	maxterm (if $F=0$)
0	000	1	$x'y'z'$
1	001	0		$x + y + z'$
2	010	1	$x'yz'$
3	011	0		$x + y' + z'$
4	100	1	$xy'z'$
5	101	1	$xy'z$
6	110	1	$xyz'$
7	111	0		$x' + y' + z'$

$$F = x'y'z' + x'yz' + xy'z' + xy'z + xyz' \qquad \text{(canonical SOP)}$$$$F = (x + y + z')(x + y' + z')(x' + y' + z') = \Pi M(1, 3, 7) \qquad \text{(canonical POS)}$$

(b) Pair minterms that differ in exactly one variable. $x'y'z'$ pairs with $x'yz'$ and $xy'z'$ pairs with $xyz'$ (each pair differs only in $y$), but $xy'z$ can only pair with $xy'z'$ (differ only in $z$), which is already used. The Idempotent law ($a = a + a$) lets us use $xy'z'$ twice.

$$\begin{aligned} F &= x'y'z' + x'yz' + xy'z' + xyz' + xy'z \\ &= x'y'z' + x'yz' + xy'z' + xyz' + xy'z' + xy'z && \text{Idempotent } (xy'z' = xy'z' + xy'z') \\ &= x'z'(y' + y) + xz'(y' + y) + xy'(z' + z) && \text{Commutative, Distributive} \\ &= x'z'\cdot1 + xz'\cdot1 + xy'\cdot1 && \text{Inverse} \\ &= x'z' + xz' + xy' && \text{Identity} \\ &= z'(x' + x) + xy' && \text{Distributive} \\ &= z' + xy' && \text{Inverse, Identity} \end{aligned}$$

Check: $z' + xy'$ is 1 when $z = 0$ (rows 0, 2, 4, 6) or when $x = 1, y = 0$ (rows 4, 5). Union $= \{0, 2, 4, 5, 6\}$ ✓.

Exercise 6

A full adder adds three bits $x$, $y$ and a carry-in $z$, producing Sum and Carry-out. From its truth table, derive canonical SOP expressions and show algebraically that

$$\text{Sum} = x \oplus y \oplus z, \qquad \text{Cout} = xy + z(x \oplus y).$$

Show solution ↓Hide solution ↑

Solution

Truth table ($x + y + z$ in binary = Cout Sum):

$x$	$y$	$z$	Cout	Sum
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Canonical SOP (rows where the output is 1):

$$\text{Sum} = x'y'z + x'yz' + xy'z' + xyz = \Sigma m(1,2,4,7), \qquad \text{Cout} = x'yz + xy'z + xyz' + xyz = \Sigma m(3,5,6,7)$$

Carry-out:

$$\begin{aligned} \text{Cout} &= x'yz + xy'z + xyz' + xyz \\ &= z(x'y + xy') + xy(z' + z) && \text{Distributive (factor } z \text{ and } xy) \\ &= z(x \oplus y) + xy\cdot 1 && \text{definition of XOR, Inverse} \\ &= xy + z(x \oplus y) && \text{Identity, Commutative} \end{aligned}$$

Sum: factor on $x$:

$$\text{Sum} = x'(y'z + yz') + x(y'z' + yz)$$

The first bracket is $y \oplus z$. For the second, show it is the complement of $y \oplus z$:

$$\begin{aligned} (y \oplus z)' &= (y'z + yz')' \\ &= (y'z)'\,(yz')' && \text{DeMorgan} \\ &= (y + z')(y' + z) && \text{DeMorgan, Double complement} \\ &= yy' + yz + z'y' + z'z && \text{Distributive} \\ &= 0 + yz + y'z' + 0 && \text{Inverse, Commutative} \\ &= y'z' + yz && \text{Identity} \end{aligned}$$

So with $w = y \oplus z$:

$$\text{Sum} = x'w + xw' = x \oplus w = x \oplus (y \oplus z) = x \oplus y \oplus z$$

(XOR is associative, so the brackets do not matter.)

Check: Sum is 1 in rows 1, 2, 4, 7, which are exactly the rows with an odd number of 1s, as $x \oplus y \oplus z$ requires ✓. Cout row $011$: $xy + z(x \oplus y) = 0 + 1\cdot(0 \oplus 1) = 1$ ✓.

Exercise 7

Using identities, simplify:

(a) $F_1 = xy + xy'z + x'$

(b) $F_2 = (x + y')(x' + y')$

(c) $F_3 = x'y'z + x'yz + xy'z + xyz$

Show solution ↓Hide solution ↑

Solution

(a)

$$\begin{aligned} F_1 &= x' + xy + xy'z && \text{Commutative} \\ &= x' + x(y + y'z) && \text{Distributive} \\ &= x' + x\big((y + y')(y + z)\big) && \text{Distributive (OR over AND)} \\ &= x' + x(y + z) && \text{Inverse, Identity} \\ &= (x' + x)(x' + y + z) && \text{Distributive (OR over AND)} \\ &= x' + y + z && \text{Inverse, Identity} \end{aligned}$$

Check: $F_1 = 0$ only when $x = 1$, $y = 0$, $z = 0$ (row 4): original gives $0 + 0 + 0 = 0$ ✓, and every other row gives 1 in both forms.

(b)

$$\begin{aligned} F_2 &= (y' + x)(y' + x') && \text{Commutative} \\ &= y' + xx' && \text{Distributive (AND form: } (a+b)(a+c) = a + bc) \\ &= y' + 0 = y' && \text{Inverse, Identity} \end{aligned}$$

(c) (the first Karnaugh-map example of the lecture, done algebraically)

$$\begin{aligned} F_3 &= x'z(y' + y) + xz(y' + y) && \text{Distributive} \\ &= x'z + xz && \text{Inverse, Identity} \\ &= z(x' + x) = z && \text{Distributive, Inverse, Identity} \end{aligned}$$

Four minterms collapse to the single variable $z$: the output does not depend on $x$ or $y$ at all. The next section (Karnaugh maps) finds this kind of result by inspection.