Solution - Exercises INF3110/4110 
                    week 47 (16.11.-20.11.2009)


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) .