# Lecture 4. Boolean algebra — basics

## 4.1 Overview

This lecture builds the algebraic foundation for the digital‑logic part of the course.
We start from the everyday notion of a **statement** that is either true or false,
encode the two truth values as $1$ and $0$, and study how statements combine through a
small set of **logical operations**.

The central object is **Boolean algebra**: the two‑element set $\{0,1\}$ with negation
($\neg$), conjunction ($\wedge$) and disjunction ($\vee$), plus the derived operations
exclusive‑or ($\oplus$), implication ($\to$) and equivalence ($\leftrightarrow$). Every
operation is completely described by a **truth table**; a function of $n$ Boolean
variables is nothing more than a truth table; and these functions obey a compact list
of **laws** — commutativity, associativity, distributivity, De Morgan's laws, and more.
Physical realisation (logic gates), systematic simplification (canonical forms,
Karnaugh maps) and the deductive side (propositional logic) come in later lectures;
here we stay with the algebra, which — as the final sections show — is *literally the
same structure* you met in **set algebra** (Lecture 2) and will meet again in
**propositional logic** (Lecture 6).

### Why should we care?

Boolean algebra is the mathematics of *decisions* and *yes/no information*, and it sits
underneath almost everything a computer does.

- **Hardware.** A wire in a digital circuit is either at a high voltage or a low
  voltage — two states, exactly the alphabet $\{1,0\}$. A logic gate computes a Boolean
  operation on its input wires. An adder, a multiplexer, the control unit of a
  processor — all are Boolean functions realised in silicon. Claude Shannon's 1937
  master's thesis showed that the algebra Boole invented to formalise reasoning is
  *precisely* the algebra of switching circuits, and modern chip design still rests on
  that identification.
