Solutions to Proposed Problems

**Problem 1.1** (page ):

The tableau continues the one in Table 1.1 like this:

Variables and Domains |
|||||||

Step |
a |
b |
c |
d |
e |
f |
g |

12 |
6 | ||||||

13 |
2 | 3..5 | |||||

14 |
0..3 | 0..2 | |||||

15 |
0..1 | 0 | |||||

16 |
0 | ||||||

Final
domains |
0 | 0..1 | 0 | 0..2 | 2 | 3..5 | 6 |

Tasks **a** and **c** must start at the beginning of the
project. Task *e* has to start at time 2, and cannot be
delayed. Tasks **b**, **d**, and **f** have a slack in
their start time.

**Problem 2.1** (page ):

?- sound(A, S). A = spot, S = bark ? ; A = barry, S = bubbles ? ; A = hobbes, S = roar ? ; no

**Problem 2.2** (page ):
Both queries are independent. The first one binds `X` to
`a`; then the toplevel backtracks and clears the bindings
made so far, thus reverting to the state previous to the query.
That is why the second query, binding `X` to a different
value, succeeded: at this point the state of the interpreter is the
same as if the first query had never been issued.

**Problem 2.3** (page ):
The answer to `?- pet(X), sound(Y, roar).` is `X =
spot, Y = hobbes` and `X = barry, Y = hobbes`. No solution
has the same value for an animal which is pet and for an animal with
roars (in other words, no pet roars). When both are forced to be
the same (using the constraint `X = Y`), the query fails.

**Problem 2.4** (page ):

?- father_of(juan, pedro). yes ?- father_of(juan, david). no ?- father_of(juan, X). X = pedro ? ; X = maria ? ; no ?- grandfather_of(X, miguel). X = juan ? ; no ?- grandfather_of(X, Y). X = juan, Y = miguel ? ; X = juan, Y = david ? ; no ?- X = Y, grandfather_of(X, Y). no ?- grandfather_of(X, Y), X = Y. no

**Problem 2.5** (page ):

grandmother_of(L,M):- mother_of(L,N), father_of(N,M). grandmother_of(X,Y):- mother_of(X,Z), mother_of(Z,Y).

**Problem 2.6** (page ):
Symmetry of relationships can, of course, be achieved by duplicating
the predicates (facts, in this case) which express this relationship,
i.e., adding the following two facts:

resistor(n1, power). resistor(n2, power).But this is not a good solution: changes to the database will have to be duplicated. Writing a bridge predicate is much better. In this case, and in order not to change the program dealing with the circuits, we will rewrite the definition of

resistor(A, B):- rst(A, B). resistor(A, B):- rst(B, A). rst(power, n1). rst(power, n2).

**Problem 3.1** (page ):
Both queries loop forever, and neither solution nor failure is
reached. The cause is the absence of a test for non-negativity of
the argument. Thus, the call `?- nt(3.4).` has, in successive
invocations, the arguments `2.4`, `1.4`, `0.4`,
`-1.4`, `-2.4`, etc., and the recursion never stops.
The call `?- nt(-8).` starts directly in the negative case.

**Problem 3.2** (page ):

odd(1). odd(N+2):- gtlin(N+2, 1), odd(N).

**Problem 3.3** (page ):

odd(N):- even(N+1).

**Problem 3.4** (page ):

multiple(0, B). multiple(A, B):- gtlin(A, 0), multiple(A - B, B).

**Problem 3.5** (page ):

even(X):- multiple(X, 2). odd(X):- multiple(X + 1, 2).

**Problem 3.6** (page ):

congruent(M, N, K):- int(M), int(N), int(K), remainder(M, K, R), remainder(N, K, R). remainder(X, Y, X):- ltlin(X, Y). remainder(X, Y, Z):- gelin(X, Y), remainder(X -Y, Y, Z).

**Problem 3.7** (page ):

better_E(N, E4*4):- better_E(N, Sign, E4). better_E(1, 1, 1). better_E(N, Sign, Sign/N + RestE):- gtlin(N, 1), better_E(N-1, -Sign, RestE).

**Problem 3.8** (page ):

fib(N, F):- fib(N, 0, 1, F). fib(0, 0, 1, 0). fib(1, _Prev, F, F). fib(N, Prev, Curr, Final):- gtlin(N, 1), fib(N - 1, Curr, Prev + Curr, Final).

The proposed query and its answer are:

?- fib(1000, F). F = 434665576869374564356885276750406258025646605173717804024817290895365554 179490518904038798400792551692959225930803226347752096896232398733224711 61642996440906533187938298969649928516003704476137795166849228875.

**Problem 3.10** (page ):
The duration of the project is not actually minimized. The queries
in the example minimize the resource consumption after minimizing
the project length--thus giving priority to finishing the project
as soon as possible. Reversing the calls will make resource
consumption as small as possible, and then try to make the task
length as short as it can.

**Problem 3.11** (page ):
Yes, there are repeated solutions--or not? From the point of view
of the user, if `A` has dinner with `B`, then it is
clear the `B` is having dinner with `A`. But it can be
argued they are not repeated: they bind different variables. We say
they are repeated only because of our perception dictates that going
for dinner is symmetrical, and does not need to be repeated. Which
is actually the way around we thought of being friends. Everything
depends on whether we are consulting or retrieving data.

``Why'' is easier. Duplicated or too much solutions are always
produced by alternative clauses giving several paths for the
solution, or too few constraints leaving too much freedom to the
variables. In this case it is `spouse/2` which causes the
``excess'' of answers.

**Problem 3.12** (page ):

even(z). even(s(s(E))):- even(E).

