Logical Equivalence

Definition 12.20. Two compound statements $A,B$ are logically equivalent (or simply equivalent), written $A\equiv B$ or $A\Leftrightarrow B$, if the columns for $A$ and $B$ in a shared truth table are identical in every row. Equivalently, $A\equiv B$ exactly when $A\leftrightarrow B$ is a tautology.

The standard Laws of Equivalence, each established by truth table and then reusable to prove further equivalences symbolically:

1. Idempotent Laws. (i) $p\vee p\equiv p$ (ii) $p\wedge p\equiv p$. Proof: both $p\vee p$ and $p\wedge p$ take exactly the same truth value as $p$ in every row.

2. Commutative Laws. (i) $p\vee q\equiv q\vee p$ (ii) $p\wedge q\equiv q\wedge p$. Proof (i): the columns for $p\vee q$ and $q\vee p$ agree row for row -- $T,T,T,F$ for both across $(T,T),(T,F),(F,T),(F,F)$.

3. Associative Laws. (i) $p\vee(q\vee r)\equiv(p\vee q)\vee r$ (ii) $p\wedge(q\wedge r)\equiv(p\wedge q)\wedge r$. Proof (i): an 8-row truth table (three variables) shows both sides agree in every row.

4. Distributive Laws. (i) $p\vee(q\wedge r)\equiv(p\vee q)\wedge(p\vee r)$ (ii) $p\wedge(q\vee r)\equiv(p\wedge q)\vee(p\wedge r)$. Proof (i): an 8-row truth table shows the columns for $p\vee(q\wedge r)$ and $(p\vee q)\wedge(p\vee r)$ match exactly.

5. Identity Laws. (i) $p\vee\mathbb T\equiv\mathbb T$ and $p\vee\mathbb F\equiv p$ (ii) $p\wedge\mathbb T\equiv p$ and $p\wedge\mathbb F\equiv\mathbb F$. Proof: since $\mathbb T$ is always $T$ and $\mathbb F$ is always $F$, $p\vee\mathbb T$ matches $\mathbb T$'s column and $p\vee\mathbb F$ matches $p$'s column exactly (dually for $\wedge$).

6. Complement Laws. (i) $p\vee\neg p\equiv\mathbb T$ and $p\wedge\neg p\equiv\mathbb F$ (ii) $\neg\mathbb T\equiv\mathbb F$ and $\neg\mathbb F\equiv\mathbb T$. Proof: direct from the truth tables of $\vee,\wedge,\neg$ applied to $p,\neg p$.

7. Involution (Double Negation) Law. $\neg(\neg p)\equiv p$. Proof: $\neg p$ flips $p$ once; $\neg(\neg p)$ flips it back, matching $p$ in every row.

8. De Morgan's Laws. (i) $\neg(p\wedge q)\equiv\neg p\vee\neg q$ (ii) $\neg(p\wedge q)\equiv\neg p\vee\neg q$. Proof (i): both columns read $F,T,T,T$ across $(T,T),(T,F),(F,T),(F,F)$. (ii), dually, $\neg(p\vee q)\equiv\neg p\wedge\neg q$.

9. Absorption Laws. (i) $p\vee(p\wedge q)\equiv p$ (ii) $p\wedge(p\vee q)\equiv p$. Proof: both columns match $p$'s column exactly in every row.

Two further named equivalences, proved by chaining the laws above (Example 12.17-12.19):

• $p\to q\equiv\neg p\vee q$ -- verified directly by truth table (both columns read $T,F,T,T$).
• $p\leftrightarrow q\equiv(p\to q)\wedge(q\to p)$ -- verified by truth table (both columns read $T,F,F,T$). …