- **Software.** Every `if`, `while`, and `? :` in a program is steered by a Boolean
  expression. The short‑circuit operators `&&` and `||`, the bitwise operators
  `& | ~ ^`, and the conditions in database queries and search engines ("cats AND
  (black OR white) NOT kittens") are Boolean algebra in disguise.
- **Reasoning.** The same laws let us decide when two conditions are *equivalent* (so
  one can safely replace the other), when a condition can *never* be satisfied (a bug —
  dead code), and when one always holds (a redundant test).

The pay‑off of this lecture is a small toolkit — a dozen laws and one principle
(duality) — that lets you transform, simplify and reason about such expressions with
the confidence of ordinary algebra.

### Roadmap

We proceed from statements to their symbolic encoding; define the elementary
operations by truth tables; count how many Boolean functions of $n$ variables exist
(the answer, $2^{2^n}$, is proved); introduce tautologies, contradictions and logical
equivalence; state the laws and **prove every one of them by truth table**; state and
**justify the duality principle**; show how identities are also derived *algebraically*;
and finally explain in what precise sense logic, sets and bits are three faces of one
structure. A short historical note and a list of exercises close the chapter.

## 4.2 Statements (propositions) and truth values

A **statement** (or **proposition**) is a declarative sentence that is either **true**
or **false**, but not both. Being a statement has nothing to do with our *knowing*
which of the two it is — only with the sentence being definitely one or the other.

**Examples and non‑examples.**

- "Today is Sunday." — a statement (true or false depending on the day).
- "$2 + 2 = 4$." — a statement (true).
- "There are infinitely many twin primes." — a statement: it is definitely true or
  definitely false, even though (as of today) nobody knows which. *Having* a truth
  value does not require us to *know* it.
- "$x < 0$." — this is a *predicate* (open sentence): it becomes a statement only once
  $x$ is fixed. Predicates with variables and quantifiers are the subject of predicate
  logic, not of this lecture.
- "How are you?" — **not** a statement; a question has no truth value.
- "Close the door." — **not** a statement; a command has no truth value.
- "This sentence is false." — **not** a statement; assuming it true makes it false and
  vice versa, so it can be assigned neither value consistently (the *liar paradox*).

We attach a symbolic **truth value** to every statement:

$$
\text{true} = 1 = T, \qquad \text{false} = 0 = F.
$$

Working with the digits $0$ and $1$ (rather than the words) is exactly what turns logic
into an *algebra*: truth values become quantities we can compute with, and logical
connectives become operations like $+$ and $\times$.

> **Remark.** Some authors write $T/F$, some $\top/\bot$, some $1/0$. This course uses
> $1$ and $0$ almost everywhere, because it makes the bridge to arithmetic and hardware
> immediate: conjunction will behave exactly like multiplication of bits, and
> disjunction almost like addition.

### Compound statements

Simple statements are usually named by letters $p, q, r, \dots$ and combined into
**compound statements** using **connectives**. Let

- $p$ = "Today is Friday",
- $q$ = "The weather is good".

Then:

| Compound statement | Reads as |
|---|---|
| $p \wedge q$ | "Today is Friday **and** the weather is good" |
| $p \vee q$ | "Today is Friday **or** the weather is good" |
| $\neg p$ | "Today is **not** Friday" |
| $\neg p \wedge q$ | "Today is not Friday **and** the weather is good" |

The truth value of a compound statement depends **only** on the truth values of its
parts and on the connectives used — never on the meaning of the words. This property is
called **truth‑functionality**, and it is the whole point of moving to Boolean algebra:
once the parts' truth values are fixed, the compound's value is determined by pure
calculation.

## 4.3 Elementary logical operations

The **alphabet** of Boolean algebra is just the two symbols $\{0, 1\}$. On top of it we
define the operations below. Each operation is defined by a **truth table** that lists
its output for every combination of inputs. We list input rows in ascending binary
order ($00, 01, 10, 11$); other authors use a different row order, but the operation is
the same.

### Negation (NOT, $\neg$)

**Negation** flips the truth value: $\neg p$ is true exactly when $p$ is false.
Common notations: $\neg p$, $\sim p$, $!p$, $\bar p$, $p'$. Negation is a *unary*
operation (one input); all the others below are *binary* (two inputs).

| $p$ | $\neg p$ |
|:-:|:-:|
| 0 | 1 |
| 1 | 0 |

### Conjunction (AND, $\wedge$)

**Conjunction** $p \wedge q$ is true exactly when **both** operands are true.
Notations: $p \wedge q$, $p \cdot q$, $pq$. Comparing the table below with a
multiplication table for $0/1$ shows they are identical: $p \wedge q = p \cdot q$. This
is why conjunction is often written as a product.

| $p$ | $q$ | $p \wedge q$ |
|:-:|:-:|:-:|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

### Disjunction (OR, $\vee$)

**Disjunction** $p \vee q$ is true when **at least one** operand is true (this is the
*inclusive* or). Notations: $p \vee q$, $p + q$. It behaves like addition of bits
*except* that $1 \vee 1 = 1$ (not $2$): disjunction is "saturating" addition capped at
$1$.

| $p$ | $q$ | $p \vee q$ |
|:-:|:-:|:-:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

> **Common pitfall.** Everyday English "or" is often *exclusive* ("soup or salad" means
> one, not both), but the logical $\vee$ is **inclusive**: $1 \vee 1 = 1$. The exclusive
> reading is a different operation, XOR, defined next.

### Exclusive‑or (XOR, $\oplus$)

**Exclusive‑or** $p \oplus q$ is true when the operands **differ** — exactly one of
them is true. It is the "or, but not both" of everyday speech, and also "the operands
are unequal", so $p \oplus q = 1$ iff $p \neq q$. It behaves like addition *modulo 2*:
$p \oplus q = (p + q) \bmod 2$.

| $p$ | $q$ | $p \oplus q$ |
|:-:|:-:|:-:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

Because $\oplus$ is addition mod 2 it has a clean **algebra**: $p\oplus p=0$,
$p\oplus 0=p$, $p\oplus 1=\overline p$; it is commutative and associative; and $\wedge$
distributes over it, $p\wedge(q\oplus r)=(p\wedge q)\oplus(p\wedge r)$. This makes
$(\{0,1\},\oplus,\wedge)$ a field, and is the basis of the *algebraic normal form*
(Lecture 5) and of parity/checksum circuits.

### Implication (IF … THEN …, $\to$)

**Implication** $p \to q$ ("if $p$ then $q$") is false in only one case: a true premise
$p$ leading to a false conclusion $q$. In particular, whenever $p$ is false the
implication is **vacuously true** — a false premise never breaks a promise. Here $p$
is the *antecedent* (hypothesis) and $q$ the *consequent* (conclusion). Notations:
$p \to q$, $p \Rightarrow q$, $p \supset q$.

| $p$ | $q$ | $p \to q$ |
|:-:|:-:|:-:|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

Think of $p \to q$ as the promise "*if* $p$ happens, *then* I guarantee $q$". The
promise is broken only if $p$ happens and $q$ fails to — the single $1 \to 0$ row.

> **Common pitfall.** Implication is **not symmetric**: $p \to q$ and $q \to p$ are
> different functions (compare their columns). And $\neg(p\to q)$ is **not** $p \to \neg q$; the correct negation is $\neg(p \to q) = p \wedge \neg q$ (the promise is broken
> exactly when the premise holds but the conclusion fails). Also, $\to$ carries no idea
> of *cause*: "If $2+2=5$ then the moon is cheese" is true, because the premise is false.

### Equivalence (IF AND ONLY IF, $\leftrightarrow$)

**Equivalence** $p \leftrightarrow q$ (also written $p \equiv q$ or $p \odot q$) is true
when both operands have the **same** truth value. It is exactly the negation of XOR:
$p \leftrightarrow q = \neg(p \oplus q)$, i.e. $p \leftrightarrow q = 1$ iff $p = q$.

| $p$ | $q$ | $p \leftrightarrow q$ |
|:-:|:-:|:-:|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

### All binary operations at a glance

Putting the two‑variable operations side by side makes their patterns easy to compare:

| $p$ | $q$ | $p \wedge q$ | $p \vee q$ | $p \oplus q$ | $p \to q$ | $p \leftrightarrow q$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 |

![The five binary connectives side by side — conjunction, disjunction, exclusive-or, implication, and biconditional — one truth-table column each](img/l04_combined_tt.png)

Only three of these operations are *primitive*; the rest are abbreviations. We will
prove below (and again in Lecture 5) that $\oplus$, $\to$ and $\leftrightarrow$ can each
be rewritten with $\neg$, $\wedge$, $\vee$ alone. Two identities worth memorising now,
because they are used constantly, are

$$
p \to q \;=\; \neg p \vee q, \qquad p \leftrightarrow q \;=\; (p \to q)\wedge(q \to p).
$$

The first is verified in the worked examples below.

## 4.4 Precedence and reading compound expressions

To avoid a thicket of parentheses we adopt the standard **precedence** (binding
strength), from tightest to loosest:

$$
\neg \;\;>\;\; \wedge \;\;>\;\; \vee \;\;>\;\; \to \;\;>\;\; \leftrightarrow .
$$

Thus $\neg p \wedge q$ means $(\neg p) \wedge q$, and $p \wedge q \vee r$ means
$(p \wedge q) \vee r$, and $p \vee q \to r$ means $(p \vee q) \to r$. Negation applies
to the smallest expression to its right; $\wedge$ binds like multiplication and $\vee$
like addition. When in doubt, parenthesise: clarity beats brevity.

> **Common pitfall.** $\neg p \wedge q$ is $(\neg p)\wedge q$, **not** $\neg(p \wedge q)$ — the bar/¬ does not stretch over the $\wedge$ unless you write it that way. In
> the notation $\overline{p}\,q$ vs $\overline{pq}$ the difference is visible; in linear
> text it is a frequent source of error.

## 4.5 Boolean variables and Boolean functions

A **Boolean variable** is a variable that ranges over $\{0, 1\}$. A **Boolean function
of $n$ variables** is any rule

$$
f : \{0,1\}^n \longrightarrow \{0,1\}
$$

that assigns a value $0$ or $1$ to each of the $2^n$ possible input combinations. Here
$\{0,1\}^n$ is the set of all $n$‑tuples (input vectors) $(x_1, \dots, x_n)$ of bits.

**A truth table *is* the function.** Because the domain $\{0,1\}^n$ is finite, a
Boolean function is fully specified simply by listing its output on every input row.
Two Boolean expressions denote the same function precisely when their truth tables
agree in every row. This is the single most important tool of the chapter:

> **To prove that two Boolean expressions are equal, build both truth tables and check
> that the final columns are identical, row by row.** To *disprove* equality, it is
> enough to exhibit **one** row where they differ (a *counterexample*).

### Counting Boolean functions

How many different Boolean functions of $n$ variables are there? The answer is
surprisingly large and grows doubly exponentially.

> **Theorem (number of Boolean functions).** The number of Boolean functions of $n$
> variables is
>

$$
N(n) \;=\; 2^{\,2^{\,n}}.
$$

![The number of Boolean functions grows doubly exponentially: $2, 4, 16, 256$ functions for $n = 0, 1, 2, 3$ variables](img/l04_func_count.png)

*Proof.* We count in two stages.

*Stage 1 — the number of input rows.* An input is an $n$‑tuple $(x_1, \dots, x_n)$ with
each $x_i \in \{0,1\}$. By the multiplication (product) rule there are $2$ independent
choices for each of the $n$ coordinates, so

$$
|\{0,1\}^n| \;=\; \underbrace{2 \cdot 2 \cdots 2}_{n} \;=\; 2^{\,n}
$$

distinct input rows. Call this number $m = 2^n$.

*Stage 2 — the number of ways to fill the output column.* A function $f$ is determined
exactly by the value $f$ assigns to each of the $m$ input rows, and these values may be
chosen **independently**: any of the $2^m$ output columns of length $m$ (each entry $0$
or $1$) determines a genuine function, and different columns determine different
functions (they differ on some row). Again by the product rule there are

$$
\underbrace{2 \cdot 2 \cdots 2}_{m} \;=\; 2^{\,m}
$$

such columns. Substituting $m = 2^n$ gives $N(n) = 2^{\,2^{\,n}}$. $\blacksquare$

The two‑stage structure — first count the rows $2^n$, then count the fillings $2^{(\text{rows})}$ — is the reason the exponent is itself an exponential.

| $n$ | rows $2^n$ | functions $2^{2^n}$ |
|:-:|:-:|:-:|
| 0 | 1 | 2 |
| 1 | 2 | 4 |
| 2 | 4 | 16 |
| 3 | 8 | 256 |
| 4 | 16 | 65 536 |
| 5 | 32 | 4 294 967 296 |

The growth is ferocious: already at $n = 6$ there are $2^{64} \approx 1.8 \times 10^{19}$
functions, more than the number of grains of sand on Earth. This explosion is exactly
why *systematic* simplification methods (Lecture 5) are needed — one cannot search all
functions by hand.

**The case $n = 0$.** A function of *no* variables has the single empty input tuple
$()$ as its only "row" ($2^0 = 1$ row), and there are $2^{2^0} = 2^1 = 2$ such
functions: the constant $0$ and the constant $1$. This matches the two truth values and
is a good sanity check on the formula.

**Example — the 4 functions of one variable.** For $n = 1$ the theorem gives
$2^{2^1} = 4$:

| $p$ | $\mathbf{0}$ | $p$ | $\neg p$ | $\mathbf{1}$ |
|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |

They are: the constant $0$, the identity $p$, the negation $\neg p$, and the constant
$1$. There are literally no others — every possible two‑row output column appears.

**Example — the 16 functions of two variables.** With $n = 2$ there are exactly
$2^{4} = 16$ functions $F_0, \dots, F_{15}$. Reading each column top‑to‑bottom over the
input rows $(x,y) = 00, 01, 10, 11$ gives its truth table (and the subscript $k$ is the
binary number spelled by that column, MSB at the top):

| $x$ | $y$ | $F_0$ | $F_1$ | $F_2$ | $F_3$ | $F_4$ | $F_5$ | $F_6$ | $F_7$ | $F_8$ | $F_9$ | $F_{10}$ | $F_{11}$ | $F_{12}$ | $F_{13}$ | $F_{14}$ | $F_{15}$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |

Several of these columns are the operations we already named:

- $F_0 = 0$ (constant false), $F_{15} = 1$ (constant true);
- $F_1 = x \wedge y$ (AND), $F_7 = x \vee y$ (OR);
- $F_3 = x$, $F_5 = y$, $F_{12} = \neg x$, $F_{10} = \neg y$ (projections and their negations);
- $F_6 = x \oplus y$ (XOR), $F_9 = x \leftrightarrow y$ (equivalence);
- $F_{13} = x \to y$, $F_{11} = y \to x$ (implications);
- $F_8 = \neg(x \vee y)$ (NOR), $F_{14} = \neg(x \wedge y)$ (NAND).

The important takeaway is not the individual names but the count: **every** possible
two‑variable truth table appears exactly once, and there are $16$ of them — no more,
no fewer. (The exhaustive named list of these sixteen, and how NAND or NOR alone can
generate them all, is taken up in Lecture 5.)

## 4.6 Truth tables of compound expressions

Any compound expression is evaluated **column by column**: introduce a helper column
for each sub‑expression, fill it from the operator's truth table, and combine helper
columns until the final column is reached. With $n$ variables the table has $2^n$ rows.
List the rows in ascending binary order so that nothing is skipped.

**Example 1 (easy) — evaluate $\neg(\neg p)$.** Two rows suffice, and the result
recovers $p$:

| $p$ | $\neg p$ | $\neg(\neg p)$ |
|:-:|:-:|:-:|
| 0 | 1 | 0 |
| 1 | 0 | 1 |

The final column equals the $p$ column: $\neg\neg p = p$. (This is the *involution* law,
proved formally below.)

**Example 2 (easy) — evaluate $(p \wedge q) \vee \neg r$.**
Three variables give $2^3 = 8$ rows. Build $p \wedge q$, then $\neg r$, then their
disjunction:

| $p$ | $q$ | $r$ | $p \wedge q$ | $\neg r$ | $(p \wedge q) \vee \neg r$ |
|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 |

The last column is the function computed by the expression; it equals $1$ on five of
the eight rows.

**Example 3 (medium) — "exactly one of $p, q$": evaluate $(p \vee q) \wedge \neg(p \wedge q)$.**

| $p$ | $q$ | $p \vee q$ | $p \wedge q$ | $\neg(p \wedge q)$ | $(p \vee q) \wedge \neg(p \wedge q)$ |
|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |

The final column reads $0, 1, 1, 0$ — exactly the XOR table. So we have *derived* the
identity $p \oplus q = (p \vee q) \wedge \neg(p \wedge q)$, showing that XOR is not a
new primitive but a combination of $\wedge$, $\vee$ and $\neg$.

**Example 4 (medium) — $p \to q$ equals $\neg p \vee q$.** This rewriting of implication
in terms of the three primitives is used everywhere; here is its proof.

| $p$ | $q$ | $p \to q$ | $\neg p$ | $\neg p \vee q$ |
|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |

The columns for $p \to q$ and $\neg p \vee q$ are identical, so $p \to q = \neg p \vee q$.

**Example 5 (harder) — the hypothetical syllogism is a tautology.** We show that
$\bigl((p \to q) \wedge (q \to r)\bigr) \to (p \to r)$ is true in every row — the
formal content of "if $p$ implies $q$ and $q$ implies $r$, then $p$ implies $r$".

| $p$ | $q$ | $r$ | $p \to q$ | $q \to r$ | $(p\to q)\wedge(q\to r)$ | $p \to r$ | whole formula |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

The final column is all $1$s, so the formula is a tautology. Notice the mechanism: on
every row where the hypothesis $(p\to q)\wedge(q\to r)$ is $1$ (rows $000, 001, 011, 111$), the conclusion $p\to r$ is also $1$; on the remaining rows the hypothesis is $0$,
so the outer implication is vacuously $1$.

## 4.7 Tautologies, contradictions, and logical equivalence

A **tautology** is an expression whose value is $1$ for **every** assignment of its
variables — the final truth‑table column is all $1$s. A **contradiction** (or
*unsatisfiable* expression) is an expression whose value is $0$ for every assignment —
the final column is all $0$s. An expression that is $1$ on at least one row is called
**satisfiable**; one that is $1$ on some rows and $0$ on others is a **contingency**.

**Example — the tautology $p \vee \neg p$** (the law of excluded middle):

| $p$ | $\neg p$ | $p \vee \neg p$ |
|:-:|:-:|:-:|
| 0 | 1 | 1 |
| 1 | 0 | 1 |

**Example — the contradiction $p \wedge \neg p$** (the law of non‑contradiction):

| $p$ | $\neg p$ | $p \wedge \neg p$ |
|:-:|:-:|:-:|
| 0 | 1 | 0 |
| 1 | 0 | 0 |

These two facts, $p \vee \neg p = 1$ and $p \wedge \neg p = 0$, are the **complement
laws** and appear among the axioms below.

**Logical equivalence.** Two expressions $A$ and $B$ are **logically equivalent**,
written $A \equiv B$, when they have the same truth value in every row — equivalently,
when the biconditional $A \leftrightarrow B$ is a tautology. This is the precise meaning
of the "$=$" sign in every Boolean identity: $A = B$ *is* $A \equiv B$. So the whole
next section is a catalogue of logical equivalences, each certified by a truth table.

> **Remark.** Satisfiability — "is there an assignment making this expression $1$?" — is
> the celebrated **SAT problem**, the first problem proved NP‑complete (Cook, 1971). A
> truth table settles it in $2^n$ rows, but for large $n$ that is hopeless, which is why
> SAT is central to complexity theory. We only need the small‑$n$ case here.

## 4.8 The laws (identities) of Boolean algebra

The following identities hold for all Boolean variables. They are written in **dual
pairs**: an AND‑form and an OR‑form.

| Law | AND‑form ($\wedge$) | OR‑form ($\vee$) |
|---|---|---|
| Commutative | $p \wedge q = q \wedge p$ | $p \vee q = q \vee p$ |
| Associative | $(p \wedge q) \wedge r = p \wedge (q \wedge r)$ | $(p \vee q) \vee r = p \vee (q \vee r)$ |
| Distributive | $p \wedge (q \vee r) = (p \wedge q) \vee (p \wedge r)$ | $p \vee (q \wedge r) = (p \vee q) \wedge (p \vee r)$ |
| Identity | $p \wedge 1 = p$ | $p \vee 0 = p$ |
| Domination | $p \wedge 0 = 0$ | $p \vee 1 = 1$ |
| Idempotent | $p \wedge p = p$ | $p \vee p = p$ |
| Complement | $p \wedge \neg p = 0$ | $p \vee \neg p = 1$ |
| Absorption | $p \wedge (p \vee q) = p$ | $p \vee (p \wedge q) = p$ |
| De Morgan | $\neg(p \wedge q) = \neg p \vee \neg q$ | $\neg(p \vee q) = \neg p \wedge \neg q$ |
| Involution | $\neg(\neg p) = p$ | (self‑dual) |

We now prove each law by the truth‑table method: **build both sides and compare final
columns.** Since $A = B$ means precisely "same value in every row", a matching pair of
columns *is* a complete proof.

### Commutativity

> **Theorem.** $p \wedge q = q \wedge p$ and $p \vee q = q \vee p$.

*Proof.* All four rows for both operations:

| $p$ | $q$ | $p \wedge q$ | $q \wedge p$ | $p \vee q$ | $q \vee p$ |
|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |

Column $p\wedge q$ equals column $q\wedge p$, and column $p\vee q$ equals column
$q\vee p$, in every row. $\blacksquare$

### Associativity

> **Theorem.** $(p \wedge q) \wedge r = p \wedge (q \wedge r)$ and
> $(p \vee q) \vee r = p \vee (q \vee r)$.

*Proof.* For conjunction:

| $p$ | $q$ | $r$ | $p \wedge q$ | $(p \wedge q)\wedge r$ | $q \wedge r$ | $p \wedge (q \wedge r)$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |

The columns $(p\wedge q)\wedge r$ and $p\wedge(q\wedge r)$ agree (both are $1$ exactly
when $p=q=r=1$). For disjunction:

| $p$ | $q$ | $r$ | $p \vee q$ | $(p \vee q)\vee r$ | $q \vee r$ | $p \vee (q \vee r)$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |

The columns $(p\vee q)\vee r$ and $p\vee(q\vee r)$ agree (both are $0$ exactly when
$p=q=r=0$). $\blacksquare$

> **Remark.** Associativity is what lets us write $p \wedge q \wedge r$ and
> $p \vee q \vee r$ without parentheses at all: the grouping does not affect the value.
> Together with commutativity it means a long AND (resp. OR) is just "are *all* inputs
> $1$?" (resp. "is *at least one* input $1$?"), regardless of order or grouping.

### Distributivity

> **Theorem.** $p \wedge (q \vee r) = (p \wedge q) \vee (p \wedge r)$ and
> $p \vee (q \wedge r) = (p \vee q) \wedge (p \vee r)$.

*Proof.* First form ($\wedge$ over $\vee$):

| $p$ | $q$ | $r$ | $q \vee r$ | $p \wedge (q \vee r)$ | $p \wedge q$ | $p \wedge r$ | $(p \wedge q) \vee (p \wedge r)$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

The columns $p \wedge (q \vee r)$ and $(p \wedge q) \vee (p \wedge r)$ coincide. Second
form ($\vee$ over $\wedge$):

| $p$ | $q$ | $r$ | $q \wedge r$ | $p \vee (q \wedge r)$ | $p \vee q$ | $p \vee r$ | $(p \vee q) \wedge (p \vee r)$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

The columns $p \vee (q \wedge r)$ and $(p \vee q) \wedge (p \vee r)$ coincide.
$\blacksquare$

> **Remark.** The first form mimics ordinary arithmetic ($a(b+c) = ab + ac$). The second
> form, $p \vee (q \wedge r) = (p \vee q)\wedge(p \vee r)$, has **no** analogue in
> ordinary arithmetic — $a + bc \neq (a+b)(a+c)$ in general — and is a hallmark of
> Boolean algebra. In Boolean algebra, $\vee$ and $\wedge$ distribute over *each other*,
> perfectly symmetrically.

### Identity and domination

> **Theorem.** $p \wedge 1 = p$, $\ p \vee 0 = p$ (identity); $\ p \wedge 0 = 0$,
> $\ p \vee 1 = 1$ (domination).

*Proof.* Here $0$ and $1$ are constants, so only the two values of $p$ matter:

| $p$ | $p \wedge 1$ | $p \vee 0$ | $p \wedge 0$ | $p \vee 1$ |
|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 |

Columns $p\wedge 1$ and $p\vee 0$ equal the $p$ column; column $p\wedge 0$ is constantly
$0$; column $p\vee 1$ is constantly $1$. $\blacksquare$

The identity law says $1$ is the neutral element for $\wedge$ and $0$ is the neutral
element for $\vee$ (compare $a \times 1 = a$ and $a + 0 = a$). Domination says $0$
annihilates under $\wedge$ (like $a \times 0 = 0$) and $1$ annihilates under $\vee$.

### Idempotence

> **Theorem.** $p \wedge p = p$ and $p \vee p = p$.

*Proof.*

| $p$ | $p \wedge p$ | $p \vee p$ |
|:-:|:-:|:-:|
| 0 | 0 | 0 |
| 1 | 1 | 1 |

Both columns equal $p$. $\blacksquare$

> **Remark.** Idempotence is where Boolean algebra departs sharply from arithmetic:
> $p + p = p$ and $p \cdot p = p$ hold for *all* Boolean values, whereas $a + a = 2a$
> and $a^2$ are usually different from $a$. Consequently repeated terms collapse —
> $p \vee p \vee p = p$ — which is the first tool of simplification.

### Complement

> **Theorem.** $p \wedge \neg p = 0$ and $p \vee \neg p = 1$.

*Proof.*

| $p$ | $\neg p$ | $p \wedge \neg p$ | $p \vee \neg p$ |
|:-:|:-:|:-:|:-:|
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |

Column $p\wedge\neg p$ is constantly $0$; column $p\vee\neg p$ is constantly $1$.
$\blacksquare$

These are exactly the contradiction and the tautology met earlier: a value and its
negation can never both hold, and one of them always holds.

### Involution

> **Theorem.** $\neg(\neg p) = p$.

*Proof.*

| $p$ | $\neg p$ | $\neg(\neg p)$ |
|:-:|:-:|:-:|
| 0 | 1 | 0 |
| 1 | 0 | 1 |

The column $\neg\neg p$ equals the $p$ column. $\blacksquare$

Involution is *self‑dual*: swapping $\wedge \leftrightarrow \vee$ and $0 \leftrightarrow 1$ leaves it unchanged, since it mentions neither.

### Absorption

> **Theorem.** $p \wedge (p \vee q) = p$ and $p \vee (p \wedge q) = p$.

*Proof.* First form:

| $p$ | $q$ | $p \vee q$ | $p \wedge (p \vee q)$ |
|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |

Column $p\wedge(p\vee q)$ equals the $p$ column. Second form:

| $p$ | $q$ | $p \wedge q$ | $p \vee (p \wedge q)$ |
|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |

Column $p\vee(p\wedge q)$ equals the $p$ column. $\blacksquare$

> **Remark.** "Absorption" names the phenomenon that the $q$ term is swallowed whole:
> whatever $q$ is, it makes no difference. Circuit designers love absorption because it
> deletes an entire gate. An algebraic derivation (not a truth table) is given in the
> next section.

### De Morgan's laws

> **Theorem (De Morgan).** $\neg(p \wedge q) = \neg p \vee \neg q$ and
> $\neg(p \vee q) = \neg p \wedge \neg q$.

![De Morgan's first law checked by truth table: the columns for $\neg(p\wedge q)$ and $\neg p\vee\neg q$ agree on every row](img/l04_demorgan_tt.png)

*Proof.* First law:

| $p$ | $q$ | $p \wedge q$ | $\neg(p \wedge q)$ | $\neg p$ | $\neg q$ | $\neg p \vee \neg q$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |

The columns $\neg(p \wedge q)$ and $\neg p \vee \neg q$ are equal in every row. Second
law:

| $p$ | $q$ | $p \vee q$ | $\neg(p \vee q)$ | $\neg p$ | $\neg q$ | $\neg p \wedge \neg q$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |

The columns $\neg(p \vee q)$ and $\neg p \wedge \neg q$ are equal in every row.
$\blacksquare$

> **Common pitfall.** De Morgan's laws say the negation **flips the connective**:
> $\neg(p\wedge q)$ is $\neg p \vee \neg q$, **not** $\neg p \wedge \neg q$. "Not (rich
> and famous)" means "poor *or* obscure", not "poor *and* obscure". Distributing a
> negation across $\wedge$/$\vee$ without switching the connective is the single most
> common error in this subject. In hardware terms: NOT of an AND is an OR of NOTs (a
> NAND rearranges into an OR gate with inverted inputs), and dually for NOR.

De Morgan's laws also show that $\{\wedge, \neg\}$ and $\{\vee, \neg\}$ each suffice to
express the other connective: $p \vee q = \neg(\neg p \wedge \neg q)$ and
$p \wedge q = \neg(\neg p \vee \neg q)$. This idea of a *functionally complete* set of
operations is developed fully in Lecture 5.

## 4.9 The duality principle

Look again at the table of laws: the two columns are mirror images. Swap
$\wedge \leftrightarrow \vee$ and $0 \leftrightarrow 1$ throughout, and every left‑hand
identity becomes the right‑hand one. This is no coincidence.

**The dual of an expression.** Given a Boolean expression $E$ built from variables, the
constants $0, 1$, and the operations $\neg, \wedge, \vee$, its **dual** $E^{d}$ is
obtained by interchanging $\wedge \leftrightarrow \vee$ and $0 \leftrightarrow 1$
everywhere, while **leaving variables and negations untouched**. For instance the dual
of $p \wedge (q \vee 0)$ is $p \vee (q \wedge 1)$.

> **Duality Principle.** If an identity $E_1 = E_2$ holds for all Boolean values, then
> the dual identity $E_1^{d} = E_2^{d}$ also holds.

The practical consequence is that the laws come in *pairs for free*: prove one form and
its dual is automatically a theorem. This halves the work of building and memorising
the theory. But why is it true? The justification rests on De Morgan and involution.

> **Lemma (complementation is dualization with negated inputs).** For every Boolean
> expression $E(x_1, \dots, x_n)$ built from $\neg, \wedge, \vee$ and constants,
>

$$
\neg\, E(x_1, \dots, x_n) \;=\; E^{d}(\neg x_1, \dots, \neg x_n)
$$

> as functions.

*Proof.* By structural induction on the way $E$ is built.

*Base cases.*
- $E = x_i$ (a variable). Then $E^{d} = x_i$, so $E^{d}(\neg x) = \neg x_i = \neg E$. ✓
- $E = 0$. Then $E^{d} = 1$, and $\neg E = \neg 0 = 1 = E^{d}(\neg x)$. ✓
- $E = 1$. Then $E^{d} = 0$, and $\neg E = \neg 1 = 0 = E^{d}(\neg x)$. ✓

*Inductive step.* Assume the claim for sub‑expressions $A, B$.
- $E = A \wedge B$. Then $E^{d} = A^{d} \vee B^{d}$, and

$$
\neg E = \neg(A \wedge B) \overset{\text{De M.}}{=} \neg A \vee \neg B \overset{\text{IH}}{=} A^{d}(\neg x) \vee B^{d}(\neg x) = (A^{d}\vee B^{d})(\neg x) = E^{d}(\neg x). \checkmark
$$

- $E = A \vee B$. Dually, $E^{d} = A^{d}\wedge B^{d}$ and
  $\neg E = \neg(A\vee B) = \neg A \wedge \neg B = A^{d}(\neg x)\wedge B^{d}(\neg x) = E^{d}(\neg x)$. ✓
- $E = \neg A$. Negation is unchanged by dualization, so $E^{d} = \neg(A^{d})$, and

$$
\neg E = \neg(\neg A) \overset{\text{invol.}}{=} A, \qquad E^{d}(\neg x) = \neg\bigl(A^{d}(\neg x)\bigr) \overset{\text{IH}}{=} \neg(\neg A) = A.
$$

  So $\neg E = E^{d}(\neg x)$. ✓

By induction the identity holds for every expression $E$. $\blacksquare$

*Proof of the Duality Principle.* Suppose $E_1 = E_2$ holds for all inputs. Then
$\neg E_1 = \neg E_2$ holds for all inputs as well. By the Lemma,

$$
E_1^{d}(\neg x_1, \dots, \neg x_n) = E_2^{d}(\neg x_1, \dots, \neg x_n) \quad\text{for all } (x_1,\dots,x_n).
$$

As $(x_1,\dots,x_n)$ ranges over all of $\{0,1\}^n$, the negated tuple
$(\neg x_1, \dots, \neg x_n)$ *also* ranges over all of $\{0,1\}^n$ (negation is a
bijection of $\{0,1\}$). Hence $E_1^{d}(y_1,\dots,y_n) = E_2^{d}(y_1,\dots,y_n)$ for all
$(y_1,\dots,y_n)$, i.e. $E_1^{d} = E_2^{d}$. $\blacksquare$

**Example.** The distributive law $p \wedge (q \vee r) = (p \wedge q) \vee (p \wedge r)$
has dual $p \vee (q \wedge r) = (p \vee q) \wedge (p \vee r)$ — the second distributive
law, which we no longer need to prove separately. Likewise absorption
$p\wedge(p\vee q)=p$ dualizes to $p\vee(p\wedge q)=p$, and the two De Morgan laws are
duals of each other.

> **Common pitfall.** The dual is **not** the negation. To dualize you swap
> $\wedge\leftrightarrow\vee$ and $0\leftrightarrow1$ but leave the variables *and their
> bars* alone. Negating an expression is a different operation (and, by the Lemma above,
> equals the dual only after you *also* negate every variable).

## 4.10 Proving identities algebraically

Truth tables always work, but for expressions with many variables they are long. Once
the laws are established, we can also prove new identities *algebraically* — by
rewriting one side into the other using the laws as rewrite rules. This is exactly how
one simplifies circuits (Lecture 5), and it is the style of proof used in propositional
logic (Lecture 6).

**Example — absorption derived from the axioms.** We prove $p \vee (p \wedge q) = p$
using only identity, distributivity and domination:

$$
\begin{aligned} p \vee (p \wedge q) &= (p \wedge 1) \vee (p \wedge q) && \text{(identity: } p = p\wedge 1)\\ &= p \wedge (1 \vee q) && \text{(distributive, factor out } p)\\ &= p \wedge 1 && \text{(domination: } 1 \vee q = 1)\\ &= p. && \text{(identity)} \end{aligned}
$$

By the duality principle, dualizing every step proves the other absorption law
$p \wedge (p \vee q) = p$ at once — no separate calculation required.

**Example — simplify $\neg(\neg p \wedge q) \wedge (p \vee q)$.**

$$
\begin{aligned} \neg(\neg p \wedge q) \wedge (p \vee q) &= (\neg\neg p \vee \neg q) \wedge (p \vee q) && \text{(De Morgan)}\\ &= (p \vee \neg q) \wedge (p \vee q) && \text{(involution)}\\ &= p \vee (\neg q \wedge q) && \text{(distributive, factor out } p)\\ &= p \vee 0 && \text{(complement)}\\ &= p. && \text{(identity)} \end{aligned}
$$

A four‑operator expression collapses to the single variable $p$. Verifying this by
truth table would take four rows; the algebra explains *why* it holds.

![Algebraic simplification of $\neg(\neg p\wedge q)\wedge(p\vee q)$ down to $p$, each step justified by a named law: De Morgan, involution, distributive, complement, identity](img/l04_simplify.png)

> **Remark.** An algebraic proof and a truth‑table proof establish the same fact but
> serve different purposes. The truth table is a *decision procedure* — it always
> terminates with a yes/no. The algebraic derivation gives *insight and structure*, and
> it scales to symbolic settings where truth tables do not (e.g. reasoning about
> circuits with hundreds of inputs, where $2^{n}$ rows is out of reach).

## 4.11 Three faces of one structure: logic, sets, and bits

The laws we proved are not special to truth values. **The same list of laws** governs
the **algebra of sets** (Lecture 2) and the **algebra of propositions** (Lecture 6).
This is because all three are instances of one abstract structure — a *Boolean algebra*
— and we can line the three up operation for operation.

![Logic, sets, and bits are one structure: $\wedge/\cap/$AND, $\vee/\cup/$OR, $\neg/$complement$/$NOT, with $F/\varnothing/0$ at the bottom and $T/U/1$ at the top](img/l04_three_faces.png)

| Concept | Propositional logic | Set algebra | Boolean (bit) algebra |
|---|---|---|---|
| "or" | $p \vee q$ | $A \cup B$ | $a \vee b$ |
| "and" | $p \wedge q$ | $A \cap B$ | $a \wedge b$ |
| "not" | $\neg p$ | $\overline{A}$ | $\neg a$ |
| bottom / empty | $F$ (contradiction) | $\varnothing$ | $0$ |
| top / universe | $T$ (tautology) | $U$ | $1$ |
| "same" | $p \equiv q$ | $A = B$ | $a = b$ |
| "at most" | $p \to q$ | $A \subseteq B$ | $a \le b$ |

Every law reads identically down any column. For example, De Morgan appears as

$$
\neg(p \wedge q) = \neg p \vee \neg q, \qquad \overline{A \cap B} = \overline{A} \cup \overline{B}, \qquad \neg(a \wedge b) = \neg a \vee \neg b,
$$

and absorption, distributivity, complement, and the rest all match line for line. This
is why a fact proved in one setting transfers to the others; the membership table you
used for sets in Lecture 2 is *the same computation* as the truth table you use here.

**A genuine isomorphism (sets $\leftrightarrow$ bit vectors).** The correspondence
between sets and bits can be made completely precise. Fix a universe $U$. To each subset
$A \subseteq U$ associate its **characteristic (indicator) function**

$$
\chi_A : U \to \{0,1\}, \qquad \chi_A(x) = \begin{cases} 1 & x \in A,\\ 0 & x \notin A. \end{cases}
$$

The map $A \mapsto \chi_A$ is a **bijection** between the power set $\mathcal{P}(U)$ and
the set $\{0,1\}^{U}$ of all bit‑valued functions on $U$ (both have $2^{|U|}$ elements,
and the map is clearly one‑to‑one and onto). Moreover it *respects every operation*,
computed pointwise:

$$
\chi_{A \cap B} = \chi_A \wedge \chi_B, \quad \chi_{A \cup B} = \chi_A \vee \chi_B, \quad \chi_{\overline A} = \neg\,\chi_A, \quad \chi_{\varnothing} = 0, \quad \chi_{U} = 1.
$$

A structure‑preserving bijection like this is called an **isomorphism**: set algebra on
$\mathcal{P}(U)$ *is*, up to renaming, the coordinatewise Boolean algebra $\{0,1\}^{U}$.
In the smallest case $|U| = 1$ we get $\mathcal{P}(U) \cong \{0,1\}$ exactly — the
two‑element bit algebra of this lecture, with $\varnothing \leftrightarrow 0$ and
$U \leftrightarrow 1$.

**And propositional logic.** On the logic side, formulas *modulo logical equivalence*
(grouping together all formulas with the same truth table) form a Boolean algebra too,
with $\wedge, \vee, \neg$ as operations, the class of contradictions as $0$, and the
class of tautologies as $1$. So the three "faces" are:

- **bits** $\{0,1\}$ under $\wedge, \vee, \neg$ — the hardware/arithmetic view;
- **subsets** of a universe under $\cap, \cup, \overline{\ \cdot\ }$ — the set view;
- **propositions** (up to equivalence) under and/or/not — the reasoning view.

They obey the same laws because they are the same algebra wearing three costumes. This
is the deep reason the Venn‑diagram intuition from Lecture 2 and the truth tables of
this lecture never conflict.

## 4.12 A note on history: Boole and Shannon

The algebra of this chapter is named for **George Boole** (1815–1864), a largely
self‑taught English mathematician. In *The Mathematical Analysis of Logic* (1847) and
the fuller *An Investigation of the Laws of Thought* (1854), Boole argued that the
laws of correct reasoning could be written as algebraic equations over quantities
taking the values $0$ and $1$ — turning logic, for the first time, into calculation. The
idempotent law $x^2 = x$ (our $p \wedge p = p$) was, in Boole's own treatment, the
equation that singled out this special algebra from ordinary algebra.

The bridge to computing came much later. In his 1937 MIT master's thesis, *A Symbolic
Analysis of Relay and Switching Circuits*, **Claude Shannon** (1916–2001) observed that
a network of on/off switches obeys exactly Boole's laws — a switch is $0$ or $1$, series
wiring is $\wedge$, parallel wiring is $\vee$ — so any switching circuit can be
*designed and simplified algebraically*. That single insight is the theoretical
foundation of all digital hardware. It is often called one of the most influential
master's theses ever written.

## 4.13 Connections to computer science and hardware

Boolean algebra is the working mathematics of the machine layer. A few threads we will
pick up or that you already use:

- **Logic gates.** The primitive operations $\neg, \wedge, \vee$ (and the derived
  NAND, NOR, XOR) are realised as physical **gates**; a Boolean expression becomes a
  circuit and vice versa. **Lecture 5** builds gates, translates expressions to
  circuits, and shows how NAND *or* NOR alone can implement everything.
- **Minimization.** Because there are $2^{2^n}$ functions but many *expressions* for
  each, we want the *smallest* expression (fewest gates). The laws above — especially
  absorption, distributivity and idempotence — are the algebraic tools; **canonical
  normal forms** (CDNF/CCNF) and **Karnaugh maps** are the systematic ones, both in
  Lecture 5.
- **Bitwise operations.** In C/Java/Python the operators `&`, `|`, `~`, `^` apply
  $\wedge, \vee, \neg, \oplus$ to all bits of an integer in parallel — Boolean algebra
  on $32$ or $64$ independent copies at once. Masks, flags and toggles are De Morgan and
  complement in action.
- **Control flow and short‑circuiting.** `&&` and `||` evaluate left‑to‑right and stop
  early; their algebra is exactly $\wedge$ and $\vee$, and refactoring a condition
  safely (e.g. `!(a && b)` into `!a || !b`) is De Morgan.
- **Search and databases.** Query languages combine conditions with AND/OR/NOT; query
  optimisation rewrites them using these very laws.
- **Deductive logic.** The tautologies and equivalences here become the *propositional equivalences* of
  **Lecture 6 (propositional logic)** and the *rules of inference* of **Lecture 7
  (proof techniques)** — for instance, the hypothetical syllogism proved above.

## Chapter summary

- A **statement** is a declarative sentence that is definitely true or false; we encode
  the values as $1$ (true) and $0$ (false). Compound statements are **truth‑functional**:
  their value depends only on the parts' values and the connectives.
- Boolean algebra works over the alphabet $\{0, 1\}$ with the primitive operations
  $\neg, \wedge, \vee$ and the derived operations $\oplus, \to, \leftrightarrow$; each is
  defined by a **truth table**. Standard precedence is
  $\neg > \wedge > \vee > \to > \leftrightarrow$.
- $\wedge$ is true only when both inputs are $1$; $\vee$ (inclusive) is true when at
  least one is $1$; $\oplus$ is true when the inputs differ; $p \to q$ is false only for
  $p=1, q=0$; $p \leftrightarrow q$ is true when the inputs match. Key rewrites:
  $p\to q = \neg p \vee q$ and $p \oplus q = (p\wedge\neg q)\vee(\neg p\wedge q)$.
- A **Boolean function** of $n$ variables is exactly a truth table with $2^n$ rows;
  there are $2^{2^n}$ such functions ($2$ for $n=0$, $4$ for $n=1$, $16$ for $n=2$,
  $256$ for $n=3$) — **proved** by counting rows then fillings.
- A **tautology** is always $1$; a **contradiction** is always $0$; expressions $A, B$
  are **logically equivalent** ($A \equiv B$) when their columns match, which is what a
  Boolean identity $A = B$ means. Compound expressions are evaluated column by column.
- The **laws** (commutative, associative, distributive, identity, domination,
  idempotent, complement, absorption, involution, De Morgan) come in **dual pairs** and
  were each **proved by truth table**. Identities can also be derived **algebraically**
  from the laws.
- The **Duality Principle** — swap $\wedge\leftrightarrow\vee$ and $0\leftrightarrow1$ —
  turns any true identity into another true identity; it is *justified* via the lemma
  $\neg E(x) = E^{d}(\neg x)$, proved by structural induction from De Morgan and
  involution.
- **Logic, sets and bits are one structure.** $\vee\leftrightarrow\cup$,
  $\wedge\leftrightarrow\cap$, $\neg\leftrightarrow$ complement, $0\leftrightarrow \varnothing$, $1\leftrightarrow U$; the characteristic‑function map
  $A \mapsto \chi_A$ is a genuine isomorphism $\mathcal{P}(U)\cong\{0,1\}^{U}$, so every
  law transfers among the three.
- **Forward pointers:** gates, functional completeness, canonical forms and Karnaugh
  maps in **Lecture 5**; the semantics of propositional logic in **Lecture 6**; proof
  and inference in **Lecture 7**.

## Exercises

### Warm‑up

1. **Statement or not?** Classify each sentence as a statement (proposition) or not,
   and if it is a statement give its truth value where possible:
   (a) "$17$ is prime."  (b) "Read Lecture 4."  (c&#41; "$x^2 = 4$."
   (d) "Every even number greater than $2$ is a sum of two primes."  (e) "Ouch!"

2. **Fill the tables.** From memory, write the truth tables of $\neg p$, $p \wedge q$,
   $p \vee q$, $p \oplus q$, $p \to q$, $p \leftrightarrow q$. State in one phrase what
   makes each operation output $1$.

3. **Evaluate at a point.** With $p = 1$, $q = 0$, $r = 1$, compute the value of
   $(p \vee q) \wedge \neg r$ and of $p \to (q \vee \neg r)$.

4. **Precedence.** Insert full parentheses according to the standard precedence:
   (a) $\neg p \wedge q \vee r$   (b) $p \vee q \to \neg r$   (c&#41; $\neg\neg p \wedge q$.

5. **When is it false?** State the single row on which $p \to q$ is $0$, and explain in
   words why $p \to q$ is $1$ whenever $p = 0$.

6. **Dictionary.** Give the set‑algebra counterpart and the propositional‑logic
   counterpart of each of $\wedge$, $\vee$, $\neg$, $0$, $1$.

### Standard

7. **Build a table.** Construct the full truth table of $(p \vee \neg q) \wedge r$ and
   state on how many of the $8$ rows it equals $1$.

8. **Implication rewrite.** Prove $p \to q \equiv \neg p \vee q$ by truth table, then use
   it to write $\neg(p \to q)$ in terms of $\wedge$ and $\neg$ only.

9. **Contrapositive.** Prove by truth table that $p \to q \equiv \neg q \to \neg p$.
   (This equivalence is the basis of proof by contraposition, Lecture 7.)

10. **Second De Morgan.** Prove $\neg(p \vee q) = \neg p \wedge \neg q$ by constructing
    and comparing truth tables.

11. **Both absorptions.** Verify $p \vee (p \wedge q) = p$ by truth table, then give a
    purely algebraic derivation of $p \wedge (p \vee q) = p$ from the laws.

12. **XOR in primitives.** Show $p \oplus q = (p \wedge \neg q) \vee (\neg p \wedge q)$
    by truth table.

13. **Classify.** For each formula decide whether it is a tautology, a contradiction, or
    a contingency, and justify with its final column:
    (a) $p \to (q \to p)$  (b) $(p \wedge \neg p) \to q$  (c&#41; $p \leftrightarrow \neg p$
    (d) $(p \to q) \wedge p \wedge \neg q$.

14. **Duals.** Write the dual of each identity (do **not** negate):
    (a) $p \wedge (q \vee r) = (p \wedge q) \vee (p \wedge r)$
    (b) $p \vee 1 = 1$   (c&#41; $p \wedge (p \vee q) = p$.

15. **Counting.** How many Boolean functions are there of $3$ variables? Of $5$
    variables? Of the $16$ two‑variable functions, how many are **commutative**
    (satisfy $f(x,y) = f(y,x)$)? Justify the last count.

16. **Simplify algebraically.** Using the laws, simplify
    $(p \wedge q) \vee (p \wedge \neg q)$ and $\ (p \vee q) \wedge (\neg p \vee q)$ to a
    single variable each. Name every law you use.

### Challenge

17. **Hypothetical syllogism.** Prove that
    $\bigl((p \to q) \wedge (q \to r)\bigr) \to (p \to r)$ is a tautology, and identify
    which rows make the outer implication vacuously true.

18. **Duality by hand.** For the specific expression $E = p \wedge (\neg q \vee 0)$,
    write down $E^{d}$, and verify the lemma $\neg E = E^{d}(\neg p, \neg q)$ by an
    $4$‑row truth table.

19. **Self‑dual functions.** A Boolean function $f$ is *self‑dual* if $f = f^{d}$,
    equivalently $f(\neg x_1, \dots, \neg x_n) = \neg f(x_1, \dots, x_n)$ for all inputs.
    How many self‑dual functions of $2$ variables are there? (Hint: pair each input with
    its bitwise complement.) List one non‑trivial example.

20. **Isomorphism check.** Let $U = \{1, 2, 3\}$, $A = \{1, 2\}$, $B = \{2, 3\}$. Write
    the characteristic vectors $\chi_A, \chi_B \in \{0,1\}^3$ (order the coordinates
    $1, 2, 3$). Compute $\chi_A \wedge \chi_B$, $\chi_A \vee \chi_B$ and $\neg \chi_A$
    coordinatewise, and confirm they are the characteristic vectors of $A \cap B$,
    $A \cup B$ and $\overline{A}$ respectively.

## Selected answers & hints

**1.** (a) statement, true. (b) not a statement (command). (c&#41; open sentence — a
statement only once $x$ is fixed. (d) statement (Goldbach's conjecture): it has a
definite truth value even though it is currently unknown. (e) not a statement
(exclamation).

**3.** $(p\vee q)\wedge\neg r = (1\vee 0)\wedge\neg 1 = 1 \wedge 0 = 0$.
$\ p\to(q\vee\neg r) = 1 \to (0 \vee 0) = 1 \to 0 = 0$.

**4.** (a) $((\neg p)\wedge q)\vee r$.  (b) $(p\vee q)\to(\neg r)$.
(c&#41; $(\neg(\neg p))\wedge q$.

**5.** False only on the row $p=1, q=0$. When $p=0$ the promise "if $p$ then $q$" is
never triggered, so it cannot be broken — the implication is vacuously $1$.

**7.** The column of $(p\vee\neg q)\wedge r$ is $1$ on exactly $3$ of the $8$ rows —
those with $r=1$ and $(p\vee\neg q)=1$, namely $(p,q,r) = (0,0,1),(1,0,1),(1,1,1)$.

**8.** The two columns match (see Example 4). Then
$\neg(p\to q) = \neg(\neg p \vee q) = \neg\neg p \wedge \neg q = p \wedge \neg q$ by
De Morgan and involution.

**9.** Both columns equal $1,1,0,1$ over the rows $00,01,10,11$; hence equivalent.

**11.** Table for $p\vee(p\wedge q)$ reads $0,0,1,1 = p$. Algebraic derivation of the
dual: $p\wedge(p\vee q) = (p\vee 0)\wedge(p\vee q) = p \vee (0\wedge q) = p \vee 0 = p$
(identity, distributive, domination, identity) — or simply dualize the derivation in the
text.

**13.** (a) tautology; (b) tautology (a contradiction implies anything); (c&#41;
contradiction; (d) contradiction (it asserts $p\to q$ together with $p$ and $\neg q$,
which is impossible).

**14.** (a) $p \vee (q \wedge r) = (p \vee q) \wedge (p \vee r)$.  (b) $p \wedge 0 = 0$.
(c&#41; $p \vee (p \wedge q) = p$.

**15.** $3$ variables: $2^{2^3} = 2^8 = 256$. $5$ variables: $2^{2^5} = 2^{32} = 4\,294\,967\,296$. Commutative two‑variable functions: the outputs on rows $01$ and $10$
must be equal, so we freely choose the output on row $00$ ($2$ ways), on the merged
$01{=}10$ ($2$ ways) and on row $11$ ($2$ ways): $2^3 = 8$.

**16.** $(p\wedge q)\vee(p\wedge\neg q) = p\wedge(q\vee\neg q) = p\wedge 1 = p$
(distributive, complement, identity). $(p\vee q)\wedge(\neg p\vee q) = q\vee(p\wedge\neg p) = q\vee 0 = q$ (dual distributive, complement, identity).

**17.** See the worked $8$‑row table in the text; the final column is all $1$s. The
outer implication is vacuously true on exactly the rows where the hypothesis
$(p\to q)\wedge(q\to r)$ is $0$, namely $(p,q,r) = 010, 100, 101, 110$.

**18.** $E = p \wedge (\neg q \vee 0) = p \wedge \neg q$, with column $0,0,1,0$ over
$pq = 00,01,10,11$, so $\neg E$ has column $1,1,0,1$. Dually $E^{d} = p \vee (\neg q \wedge 1)$, and $E^{d}(\neg p, \neg q) = \neg p \vee (q \wedge 1) = \neg p \vee q$, whose
column is also $1,1,0,1$. The two columns agree in all four rows, confirming
$\neg E = E^{d}(\neg p, \neg q)$.

**19.** $4$ self‑dual functions of two variables. The inputs pair up as $\{00,11\}$ and
$\{01,10\}$ under bitwise complement; on each pair the two outputs must be complementary,
leaving $2$ pairs $\times\ 2$ choices $= 2^2 = 4$. Example: the projection $f(x,y) = x$
is self‑dual.

**20.** $\chi_A = (1,1,0)$, $\chi_B = (0,1,1)$. Then $\chi_A\wedge\chi_B = (0,1,0) = \chi_{A\cap B}$ with $A\cap B = \{2\}$; $\chi_A\vee\chi_B = (1,1,1) = \chi_{A\cup B}$ with
$A\cup B = \{1,2,3\} = U$; $\neg\chi_A = (0,0,1) = \chi_{\overline A}$ with $\overline A = \{3\}$. All three match, illustrating the isomorphism.

## Further reading

- K. H. Rosen, *Discrete Mathematics and Its Applications* — the chapter on logic and
  logical equivalences (propositional logic, laws, tautologies) and the chapter on
  Boolean algebra (Boolean functions, identities, duality, gates).
- S. S. Epp, *Discrete Mathematics with Applications* — the chapter on the logic of
  compound statements (truth tables, logical equivalence, De Morgan's laws) and the
  section on Boolean algebras and digital logic circuits.
- Historical primary sources: G. Boole, *An Investigation of the Laws of Thought*
  (1854); C. E. Shannon, "A Symbolic Analysis of Relay and Switching Circuits" (1938).