Mathematics.

propositional logic

Logical Equivalences

Discrete Mathematics20 minDifficulty2 out of 10

You should know: propositional logic

Overview

Two propositional formulas are logically equivalent if they have the same truth value under every possible assignment of truth values to their variables, written p ≡ q. Equivalences let us rewrite statements into simpler or more useful forms without changing their meaning, much like algebraic identities let us rewrite expressions. A standard library of equivalences — De Morgan's laws, the distributive laws, double negation, contrapositive, and the biconditional's expansion — covers the vast majority of simplifications needed in proofs and digital logic. Verifying an equivalence can always be done mechanically by comparing truth tables, but recognizing and applying named equivalences is far faster in practice.

Intuition

Think of a logical equivalence as two different recipes that always produce the same dish: no matter which raw ingredients (truth values) you feed in, both formulas come out identical. This is why you can substitute one side for the other anywhere inside a larger proof — it's the logical analogue of substituting equal quantities in algebra, and it's how a messy conditional statement gets rewritten into a clean disjunction or a checkable contrapositive.

Formal Definition

Definition

p and q are logically equivalent, written p ≡ q, exactly when p ↔ q is a tautology (true under every assignment). Key named equivalences include:

¬(p∧q)≡¬p∨¬q\neg(p \land q) \equiv \neg p \lor \neg q
De Morgan's law
¬(p∨q)≡¬p∧¬q\neg(p \lor q) \equiv \neg p \land \neg q
De Morgan's law (dual)
p→q≡¬p∨q≡¬q→¬pp \rightarrow q \equiv \neg p \lor q \equiv \neg q \rightarrow \neg p
Conditional as disjunction / contrapositive
p∧(q∨r)≡(p∧q)∨(p∧r)p \land (q \lor r) \equiv (p \land q) \lor (p \land r)
Distributive law

Worked Examples

  1. Rewrite the conditional as a disjunction.

    p→q≡¬p∨qp \rightarrow q \equiv \neg p \lor q

  2. Negate both sides and apply De Morgan's law.

    ¬(p→q)≡¬(¬p∨q)≡¬¬p∧¬q\neg(p \rightarrow q) \equiv \neg(\neg p \lor q) \equiv \neg\neg p \land \neg q

  3. Double negation simplifies ¬¬p to p.

    ≡p∧¬q\equiv p \land \neg q

Answer: ¬(p → q) ≡ p ∧ ¬q.

Practice Problems

Difficulty 2/10

Use De Morgan's law to simplify ¬(¬p ∨ q).

Difficulty 3/10

Show that p ↔ q is equivalent to (p → q) ∧ (q → p).

Difficulty 4/10

Prove that (p → r) ∧ (q → r) ≡ (p ∨ q) → r.

Quiz

Which formula is logically equivalent to ¬(p ∧ q)?
The contrapositive of p → q is:
Two formulas are logically equivalent exactly when:

Summary

  • p ≡ q means p and q have identical truth values under every assignment, equivalently p ↔ q is a tautology.
  • Named equivalences (De Morgan's, distributive, contrapositive, double negation) let you rewrite formulas without checking a full truth table.
  • Equivalences justify substitution: any subformula can be replaced by an equivalent one anywhere inside a larger expression.

References

  1. WebsiteWikipedia — Logical equivalence