Tautologies, Contradictions, and Contingencies

• A tautology is always true
  • $p \lor \neg p$
  • $q \implies (p \lor q)$
• A contradiction is always false
• A contingency is neither a tautology or a contradiction (such as $p$)

Logical Equivalence

• Two propositions, $p$ and $q$, are logically equivalent if they have the same truth table
  • Alternatively, if $p \iff q$ is a tautology
  • Labeled $p \equiv q$

De Morgan’s Law

• Distribute the negation and switch the and/or operator

Key Equivalences

Identity Laws

• $p \land T \equiv p$
• $p \lor F \equiv p$

Domination Laws

• $p \lor T \equiv T$
• $p \land F \equiv F$

Idempotent Laws

• $p \lor p \equiv p$
• $p \land p \equiv p$

Absorption Laws

• $p \land (p \lor q) \equiv p$
• $p \lor (p \land q) \equiv p$

Commutative Laws

• $p \land q \equiv q \land p$
• $p \lor q \equiv q \lor p$

Associative Laws

• $(p \land q) \land r \equiv p \land (q \land r)$
• $(p \lor q) \lor r \equiv p \lor (q \lor r)$

Distributive Laws

• $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
• $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$

Satisfiability

• A compound proposition is satisfiable if there is an arrangement of propositional variables that make its output true, and insatisfiable otherwise
  • can prove insatisfiable if its negation is a tautology

References

• Course slides §2.1: Logic Applications
• Course slides §3.2: Proving New Equivalences, Satisfibility