- 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 sil/2, fib/2 i nwd/3.
- 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
- f(s(1),A)?
- f(s(s(1)),two)?
- f(s(s(s(s(s(s(1)))))),C)?
- f(D,three)?
- Proszę zdefiniować predykat rzym/2, który transformuje rzymskie liczby do liczb dziesiętnich.
Liczby rzymskie można po prostu reprezentować jako listy, n.p. [x,l,v,i,i].
- 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.
- Proszę zdefiniować predykaty plus/3, times/3 oraz sum-up/2 w sposobie rekurencyjnym.
Predykat sum-up(N,X) ma być spełniony, jeżeli X jest sumą liczb od 0 do N.
- Predykat sil/2 da się zrealizować następująco.
sil(X,N) :- sil(X,N,1).
sil(0,A,A).
sil(X,N,A) :- N > 0, A1 is A * N, N1 is N - 1, sil(X,N1,A1).
Proszę zdefiniować predykaty z zadania 5. i fib/2 używając tą technikę.
(Zmienna A z predykatu sil/3 się nazywa akumulator.)
- 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).
Proszę zilustrować, jak Prolog odpowiada na
pytania ?-qi(tom,pat). oraz ?-qi(liz,jim).
- 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]).
- Proszę zdefiniować następujące predykaty dla list.
- last(X,L), który jest spełniony, jeżeli X jest ostatnim elementem listy L.
- delete(X,L1,L2), który jest spełniony, jeżeli L2 równa się L1 bez elementu X.
- delete(L1,L2), który jest spełniony, jeżeli L2 równa się L1 bez ostatnich trzech elementów.
- reverse(L1,L2), który jest spełniony, jeżeli L2 jest
listą L1 w odwrotnej kolejności.
- evenlength(L) oraz oddlength(L), które są spełnione, jeżeli długość listy L jest parzysta oraz nieparzysta.
- 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]
- 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]
- 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]]
- 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
- 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
- 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]
- Proszę zdefiniować następujące predykaty dla list.
- ordered(L), który jest spełniony, jeżeli lista L jest posortowana.
- mergesort(L1,L2), który jest spełniony, jeżeli lista L2 jest wersją posortowaną listy L1.
Predykat ma simulowac algorytm mergesort.
- 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.
- 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.
- size(D,N), który jest spełniony, jeżeli N jest ilością elementów drzewa D.
- search(D,N), który jest spełniony, jeżeli N jest elementem drzewa D.
- max(D,N), który jest spełniony, jeżeli N jest maximum elementów w drzewie D.
- times(N,D1,D2), który bierzy wszystkie wartości węzłów drzewa D1 razy N.
- preorder(D,L), który jest spełniony, jeżeli lista L zawiera elementy drzewa D w kolejności
prefiksowym.
- Graf można reprezentować przy użciu predykatu edge(V1,V2), gdzie V1 oraz V2 są węzłami.
- Proszę zdefiniować predykat path(V1,V2), który znajduje drogę między V1 i V2.
- Proszę zdefiniować predykat path(V1,V2,L), który znajduje drogę między V1 i V2 oraz drogę
tą podaje w liście L.
- Jak można reprezentować graf z wagami oraz w takim grafie obliczyć koszty drogi między węzłami V1 i V2?
- Proszę zdefiniować predykat route(Place1,Place2,Day,Route), który zrealizuje planowanie lotów na podstawie rozkładu jazdy.
Rozkład jazdy jest podane przez predykat timetable(Place1,Place2,List_of_flights), gdzie List_of_Flights jest listą lotów od
Place1 do Place2.
Każdy lot jest listą [Departure_time,Arrival_time,Flight_number,List_of_days].
Przykład:
timetable( london, edinburgh,
[ [ 9:40, 10:50, ba4733, alldays],
[19:40, 20:50, ba4833, [mo,tu,we,th,fr]] ]).
Plan lotów Route jest listą lotów PlaceA-PlaceB:Flight_number:Departure_time, taka że
- PlaceA w pierwszym elemencie w liście, to Place1.
- PlaceB w ostatnim elemencie w liście, to Place2.
- wszystkie loty odbędą się w tym samym dniu.
- między lotami jest wystarczający czas na transfer.
Przykład:
?- route(ljubljana,edinburgh,th,R).
R = [ljubljana-zurich:yu322:11:30, zurich-london:sr806:16:10, london-edinburgh:ba4822:18:40].
- 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.
- 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
- 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.
- 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ą.
- 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'))
- 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ą.
- Proszę dla następujących pytań podać drzewo SLD. Jakie odpowiedzi daje Prolog?
-
s(X) :- p(X), r(X).
s(X) :- q(X).
p(a). q(a). r(a).
p(b). q(c). r(b). ?- s(X).
-
q(X) :- p(X), r(X).
p(a).
r(a).
r(f(Y)) :- r(Y). ?- r(Z). oraz ?- q(Z).
-
p(X,Z) :- q(X,Y), p(Y,Z).
p(X,X).
q(a,b). ?- p(X,b).
- Proszę dla następujących pytań podać drzewo SLD. Jakie odpowiedzi daje Prolog?
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]).
is_list([]).
is_list([X|L]) :- is_list(L). ?- is_list(L).
- Używając dzrewa SLD proszę pokazać jak Prolog odpowiada na następujące pytania.
-
p(1).
p(2) :- !.
p(3).
?- p(x). ?- p(x), p(y). ?- p(x), !, p(y).
-
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).
- 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)?
- 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).
- Proszę zdefiniować predykat difference(A,B,C) dla zbiorów A, B i C,
który jest spełniony, wtedy i tylko wtedy C = A \ B .
- Proszę zoptimalizować następucący program używając (raz green a raz red) cuts.
class(Number, positive) :- Number > 0.
class(0,zero).
class(Number, negative) :- Number < 0.
- Proszę zdefiniować predykat if-then-else(W,C,A),
który realizuje operator "if W then C else A".
- Proszę zdefiniować predykat list_to_term(L,T), który jest spełniony, jeżeli L jest niepustą listą
liczb naturalnych a T jest termem zbudowany z tych liczb przy pomocy operatora +.
Przykłady:
?- list_to_term([1,2,3,4],T).
T = 1 + (2 + (3 + 4))
?- list_to_term([7],T).
T = 7
- Proszę zdefiniować predykat count(A,T,N) dla elementu A, termu T i liczbę N,
który jest spełniony jeżeli N jest ilością
występowania A w T. Przykłady:
?- count(a,f(a),N).
N = 1
?- count(a,f(a,g(b,a),N).
N = 2.
?- count(a,f(a,g(X,a),N).
N = 2.
- Niech będzie dana lista właściwości, n.p. [animate, male, canine, feline] oraz klausuly używające
te właściwoście, n.p.
animate(fred).
animate(alice).
male(fred).
canine(alice).
feline(fred).
Proszę zdefiniować predykat checkprops(A,L), gdzie A jest dowolnym objektem a L
listą właściwości. Predykat ma być spełniony, jeśli objekt A posiada wszystkie
właściwoście w L, n.p.
?- checkprops(fred, [animate, male]).
yes
?- checkprops(alice, [animate, feline]).
no
- Proszę zdefiniować predykat filter(P,L1,L2), który jest spełniony, jeżeli lista L2 zawiera dokładnie te
elementy z listy L1, który spełniają predykat P.
Przykład:
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]
- Proszę zdefiniować predykat powerset(L1,L2)
używając predykat bagof.
- Następujący predykat obliczący liczb Fibonacci'ego
powtórzy dużą ilość obliczeń.
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.
Proszę predykat ten ulepszyć raz używając akumulator a raz używając funktor assert.
- Proszę zrealizować koncept licznika.
Licznik ma nazwę oraz wartość, i można go manipulować z operacjami init/2, getv/2, incr/1, decr/1 oraz del/1.
Przykłady:
?- 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
- Na wykład został umówiony bazę danych rodziń.
a) Proszę podać pytania dla
- nazw rodziń bez dzieci
- pracujących dzieci
- nazw rodziń z pracującą żoną a nie pracującym mężem
- dzieci, których rodziców w wieku mają rónicę conajmniej 15 lat
b) Proszę zdefiniować predykaty
- twins/2
- n-th_child/3
- siblings/1.
- Na wykład został umówiony predykat solve(State, Solution), któy używa depth first search.
Proszę zmienić predykat solve taki, że
- używa depth first search z ograniczeniem globalnym.
- używa depth first search z iterative deepening.
- Jak w Prologu można reprezentować automaty (z stosem)?
Proszę zdefiniować predykat palindrom(L) raz konwencjonalnie a raz używając odpowiednego automatu.
- Grafy z kosztami można zareprezentować używając zbiór
faktów edge(Vertice1,Vertice2,Cost).
Proszę zdefiniować predykat path(V1,V2,C), który obliczy koszty
drogi C od V1 do V2.
Proszę rozwiązać zadanie używając raz algorytm depth-first-search a raz algorytm breadth-first-search.