EECS 3401 3.0 Intro to AI and LP Dept. of Electrical Eng. & Computer Sci.
Fall 2018 York University
Assignment 1
Total marks: 75.
Out: September 26
Due: October 15 at 23:59
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. [25 points] Write and test a Prolog program q1.pl that deals with family relations.
Assume that the predicate parent(X,Y), meaning that X is a parent of Y has al-
ready been defined (and that the definition is loaded separately).
Your program’s job is to define the following predicates:
• ancestor(X,Y), meaning that X is an ancestor of Y, i.e. either X is a parent
of Y or X is an ancestor of someone who is a parent of Y;
• common ancestor(X,Y,Z), meaning that X is a common ancestor of Y
and Z, i.e. X is an ancestor of both Y and Z;
• closest common ancestor(X,Y,Z), meaning that X is a closest com-
mon ancestor of Y and Z, i.e. X is a common ancestor of Y and Z and no child
of X is a common ancestor of Y and Z;
• ancestorList(X,Y,L), which holds iff X is an ancestor of Y and L is
a list of the decendants of X (i.e., people whose ancestor is X) that are an-
cestors of Y ordered from the closest to the farthest from X; e.g. if john is
a parent of paul who is a parent of henry who is a parent of helen, then
ancestorList(john,helen,L) should succeed with L = [paul,henry]
being returned;
• descendantTree(X,L), which holds iff L is a list structure representing
the tree of all descendants of X; each node in the tree of descendants should be
represented by a list whose first element is the node label and the remaining el-
ements are the representations of its children if any; e.g. if john’s children are
paul and mary, paul’s children are henry and june, henry’s only child
is helen, mary’s only child is adam, and neither adam nor june nor helen
have any children, then descendantTree(john,L) should succeed with
1
L =
[john,
[paul,
[henry,
[helen]
],
[june]
],
[mary,
[adam]
]
]
being returned (indentations and line breaks have been added here for readabil-
ity, but your program should not do this).
You may define some auxiliary relations if that helps in defining the ones above. Test
your program thoroughly before submitting it. Document your code appropriately.
Do not include any parent(X,Y) facts in your file.
2. [20 points] Write and test a Prolog program q2.pl that solves the following puzzle:
The police are trying to track down the gang of three kids who have been
stealing pumpkins. So far, they have established the following facts: the
kids’ first names are Angela, Mary, and David; one is 5, one is 7, and one
is 8; one has the last name Diamond, and the one with the last name Grant
is 3 years older than the one with the last name Leung. You can assume
Angela and Mary are female and David is male.
Use the technique shown in the zebra example discussed in class (the code is available
on the course web page) to find missing information on the gang: each child’s age,
gender, first name and last name, consistent with the data above. (Encode the above
data as is and do not add additional facts.)
Use your Prolog code to show whether or not the computed information uniquely
identifies the culprits; submit these test results in the file q2tests.txt, together
with the program file. Document your code appropriately.
3. [30 points] (Adapted from Genesereth and Nilsson (1987)) This non-programming
question concerns the following situation:
Victor has been murdered, and Arthur, Bertram, and Carleton are the only
suspects (meaning exactly one of them is the murderer). Arthur says
2
that Bertram was the victim’s friend, but that Carleton hated the victim.
Bertram says that he was out of town the day of the murder and besides, he
did not even know the guy. Carleton says that he saw Arthur and Bertram
with the victim just before the murder. You may assume that everyone,
except possibly the murderer, is telling the truth.
a) Write sentences in first-order logic that represent this knowledge. Also provide a
glossary where you indicate the intended meaning of your predicate, function,
and constant symbols in English.
b) Convert the sentences into clausal form and give the resulting set of clauses.
c) Use resolution with answer extraction to find the murderer. State how you repre-
sent the query in first-order logic and what clause (with an answer predicate) is
added to the theory. Show the complete resolution derivation (in sequence or
tree form), clearly indicating which literals/clauses are resolved and the unifier
used.
d) Suppose that we can no longer assume that there was only a single murderer.
What sentences must you remove from the theory? Show that the modified
theory no longer entails that the answer you obtained in c) is the murderer. Do
this by specifying an interpretation where the answer in c) is not the murderer
and showing that it satisfies all the axioms of the theory.
Submit your answer to this question as PDF file q3.pdf.
To hand in your report for this assignment, put all the required files in a directory a1answers
and submit it electronically by the deadline. To submit electronically, use the following
Prism lab command:
submit 3401 a1 a1answers
Your Prolog code should work correctly on Prism.
3