COMP 10070: Transformational Proofs - Logical Laws

Propositional Logic Fundamentals

• Logical Equivalence: Two formulae are said to be logically equivalent ($p \equiv q$) if and only if their equivalence is a tautology (identical in meaning), allowing one to replace the other without changing the meaning.

• Logical Implication: A formula $p$ logically implies a formula $q$ ($p \Rightarrow q$) if and only if their implication ($p \Rightarrow q$) is a tautology.

Key Logical Laws

• 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)$

• De Morgan's Laws:

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

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

• Law of Negation (Involution): $\neg(\neg p) \equiv p$

• Complement Laws:

  • Law of Excluded Middle: $p \lor \neg p \equiv \text{true}$

  • Law of Contradiction: $p \land \neg p \equiv \text{false}$

• Implication and Equivalence Laws:

  • Law of Implication: $p \Rightarrow q \equiv \neg p \lor q$

  • Contrapositive Law: $p \Rightarrow q \equiv \neg q \Rightarrow \neg p$

  • Law of Equivalence: $(p \Leftrightarrow q) \equiv (p \Rightarrow q) \land (q \Rightarrow p)$

• Idempotence Laws:

  • $p \lor p \equiv p$

  • $p \land p \equiv p$

• Laws of Simplification (Identity Laws):

  • $p \land \text{true} \equiv p$

  • $p \lor \text{true} \equiv \text{true}$

  • $p \land \text{false} \equiv \text{false}$

  • $p \lor \text{false} \equiv p$

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

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

Rules for Transformational Proofs

• Rule of Substitution: A logically equivalent formula can always replace a subformula within a larger formula without changing its meaning.

• Rule of Transitivity: If $p \equiv q$ and $q \equiv r$ then $p \equiv r$.