**Problem 3.13** (page ):

times(z, _, z). times(s(X), Y, Z):- plus(Y, Z1, Z), times(X, Y, Z1). exp(z, _, s(z)). exp(s(N), Y, Z):- exp(N, Y, Z1), times(Y, Z1, Z). factorial(z, s(z)). factorial(s(N), F):- factorial(N, F1), times(s(N), F1, F). minimum(z, s(_), z). minimum(s(_), z, z). minimum(z, z, z). minimum(s(A), s(B), s(M)):- minimum(A, B, M). ltn(z, s(_)). ltn(s(A), s(B)):- ltn(A, B).

**Problem 3.14** (page ):
The query behaves as follows:

?- member(gogo, L). L = [gogo|_] ? ; L = [_,gogo|_] ? ; L = [_,_,gogo|_] ? ; L = [_,_,_,gogo|_] ? ; L = [_,_,_,_,gogo|_] ? . . .The answers returned are, in fact, the most general possible.

**Problem 3.15** (page ):
A possible solution is the following query:

?- append(Xs, [_], [1|Xs]), Xs = [X1, X2, X3, X4].

The `size/1` constraint of *Prolog IV* is simulated by explicitly
writing a list of four variables. This query solves the problem, but
falls into an infinite failure (i.e., an endless loop trying to find
more solutions), due to backtracking
generating lists of `1`s. Putting at the beginning the
generation of the list `Xs` solves this problem (remember that
a property of constraints, unlike algorithmic solving, is the
independence or the order in which they are generated):

?- Xs = [X1, X2, X3, x4], append(Xs, [_], [1|Xs]).

The query is automatically solved as follows: suppose we are dealing
with a list `Xs` of length 4; let us denote its elements (free
variables, at the beginning) as `Xs = [X1, X2, X3, X4]`. Then
`[1|Xs]` is `[1, X1, X2, X3, X4]`, and `Xs o [_]`
is `[X1, X2, X3, X4, _]`. Equating these two lists generates
the following:

1 | = | X1 |

X1 | = | X2 |

X2 | = | X3 |

X3 | = | X4 |

X4 | = | _ |

from which every element of the list is `1`.

**Problem 3.16** (page ):
The second implementation runs in time linear with the length of the
list to be reversed. This is so because that list is traversed
downwards only once, and when the end of the list is found, the
answer (in the second argument) is unified with the output argument
(the third one).

**Problem 3.17** (page ):

len([], z). len([X|Xs], s(L)):- len(Xs, L).

suffix(S, L):- append(_, S, L). prefix(P, L):- append(P, _, L).

Alternative solution:

suffix(X, X). suffix(S, [X|Xs]):- suffix(S, Xs). prefix([], Xs). prefix([X|P], [X|Xs]):- prefix(P, Xs).

sublist(S, L):- prefix(P, L), suffix(S, P).

palindrome(L):- reverse(L, L).

evenodd([], [], []). evenodd([E1], [], [E1]). evenodd([E1, E2|Rest], [E2|Evens], [E1|Odds]):- evenodd(Rest, Evens, Odds).

Alternative solution:

evenodd([], [], []). evenodd([E|Rest], Evens, [E|Odds]):- evenodd(Rest, Odds, Evens).

select(E, L1, L2):- append(Head, [E|Rest], L1), append(Head, Rest, L2).

Alternative solution:

select(X, [X|Xs], Xs). select(X, [Y|Xs], [Y|Ys]):- select(X, Xs, Ys).

**Problem 3.18** (page ):
Simply duplicate the element when it is found in the list (third
clause):

insert_ordlist(Element, [], [Element]). insert_ordlist(Element, [This|Rest], [This, Element|Rest]):- precedes(This, Element). insert_ordlist(Element, [Element|Rest], [Element, Element|Rest]). insert_ordlist(Element, [This|Rest], [This|NewList]):- precedes(Element, This), insert_ordlist(Element, Rest, NewList).

**Problem 3.19** (page ):

Note that the item of the current non-empty node is *consed* to
the list coming from the right subtree before appending the left and
right lists, in order to make it appear in between them.

in_order(void, []). in_order(tree(X, Left, Right), InOrder):- in_order(Left, OrdLft), in_order(Right, OrdRght), append(OrdLft, [X|OrdRght], InOrder).

The need of placing an element at the end of a list makes necessary the use of two appends. The item of information in the current non-empty node is appended to the list from the traversal of the rightmost tree to minimize the work.

post_order(void, []). post_order(tree(X, Left, Right), Order):- post_order(Left, OrdLft), post_order(Right, OrdRght), append(OrdRght, [X], OrderMid), append(OrdLft, OrderMid, Order).

**Problem 4.1** (page ):
The unification (both in the containing and in the contained term) is
made in the very first clause, which reads

subterm(Term, Term).

**Problem 4.2** (page ):
The same predicate `add_matrices/3` is used for matrices and
numbers: there is a clause for each case.

add_matrices(M1, M2, M3):- number(M1), number(M2), M3 is M1 + M2. add_matrices(M1, M2, M3):- functor(M1, mat, N), N > 0, functor(M2, mat, N), functor(M3, mat, N), add_matrices(N, M1, M2, M3). add_matrices(0, _, _, _). add_matrices(N, M1, M2, M3):- N > 0, arg(N, M1, A1), arg(N, M2, A2), arg(N, M3, A3), add_matrices(A1, A2, A3), N1 is N - 1, add_matrices(N1, M1, M2, M3).

**Problem 4.3** (page ):
Ensure that the goal in `not/1` is ground:

unmarried_student(X):- student(X), not(married(X)). student(joe). married(john).

1998-12-03