LE/EECS 4401/5326 3.0 Artificial Intelligence Dept. of Electrical Eng. & Computer Sci.
GS/EECS 5326 3.0 Topics in Artificial Intelligence York University Winter 2021
Assignment 1
Total marks: 70.
Out: February 4
Due: February 22 at 10:00am
Note: Your report for this assignment should be the result of your own individual work.
Take care to avoid plagiarism (“copying”). You may discuss the problems with other stu-
dents, but do not take written notes during these discussions, and do not share your written
solutions.
1. [30 points] Consider the following piece of knowledge:
Tony, Mike, and John belong to the Alpine Club. Every member of the
Alpine Club who is not a skier is a mountain climber. Mountain climbers
do not like rain, and anyone who does not like snow is not a skier. Mike
dislikes whatever Tony likes and likes whatever Tony dislikes. Tony likes
rain and snow.
a) Write some sentences in first-order logic that represent the knowledge given
above. Use the notation in Brachman and Levesque’s book for this question.
Also provide a glossary where you indicate the intended meaning of your pred-
icate, function, and constant symbols in English.
b) Prove that the given sentences entail that there is a member of the Alpine Clib
who is a mountain climber but not a skier.
c) Suppose that we had been told that Mike likes whatever Tony dislikes, but we had
not been told that Mike dislikes whatever Tony likes. Prove that the resulting
set of sentences no longer entail that there is a member of the Alpine Club who
is a mountain climber but not a skier.
For this question, your proofs should use the definition of entailment and refer to
interpretations; do not use resolution.
2. [20 points]
a) Show that the following sentence is valid in the description logic of Brachman
and Levesque Chapter 9:
[AND [ALL r1 [AND d1 d2 d3]] [FILLS r1 c1]]
v [AND [ALL r1 d1] [EXISTS 1 r1]]
1
b) Show that the following sentence is not valid in the description logic of Brachman
and Levesque Chapter 9:
[AND [ALL r1 [AND d1 d2 d3]] [FILLS r1 c1] [FILLS r1 c2]]
v [AND [ALL r1 d1] [EXISTS 2 r1]]
For this question, your proofs should use the definition of validity and refer to inter-
pretations. Use the notation in Brachman and Levesque Chapter 9.
3. [20 points] Use the tableau method for description logic ALC described in Baader
and Sattler’s paper to check whether the following concepts are satisfiable/consistent.
Show the steps and rules that are used. If the concept is satisfiable give the model
(satisfying interpretation) obtained by the method.
a) (∀R.∀R.∀R.∃R.¬D) u (∀R.∀R.∃R.C)
u (∀R.∃R.B) u (∃R.A) u ∀R.∀R.∀R.∀R.D)
b) (∃R.A) u (∀R.∃R.(∃R.A unionsq ∃R.¬B))
u (∀R.∀R.∃R.C) u (∀R.∀R.(∀R.¬A unionsq ∀R.B unionsq ∀R.¬C))
Bonus [5 points] This is a follow up to question 1. Use resolution with answer extraction
to find the member of the Alpine club who is a mountain climber but not a skier. Show
how the sentences obtained in question 1a are converted to clausal form and the resolution
derivation. For each resolution step, state which two clauses are being resolved and the
substitution used.
2

欢迎咨询51作业君