Exercise � Let f be a binary function symbol, g, h unary, and c a constant symbol. Find the most
general unifier for the following pairs of terms.
(i) f (g(x), y) and f (x, h(y))
(ii) f (h(x), x) and f (x, h(y))
(iii) f (x, f (x, g(y))) and f (y, f (h(c), x))
(iv) f (f (x, c), g(f (y, x))) and f (x, g(x))
Exercise � Suppose we are given a predicate flight(From, To, Time, Price) containing information
about direct flights including the starting airport, the destination, the flight time, and the price of a
ticket. Write a Prolog program computing a predicate travel(From, To, Stops, Time, Price) indicating
all possibilities to travel from one city to another using one or several flights.
Exercise � Write a Prolog predicate fib(N, X) computing the Fibonacci sequence. Evaluate fib(, X)
and fib(N, ).
Exercise � Write Prolog definitions of the following predicates.
length(List, N) N is the length of List .
append(X, Y, Z) Z is the concatenation of the lists X and Y .
reverse(X, Y) Y is the reverse of the list X .
map(X, Y) maps a list X = [X, . . . , Xn] to Y = [f (X), . . . , f (Xn)] .
fold_left(X, Y, Z) maps Y = [Y, . . . , Yn] to Z = f (⋯f (f (X, Y), Y)⋯, Yn) .
fold_right(X, Y, Z) maps Y = [Y, . . . , Yn] to Z = f (Y, f (Y, . . . , f (Yn, X) . . . ))) .
The Prolog notation for lists is as follows:
[] [X, Y, Z] [X Y] [X, Y Z] .
Exercise � Write a naive sort function
naive_sort(X,Y) :- permute(X,Y), sorted(Y).
by implementing the relations
sorted(X) checks that the list X is sorted.
insert(X, Y, Z) if the list Z is obtained from Y by inserting X at an arbitrary position.
permute(X, Y) if the list Y is a permutation of X .
Implement merge sort using the relations
merge(X, Y, Z) merges two sorted lists X and Y into Z .
split(X, Y, Z) splits the list X into two lists Y and Z .
1
Exercise � We consider undirected graphs of the form ⟨V, E⟩. Express the following relation in
relational algebra.
(a) x and y are not connected by an edge.
(b) The edge ⟨x, y⟩ is part of a triangle.
(c) x has at least two neighbours.
(d) Every neighbour of x is also a neighbour of y.
Exercise � Evaluate the following Datalog program on the tree ⟨V, E, P⟩ to the right.
U ← S(x, y) ∧ W(x) ∧ W(y)
W(x) ← P(x)
W(x) ← E(x, y) ∧ W(y)
S(x, y) ← E(z, x) ∧ E(z, y) ∧ x ≠ y
R(x, y) ← P(x) ∧ x = y
R(x, y) ← E(x, z) ∧ R(z, y)
R(x, y) ← R(x, z) ∧ E(z, y)

 
  
 
P
P
P
2