Exercises (Prolog)

1. A predicate length/2 describing the length of a list can be defined as follows.

     length(0,[]).
     length(N,[_|L]) :- length(M,L), N is M+1.
   

   Please define predicates member/2, fac/2, fib/2, and gcd/3 analogously.
   
   
2. Suppose predicates parent/2, female/1 i male/1 with the obvious interpretation are given.
   Please define predicates child/2, mother/2, sister/2, has_a_child/1, grandparent/2 and predecessor/2.
   
   
3. Suppose the following predicate f/2 is given.

    f(1,one).
    f(s(1),two).
    f(s(s(1)),three).
    f(s(s(s(X))),N) :- f(X,N). 

   How does Prolog answer to the following questions?
   
   
   1. f(s(1),A)?
   2. f(s(s(1)),two)?
   3. f(s(s(s(s(s(s(1)))))),C)?
   4. f(D,three)?
   
   
4. Please define a predicate latin/2, which transforms Latin numbers into arabic numbers. Latin numbers are represented by ordinary lists,
   for example [x,l,v,i,i] denotes 47. You can assume that the Latin number is correct.
   
   
5. Please define predicates plus/3, times/3, and sum-up/2 (using recursion).
   Predicate sum-up(N,X) is fulfilled, if X equals the sum from 0 to N.
   
   
6. Predicate fac/2 from exercise 1 can also be defined as follows:

     fac(X,N) :- fac(X,N,1).
   
     fac(0,A,A).
     fac(X,N,A) :- X > 0, A1 is A * X, X1 is X - 1, fac(X1,N,A1).
   

   Please define the predicates from exercise 5 and predcate fib/2 from exercise 1 using this technique. (Note: The third argument of of fac/3 is called accumulator.)
   
   
7. Assume the following predicates are given.

    q1(X,Y) :- p(X,Y).                q2(X,Y) :- p(X,Z), q2(Z,Y).
    q1(X,Y) :- p(X,Z), q1(Z,Y).       q2(X,Y) :- p(X,Y).  
   
    q3(X,Y) :- p(X,Y).                q4(X,Y) :- q4(X,Z), p(Z,Y).  
    q3(X,Y) :- q3(X,Z), p(Z,Y).       q4(X,Y) :- p(X,Y). 
       
    p(tom,bob).
    p(tom,liz).
    p(bob,ann).      
    p(bob,pat).     
    p(pat,jim). 

   Using answer trees please show how Prolog answers to the following questions: ?-q_i(tom,pat). and ?-q_i(liz,jim) for i = 1, ... 4.
   
   
8. Assume the following definition of the predicate append is given.

     append([X|L1], L2, [X|L3]) :- append(L1, L2, L3).
     append([], L, L).   

   Using answer trees please show how Prolog answers to the questions

    ?- append(X, [3,4], [2,3,4]).
   

9. Please define the following predicates for lists.
   
   
   1. last(X,L), which is fulfilled if X is the last element of L.
      
      
   2. delete(X,L1,L2), which is fulfilled if L2 is the list L1 without the element X.
      
      
   3. delete(L1,L2), which is fulfilled if L2 is the list L1 without L1's last three elements.
      
      
   4. reverse(L1,L2), which is fulfilled if L2 is the list L2 in reversed order.
      
      
   5. evenlength(L) and oddlength(L), which are fulfilled if the length of L is even and odd, respectively.
      
      
   6. shift(L1,L2), which is fulfilled if L2 the list L1 after one rotation to left.
      Example:

       ?- shift([1,2,3,4,5],L).
       L = [2,3,4,5,1] 

   7. quadrat(L1,L2), which is fulfilled if L2 contains the squares of the elements of L1.
      Example:

       ?- quadrat([1,2,3,4,5],L).
       L = [1,4,9,16,25] 

   8. combine(L1,L2,L3), which is fulfilled if L3 contains the pairs of the elements of L1 and L2.
      Example:

       ?- combine([1,2,3,4],[a,b,c,d],L).
       L = [[1,a],[2,b],[3,c],[4,d]] 

   9. palindrom(L), which is fulfilled if L contains a palindrom.
      Examples:

       ?- palindrom([a,b,c]).
       no
       ?- palindrom([a,b,c,d,c,b,a]).
       yes 

   10. p(X,L,Y,Z), which is fulfilled if Y is the predecessor of X in L and Z is the successor of X in L.
       Example:

        ?- p(3,[1,2,3,4,5],Y,Z).
        Y = 2, Z = 4 

   11. q(X,L1,L2), which is fulfilled if L2 is the beginning of the list L1 up to the (first) double occurence of element X.
       Example:

        ?- q(3,[1,2,3,3,1,2,4],Z).
        Z = [1,2,3,3] 

