Logical Equivalence: Prove Statements Are Equivalent

Two compound statements are logically equivalent when they have the same truth value in every row of a shared truth table, written p ≡ q. For example, ¬(p ∧ q) and ¬p ∨ ¬q always agree. Equivalence is about matching behaviour, not about looking alike.

Equivalence lets you rewrite statements into simpler forms without changing their meaning. Simplifying a circuit or negating a complicated condition in code both depend on replacing a statement by an equivalent one.

Key Concepts

• Logical equivalence (≡): p ≡ q exactly when p ↔ q is a tautology, i.e. their truth-table columns are identical in every row.
• Test: build one truth table with columns for both statements and compare the final columns row by row.
• De Morgan's laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q (negation flips the connective).
• Implication rewrite: p → q ≡ ¬p ∨ q, and the contrapositive p → q ≡ ¬q → ¬p.

How It Works

To prove p ≡ q with a truth table:

1. List all 2n rows for the variables appearing in either statement.
2. Compute a column for the first statement.
3. Compute a column for the second statement.
4. Compare the final columns. A match in every row means equivalence; one differing row destroys it.

Worked Example

Prove De Morgan's law ¬(p ∨ q) ≡ ¬p ∧ ¬q. Compute both sides row by row:

• Row 1 (T, T): ¬(p ∨ q) = F; ¬p ∧ ¬q = F ∧ F = F. Match.
• Row 2 (T, F): ¬(p ∨ q) = F; ¬p ∧ ¬q = F ∧ T = F. Match.
• Row 3 (F, T): ¬(p ∨ q) = F; ¬p ∧ ¬q = T ∧ F = F. Match.
• Row 4 (F, F): ¬(p ∨ q) = T; ¬p ∧ ¬q = T ∧ T = T. Match.

Both final columns read F, F, F, T, so the equivalence is proved: "not (p or q)" means exactly "not p and not q".

Common Misconceptions

• "≡ and → are the same thing." They are very different: p → q varies by row, while p ≡ q claims the whole tables match (equivalently, p ↔ q is a tautology).
• "Equivalent statements must use the same connectives." No. ¬(p ∧ q) uses negation and conjunction while ¬p ∨ ¬q uses negation and disjunction, yet they are equivalent. Equivalence is about columns, not appearance.
• "One matching row is enough." One agreeing row proves nothing; equivalence demands every row.

Real-World Applications

• Circuit simplification: replacing a gate network by an equivalent simpler one cuts cost and power; equivalence checking verifies the replacement is safe.
• Programming: rewriting if (!(a && b)) as if (!a || !b) uses De Morgan's law; compilers apply such rewrites automatically.
• Mathematics: the contrapositive lets you prove "if p then q" by proving the equivalent "if not q then not p", which is often easier.

Logical equivalence means identical truth-table columns in every row, written p ≡ q. Test it by computing both sides side by side, and lean on De Morgan's laws, p → q ≡ ¬p ∨ q, and the contrapositive.