Lists, Negation, and Symmetric Transitive Relationships

List Processing in Prolog

A list is a special term of the form [term, term, ..., term] or [].

Prolog provides a built-in member predicate for lists:

?- member(3, [1, 2, 3, 4, 5]).
true .

?- member(X, [1, 2, 3, 4, 5]).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;
X = 5.

?- member(X, []).
false.

?- \+ member(3, [1, 2, 3, 4, 5]).
false.

Negation in Prolog

In Prolog \+ means "not". More accurately, "\+ pred" is true if no proof of "pred" can be found.

Defining List Predicates

The term [X | Y] is a list with head = X and tail = Y. For example:

?- [X | Y] = [1, 2, 3, 4, 5].
X = 1,
Y = [2, 3, 4, 5].

We can use this to define predicates for accessing and modifying lists: ListPreds.pl.

Defining symmetric and transitive relationships in Prolog

Assume the Simpsons adopted some of the Griffin children:

sib1(bart, lisa).

sib1(lisa, maggie).

sib1(maggie, stewie).

sib1(stewie, chris).

Let's define sib2 as the symmetric closure of sib1:

sib2(X, Y) :- sib1(X, Y) ; sib1(Y, X).

We then define sibling as the transitive closure of sib2:

sibling(X, Y) :- sib2(X, Y).

sibling(X, Y) :- sib2(X, Z), sibling(Z, Y).

Unfortunately, this leads to infinite loops.

Version  2

To prevent infinite loops and repeated solutions, we must use an internal list to keep track of all answers we have seen so far: kinship.pl.

?- sibling(lisa, X).
X = maggie ;
X = bart ;
X = stewie ;
X = chris ;
false.

?- sibling(X, lisa).
X = bart ;
X = maggie ;
X = stewie ;
X = chris ;
false.