L5: Axioms

The Laws of Binary Algebra

Objective
Understand the basic axioms that govern 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 Axioms?

Axioms are the basic assumptions taken to be true without proof. In Boolean algebra they define how the constants (0 and 1) and the basic operations (AND, OR, NOT) behave, giving a small set of rules from which all other identities are derived. By working from axioms you can prove standard laws (see L6–L8) and thus manipulate logical expressions reliably.

Axioms also connect the abstract algebra to real hardware: the same rules that govern truth values describe how switch networks and digital circuits behave.

Boolean Algebra

Boolean algebra, introduced by George Boole in 1849, is a mathematical framework for representing logical thought and reasoning. In the 1930s, Claude Shannon revolutionized the field of electrical engineering by applying Boolean algebra to describe and analyze circuits built with switches. This groundbreaking work demonstrated how logical operations could be represented and manipulated mathematically, paving the way for the development of modern digital systems. Shannon’s application of Boolean algebra bridged the gap between abstract mathematics and practical engineering, enabling the design of efficient and reliable circuits.

Switches

Consider the following figure, which contains two switches. The first is closed, meaning current can flow through the switch. The second is open, meaning current cannot flow through the switch. These switches will allow us to reason in the same language as the pioneers of Boolean algebra.

Let’s first assign a value to each state. The closed state gets the value of 1, and the open state gets a value of 0. The astute student will see where we’re going with this: setting a Boolean value to each switch state will let us reason about the way current flows through a network of switches.

Let’s build a simple circuit with a switch. In the following figure, there is a voltage source (e.g., a battery) on the left and a lamp on the right. The switch on top is closed, allowing current to flow to the lamp.

In the following figure, the switch on top has been opened, prohibiting current from flowing to the lamp.

Let’s use the lamp’s state as the output of this circuit: 1 for ON, 0 for OFF. When the switch is open ($x=0$), the lamp is off ($\text{lamp} = 0$). When the switch is closed ($x=1$), the lamp is on ($\text{lamp} = 1$). Thus, the equation $\text{lamp} = x$ represents this circuit.

Switches in Series

Now let’s make a more complex circuit. What happens when we operate two switches in series?

When two series switches are open, current cannot flow.

Even when only one series switch is open, current cannot flow.

But when both switches are closed, current is able to flow.

That means two switches in parallel can be used to represent an AND gate. For switches $x_1$ and $x_2$, we can use the equation $\text{lamp} = x_1 \land x_2$.

Switches in Parallel

What happens when we operate two switches in parallel?

When two parallel switches are open, current cannot flow.

When only one parallel switch is open, current flows.

And when both switches are closed, current is able to flow.

That means two switches in parallel can be used to represent an OR gate. For switches $x_1$ and $x_2$, we can use the equation $\text{lamp} = x_1 \lor x_2$.

A Switch Inverter?

Yes, we can even make a NOT gate with switches! Take a look at this circuit and convince yourself it works as an inverter. Trace the path of the current, and recall that current prefers the path of least resistance.

Notation

Boolean algebra uses a variety of notations to represent logical operations. Here are some common options, but many others exist. People can sometimes be dogmatic about this, but any clear option is fine by me.

Logical Symbols (my favorite)
- AND: $x \land y$ (LaTeX: x \land y)
- OR: $x \lor y$ (LaTeX: x \lor y)
- NOT: $\lnot x$ (LaTeX: \lnot x)
Math Notation (usually used in the textbook)
- AND: $x \cdot y$ (LaTeX: x \cdot y)
- OR: $x + y$ (LaTeX: x + y)
- NOT: $\overline{x}$ (LaTeX: \overline{x})
Dotless Notation
- AND: $xy$ (LaTeX: xy)
- OR: $x + y$ (LaTeX: x + y)
- NOT: $\overline{x}$ (LaTeX: \overline{x})
Programming Notation
- AND: x && y
- OR: x || y
- NOT: !x

The Axioms

Axioms are foundational truths or principles that serve as the building blocks for a system of logic or mathematics. They are assumed to be true without proof, providing a framework upon which theorems and more complex ideas can be constructed. In Boolean algebra, axioms define the basic rules for manipulating logical expressions, ensuring consistency and enabling systematic reasoning about logical operations.

Axiom 1
1a. $1 \lor 1 = 1$
1b. $0 \land 0 = 0$

Axiom 2
2a. $1 \land 1 = 1$
2b. $0 \lor 0 = 0$

Axiom 3
3a. $0 \land 1 = 1 \land 0 = 0$
3b. $0 \lor 1 = 1 \lor 0 = 1$

Axiom 4
4a. If $x = 0$ then $\lnot x = 1$
4b. If $x = 1$ then $\lnot x = 0$

The Principle of Duality states that every Boolean algebra expression remains valid if we interchange AND with O, and 0 with 1. This principle highlights the symmetry in Boolean algebra, allowing us to derive new truths from existing ones by simply applying duality. This principle is reflected in the pairing of axioms. For example, Axiom 1b is the dual of Axiom 1a.

Axiom Truth Table

The following truth table summarizes the assumptions the axioms allow us to make.

$x$	$y$	$x \land y$	$x \lor y$	$\lnot x$	$\lnot y$
$0$	$0$	$0$	$0$	$1$	$1$
$0$	$1$	$0$	$1$	$1$	$0$
$1$	$0$	$0$	$1$	$0$	$1$
$1$	$1$	$1$	$1$	$0$	$0$

How the rows correspond to the axioms:

Axiom 1a ($1 \lor 1 = 1$): row $(1,1)$ shows $x\lor y = 1$.
Axiom 1b ($0 \land 0 = 0$): row $(0,0)$ shows $x\land y = 0$.
Axiom 2a ($1 \land 1 = 1$): row $(1,1)$ shows $x\land y = 1$.
Axiom 2b ($0 \lor 0 = 0$): row $(0,0)$ shows $x\lor y = 0$.
Axiom 3a ($0 \land 1 = 1 \land 0 = 0$): rows $(0,1),(1,0)$ show $x\land y = 0$.
Axiom 3b ($0 \lor 1 = 1 \lor 0 = 1$): rows $(0,1),(1,0)$ show $x\lor y = 1$.
Axiom 4 ($\lnot 0 = 1$, $\lnot 1 = 0$): columns $\lnot x$, $\lnot y$ confirm negation.

$x$	$y$	$x \land y$	$x \lor y$	$\lnot x$	$\lnot y$
$0$	$0$	$0$	$0$	$1$	$1$
$0$	$1$	$0$	$1$	$1$	$0$
$1$	$0$	$0$	$1$	$0$	$1$
$1$	$1$	$1$	$1$	$0$	$0$

$x$	$y$	$x \land y$	$x \lor y$	$\lnot x$	$\lnot y$
$0$	$0$	$0$	$0$	$1$	$1$
$0$	$1$	$0$	$1$	$1$	$0$
$1$	$0$	$0$	$1$	$0$	$1$
$1$	$1$	$1$	$1$	$0$	$0$

$x$	$y$	$x \land y$	$x \lor y$	$\lnot x$	$\lnot y$
$0$	$0$	$0$	$0$	$1$	$1$
$0$	$1$	$0$	$1$	$1$	$0$
$1$	$0$	$0$	$1$	$0$	$1$
$1$	$1$	$1$	$1$	$0$	$0$