Logical Equivalences

Overview

Simplifying with Equivalences

Two compound propositions are logically equivalent (written ≡) if they have the same truth value for every possible assignment of truth values to their variables. Equivalence laws let you simplify and transform logical expressions, much like algebraic identities let you simplify numeric expressions.

Definition

Logical Equivalence

Propositions p and q are logically equivalent, written p ≡ q, if the biconditional p ↔ q is a tautology. Equivalently, they have identical truth tables.

Theorem

De Morgan's Laws

¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q

De Morgan's Laws tell you how to distribute negation over conjunction and disjunction: negate each part and flip the connective (∧ becomes ∨ and vice versa).

Theorem

Key Equivalence Laws

Identity: p ∧ T ≡ p, p ∨ F ≡ p Domination: p ∨ T ≡ T, p ∧ F ≡ F Idempotent: p ∨ p ≡ p, p ∧ p ≡ p Double negation: ¬(¬p) ≡ p Commutative: p ∧ q ≡ q ∧ p, p ∨ q ≡ q ∨ p Associative: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) Distributive: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Absorption: p ∨ (p ∧ q) ≡ p, p ∧ (p ∨ q) ≡ p

Theorem

Conditional Equivalences

p → q ≡ ¬p ∨ q p → q ≡ ¬q → ¬p (contrapositive) ¬(p → q) ≡ p ∧ ¬q p ↔ q ≡ (p → q) ∧ (q → p)

Example

Simplification Example

Simplify ¬(p ∨ ¬q):

Step 1: Apply De Morgan's Law → ¬p ∧ ¬(¬q) Step 2: Apply Double Negation → ¬p ∧ q

So ¬(p ∨ ¬q) ≡ ¬p ∧ q.

Example

Proving Equivalence with a Truth Table

Verify p → q ≡ ¬p ∨ q:

p | q | p → q | ¬p | ¬p ∨ q ----|----| ------|----|------- T | T | T | F | T T | F | F | F | F F | T | T | T | T F | F | T | T | T

The columns for p → q and ¬p ∨ q match in every row, confirming the equivalence.

Note

Using Equivalences in Proofs

Logical equivalences are the primary tool for simplifying proof steps, optimizing Boolean circuits, and rewriting SQL queries. Memorize the key laws - they appear constantly throughout discrete math and computer science.