The University of Melbourne
School of Computing and Information Systems COMP30026 Models of Computation
Sample Answers to Tutorial Exercises, Week 5
35. In each case below we use two interpretations over the same domain. That is just a
coincidence—we could have chosen differently.
(a) Let the domain be very simple, say {0}. Interpreting P as ‘=’ makes ∀x∀y(P(x,y))
true. Interpreting P as ‘≠ ’ makes ∀x∀y(P (x, y)) false.
(b) Let the domain be the set of natural numbers, N. Interpreting P as ‘=’ makes this true.
Interpreting P as ‘<’ makes it false.
(c) The same interpretation will work here.
36. Let I be an interpretation that satisfies ∀x(P(x)). If the domain of I is D then the relation that P is assigned to is the full relation, that is, the one that holds for every d ∈ D. Since D
is assumed to be non-empty, there is some d ∈ D for which P holds, so I satisfies ∃y(P (y)). The converse does not hold. Let I be the interpretation with domain Z (the set of integers),
and let P stand for the relation “is zero”. Then I satisfies ∃y(P(y)) but not ∀x(P(x)). nm
37. We can use the rules of passage for the quantifiers. First note that the sub-formula P (x) ⇒ ∀y∀z(Q(y, z))
has no free occurrence of y or z. Hence we can simply drop the quantifiers ∀y∃z that we find
in front of that sub-formula, which leaves us with
∀xP(x)⇒∀y∀z(Q(y,z)). VxGPHDVVyvzco.ly
Since the right-hand side of the arrow has no free occurrence of x, we can push the remaining universal quantifier in, which yields ∃x(P (x)) ⇒ ∀y∀z(Q(y, z)). This is of the required form. If you wonder about the universal quantifier turning into an existential quantifier, complete this exercise by filling in the details (start by rewriting the implication to a disjunction).
38. It is easy to see that ¬∀x∃y (¬P (x) ∧ P (y)) is valid. For example, first push negation in, to get ∃x∀y (P (x) ∨ ¬P (y)). Both quantifiers can be pushed in, since there is no y in the left conjunct. So this formula is equivalent: ∃x (P (x)) ∨ ∀y (¬P (y)). This is clearly valid. It is also straight-forward to turn into clausal form; we get just one clause: P (a) ∨ ¬P (y).
39. Here is how we might capture “z is a mouse”: M(z), and here is how we can say that “x is a catwholikesmice”: C(x)∧∀y(M(y)⇒L(x,y)). Nowwewanttosaythatifbothofthose two statements are true then z does not like x, and that’s that case no matter which z and which x we are talking about:
To HE Esp C
∀x∀z M(z)∧C(x)∧∀y(M(y)⇒L(x,y))⇒¬L(z,x) Now, as a bonus exercise, turn that into clausal form!
Domain
Equation
T x G R D V V y l t dQ y z VxGPHDV VyHzCQY27
axePHD vyvzco.lyzD 7x PIX VyElQy21
Il
Es HyukE constancy 40. Let’s start by pushing negation in. The formula becomes
41. (a)
If
1I ¬Q(a, f (y)) ∨ ¬P (y) ∨ Q(g(y), a)
The pair of terms (h(f (x), g(y, f (x)), y), h(f (u), g(v, v), u)) is not unifiable. Applying rule 1 (decomposition) to {h(f (x), g(y, f (x)), y) = h(f (u), g(v, v), u)}, we get
f ( x ) = f ( u ) g(y, f (x)) = g(v, v) y=u
Applying rule 1 (decomposition) again, to each of the first two equations, yields x = u
y = v f(x) = v
y = u Applying rule 6 (substitution) with the first equation, we get
x = u y = v
f(u) = v y = u
Applying rule 4 (reorientation) to the third equation, followed by rule 6 to the result yields
x = u y = f ( u )
v = f(u) y = u
Applying rule 6 (substitution) with the last equation yields
x = u u = f ( u )
v = f(u) y = u
∃x ∀y ∃z (¬Q(x,z)∨¬P(y))∨∃u Q(u,x)
Now we can Skolemize and remove universal quantifiers. The result is a single clause:
Now the occur check applied to the second equation yields failure.
(b) The pair of terms (h(f (g(x, y)), y, g(y, y)), h(f (u), g(a, v), u)) is unifiable.
Applying rule 1 (decomposition) to {h(f (g(x, y)), y, g(y, y)) = h(f (u), g(a, v), u)}, we get
f(g(x,y)) = f(u) y = g(a,v)
gay
g(y,y)=u gexyglyy
2y u
xy
gca v y cy y
U
and a second application yields
g ( x , y ) = u y = g(a,v)
g(y,y) = u
Applying rule 4 (reorientation) to the first and the third equation, we have
u = y = u =
Applying rule 6 (to the first equation) we
u y g(x,y)
which, after an application of rule 1 gives
u =
y =
g ( x , y ) g(a,v) g(y,y)
then get
= g ( x , y ) = g(a,v)
= g(y,y)
g ( x , y ) g(a,v)
x=y
y = y
The last equation is dropped, by rule 3, and then rule 6 applied to the third equation
gives
u = g ( y , y ) y = g(a, v) x=y
Finally, rule 6 applied to the second equation gives
u = g(g(a, v), g(a, v))
y = g(a,v) x = g(a,v)
He EatAsHap E
This is a normal form and {u → g(g(a, v), g(a, v)), y → g(a, v), x → g(a, v)} is the most general unifier.
(c) The pair of terms (h(g(x,x),g(y,z),g(y,f(z))),h(g(u,v),g(v,u),v)) is not unifiable. Applying rule 1 (decomposition) to {h(g(x, x), g(y, z), g(y, f (z))) = h(g(u, v), g(v, u), v)}, we get
g(x,x) = g(u,v) g(y, z) = g(v, u)
g(y,f(z)) = v
Applying rule 1 (decomposition) again, to each of the first two equations, yields
x=u
xu x=v
z
y=v
z=u g(y,f(z)) = v
y
vlY
gu.fi
3
Applying rule 4 (reorientation) to the last equation, followed by rule 6 applied to v yields
x = u
x = g(y,f(z))
y = g(y,f(z))FfIEFLtuff z = u
v = g(y,f(z))
Now the occur check (rule 5) applied to the third equation yields failure.
(d) The pair of terms (h(v, g(v), f (u, a)), h(g(x), y, x)) is unifiable. Applying rule 1 (decom- position) to {h(v, g(v), f (u, a)) = h(g(x), y, x)}, we get
v = g ( x ) g(v) = y f(u,a))=x
Reorienting the last two equations:
v=g(x) y = g(v)
x = f(u,a))
Now replacing x (rule 6):
v = g(f(u,a))
Finally replacing v (rule 6):
y = g(v) x=f(u,a))
v = g(f(u,a)) Hap 3 y = g(g(f(u,a)))
x = f(u,a))
we have a normal form and {v → g(f(u,a)),x → f(u,a),y → g(g(f(u,a)))} is the most
general unifier.
(e) The pair of terms (h(f (x, x), y, y, x), h(v, v, f (a, b), a)) is not unifiable. Applying rule 1
(decomposition) to {h(f (x, x), y, y, x) = h(v, v, f (a, b), a)}, we get f ( x , x ) = v
y=v y = f(a,b)
x=a Reorienting the first equation yields
v = f ( x , x ) y = v
y = f(a,b) x = a
Now applying rule 6 to x and then to v, we get
v = f(a,a) y = f(a,a)
y = f(a,b) x = a
4
Now apply rule 6 to, say, the second equation and get
v = f(a,a) y = f(a,a)
f(a,a) = f(a,b) x=a
Decomposition (rule 1) then yields
v = f(a,a)
a = a y = f(a,a)
a=b
x = a
Now the second-last equation gives match failure (rule 2 applies), and so the original
pair of terms were not unifiable.
5