Plan
School of Computing and Information Systems COMP30026 Models of Computation Tutorial Week 5
2–4 September 2020
This week’s exercises are not too time consuming, so you may find time to catch up on any questions you had to skip earlier, or alternatively, spend more time discussing the various logic concepts.
The exercises
35. For each of the following predicate logic formulas, give an interpretation that makes the formula true, and one that makes it false:
(a) ∀x∀y(P(x,y))
(b) ∀x∃y(P(x,y)∧P(y,x))
(c) (∀x∃yP(x,y))∧(∀x∃yP(y,x))
36. Show that ∀x(P(x)) |= ∃y(P(y)) holds. Does ∃x(P(x)) |= ∀y(P(y)) also hold? Recall that
part of our definition of interpretation is that the domain is non-empty.
37. Turn the closed formula ∀x∀y∃zP (x) ⇒ ∀y∀z(Q(y, z)) into a simpler, equivalent formula
of form φ⇒ψ.
38. Determine whether ¬∀x∃y (¬P (x)∧P (y)) is valid and/or satisfiable. Then convert the formula
to clausal form.
39. Consider the following predicates:
• C(x), which stands for “x is a cat”
• M(x), which stands for “x is a mouse” • L(x, y), which stands for “x likes y”
Express the statement “No mouse likes a cat who likes mice” as a formula in first-order predicate logic (not clausal form). Here “likes mice” means “likes every mouse”. (This is arguably an abuse of the predicate symbol L, as we are using it for two different senses of “likes”.)
40. Turn the closed formula ¬∀x ∃y ∀z Q(x, z) ∧ P (y) ∧ ∀u ¬Q(u, x) into clausal form.
41. For each of the following pairs of terms, determine whether the pair is unifiable. If it is, give
the most general unifier.
(a) (h(f(x),g(y,f(x)),y),h(f(u),g(v,v),u)) (b) (h(f(g(x,y)),y,g(y,y)),h(f(u),g(a,v),u))
(c) (h(g(x,x),g(y,z),g(y,f(z))),h(g(u,v),g(v,u),v)) (d) (h(v,g(v),f(u,a)),h(g(x),y,x))
(e) (h(f(x,x),y,y,x),h(v,v,f(a,b),a))
(Don’t forget our agreed convention: for constants we use letters from the beginning of the alphabet, here a and b, whereas for variables we use letters from the end of the alphabet.)