/Users/billy/gits/moc-2021/tutes/week04.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Tutorial Week 4
16–20 August 2021
Content: Translation to and from predicate logic, quantifier order.
Reminder
Assessed Worksheet 1 is due at the end of this week (22nd of August).
The exercises
T4.1 Express the following statements in predicate logic, using the one-place predicatesD(x),M(x),
where D(x) means “x is a duck”, and M(x) means “x is muddy”. Use the constant a as a
name for Jemima.
(i) Jemima is a duck
(ii) If x is a duck then it’s muddy
(iii) x is a muddy duck
(iv) Every duck is muddy
(v) There is a muddy duck
(vi) Everything is a muddy duck
T4.2 Let’s add a new two-place predicate L(x, y), which means “x lays y”, and a one-place predicate
E(z) which means “z is an egg”. Translate the following formulas into predicate logic.
(i) x lays an egg
(ii) Jemima is muddy and lays an egg
(iii) Everything lays an egg
(iv) Every duck lays an egg
(v) Every muddy duck lays an egg
(vi) There is a duck who lays every egg
T4.3 Translate the following predicate logic formulas to natural language, by interpreting L(x, y)
as “x loves y”. It may help to translate the inner formula first. For example, inside the first
formula, ∃y L(x, y) says “x loves somebody”.
(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))
T4.4 What is the effect of quantifier order on a formula? Use your understanding of the formulas in
the last question to explain which ones are logical consequences of another. Are any logically
equivalent? You do not need to compare every single pair of formulas.