Zadania

1. Długość listy można w Prologu zdefiniować następująco:

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

   Proszę zdefiniować predykaty member/2 oraz silnia/2, fibonacci/2 i nwd/3.
   
   
2. Niech będzie dany następujący program:

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

   Jak odpowiada Prolog na pytanie
   
   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)?
   
   
3. Proszę zdefiniować predykat rzym/2, który transformuje rzymskie liczby do liczb dziesiętnich.
   Liczby rzymskie można po prostu reprezentować jako listy. Przykład:
   
   ?- rzym([x,l,v,i,i],N).
   N = 47
   
   
4. Niech będzie dana baza danych zawierająca predykaty parent/2, female/1 i male/1.
   Proszę zdefiniować predykaty child/2, mother/2, sister/2, has_a_child/1, grandparent/2 oraz predecessor/2.
   
   
5. Niech będą dane następujące predykaty:

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

   oraz baza danych dla predykat p:

    p(pam,bob).       
    p(tom,bob).
    p(tom,liz).
    p(bob,ann).      
    p(bob,pat).     
    p(pat,jim). 

   Używając drzewo odpowiedzi proszę zilustrować, jak Prolog odpowiada na pytania ?-q_i(tom,pat). oraz ?-q_i(liz,jim).
   
   
6. Proszę zdefiniować następujące predykaty dla list.
   
   
   1. last(X,L), który jest spełniony, jeżeli X jest ostatnim elementem listy L.
   2. delete(X,L1,L2), który jest spełniony, jeżeli L2 równa się L1 bez elementu X.
   3. delete(L1,L2), który jest spełniony, jeżeli L2 równa się L1 bez ostatnich trzech elementów.
   4. reverse(L1,L2), który jest spełniony, jeżeli L2 jest listą L1 w odwrotnej kolejności.
   5. evenlength(L) oraz oddlength(L), które są spełnione, jeżeli długość listy L jest parzysta oraz nieparzysta.
      
   6. shift(L1,L2), który jest spełniony, jeżeli L2 równa się L1 po jednej rotacji do lewej.
      Przykład:

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

   7. quadrat(L1,L2), który jest spełniony, jeżeli L2 zawiera quadraty elementów listy L1.
      Przykład:

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

   8. combine(L1,L2,L3), który jest spełniony, jeżeli L3 zawiera pary elementów z list L1 i L2.
      Przykład:

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

   9. palindrom(L), który jest spełniony, jeżeli lista L zawiera palindrom.
      Przykłady:

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

   10. p(X,L,Y,Z), który jest spełniony, jeżeli Y jest poprzednikiem elementu X w liście L a Z następcą elementu X w liście L.
       Przykład:

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

   11. q(X,L1,L2), który jest spełniony, jeżeli L2 równa się początku listy L1 do podwójnego wystąpienia elementu X.
       Przykład:

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

   
   
7. Proszę zdefiniować następujące predykaty dla list.
   
   
   1. nth(N,L,X), który jest spełniony, jeżeli X jest N-tym elementem listy L.
      
   2. ordered(L), który jest spełniony, jeżeli lista L jest posortowana.
   3. mergesort(L1,L2), który jest spełniony, jeżeli lista L2 jest wersją posortowaną listy L1. Predykat ma symulowac algorytm mergesort.
      
      
8. Niech będą dane następująca defincja predykatu append2.

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

   Proszę zilustrować, jak Prolog odpowiada na pytanie

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

9. Proszę zdefiniować predykat permutation(L1,L2), który jest spełniony, jeżeli lista L2 jest permutacją listy L1.
   Przy użyciu ";" powiennien być możliwe wyliczać wszystkie permutacje listy L1.
   
   
10. Drzewo binarne D jest albo pusty (repezentowane przez nil) albo zawiera element X i dwa poddrzewa L i P (reprezentowane przez drzewo(X,L,P)).
    Proszę zdefiniować następujące predykaty dla drzew.
    
    
    1. size(D,N), który jest spełniony, jeżeli N jest ilością elementów drzewa D.
    2. search(D,N), który jest spełniony, jeżeli N jest elementem drzewa D.
    3. max(D,N), który jest spełniony, jeżeli N jest maximum elementów w drzewie D.
    4. times(N,D1,D2), który bierzy wszystkie wartości węzłów drzewa D1 razy N.
    5. preorder(D,L), który jest spełniony, jeżeli lista L zawiera elementy drzewa D w kolejności prefiksowym.
    6. subtree(D1,D2), który jest spełniony, jeżeli drzewo D1 jest poddrzewem drzewa D1.
    7. subst(D1,D2,D3,D4), który jest spełniony, jeżeli drzewo D4 jest drzewem D2, w którym wszystkie poddrzewa D1 zostały zmienione na drzewo D4.
    
    
11. Niech będą
    
    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))
    
    Proszę transformować A, B oraz C do zbiorów klausuli.
    
    
12. Używając rezolucję proszę sprawdzić czy następujące konsekwencje logiczne są poprawne.
    
    a) (p → q) → r |= p → (q → r)
    
    b) p → (q → r) |= (p → q) → r
    
    
13. Niech będą
    
    A ≡ (p → (¬ q ∨ ¬ r)) ∧ ((p ∧ r) ∨ ( q → (q → r)))
    B ≡ (p ∧ (¬ q ∧ r)) ∨ (r ∧ (r → p))
    C ≡ (p ∧ r) ∨ (¬(q → r)).
    
    Używając rezolucję proszę sprawdzić czy {A,B}|= C jest ważna.
    
    
14. Niech będą
    
    A ≡ (¬q → (p ∧ r))
    B ≡ r → (¬p ∧ ¬q)
    C ≡ (r ∨ w) → ¬(w → ¬q)
    
    Używając rezolucję proszę sprawdzić czy (A ∧ B) → C jest tautologią.
    
    
15. Proszę obliczyć najbardziej ogólny unifikator dla następujących wyrażeń.
    
    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'))
    
    
16. Używając rezolucję proszę pokazać, że A ≡ (∀x∃y p(x,y) ∧ ∀y∃z q(y,z)) → ∀x∃y∃z (p(x,y) ∧ q(y,z)) jest tautologią.
    
    
17. Proszę dla następujących pytań podać drzewo SLD. Jakie odpowiedzi daje 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).  oraz  ?- q(Z).

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

18. Proszę dla następujących pytań podać drzewo SLD. Jakie odpowiedzi daje Prolog?
    

    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([1,a,2]).  oraz  ?- is_list(L).
       

19. Używając dzrewa SLD proszę pokazać jak Prolog odpowiada na następujące pytania.
    

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

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

20. Niech będzie dana następująca definicja.

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

    Na kolejne pytanie Prolog odpowiada "błędnie":

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

    Dlaczego Prolog tak odpowiada i jak można to zreperować (bez zmian cut'u i drugiej reguły)?
    
    
21. Niech będzie dana następująca definicja predykatu memberc(X,L).

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

    Proszę porównać tą definicję z zwykłą definicją member(X,L).