The University of British Columbia
Department of Computer Science
Midterm Examination 3 ¡ª Fall 2018 Computer Science 312 Functional and Logic Programming
Question 1 [10 marks]
Consider the following knowledge base, KB. (Assume predicates have been defined dynamic so there are no undefined procedure errors.)
p :- m,c.
p :- r,s.
m :- n.
c.
r :- t.
r :- w.
t :- v.
w.
s :- a. a.
(a) [4 marks] m is not a logical consequence of KB. Give a model of KB in which m is false.
(b) [6 marks] p is a logical consequence of KB. Complete the following successful top-down derivation for the query ?- p. (Hint: work out which choices lead to a proof; do not include the failing branches)
Answer clause
yes :- p
yes :- r, s
Clause resolved –
p :- r, s
Question 2 [12 marks]
Here is the KB from the previous page
p :- m,c.
p :- r,s.
m :- n.
c.
s :- a.
r:-t. r:-w. t:-v. w.
a.
1
(a) [6 marks] Draw the box model for p. You need to include the ports, but not the port names. You need to include the names for the atoms that the boxes represent.
(b) [6 marks] Here is a (edited) trace of the query ?- p. [trace] ?- p.
Call: p
_______________________________________
Call: n
_______________________________________
Fail: m
Redo: p
_______________________________________
Call: t
Call: v
Fail: v
_______________________________________
Redo: r
Call: w
Exit: w
Exit: r
_______________________________________
Call: a
Exit: a
_______________________________________
Exit: p true.
Question 3 [10 marks]
The following code is from Assignment 4.
Fill in the missing (underlined) lines:
% name(P,F,L) means person P¡¯s first name is F and last name is L
name(davidp, “David”, “Poole”).
name(ainaz , “Ainaz”, “Hajimoradlou”).
name(liran, “Liran”, “Li”).
name(rui, “Rui”, “Ge”).
% office_hour(P, D, S, F) means office hours for person P are on day D from S to F.
office_hour(davidp, wednesday, 15, 16).
office_hour(ainaz, thursday, 16, 17).
office_hour(liran, monday, 11, 12).
office_hour(liran, wednesday, 17, 18).
office_hour(rui, thursday, 10, 11).
(a) [4 marks] David wrote the following program
% twoofficehours(D) is true if there are office hours
2
% on day D starting at different times
twoofficehours(D) :-
office_hour(_,D,H1,_),
office_hour(_,D,H2,_),
H1 < H2.
Why did he write H1 < H2?
(b) [6 marks] Define the following predicate that is true if F1 and F2 are the first names of two people that have office hours on the same day. This must work even if two or more of the people have the same first name. It should work whether the names are provided in a query or not. You may use any of: dif , append, length, <
office_hours_on_same_day(F1,F2) :-
Question 4 [10 marks]
(a) [6 marks] Write a program delall(E,L,R) which is true when R is a list with the same elements as list L (in the same order) but with all instances of E deleted. The only predefined predicate you may use is dif (X , Y ) that is true when X and Y are different. For example, it should have the following behaviour (where these are all the answers and different answers are separated by ¡°;¡±):
?- delall(a,[a,v,a,t,a,r],R).
R = [v, t, r]
?- delall(a,[f,U,n],R).
U = a,
R = [f, n] ;
R = [f, U, n],
dif(U, a)
(b) [4 marks] What are all of the answers to the query
?- delall(X,[a,b,c,a],R).
(Note that you should be able to do this, even if you cannot do part (a).)
3