Lecture on Tautologies, Contradictions, and Logical Equivalences

Introduction

• Focus on tautologies, contradictions, and logical equivalences.
• Practice through truth tables.

Tautologies

• Definition: Comes from Greek, meaning "already said". In logic, it refers to a statement that is always true.

• Example: Proposition p and p or not p.

  • Truth table:
    • p: True, False
    • not p: False, True
    • p or not p: True, True
  • Conclusion: Last column is all true, hence a tautology.

• Another Example: P and (P implies Q) implies Q.

  • Explanation: Known in logic as Modus Ponens.
  • Truth table:
    • P: True, True, False, False
    • Q: True, False, True, False
    • P implies Q: True, False, True, True
    • P and (P implies Q): True, False, False, False
    • Result: True, True, True, True
  • Conclusion: Last column is all true, hence a tautology.

• Law of the Excluded Middle: P is equivalent to not not P.

Contradictions

• Definition: Statements that are always false.
• Example: P and not P.
  • Truth table:
    • P: True, False
    • not P: False, True
    • P and not P: False, False
  • Conclusion: Last column is all false, hence a contradiction.

Logical Equivalences

• Definition: Two propositions are logically equivalent if they are true at the same time.
• Example: not (P and Q) and not P or not Q.
  • Based on De Morgan's Law.
  • Truth table:
    • P: True, True, False, False
    • Q: True, False, True, False
    • not (P and Q): False, True, True, True
    • not P or not Q: False, True, True, True
  • Conclusion: Both results are the same, hence logically equivalent.

Conclusion

• Next session will cover the laws of propositional logic, focusing on logical equivalences.
• These correspond to the table of Boolean algebra.