Lecture 9.6: The Logic of Relations - Proofs

Introduction

• In predicate logic, inference rules remain unchanged with the inclusion of relations.
• Some restrictions become important in new proof contexts involving relations.

Applying Quantifiers

• Multiple Quantifiers:
  • Remove quantifiers one at a time, from left to right using UI (Universal Instantiation) or EI (Existential Instantiation).
  • Follow the "Mixed Quantifier Mantra": Apply EI before UI.
  • Example:
    • Premise: ((x)(y)(Hxy \rightarrow Ia))
    • Example incorrect application shown in-class.

Implicational Rules

• Generalization and Instantiation (EG, UG, EI, UI)

  • These are implicational, not equivalence rules.
  • For UI and EI, apply to quantifiers with scope over entire statement.
  • Example of incorrect proof provided with correction shown in class.

• EG and UG: Apply rules to the entire statement in proof.

  • Example given with incorrect and corrected proof.

Uniform Substitution

• When using UI and EI, constants must replace variables uniformly.
  • Example of correct and incorrect substitutions provided.

Choosing Constants

• When applying EI, choose a constant not previously used in the proof.
  • Incorrect application example demonstrates a logical error akin to absurd conclusions (e.g., someone being their own mother).

Universal Generalization Restrictions

• UG can infer generalization ((\forall)) from individual case ((\exists)), if:
  • The constant does not occur in the formula, premise, line from EI, or undischarged assumption.
  • Example of violation and its intuitive incorrectness provided.
  • Example of an appropriate generalization in a proof.

Final Example Argument

• Logical argument: "Kim is a genius. So anyone who admires Kim admires a genius."
  • This argument's validity is demonstrated in a logical proof format.

Conclusion

• Understanding these rules and restrictions is crucial for correctly forming logical proofs involving relations and quantifiers.