Solution - Exercises INF3110/4110 week 47 (17.11.-21.11.2008) Exercise 1 ---------- 1. Define child(X,Y) :- p(X,Y,_Z,_W) . child(X,Y) :- p(X,_Z,Y,_W) . and gc(X,Y) :- child(X,Z) , child(Z,Y) . 2. The query gc(beate, aale) will return yes. The question gc(beate, X) will return the values aase and aale for X. 3. Define descendant(X,Y) :- child(X,Y). descendant(X,Y) :-child(X,Z), descendant(Z,Y). and cd(X,Y) :- descendant(Z,X), descendant(Z,Y), X \== Y. 4. Define not(X) :- \+(X) . sibling(X,Y) :- child(X,Z) , child(Y,Z) , X \== Y . and oc(X) :- p(X,_,_,_) , not(sibling(X,_)) . In the following we assume that the predicate "not" is defined as above. Exercise 2 ----------- a) IN211 exam 1992, problem 2e: 1. %boss(X,Y) : X is the boss of Y boss(eva,anne). boss(eva,atle). boss(lars,eva). 2. sup(X,Y) :- boss(X,Y) . sup(X,Y) :- boss(X,Z) , sup(Z,Y) . 3. %Helper relation, moreThanOne(X) : X has more than one boss. moreThanOne(X) :- boss(Y,X), boss(Z,X),Z \== Y . %Test if boss facts are OK bossOK :- not(moreThanOne(X)), not(sup(X,X)) . %Or conversely, test if they are not OK. notOKboss :- moreThanOne(X) ; sup(X,X) . Note: if there is an instance of sup(X,X), then the answer is repeated indefinietely, since there is a cycle in the graph!. b) IN211 exam 1997, problem 3: %Look up find(I,X) :- ls(I,X) . find(I,X) :- rs(I,X) . %Error error(I) :- ls(I,X) ,rs(I,Y) , X\==Y . %Multiple multi(X) :- ls(I1,X) , ls(I2,X) , I1\==I2 . multi(X) :- rs(I1,X) , rs(I2,X) , I1\==I2 . multi(X) :- ls(I1,X) , rs(I2,X) , I1\==I2 . %This definition of multi gives 3 solutions. c) INF3110/4110 exam 2003 problem 6. (http://www.uio.no/studier/emner/matnat/ifi/INF3110/h06/gamle_eksamen/INF3110-4110-2003-eks-eng.pdf) 6a) 1. G = [1,2,3,4] 2. U = a, Z = h(a) 3. no 4. Y = 2, Z = X 6b) Given the following definition of member: member(E, [E|_]). /* 1 */ member(E, [_|Rest]) :- member(E, Rest). /* 2 */ The calculation member(X,[1,2]) gives the following tree: member(X,[1,2]) / \ / \ unifies with R1 and by R2 the substitution {X=1} \ / \ / member(X,[2]) member(1,[1,2]) / \ | / \ yes by R1 and by R2 {X=2} \ | \ member(2,[2]) member(X,[]) | | yes cannot be unified | no So the solutions are X=1; X=2; X=no . Exercise 3 ----------- addAtEnd([X|Xs],Y,[X|Zs]) :- addAtEnd(Xs,Y,Zs) . addAtEnd([],Y,[Y]) . Exercise 4 ----------- reverse([],[]) . reverse([X],[X]) . reverse([X|Xs],Zs) :- reverse(Xs,Ws) , addAtEnd(Ws,X,Zs) .