Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Prolog repeating solutions on symmetric relations

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).?

like image 251
tcigler Avatar asked Apr 26 '14 17:04

tcigler


2 Answers

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.

like image 167
lurker Avatar answered Oct 14 '22 11:10

lurker


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.
like image 41
false Avatar answered Oct 14 '22 10:10

false