Session 4: Predicate Logic — Quantifiers, Binding, Scope

Overview

Predicate logic: quantifiers as inference rules, how binders scope, and what goes wrong when substitution captures a variable.

Lecturer

Ayman Kaçan

Session Information

Core Concepts

  • Predicates, domains, ∀ and ∃; ∀I/∀E and ∃I/∃E as inference rules
  • Free and bound variables; the scope of a binder
  • α-renaming: why ∀x. P(x) and ∀y. P(y) are the same statement
  • Variable capture and failed substitution
  • Nested quantifiers and order sensitivity (∀ε∃δ vs ∃δ∀ε)
  • Negating quantified statements: ¬∀ ≡ ∃¬
  • Translating English into logic, and the ambiguity of English

Slides

Session 4 Slides: Download PDF

Readings

Exercises & Extra Steps

  • Practice (not collected): negate and simplify ∀x ∃y (P(x,y) → ∀z Q(y,z))
  • Practice (not collected): perform a substitution in which naive replacement captures a variable, then do it correctly

Questions? Reach out on the course WhatsApp!