/Users/billy/gits/moc-2021/problem-sets/ps05.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Problem Set 5
23–27 August 2021
Content: interpretations in predicate logic, clausal form
P5.1 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))
P5.2 Show that ∀x(P (x)) |= ∃y(P (y)) holds, by supposing that an interpretation I makes ∀x(P (x))
true (so I � ∀x(P (x))), and explaining why it must make ∃y(P (y)) true. Does ∃x(P (x)) |=
∀y(P (y)) also hold? Recall that part of our definition of interpretation is that the domain is
non-empty.
P5.3 Turn the closed formula ∀x∀y∃z
(
P (x) ⇒ ∀y∀z(Q(y, z))
)
into a simpler, equivalent formula
of the form ϕ⇒ ψ.
P5.4 Determine whether ¬∀x∃y (¬P (x)∧P (y)) is valid and/or satisfiable. Then convert the formula
to clausal form.
P5.5 Turn the closed formula ¬∀x ∃y
[
∀z
(
Q(x, z) ∧ P (y)
)
∧ ∀u
(
¬Q(u, x)
)]
into clausal form.