Equivalences

Topics

Tautologies, contradictions, and contingencies

• Tautology is a proposition which is always true
• Contradiction is a proposition which is always false
• Contingency is neither a tautology nor a contradiction

Logical equivalence

• Two compound propositions p and q are logically equivalent if p↔q is a tautology.
• We write this as p⇔q or as p≡q where p and q are compound propositions.
• (laws posted below except Idempotent Laws: p∨ p ≡ p, p^p≡ p)

Normal forms (skipped for now)

Propositional satisfiability.

• A compound proposition is satisfiable if there is an assignment of truth values to its variables that make it true. When no such assignments exist, the compound proposition is unsatisfiable.
• A compound proposition is unsatisfiable if and only if its negation is a tautology.