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/2 (and the part of the database which stores the information about resistors) to become

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. gogo is member of the list L either being in the first, second, etc. position in that list, which continues indefinitely. The first answer is returned by the first clause (the fact) of member/2; on backtracking, alternative solutions are returned by prepending free variables to the list.

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

$\mathbf\therefore$