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