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
Midterm Test — March 2, 2021
Duration: 90 minutes
Total marks: 70
Instructions:
• The test is to be completed individually; you are not to discuss or share the questions
or potential answers with anyone, including other students in this course.
• You may consult the class readings, lecture notes, and textbook during the exam.
• Submit your answers as a PDF file in eClass by the end of the test period. You may
submit more than once and the last submission will be graded.
• Write your name and student number at the beginning of the document.
• Clearly indicate which question and subquestion is being answered everywhere.
• By submitting your answers in eClass, you agree to the following statement:
I attest to the fact that it is my own work that has been submitted in this
assessment, and that I have acted with integrity, abiding by the Senate
Policy on Academic Honesty and any rules the instructor has articulated
for this assessment.
1) /5
2) /5
3) /5
4) /5
5) /10
6) /20
7) /10
8) /10
Total /70
1
1. [5 points] Most description logics can be translated into first-order logic. What is the
main advantage of a description logic such as ALC over first-order logic?
2. [5 points] What does it mean when we say that resolution is not complete but is
refutation complete?
3. [5 points] Skolemizing a CNF formula does not preserve logical equivalence. For
example, if we skolemize ∃xP (x), we get P (a), which is not logically equivalent
to the original formula. Yet, skolemization works when one does resolution proofs.
Briefly explain why.
4. [5 points] Reasoning in classical logic (e.g., first-order logic) is monotonic. Explain
what this mean. Also explain why default reasoning is nonmonotonic.
5. [10 points] Translate the following English sentences into first-order logic:
(a) Every human has a parent.
(b) No salesperson likes all customers.
(c) There is a question that no student knows the answer to.
(d) All but one of the landowners are rich.
(e) A lawyer is happy if he/she belongs to all committees.
6. [20 points]
Suppose that we have the following knowledge base (KB) represented as a set of
FOL sentences about three boys, Tommy, Johnny, and Bobby:
(1) Tall(tommy) Tommy is tall.
(2) Short(johnny) Johnny is short.
(3) Likes(johnny, bobby) Johnny likes Bobby.
(4) Tall(bobby) ∨ Short(bobby) Bobby is either tall or short.
(5) ¬Tall(bobby) ∨ ¬Short(bobby) Bobby is not both tall and short.
(6) Likes(bobby, tommy) Bobby likes Tommy.
(a) Prove that the KB does not entail that Bobby is tall. That is, show that there is
an interpretation that satisfies the KB but does not satisfy this conclusion.
(b) Using the definition of entailment in terms of interpretations, prove that the KB
entails that some short boy likes some tall boy. Show how the query is expressed
in first-order logic and give a detailed proof. Do not use resolution.
2
7. [10 points] Use the tableau method for ALC described in Baader and Sattler’s pa-
per to check whether the following concept is satisfiable/consistent. Show the steps
and rules that are used. If the concept is satisfiable give the model(s) (satisfying
interpretation(s)) obtained by the method.
(∃R.¬A) u ((∀R.(∃R.¬B)) u ((∀R.(∀R.C))
u (∀R.((∀R.B) unionsq (∀R.¬C) unionsq (∀R.D)))
8. [10 points]
a) What are the extension(s) of the default logic theory 〈D,F〉, where
D = {〈 Sailor(x)⇒ BeerDrinker(x)〉} and
F = {Sailor(John), T ruckDriver(Bob)}?
b) What are the extension(s) of the default logic theory 〈D,F〉, where
D = {〈 Sailor(x)⇒ BeerDrinker(x)〉} and
F = {Sailor(John), (Sailor(Bob) ∨ Sailor(Paul))}?
c) What are the extension(s) of the default theory 〈D,F〉, where
D = {〈 Sailor(x)⇒ BeerDrinker(x)〉, 〈Religious(x)⇒ ¬BeerDrinker(x)〉}
and F = {Sailor(John), Religious(John), Sailor(Bob)}?
3

欢迎咨询51作业君