Prolog repeating solutions on symmetric relations

Question

Consider this small program:

married(bill, hillary).
spouse(X, Y) :- married(X, Y); married(Y, X).
likes(X, Y) :- spouse(X, Y).

Now I want to evaluate a goal

?- likes(X, Y).
X = bill
Y = hillary ?;
X = hillary
Y = bill
yes

Is there a way to prevent repeating on this symmetric relation when backtrack and still preserve symmetry for goals like ?- likes(hillary, X).?

lurker · Accepted Answer · 2014-04-26T22:42:06.970

Here's a way to define spouse/2:

married(bill, hillary).
married(tom, mary).
married(sam, linda).

spouse(X, Y) :-
     \+ married(X, Y) -> married(Y, X) ; married(X, Y).

So if there's no way to make married(X, Y) true, then it will try married(Y, X). Otherwise, married(X, Y).

| ?- spouse(X, Y).

X = bill
Y = hillary ? ;

X = tom
Y = mary ? ;

X = sam
Y = linda

(1 ms) yes
| ?- spouse(tom, Y).

X = tom
Y = mary

yes
| ?- spouse(X, tom).

X = mary
Y = tom

yes

It would appear on the surface that the following, slightly simpler, predicate may be equivalent, but it will not find all the solutions:

spouse(X, Y) :-
     married(X, Y) -> true ; married(Y, X).

| ?- spouse(X, Y).

X = bill
Y = hillary ? ;

(1 ms) yes
| ?-

ADDENDUM

Building on Sergey's observation:

| ?- Y = bill, spouse(X, Y).

X = hillary
Y = bill

yes

But:

| ?- spouse(X, Y), Y = bill.

no

This result is inconsistent because by confining spouse/2 to unique solutions that consider symmetrical solutions redundant, the predicate is essentially saying that only one of spouse(bill, hillary) and spouse(hillary, bill) can be true at any given time. If the first argument is pre-defined to be bill, that then means the second argument must be hillary. If neither argument is instantiated and spouse(X, Y) indicates the solution X = bill and Y = hillary, then a subsequent query of Y = bill fails.

So, again as @Sergey indicated in his comment, this kind of predicate must be used with caution, understanding that its logical meaning is somewhat limited and even self-contradictory in some contexts.

Some caution with usage is needed: `Y = bill, likes(X, Y).` will succeed, but `likes(X, Y), Y = bill.` will fail. — Sergii Dymchenko, Apr 26 '14 at 18:17
@SergeyDymchenko that "defect" may be an unavoidable side-effect of defining `spouse(X, Y)` as being true only for unique solutions in `X` and `Y` including their permutation. Once an `X` and `Y` pair are established, then their commutation is by definition false. It's really an odd way to define a `likes` or `spouse` predicate (as @false alludes to in his answer). — lurker, Apr 26 '14 at 22:13
@lurker: When you define relations, certain things simply cannot be. — false, Apr 26 '14 at 22:39

score 2 · Answer 2 · answered Apr 26 '14 at 19:52

There is no way to define a predicate such that it still retains its relational properties and fulfills your wishes, as @SergeyDymchenko observed in a comment.

It is not clear to me why you want this anyway. Maybe you want to reduce output? Then simply ask another query:

?- spouse(X,Y), X @=< Y.

Prolog repeating solutions on symmetric relations

2 Answers2