prolog - 简单的 prolog 程序过早返回 false

Question

我已经有一段时间没有用 Prolog 编程了。今天，我尝试编写一个简单的程序。它列出了一些关于谁属于同一家庭的事实。如果两个人属于同一家庭，则不能互相赠送礼物。我想要找到所有被允许赠送礼物的人(或至少一个人)。

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

某些查询如果sameFamilyTrans/2返回false，而实际上它们应该返回true。

sameFamilyTrans/2 显然是错误的。我想我需要保留一份中间传递性列表。像这样的事情:

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

但是我不知道如何调用它。

P.S.我正在使用 SWI-Prolog，如果这有什么区别的话。

Answer 1

是的，您走在正确的道路上。诀窍是用空累加器调用传递闭包，并在每一步中检查是否找到循环(即，我们以前是否见过这个家庭成员。正如“false”所指出的那样，这些人需要不过，在进入 not 之前已经实例化了。

总而言之，这是有效的:

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, [])).

一点背景知识:传递闭包实际上并不是一阶可定义的(参见 https://en.wikipedia.org/wiki/Transitive_closure#In_logic_and_computational_complexity )。因此可以预见，这会有点棘手。