tutorial8.dvi
COMP9414: Artificial Intelligence
Tutorial 8: First-Order Logic
1. Translate the following first-order sentences into English.
(i) ∀x (bird(x) → flies(x))
(ii) ∀x∃y (person(x) → mother(y, x))
(iii) ∃x∀y (person(x) ∧mother(x, y))
Where:
bird(x) means “x is a bird”
flies(x) means “x flies”
person(x) means “x is a person”
mother(x, y) means “x is the mother of y”
2. Convert the following English sentences into sentences of first-order logic.
(i) All cats are mammals.
(ii) No cat is a reptile.
(iii) All computer scientists like some operating system.
Use meaningful predicate names or state the scheme of abbreviation.
3. Convert the following first-order sentences into conjunctive normal form.
(i) ∀x (bird(x) → flies(x))
(ii) ∃x∀y ∀z (person(x) ∧ ((likes(x, y) ∧ y 6= z) → ¬likes(x, z)))
4. Determine whether the following are valid inferences in first-order logic using resolution.
(i) ∀x (P (x) → Q(x)) ⊢ ∀y (¬Q(y) → ¬P (y))
(ii) ∀x (P (x) → Q(x)) ⊢ ∀x (¬Q(x) → ¬P (x))
(iii) ∀x (P (x) → Q(x)), P (a) ⊢ Q(a)
(iv) ∀x (P (x) → Q(x)), ∃xP (x) ⊢ ∃xQ(x)
(v) ∀x (P (x) → Q(x)), ∀x (Q(x) → R(x)) ⊢ ∀x (P (x) → R(x))
Check your answers using the Python program tableau fol prover.py.
5. Consider the following three sentences
(A) There is a computer scientist who likes every operating system.
(B) Linux is an operating system.
(C) Someone likes Linux.
Now investigate the relationship among these three sentences.
(i) Write formulae A, B and C in first-order logic expressing each of the facts.
(ii) Write the clausal forms of A, B and ¬C.
(iii) Derive the empty clause from the corresponding set of clauses using resolution.
(iv) Is there an SLD resolution of the empty clause? Why or why not?
(v) Explain what entailment relation this derivation shows among the three sentences.