/Users/billy/gits/moc-2021/problem-sets/solps05.dvi
The University of Melbourne
School of Computing and Information Systems
COMP30026 Models of Computation
Sample Answers to Tutorial Exercises, Week 4
P5.1 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 ‘ 6=’ 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. P5.2 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)). P5.3 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 ∀x ( P (x)⇒∀y∀z(Q(y, z)) ) . 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). P5.4 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). P5.5 Let’s start by pushing negation in. The formula becomes ∃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: ¬Q(a, f(y)) ∨ ¬P (y) ∨Q(g(y), a)