如何表达传递关系

Question

我想表达一种传递关系。如果 A 引用 B，B 引用 C，那么 A 引用 C。我有这个：

proj(A).
proj(B).
proj(C).
ref(A,B).
ref(B,C).

当我使用 proj(A) 查询时，我得到：

[46] ?-proj(A).
A = _639

“_639”是什么意思？我期待是或否，并得到了那种陌生感。我需要添加一条规则：

ref(A,C). 并得到 YES。理想情况下，如果可能的话，我想展示这种关系是如何产生的：(A => B => C).

Answer 1

_639 是一个未实例化的匿名变量。你的 "facts" 有变量而不是原子。例如：

proj(A).   % This has a variable A and means "any A is a project"

所以如果我查询：

:- proj(X).
X = _blah    % anonymous variable: anything is a project!

你需要原子：

proj(a).
proj(b).

查询结果：

:- proj(X).
X = a ;
X = b

如果你有：

ref(a,b).
ref(b,c).

然后，在 Prolog 中表达传递性属性的最简单方法是声明 rule（或所谓的 predicate 在序言中）：

ref(A,C) :- ref(A,B), ref(B,C).

这表示，如果 ref(A,B) 为真且 ref(B,C) 为真，则 ref(A,C) 为真。。运行查询：

:- ref(a,c).
true ;
Out of stack

或者：

:- ref(a,X).
X = b ;
X = c ;
Out of stack

这听起来合乎逻辑，但有一个问题：由于自引用，您可能会陷入循环。一个简单的解决方法是使规则名称与事实名称不同：

refx(A, B) :- ref(A, B).
refx(A, C) :- ref(A, B), refx(B, C).

现在如果我查询：

:- refx(a, b).
true ;
no

:- refx(a, c).
yes

:- refx(a, X).
X = b ;
X = c
yes

等

但是，如果事实包含自反或交换关系，则仍然存在终止问题的情况。例如：

ref(a,b).
ref(b,a).
ref(b,c).

在这种情况下，对 refx(a, b) 的查询会产生：

| ?- refx(a, b).
true ? ;
true ? ;
true ? ;
...

正如@lambda.xy.x 指出的那样，这可以通过跟踪我们去过的地方并避免重复 "visits":

来解决

refx(X, Y) :-
    refx(X, Y, []).

refx(X, Y, A) :-
    ref(X, Y),
    \+ memberchk((X, Y), A).   % Make sure we haven't visited this case
refx(X, Y, A) :-
    ref(X, Z),
    \+ memberchk((X, Z), A),   % Make sure we haven't visited this case
    refx(Z, Y, [(X,Z)|A]).

现在我们以 refx(a,b) 结束并成功一次：

| ?- refx(a,b).
true ? ;
no
| ?-

并且refx(X, Y)产生了所有的解决方案（虽然，由于多次成功而重复了一些）：

| ?- refx(X, Y).

X = a
Y = b ? ;

X = b
Y = a ? ;

X = b
Y = c ? ;

X = a
Y = a ? ;

X = a
Y = c ? ;

X = b
Y = b ? ;

X = b
Y = c ? ;

(2 ms) no

如何表达传递关系

How to express a transitive relationship

prolog

transitive-closure