/Users/billy/gits/moc-2021/tutes/sol05.dvi
The University of Melbourne
School of Computing and Information Systems
COMP30026 Models of Computation
Sample Answers to Tutorial Exercises, Week 5
T5.1 (i)
I(v, F (x, a)) = I(F )(I(v, x), I(v, a))
= I(F )(v(x), I(a))
= I(F )(Louise, Jemima)
= f
(ii) I(v, ∃y F (x, y)) = t because the inner formula is satisfied when y 7→ Thelma
I(vy 7→Thelma, F (x, y)) = I(F )(I(vy 7→Thelma, x), I(vy 7→Thelma, y))
= I(F )(vy 7→Thelma(x), vy 7→Thelma(y))
= I(F )(Louise,Thelma)
= t
(iii) I(v, ∀x∃y F (x, y)) = t because we have all of
• I(vx 7→Jemima, ∃y F (x, y)) = t,
– since I(v[x 7→ Jemima, y 7→ Louise], F (x, y)) = I(F )(Jemima, Louise) = t
• I(vx 7→Thelma, ∃y F (x, y)) = t,
– since I(v[x 7→ Thelma, y 7→ Jemima], F (x, y)) = I(F )(Thelma, Jemima) = t
• I(vx 7→Louise, ∃y F (x, y)) = t,
– since I(v[x 7→ Louise, y 7→ Thelma], F (x, y)) = I(F )(Louise,Thelma) = t
(iv) I(v, ∀y F (b, y)) = f because the inner formula is not true when y 7→ Louise
I(vy 7→Louise, F (b, y)) = I(F )(I(vy 7→Louise, b), I(vy 7→Louise, y))
= I(F )(I(b), vy 7→Louise(y))
= I(F )(Thelma, Louise)
= f
(v) I(v, ∃x(∀y F (x, y))) = f because all of the possible mappings of x fail the inner formula
• I(vx 7→Jemima, ∀y F (x, y)) = f ,
– since I(v[x 7→ Jemima, y 7→ Jemima], F (x, y)) = I(F )(Jemima, Jemima) = f
• I(vx 7→Thelma, ∀y F (x, y)) = f ,
– since I(v[x 7→ Thelma, y 7→ Louise], F (x, y)) = I(F )(Thelma, Louise) = f
• I(vx 7→Louise, ∀y F (x, y)) = f ,
– since I(v[x 7→ Louise, y 7→ Jemima], F (x, y)) = I(F )(Louise, Jemima) = f
T5.2 (i) No. I 2 P (s(a), a, s(s(a))), because I(σ, P (s(a), a, s(s(a)))) = I(P )(1, 0, 2) = f , since
this asserts that 1 + 0 = 2. The choice of σ does not affect the outcome, so any choice
is sufficient to show this formula is false in this interpretation.
(ii) Yes. I � ∃xP (s(s(a)), s(a), s(x)), because for any valuation σ, I(σx 7→2, P (s(s(a)), s(a), s(x))) =
I(P )(2, 1, 3) = t, since 2 + 1 = 3. So I(σ, ∃x P (s(s(a)), s(a), s(x))) = t
(iii) No. I 2 P (s(s(a)), s(a), s(x)), because if we choose a valuation σ such that σ(x) = a,
then I(σ, P (s(s(a)), s(a), s(x))) = I(P )(2, 1, 1) = f , since it asserts that 2+1 = 1. So it
is not the case that the formula is true in the interpretation with any valuation, since
we provided one which makes it false.
(iv) Yes. I � ∀x∀y∀z(P (x, y, z) ⇒ P (y, x, z)), since this asserts that if x + y = z then
y + x = z, which is true for all triples of numbers, x, y, z ∈ N.
(v) No. I 2 ∀x(∃yL(s(y), x)), because if I(σx 7→0, ∃yL(s(y), x)) = f , since y + 1 6≤ 0 for any
number y ∈ N.
(vi) Yes. I � L(x, s(x)), since for any valuation σ, I(σ, L(x, s(x))) = I(L)(σ(x), I(s)(σ(x))) =
t, because this asserts that σ(x) ≤ σ(x) + 1, which is true regardless of what number
σ(x) ∈ N is.
T5.3 (i) I � ¬∀x∃y F (x, y) if we make the modification I(F )(Jemima, Louise) := f
(ii) I � M(a) ∧ M(b) ∧ M(c) ∧ ¬∀x M(x) if we make the modification I(b) := Jemima.
Technically, we also need to ensure that all the other unmentioned constants are not
assigned to Thelma by the interpretation.
(iii) I � ∀x F (x, g(x)) if we define I(g) : ID → ID such that I(g)(Jemima) := Louise,
I(g)(Thelma) := Thelma, I(g)(Louise) := Thelma. This function always picks out an
object that the input object “follows”.
(iv) I � M(x) if we make the modification I(M)(Thelma) := t. Then any valuation must
send x to a muddy object, since they all are.
2