Version without JavaScript, read-only: workshops, quizzes and running code are not available here. Full version · Catalogue · Sign in

Exercise sheet 7

First-order logic: the language

Terms and formulas, free and bound variables, renaming and capture-avoiding substitution. Chapter 7.

Solution
  1. Term.
  2. Atomic formula.
  3. Neither: $P$ expects a term, and $R(x, y)$ is a formula.
  4. Formula, closed.
  5. Neither: $f$ expects a term.
  6. Neither: only variables can be quantified, and $a$ is a constant.
Solution
  1. An occurrence of $x$ is free if it is not in the scope of any quantifier over $x$. A variable is free in a formula if it has at least one free occurrence in it.
  2. In $R(y, x)$, $y$ and $x$ are free: they are outside the scope of $\forall x$, and the $\exists y$ only covers $R(x, y)$. Free variables: $\{x, y\}$.
  3. Only $z$ is free; the $x$ of $R(x, z)$ is bound by the inner $\forall x$, the nearest one. Free variables: $\{z\}$.
  4. None: the formula is closed.
Solution
  1. $x$ is free: its occurrences in $R(x, z)$ and $S(x)$ are outside the scope of $\forall x$. It is also bound in the first part. $y$ is not free: its only occurrence is bound by $\exists y$.
  2. We rename the bound $x$: $(\forall u\, \exists y\, R(f(u), f(y))) \land ((\forall z\, R(x, z)) \to S(x))$.
  3. Only the free occurrences are replaced: $(\forall x\, \exists y\, R(f(x), f(y))) \land ((\forall z\, R(t, z)) \to S(t))$. $t$ must not contain $z$, otherwise it would be captured by $\forall z$. If $t = g(z)$ for instance, we first rename $z$ to $w$: $(\forall x\, \exists y\, R(f(x), f(y))) \land ((\forall w\, R(g(z), w)) \to S(g(z)))$.
Solution
  1. $y$ occurs in $f(y)$ and would be captured. We rename: $\exists z\, R(x, z)$, then substitute: $\exists z\, R(f(y), z)$.
  2. $\exists y\, (x < y)$ is true for every $x$. Naive substitution gives $\exists y\, (f(y) < y)$: with $f$ interpreted as “plus one”, it says that some integer is greater than its successor, which is false. The correct substitution, $\exists z\, (f(y) < z)$, is true for every $y$, just as the original formula was for every $x$.