- 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.
- 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.
- 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?
- f(s(1),A)?
- f(s(s(1)),two)?
- f(s(s(s(s(s(s(1)))))),C)?
- f(D,three)?
- 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.
- 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.
- 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.)
- 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.
- Please define the following predicates for lists.
- last(X,L), which is fulfilled if X is the last element of L.
- delete(X,L1,L2), which is fulfilled if L2 is the list L1 without the element X.
- delete(L1,L2), which is fulfilled if L2 is the list L1 without L1's last three elements.
- reverse(L1,L2), which is fulfilled if L2 is the list L2 in reversed order.
- evenlength(L) and oddlength(L), which are fulfilled if the length of L
is even and odd, respectively.
- 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]
- 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]
- 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]]
- 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
- 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
- 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]
- 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]).
- Please define the following predicates for lists.
- nth(N,L,X), which is fulfilled if X is the N-th element in the list L.
- ordered(L), which is fulfilled if list L is ordered.
- mergesort(L1,L2), which is fulfilled if L2 is the ordered version of the list L1.
The predicate should simulate algorithm mergesort.
- 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.)
- 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
- PlaceA in the first element of Route is Place1.
- PlaceB in the last element of Route is Place2.
- all flights in Route take place the same day.
- 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].
- 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.
- size(T,N), which is fulfilled if N is the number of elements of tree D.
- search(T,X), which is fulfilled if X appears in tree T.
- max(T,X), which is fulfilled if X is the largest element of tree T.
- times(N,T1,T2), which is fulfilled if D2 is the tree D1 in which each element has been multiplied with N.
- preorder(T,L), which is fulfilled if L is the list of D's elements in preorder.
- 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
- 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.
- 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.
- 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.
- 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'))
- 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.
- Please give the SLD-trees for the following queries. Which answers gives 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). and ?- q(Z).
-
p(X,Z) :- q(X,Y), p(Y,Z).
p(X,X).
q(a,b). ?- p(X,b).
- Please give the SLD-trees for the following queries
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).
- Using SLD-trees please show, how Prolog answers to the following queries.
-
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).
-
p(1).
p(2) :- !.
p(3).
?- p(x). ?- p(x), p(y). ?- p(x), !, p(y).
- 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).
- Please define a predicate delete(X,L1,L2),
which is fulfilled if and only if L2 is the list
L1 without all elements X.
- 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)?
- Please define a predicate if-then-else(Condition,Consequence,Alternative)
realizing the usual operator "if Condition then Consequence else Alternative".
- 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 .
- 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
- 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]
- Please define a predicate variables(T,L), which is fulfilled if L is the list of variables in term T.
- 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
- 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
- Please define predicate powerset(L1,L2) using bagof.
- 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.
- 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