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: ?-qi(tom,pat). and ?-qi(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'))