L7: Theorems A

A set of mathematical building blocks

Objective
Understand 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

What are Theorems?

Theorems are propositions that can be logically derived from axioms. They are not assumed true a priori; instead, each theorem follows from a sequence of valid deductions. In practice, theorems are the workhorse rules used to simplify expressions and design or optimize logic circuits.

Single-Variable Theorems

Given variable $x$, these theorems can be easily derived from the axioms of Boolean algebra.

Theorem 5
5a.   $x \land 0 = 0$
5b.   $x \lor 1 = 1$

Theorem 6
6a.   $x \land 1 = x$
6b.   $x \lor 0 = x$

Theorem 7
7a.   $x \land x = x$
7b.   $x \lor x = x$

Theorem 8
8a.   $x \land \lnot x = 0$
8b.   $x \lor \lnot x = 1$

Theorem 9
9.   $\lnot (\lnot x) = x$

Multi-Variable Theorems

If you’re good at pattern matching, you can use these as a shortcut when solving problems (just like in Decimal algebra).

Theorem 10   The Commutative Property
10a.   $x \land y = y \land x$
10b.   $x \lor y = y \lor x$

Theorem 11   The Associative Property
11a.   $x \land (y \land z) = (x \land y) \land z$
11b.   $x \lor (y \lor z) = (x \lor y) \lor z$

Theorem 12   The Distributive Property
12a.   $x \land (y \lor z) = x \land y \lor x \land z$
12b.   $x \lor y \land z = (x \lor y) \land (x \lor z)$

Theorem 13   The Absorption Property
13a.   $x \lor x \land y = x$
13b.   $x \land (x \lor y) = x$

Theorem 14   The Combining Property
14a.   $x \land y \lor x \land \lnot y = x$
14b.   $(x \lor y) \land (x \lor \lnot y) = x$

Theorem 15   DeMorgan’s Theorem – Our Favorite
15a.   $\lnot(x \land y) = \lnot x \lor \lnot y$
15b.   $\lnot(x \lor y) = \lnot x \land \lnot y$

Theorem 16
16a.   $x \lor \lnot x \land y = x \lor y$
16b.   $x \land (\lnot x \lor y) = x \land y$

Theorem 17   The Consensus Property
17a.   $x \land y \lor y \land z \lor \lnot x \land z = x \land y \lor \lnot x \land z$
17b.   $(x \lor y) \land (y \lor z) \land (\lnot x \lor z) = (x \lor y) \land (\lnot x \land z)$

Proving a Theorem

We don’t have time to prove all the theorems in this lecture (some of that will be left as homework or quiz problems), but let’s prove DeMorgan’s Theorem as a class.

Theorem 15   DeMorgan’s Theorem
15a.   $\lnot(x \land y) = \lnot x \lor \lnot y$
15b.   $\lnot(x \lor y) = \lnot x \land \lnot y$

Since there are only two variables, let’s solve it using a truth table. For space saving purposes, let’s use dotless notation.

We can see that the truth tables match perfectly for the right and left hand sides of the theorem, so there’s our proof!