Lecture 8

Substitution theorem

Recall the statement in the optional part of Homework 1.

Review of

  • semantics of first-order logic
  • definition of capture-avoiding substitution and the set of free variables
  • structural induction on algebraic data types and comparison to induction on natural numbers
  • proof of substitution theorem using structural induction
  • the case of a quantifier as a justification for the definition of capture-avoiding substitution

Quantifier elimination from Homework 2

  • transformation to conjunctions of literals
  • the idea of Fourier-Motzkin elimination

Resolution through an example

(ALL x. EX y. R(x,y))  &
(ALL x y z. R(x,y) --> R(x, plus(y,z)))  &
(Ev(x) | Ev(plus(x,1))) -->
  (ALL x. EX y. R(x,y) & E(y))

The intuitive infinite model. Example finite model where this holds.

Review of transformation to clauses, unification, resolution rule in this example.

The meaning of completeness and soundness of resolution.

Homework 3 review

Galois connection. Characterization of injective and surjective functions. Two equivalent definitions of Galois connection.