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:

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).

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.

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$.

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$.

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$.

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$.

All binary operations at a glance #

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

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}}.$$

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.

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$:

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):

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$:

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:

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)$.

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.

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$”.

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):

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

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.

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:

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:

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:

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$):

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

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:

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.

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.

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.

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:

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

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$.

Proof. First law:

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

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: