September 12
EECS 3401 Introduction to AI & Logic Programming
Report 1 Specification
Due: Monday, September 26, 2:15 pm Where, What and How: see Section 1.3
1 Main points
Be sure to read and follow all the guidelines from the links on reports and academic honesty from the WWW home page for the course.
You should read the course web page on reports – link Reports in the table of contents.
You should read the notes on testing – link is in the Resources page for the course. Of particular use for the Prolog predicates in this report are the notes on partition testing.
1.1 Learning objectives
• How Prolog searches for an answer
• Writing predicates in Prolog
• Using PlUnit to test predicates
1.2 The report
The report body is a single ASCII file, called report_1.pl containing all your documentation, all your Prolog predicates, and all your test cases. Follow the link Examples, exam questions and Prolog programs from the Resources page, you will find an example specification with an example report file corresponding to the specification.
After loading the file report_1.pl, the query run_tests should run all of your test predicates. It should also be possible to run the test cases for each exercise individually. You should clearly document how to run your predicates and test cases.
1.3 Electronic submission
Before the deadline, submit the following files – an automatic program will close the submission directory at 2:15pm by the clock in the Prism system.
• 3401_report_1_CoverPage.pdf – a copy of the cover page you download from the forum posting with the subject Report 1 specification on which you write your name(s) and EECS account number(s)
• report_1.pl – the report file you created (see Section 1.2)
To submit your files use the following submit web app (link File submission on the course home page).
The app requires you to login with your EECS account.
https://webapp.eecs.yorku.ca/submit/
It is strongly recommended that you periodically submit report_1.pl before the deadline to be sure that something has been submitted; computers and networks can fail.
While you can develop your programs on your personal computer, be sure your files will load and execute correctly on Prism.
September 12 3401 Report 1 Specification Page 2 of 5
2 Background
A set of sentences S = {S1, S2, …, Sp}logical entails another sentence Sq if the truth of Sq is implicit in the truth of the set S of sentences. For example, the sentence “There is a leak in the kitchen” is entailed by the following set of sentences.
1. The hall is wet.
2. The bathroom is dry.
3. The window is closed.
4. If the hall is wet and the kitchen is dry then there is a leak in the bathroom.
5. If the hall is wet and the bathroom is dry then there is a problem in the kitchen.
6. If there is no rain then there is no water from outside.
7. If the window is closed then there is no water from outside.
8. If there is a problem in the kitchen and there is no water from outside then there is a leak in the kitchen.
The following algorithm describes the computational procedure backward chaining that is used to determine whether or not a sentence is entailed by a given set of sentences.
Step 1. Step 2. Step 3. Step 4.
Given a knowledge base, KB, of sentences.
Establish the truth-value of the sentence Q.
Try to locate Q explicitly in the KB. If you can, then return true. Try to locate an untried conditional sentence of the form
if S1 and S2 and … and Sp then Q in the KB. If you cannot, then return false.
Step 5. Use backward chaining to try to establish S1, then S2, then … , then Sp. If these are all true, then return true.
Step 6. Otherwise, go to step 4 and look for another conditional.
Apply the procedure to the sentence “There is a leak in the kitchen”. The sentence is not explicitly in the KB. Sentence 8 is a conditional of the form in step 4. Try to establish that “there is problem in the kitchen” and “there is no water from outside” are both entailed by the KB.
“there is problem in the kitchen” is not explicitly in the KB but sentence 5 is of the form in step 4. Try to establish “the hall is wet” and “the bathroom is dry” are both entailed by the KB. “the hall is wet” is explicitly in the KB, hence it is true. “the bathroom is dry” is explicitly in the KB, hence it is true. As a consequence “there is a problem in the kitchen” is entailed by the KB (it is true).
“there is no water from the outside” is not explicitly in the KB but sentence 6 is a conditional of the form in step 4. Try to establish that “there is no rain” is entailed by the KB. It is not explicitly in the KB. There is no conditional in the form in step 4. Step 6 says to try another conditional, which is sentence 7. Try to establish that “the window is closed” is entailed by the KB. It is explicitly in KB, hence “the window is closed” is true. As a consequence, “there is no water from outside” is true.
Since both “there is problem in the kitchen” and “there is no water from the outside” are both entailed by the KB, they are true, therefore the statement “there is a leak in the kitchen” is entailed by the KB (is true).
September 12 3401 Report 1 Specification Page 3 of 5
3 The Exercises
For all exercises assume the input is correct. The point of the exercises is to learn to program in Prolog, not to write bulletproof systems. For all exercises do not use either cut or not.
Exercise 1
Consider the following knowledge base KB
bay is left of yonge spadina is left of st_george bathurst is left of spadina christie is left of bathurst If X is left of Y then X is west of Y
If X is left of Y and Y is west of Z then X is west of Z
If X is west of Y then Y is east of X
st_george is left of bay
1. Give an example of an atomic sentence that is not in KB but that is entailed by it.
2. Explain informally why the sentence “spadina is right of bathurst” is not entailed by KB.
3. Trace the back-chaining procedure on the following a) spadina is west of st_george
b) yonge is east of bay
c) christie is west of spadina
d) yonge is west of yonge
e) bay is west of sherborne
4. Suppose the second conditional in KB is replaced by
if X is west of Y and Y is left of Z then X is west of Z
would this change what is entailed? What happens now with the back-chained procedure on the query 3d?
5. Suppose the (incorrect) atomic sentence “yonge is left of bay” were added to KB. For what values of X would the resulting KB entail “spadina is west of X”? What happens now with the back- chaining procedure on the query 3e?
Clearly show the values of all variables at all times, including when they are renamed. For an example and style to follow, look at the trace for append in the utility slides.
Exercise 2
Define the predicate everyNth (N, List1, List2) that asserts that List2 contains the first item followed by every N’th item after the first item of List1. Use append and length. You do not need any other support predicates.
N≥1
#List2 = #List1 div N
∀j : 1 .. #List2 • List2 (j) = List(1 + (j–1)*N)
Examples:
everyNth( 3 , [1, 2], List2). List2 = [1] ;
false.
everyNth( 3 , [1, 2, [3, 4], [[5]], 6, [7, 8, [[9]]], 10] , List2).
List2 = [1, [[5]], 10] ; false.
everyNth( 3 , [1, 2, [3, 4], [[5]], 6, [7, 8, [[9]]], 10, 11] , List2).
List2 = [1, [[5]], 10] ; false.
September 12 3401 Report 1 Specification Page 4 of 5
Exercise 3
Define the predicate sumOf (Integers1, Integers2, Integers3) that asserts that Integers3 contains the sum of the integers in the corresponding position in Integers1 and Integers2. Assume the shorter list is extended with zeros to the length of the longer list.
∀j : 1..min(#Integers1, Integers2) • Integers3(j) = Integers1(j) + Integers2(j) #Integers1 < #Integers2 → ∀j : #Integers1+1 .. #Integers2 • Integers3(j) = Integers2(j) #Integers2 < #Integers1 → ∀j : #Integers2+1 .. #Integers1 • Integers3(j) = Integers1(j)
sumOf([0, 11, 22, 33, 44], [-1, -2, -3, -4], Sum). à Sum = [-1, 9, 19, 29, 44]
Exercise 4
Define the predicate removeContig (A, B) that asserts the list B is the same as the list A except that instances of a contiguous sequence of identical items are reduced to one instance. Work only at the top level.
Examples:
removeContig([a,a,b,b,b,c,c,c],[a,b,c]) àtrue. removeContig([a,a,b,b,b,c,c,c],[a,b,b,c] à false. removeContig([a,b,c,a,b,c],[a,b,c]) à false. removeContig([a,b,c,a,b,c],[a,b,c,a,b,c]) à true. removeContig([[a],[b,b],[b,b],[a,a],[a,a],[b]]
, [[a],[b,b],[a,a],[b]]) à true. removeContig([a,a,b,b,b,c,c,c],R) àR=[a,b,c];false.
Hint: the following predicate is true if the third item on a list is A, otherwise the predicate is false.
thirdIs( A , [ _ , _ , A | _] ).
Exercise 5
Define the predicate zipper([[List1, List2], Zippered)) that asserts Zippered is the result of zippering (interleaving) the elements of List1 and List2; List1 and List2 must be instantiated.
Examples:
zipper([[1,3,5,7], [2,4,6,8]], [1,2,3,4,5,6,7,8]) à true zipper([[1,3,5], [2,4,6,7,8]], [1,2,3,4,5,6,7,8]) à true zipper([[1,3,5,6,7], [2,4]], [1,2,3,4,5,6,7]) à true
Define the predicate unzipper(Zippered,[[List1, List2])) that asserts List1 and List2 are the un- zippered parts of Zippered; Zippered must be instantiated.
Examples:
unzipper([1,2,3,4,5,6,7], [[1,3,5,7], [2,4,6]) à true unzipper([1,2,3,4,5,6,7,8], [[1,3,5,7], [2,4,6,8]) à true
Describe the conditions when the following query must be true.
zipper([List1, List2], Zippered) , unzipper(Zippered, [List1, List2])
September 12 3401 Report 1 Specification Page 5 of 5
Exercise 6
In family relationships the term “She is my second cousin” or “She is my second cousin fourth removed” may be used. The general phrase is “She is my p’th cousin q’th removed”, where p is an integer greater than or equal to one, and q is an integer greater than or equal to zero. What are these relationships? How are the computed? Figure 1 shows a simple family tree. Among the myriad relationships the following hold.
• Thomas and Farah are cousins – Farah and Thomas are first cousins zero’th removed
1 (first) and 0 (zero), in those positions, are assumed by default and not mentioned. The relationship is symmetric.
• Thomas and Zack are cousins twice removed.
• Thomas and Nikolay are second cousins once removed.
• Thomas and Saul are third cousins.
Figure 1: A simple family tree
What is the rule? Assume that A and B have C as the nearest common ancestor. Let ⎜C – A ⎜ be the path length from C to A. The following hold.
• ⎜C–A⎜≥2 ∧ ⎜C–B⎜≥2
• p=minimum(⎜C–A⎜,⎜C–B⎜) –1
• q = ⎜ ⎜ C – A ⎜ – ⎜C – B ⎜ ⎜
Define the predicate cousins(Name1, Name2, P, Q) that asserts that Name1 and Name2 are P’th cousins Q’th removed. If the common ancestor is too close or there is no common ancestor then return
P = Q = –1. Your solution should use predicates such as ancestor(Person, Ancestor) that asserts that Ancestor is an ancestor of Person, and distance(Person, Ancestor, Distance) that asserts Distance is the path length from Person to Ancestor.
The edges in the family tree are to be encoded with the predicate parent(the_parent, a_child).
Explain why you have multiple answers, and what you need to have available to prevent multiple answers.
4 Grading scheme
The grade for the report is partitioned into the following parts.
• Report – 35%
Includes Exercise 1, and comments in the remaining exercises
• Programming (Exercises 2..6) – 15%
• Y our tests (Exercises 2..6) – 25%
• Our tests (Exercises 2..6) – 25%