CS计算机代考程序代写 /Users/billy/gits/moc-2021/problem-sets/ps05.dvi

/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.