简单传递性检查的不必要谓词定义？

Question

对于给定的事实：

trust_direct(p1, p2).
trust_direct(p1, p3).
trust_direct(p2, p4).
trust_direct(p2, p5).
trust_direct(p5, p6).
trust_direct(p6, p7).
trust_direct(p7, p8).
trust_direct(p100, p200).

这个解决方案：

trusts(A, B) :-
        trust_direct(A, B).
trusts(A, C) :-
        trust_direct(A, B),
        trusts(B, C).

...用于改善中描述的堆栈溢出问题。

解决方案本身就像一个魅力。但是，我对加倍的trust_direct(A, B)感到困惑。为什么这是必要的？

trusts(A, C) 谓词不应该已经涵盖了 trust_direct(A, B) 关系吗？

Answer 1

这是一个很好的问题！

为了说明原因，我使用以下定义启用声明式调试：

:- op(950,fy, *).

*_.

我现在可以将 * 放在任何目标前面，以 概括它 。声明地，这意味着我可以简单地忽略目标（回想一下，目标始终是约束，限制任何解决方案）。我当然也可以简单地 comment goals away，但这对于子句主体的 last goal 来说效果不佳。

现在考虑你的定义：

trusts(A, B) :-
        trust_direct(A, B).
trusts(A, C) :-
        trust_direct(A, B),
        trusts(B, C).

现在，为了回答您非常合理的问题，假设我们只有有第二个子句，即：

trusts(A, C) :-
        trust_direct(A, B),
        trusts(B, C).

为了让我们的生活更简单，我现在概括这个定义如下：

trusts(A, C) :-
        * trust_direct(A, B),
        trusts(B, C).

这比前面的片段更通用：If trusts(X, Y) 对任何 X 和Y 与前面的代码片段，则 trusts(X, Y) 也符合此定义。

我使用了 ~~删除线~~ 文本来指示不相关的目标（因为它们被概括掉了）。所以，这在声明上等同于：

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

让我们宣读：

trusts(A, C) holds if trusts(B, C) holds.

但是什么时候 trusts(B, C) 成立？当然（通过简单地再次应用定义），if trusts(B', C') 成立。 什么时候 这成立吗？当然（通过简单地应用定义），if......等等。从这里，很容易看出我们永远不会找到任何A 和 C，因此 trusts(A, C) 总成立。

而且尽管事实上这实际上是原始条款的 明显更通用 的版本！所以，满足更具体的版本没有丝毫希望！

这回答了我们的问题：我们需要一个 实际成立 的案例，还有什么比谈论 trust_direct/2 更简单的，这实际上是最简单的案例我们肯定期望更一般的关系 trusts/2 也持有 .

因此很自然地从这个案例开始说：

If trust_direct(X, Y) holds then trusts(X, Y) holds.

序言中：

trusts(X, Y) :- trust_direct(X, Y).

这正是您的第一个子句！

简单传递性检查的不必要谓词定义？

Unnecessary predicate definition for simple transitivity checkup?

prolog

transitivity