L8: Theorems B

Let’s practice Boolean algebra!

Objective
Practice usage of theorems 5-17 of Boolean algebra.

Additional Materials & Formats
Check Box for the most up-to-date versions of this lecture’s materials.

Before the Lecture

Required Textbook Reading:

• 2.5 (Boolean Algebra)

Optional Supplemental Instruction:

• Boolean algebra (Wikipedia) – deep dive into the history and laws of Boolean algebra
• The Mathematics of Boolean Algebra (Stanford Encyclopedia of Philosophy) – philosophical look at Boolean algebra, a perspective you don’t always get in computing courses
• Boolean Algebra in 13 Minutes (TrevTutor on YouTube) – quick but helpful overview

Theorems in Practice

Example 1

$$ (x_1 + x_3) (\overline{x}_1 + \overline{x}_3) \overset{?}{=} x_1 \overline{x}_3 + \overline{x}_1 x_3 $$

$$ \begin{gather} \text{LHS} \quad = (x_1 + x_3) \cdot \overline{x}_1 + (x_1 + x_3) \cdot \overline{x}_3 &\text{using 12a} \newline = x_1 \cdot \overline{x}_1 + x_3 \cdot \overline{x}_1 + x_1 \cdot \overline{x}_3 + x_3 \cdot \overline{x}_3 &\text{using 12a} \newline = 0 + x_3 \cdot \overline{x}_1 + x_1 \cdot \overline{x}_3 + 0 &\text{using 8a} \newline = x_3 \cdot \overline{x}_1 + x_1 \cdot \overline{x}_3 &\text{using 6b} \newline = x_1 \cdot \overline{x}_3 + \overline{x}_1 \cdot x_3 &\text{using 10} \newline \textbf{Q.E.D.} \end{gather} $$

Example 2

$$ x_1 \cdot \overline{x}_3 + \overline{x}_2 \cdot \overline{x}_3 + x_1 \cdot x_3 + \overline{x}_2 \cdot x_3 \overset{?}{=} \overline{x}_1 \cdot \overline{x}_2 + x_1 \cdot x_2 + x_1 \cdot \overline{x}_2 $$

$$ \begin{gather} \text{LHS} \quad &= x_1 \cdot \overline{x}_3 + x_1 \cdot x_3 + \overline{x}_2 \cdot \overline{x}_3 + \overline{x}_2 \cdot x_3 &&\text{using 10b} \newline &= x_1 \cdot (\overline{x}_3 + x_3) + \overline{x}_2 \cdot (\overline{x}_3 + x_3) &&\text{using 12a} \newline &= x_1 \cdot 1 + \overline{x}_2 \cdot 1 &&\text{using 8b} \newline &= x_1 + \overline{x}_2 &&\text{using 6a} \newline \text{RHS} \quad &= \overline{x}_1 \cdot \overline{x}_2 + x_1 \cdot (x_2 + \overline{x}_2) &&\text{using 12a} \newline &= \overline{x}_1 \cdot \overline{x}_2 + x_1 \cdot 1 &&\text{using 8b} \newline &= \overline{x}_1 \cdot \overline{x}_2 + x_1 &&\text{using 6a} \newline &= x_1 + \overline{x}_1 \cdot \overline{x}_2 &&\text{using 10b} \newline &= x_1 + \overline{x}_2 &&\text{using 16a} \newline &\textbf{Q.E.D.} \end{gather} $$

Example 3

$$ x + x y \overset{?}{=} x $$

$$ \begin{gather} \text{LHS} \quad = x + x y \newline = x (1 + y) &&\text{using 12a} \newline = x \cdot 1 &&\text{using 5b} \newline = x &&\text{using 6a} \newline \textbf{Q.E.D.} \end{gather} $$

Example 4

$$ (x + y)(\overline{x} + \overline{y}) \overset{?}{=} x\overline{y} + \overline{x}y $$

$$ \begin{gather} \text{LHS} \quad = (x + y)\overline{x} + (x + y)\overline{y} &&\text{using 12a} \newline = x\overline{x} + y\overline{x} + x\overline{y} + y\overline{y} &&\text{using 12a} \newline = 0 + y\overline{x} + x\overline{y} + 0 &&\text{using 8a} \newline = x\overline{y} + \overline{x}y &&\text{using 10b} \newline \textbf{Q.E.D.} \end{gather} $$

Example 5

$$ \overline{xy + z} \overset{?}{=} (\overline{x} + \overline{y})\overline{z} $$

$$ \begin{gather} \text{LHS} \quad = \overline{xy + z} \newline = \overline{xy}\ \overline{z} &&\text{using 15b} \newline = (\overline{x} + \overline{y})\overline{z} &&\text{using 15a} \newline \textbf{Q.E.D.} \end{gather} $$

Example 6

$$ x y + x \overline{y} \overset{?}{=} x $$

$$ \begin{gather} \text{LHS} \quad = x y + x \overline{y} \newline = x (y + \overline{y}) &&\text{using 12a} \newline = x \cdot 1 &&\text{using 8b} \newline = x &&\text{using 6a} \newline \textbf{Q.E.D.} \end{gather} $$

Example 7

$$ x(y + z) + \overline{x}z \overset{?}{=} x y + z $$

$$ \begin{gather} \text{LHS} \quad = x y + x z + \overline{x} z &&\text{using 12a} \newline = x y + z(x + \overline{x}) &&\text{using 12b} \newline = x y + z \cdot 1 &&\text{using 9} \newline = x y + z &&\text{using 6a} \newline \textbf{Q.E.D.} \end{gather} $$

More Examples

• $(x + y)(\overline{x} + z) \overset{?}{=} x\overline{x} + xz + y\overline{x} + yz$
• $x + \overline{x}y z \overset{?}{=} x + y z$ (use 16a)
• $(x \land y) \lor (\overline{x} \land y) \overset{?}{=} y$ (factor and use 13a)
• $\overline{x \lor (y \land z)} \overset{?}{=} \overline{x} \land (\overline{y} \lor \overline{z})$ (apply DeMorgan then distribute)
• $(x \lor y) \land (\overline{x} \lor y) \land (x \lor \overline{y}) \overset{?}{=} y \lor x$ (try consensus/associative patterns)
• $x\overline{y} + xy + \overline{x}y \overset{?}{=} x + y$ (test by grouping and absorption)
• $(x + \overline{x}y)(\overline{x} + z) \overset{?}{=} x(\overline{x}+z) + \overline{x}y(\overline{x}+z)$ (expand then simplify)