Simple prolog program returns false too early

2
votes

It's been a while since I've programmed in Prolog. Today, I tried to make a simple program. It lists some facts of who belongs to the same family. If two people belong to the same family, they cannot give eachother gifts. I want to get all the people (or at least one person) to whom someone is allowed to give a gift.

family(john, jack).
family(matt, ann).
family(ann, jack).
family(jordan, michael).
family(michael, liz).

sameFamily(X, Y) :-
  family(X, Y).
sameFamily(X, X) :-
  false.
sameFamilySym(X, Y) :-
  sameFamily(X, Y).
sameFamilySym(X, Y) :-
  sameFamily(Y, X).
sameFamilyTrans(X, Z) :-
  sameFamilySym(X, Y),
  sameFamilySym(Y, Z).

gift(X, Y) :-
  not(sameFamilyTrans(X, Y)).

Some queries if sameFamilyTrans/2 return false when they should in fact return true.

sameFamilyTrans/2 is obviously wrong. I think I need to keep a list of intermediate transitivities. Something like this:

sameFamilyTrans(X, Z, [Y|Ys]) :-
  sameFamilySym(X, Y, []),
  sameFamilyTrans(Y, Z, Ys).

But then I don't know how to call this.

P.S. I am using SWI-Prolog, if that makes any difference.

2
prolog

2 Answers

4
votes

Yes, you were on the right track. The trick is to call the transitive closure with an empty accumulator, and check in each step whether a cycle is found (i.e., whether we have seen this member of the family before. As "false" has pointed out, the persons need to be instantiated already before going into the not, though.

So in sum, this works:

family(john, jack).
family(matt, ann).
family(ann, jack).
family(jordan, michael).
family(michael, liz).

sameFamily(X, Y) :-
  family(X, Y).
sameFamilySym(X, Y) :-
  sameFamily(X, Y).
sameFamilySym(X, Y) :-
  sameFamily(Y, X).

sameFamilyTrans(X, Y, Acc) :-
  sameFamilySym(X, Y),
  not(member(Y,Acc)).

sameFamilyTrans(X, Z, Acc) :-
  sameFamilySym(X, Y),
  not(member(Y,Acc)),
  sameFamilyTrans(Y, Z, [X|Acc]).

person(X) :- family(X, _).
person(X) :- family(_, X).

gift(X, Y) :-
  person(X),
  person(Y),
  X \= Y,
  not(sameFamilyTrans(X, Y, [])).

A bit of background: Transitive closure is not actually first-order definable (cf. https://en.wikipedia.org/wiki/Transitive_closure#In_logic_and_computational_complexity). So it can be expected that this would be a little tricky.

1
votes

Negation is implemented in Prolog in a very rudimentary manner. You can essentially get a useful answer only if a negated query is sufficiently instantiated. To do this, define a relation person/1 that describes all persons you are considering. Then you can write:

gift(X,Y) :-
   person(X),
   person(Y),
   \+ sameFamily(X,Y).

There is another issue with the definition of sameFamily/2.