10. Please define the following predicates for lists.
    
    
    1. nth(N,L,X), which is fulfilled if X is the N-th element in the list L.
       
       
    2. ordered(L), which is fulfilled if list L is ordered.
       
       
    3. mergesort(L1,L2), which is fulfilled if L2 is the ordered version of the list L1. The predicate should simulate algorithm mergesort.
       
       
11. Please define a predicate permutation(L1,L2), which is fulfilled if the list L2 is a permuation of L1.
    (Using ";" it should be possible to enumerate all permutations of L1.)
    
    
12. A binary tree T is either empty - represented by the term nil - or consists of an element X (the root element) and two subtrees L and P - represented by the term node(X,L,P).
    Please define the following predicates for binary trees.
    
    
    1. size(T,N), which is fulfilled if N is the number of elements of tree D.
       
       
    2. search(T,X), which is fulfilled if X appears in tree T.
       
       
    3. max(T,X), which is fulfilled if X is the greatest element of tree T.
       
       
    4. times(N,T1,T2), which is fulfilled if D2 is the tree D1 in which each element has been multiplied with N.
       
       
    5. preorder(T,L), which is fulfilled if L is the list of D's elements in preorder.
    
    
13. Using resoluton please check, whether the following logical consequences are true.
    
    a) (p → q) → r |= p → (q → r)
    
    b) p → (q → r) |= (p → q) → r
    
    
14. Suppose that
    
    A ≡ (p → (¬ q ∨ ¬ r)) ∧ ((p ∧ r) ∨ ( q → (q → r)))
    B ≡ (p ∧ (¬ q ∧ r)) ∨ (r ∧ (r → p))
    C ≡ (p ∧ r) ∨ (¬(q → r)).
    
    Using resoluton please check, whether {A,B}|= C is true.
    
    
15. Suppose that
    
    A ≡ (¬q → (p ∧ r))
    B ≡ r → (¬p ∧ ¬q)
    C ≡ (r ∨ w) → ¬(w → ¬q)
    
    Using resoluton please check, whether (A ∧ B) → C is a tautology.
    
    
16. Please compute the most general unifier of the following terms.
    
    a)   f(x,g(b))                         f(a,y)
    b)   f(h(x,b),y)                      f(h(a,y),x)
    c)   f(x,y)                              f(h(x,b),y)
    d)   g(x,h(x,y),h(y,h(x,y)))     g(x,y',h(z,y'))
    e)   g(x,h(x,y),h(y,h(x,y)))     g(x,y',h(y',z))
    f)   f(a,x,h(g(y)))                   f(z,h(z),h(z'))
    
    
17. Suppose that
    
    A ≡ ∀x∀y∃z p(x,y,z)
    B ≡ ∀u∀v∀w∀x∀y∀z (p(x,y,u) ∧ p(y,z,v)) → (p(x,v,w) ↔ p(u,z,w))
    C ≡ ∃x (∀y p(x,y,y)) ∧ (∀y∃z p(z,y,x))
    
    Please compute the set of clauses for A, B and C.
    
    
18. Suppose that
    
    A ≡ ∃x (p(x) ∧ ∀y (d(y) → l(x,y)))
    B ≡ ∀x (p(x) → ∀y (q(y) → ¬l(x,y))
    C ≡ ∀x (d(x) → ¬q(x))
    
    Using resoluton please check, whether {A,B}|= C is true.
    
    
19. Using resoluton please show, that A ≡ (∀x∃y p(x,y) ∧ ∀y∃z q(y,z)) → ∀x∃y∃z (p(x,y) ∧ q(y,z)) is a tautology.
    
    
20. Please give the SLD-trees for the following queries. Which answers gives Prolog?
    

    1.  s(X) :- p(X), r(X).
        s(X) :- q(X).
        p(a).   q(a).   r(a).
        p(b).   q(c).   r(b).                        ?- s(X).

    2.  q(X) :- p(X), r(X).
        p(a).
        r(a).
        r(f(Y)) :- r(Y).                             ?- r(Z).  and  ?- q(Z).

    3.  p(X,Z) :- q(X,Y), p(Y,Z).
        p(X,X).
        q(a,b).                                      ?- p(X,b). 

21. Please give the SLD-trees for the following queries
    

    1.  append1([],L,L).
        append1([H|L1],L2,[H|L3]) :- append1(L1,L2,L3).
       
        append2([H|L1],L2,[H|L3]) :- append2(L1,L2,L3).
        append2([],L,L).                                   ?- appendi(X,[3,4],[2,3,4]).
       

    2.  is_list([]).
        is_list([X|L]) :- is_list(L).                      ?- is_list(L).
       

22. Using SLD-trees please show, how Prolog answers to the following queries.
    

    1.  p(x) :- a(x).
        p(x) :- b(x), c(x), !, d(x).
        p(x) :- f(x).                       
        a(1).     
        b(1).     
        c(1).
        b(2).     
        c(2).     
        d(2).
        f(3).
       
        ?- p(x). 

    2.  p(1). 
        p(2) :- !.
        p(3).
       
        ?- p(x).       ?- p(x), p(y).    ?- p(x), !, p(y). 

23. Suppose the following definiton of predicate memberc(X,L) is given.

    memberc(X,[X|_]) :- !.
    memberc(X,[_|L]) :- memberc(X,L).
    

    Please compare this definition with the ordinary one of member(X,L).
    
    
24. Suppose the following definiton of a predicate maximum is given.

     maximum(X,Y,X) :- X >= Y, !.
     maximum(X,Y,Y).
    

    Then Prolog answers "incorrectly" to the question

     ?- maximum(5,2,2).
     yes
    

    Why does Prolog answer "yes" and how this error can be fixed (nor eliminating the cut or modifying the the fact)?
    
    
25. Consider the following predicates person, female, and male.

        person(P,female) :- woman(P).
        person(P,male) :- man(P).
        woman(anna). ...
        man(peter). ...
    

    a) Please give the SLD-tree for the query person(P,K).
    
    b) Please optimize predicate person using .
    
    c) Is your cut in part b) green or red?
    
    
