Exercises (Prolog)

  1. A predicate 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 oraz fac/2, fib/2 i gcd/3 analogous.

  2. Suppose predicates parent/2, female/1 i male/1 wth 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 supposed to be represented by ordinary lists, for example [x,l,v,i,i] denotes 47.

  5. Please define predicates plus/3, times/3, fib/2 oraz sum-up/2 (using recursion).
    Predicate sum-up(N,X) is fulfilled, if X is the sum from 0 to N.

  6. Predicate sil/2 can also be defined as follows: 
      sil(X,N) :- sil(X,N,1).

  sil(0,A,A).
  sil(X,N,A) :- X > 0, A1 is A * X, X1 is X - 1, sil(X1,N,A1).
    Please define the predicatess from exercise 5 using this technique. (Note: The variable A of sil/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: ?-qi(tom,pat). and ?-qi(liz,jim) for i = 1, ... 4.

  8. 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]
  9. 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]).
  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. Please define a predicate route(Place1,Place2,Day,Route) finding connections based on a timetable.
    The timetable is given by a predicate timetable(Place1,Place2,List_of_flights), where List_of_Flights is a flight list from Place1 to Place2.
    Each flight is a list [Departure_time,Arrival_time,Flight_number,List_of_days].
    Example timetable: 
        timetable(edinburgh,london,
       [ [ 9:40, 10:50, ba4733, alldays],
         [13:40, 14:50, ba4773, alldays],
         [19:40, 20:50, ba4833, [mo,tu,we,th,fr,su]] ]).
     
    timetable(london, edinburgh,
       [ [ 9:40, 10:50, ba4732, alldays],
         [13:40, 14:50, ba4752, alldays],
         [18:40, 19:50, ba4822, [mo,tu,we,th,fr]] ]).
     
    timetable(london,ljubljana,
       [ [13:20, 16:20, ju201, [fr]],
         [13:20, 16:20, ju213, [su]] ]).
     
    timetable(ljubljana, zurich,
       [ [11:30, 12:40, ju322, [tu,th]] ]).
   
    timetable(zurich, london,
       [ [ 9:00,  9:40, ba613, [mo,tu,we,th,fr,sa]],
         [16:10, 16:55, sr806, [mo,th,we,th,fr,su]] ]).
    A connection Route from Place1 to Place2 is a list of flights PlaceA-PlaceB:Flight_number:Departure_time such that

    1. PlaceA in the first element of Route is Place1.
    2. PlaceB in the last element of Route is Place2.
    3. all flights in Route take place the same day.
    4. Between all flights there is enough transfer time, let's say 45 minutes.

    Example: 
         ?- route(ljubljana,edinburgh,th,Route).
     Route = [ljubljana-zurich:ju322:11:30, zurich-london:sr806:16:10, london-edinburgh:ba4822:18:40].
  13. 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 largest 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.

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

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

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

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

  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. Please define a predicate delete(X,L1,L2), which is fulfilled if and only if L2 is the list L1 without all elements X.

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

  26. Please define a predicate if-then-else(Condition,Consequence,Alternative) realizing the usual operator "if Condition then Consequence else Alternative".

  27. Please define a predicate difference(A,B,C) for sets A, B i C (represented as lists), which is fulfilled if and only if C = A \ B .

  28. 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
  29. 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]
  30. Please define a predicate variables(T,L), which is fulfilled if L is the list of variables in term T.

  31. Please define a predicate list_to_term(L,T), which is fulfilled if L is a non-empty list of numbers and T is the term buuilt from these numbers using +.
    Examples: 
     ?- list_to_term([1,2,3,4],T).
 T = 1 + (2 + (3 + 4))
 ?- list_to_term([7],T).
 T = 7
  32. Please define a predicate count(A,L,N), which is fulfilled if N is the number of occurences of A in term T. You can assume that A contains no variables. 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
  33. Please define predicate powerset(L1,L2) using bagof.

  34. The following predicate defines the Fibonacci sequence. 
     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 optimize the predicate using assert.

  35. Please define the concept of counters in Prolog: A counter has a name and a value and can be manipultated by operations init/2, getv/2, incr/1, decr/1, and del/1.
    Examples: 
     ?- init(z,3).
 true
 ?- getv(z,V).
 V = 3
 ?- incr(z), decr(z), decr(z).
 true
 ?- getv(z,V).
 V = 2
 ?- del(z).
 true
 ?- get(z,V).
 no