EECS 3401 3.0 Intro to AI and LP Fall 2018
Dept. of Electrical Eng. & Computer Sci. York University
Assignment 1
Total marks: 75.
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)shouldsucceedwithL = [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
Out: September 26
Due: October 15 at 23:59
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.
- [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.
- [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