26. Please define a predicate count(A,T,L), which is fulfilled if term A appears N times in list L.
    Examples:

     ?- count(a, [a,b,b,a], N).
     N = 2
     ?- count(a, [a,X,a,b,Z, N).
     N = 2
     ?- count(X, [a,X,Y,b], N).
     N = 1
     ?- count([a], [a,[a],X,[a,b]], N).
     N = 1
    

27. Suppose given are a list of properties, for example [animate, male, canine, feline], and a list of clauses such as

     animate(fred).
     animate(alice).
     male(fred).
     canine(alice).
     feline(fred).
    

    Please define a predicate checkprops(P,L), where P is a person and L a list of properties. checkprops(A,L) is fulfilled, if P has all properties from L.
    Examples:

     ?- checkprops(fred, [animate, male]).
     yes
     ?- checkprops(alice, [animate, feline]).
     no
    

28. Please define a predicate filter(P,L1,L2), which is fulfilled if list L2 contains all elements from list L1 fulfilling predicate P.
    Example:

     pos(X) :- X > 0.
     neg(X) :- X < 0.
    
     ?- filter(pos,[1,2,0,5,-5,-6,8],L).
     L = [1,2,5,8]
     ?- filter(neg,[1,2,0,5,-5,-6,8],L).
     L = [-5,-6]
    

29. Please define a predicate variables(T,L), which is fulfilled if L is the list of variables appearing in term T.
    
    
30. Please define a predicate count(A,T,N), which is fulfilled if term A appears N times in term T.
    Examples:

     ?- count(a, f(a), N).
     N = 1
     ?- count(a, f(a, g(b,a)), N).
     N = 2
     ?- count(a, f(a,X)), N).
     N = 1
     ?- count(f(a), f(a,g(f(a),f(a))), N).
     N = 2
    

31. Please define a predicate powerset(L1,L2) using bagof.
    
    
32. The following predicate gives the N-th Fibonacci number.

     fib(0,1).
     fib(1,1).
     fib(N,F) :- N >1, N1 is N-1, N2 is N-2, fib(N1,F1), fib(N2,F2), F is F1 + F2.
    

    Please improve this predicate using assert.
    
    
33. Please implement counters in Prolog: A counter has a name and a value and should provide operations init/2, getvalue/2, incr/1, decr/1, and del/1.
    Example:

     ?- init(z,3).
     true
     ?- getvalue(z,V).
     V = 3
     ?- incr(z), decr(z), decr(z).
     true
     ?- getvalue(z,V).
     V = 2
     ?- del(z).
     true
     ?- getvalue(z,V).
     no