CS计算机代考程序代写 /Users/billy/gits/moc-2021/tutes/sol04.dvi

/Users/billy/gits/moc-2021/tutes/sol04.dvi

The University of Melbourne

School of Computing and Information Systems

COMP30026 Models of Computation

Sample Answers to Tutorial Exercises, Week 4

T4.1 (i) D(a)

(ii) D(x)⇒M(x)

(iii) D(x) ∧M(x)

(iv) ∀x(D(x)⇒M(x))

(v) ∃x(M(x) ∧D(x))

(vi) ∀x(M(x) ∧D(x))

T4.2 (i) ∃y(L(x, y) ∧ E(y))

(ii) M(a) ∧ ∃y(L(a, y) ∧ E(y))

(iii) ∀x(∃y(L(x, y) ∧ E(y)))

(iv) ∀x(D(x)⇒∃y(L(x, y) ∧ E(y)))

(v) ∀x((M(x)∧D(x))⇒∃y(L(x, y)∧E(y)))

(vi) ∃x(D(x) ∧ ∀y(E(y)⇒ L(x, y)))

T4.3 (i) Everybody loves somebody

(ii) Somebody is loved by everybody

(iii) Everybody is loved by someone

(iv) Somebody loves everybody

(v) Everybody loves everybody

(vi) Everybody is loved by everybody

T4.4 We will list all of the logical consequences for each formula, and omit all of the pairs where
there is no logical consequence relationship.

(i) ∀x(∃y L(x, y))

(i) · · · � ∀x(∃y L(x, y))

(ii) ∃y(∀x L(x, y))

(i) · · · � ∀x(∃y L(x, y))

(ii) · · · � ∃y(∀x L(x, y))

(iii) ∀x(∃y L(y, x))

(iii) · · · � ∀x(∃y L(y, x))

(iv) ∃y(∀x L(y, x))

(iii) · · · � ∀x(∃y L(y, x))

(iv) · · · � ∃y(∀x L(y, x))

(v) ∀x(∀y L(x, y))

(i) · · · � ∀x(∃y L(x, y))

(ii) · · · � ∃y(∀x L(x, y))

(iii) · · · � ∀x(∃y L(y, x))

(iv) · · · � ∃y(∀x L(y, x))

(v) · · · � ∀x(∀y L(x, y))

(vi) · · · � ∀y(∀x L(x, y))

(vi) ∀y(∀x L(x, y))

(i) · · · � ∀x(∃y L(x, y))

(ii) · · · � ∃y(∀x L(x, y))

(iii) · · · � ∀x(∃y L(y, x))

(iv) · · · � ∃y(∀x L(y, x))

(v) · · · � ∀x(∀y L(x, y))

(vi) · · · � ∀y(∀x L(x, y))