简单传递性检查的不必要谓词定义? [英] Unnecessary predicate definition for simple transitivity checkup?

问题描述

对于给定的事实:

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).信托(A，C):-trust_direct(A, B),信托(B，C).

...用于改善我在 Prolog 中描述的堆栈溢出问题:检查简单事实的传递性.

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

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

解决方案

这是个好问题！

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

<块引用><预>:- op(950,fy, *).*_.

我现在可以将 * 放在任何目标前面以概括.声明性地，这意味着我可以简单地忽略目标(回想一下，目标始终是一个约束，限制了任何解决方案).我当然也可以简单地评论目标，但这对于子句正文的最后目标效果不佳.

现在考虑你的定义:

<预>信托(A，B):-trust_direct(A, B).信托(A，C):-trust_direct(A, B),信托(B，C).

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

<预>信托(A，C):-trust_direct(A, B),信托(B，C).

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

<预>信托(A，C):-* trust_direct(A, B),信托(B，C).

这比之前的代码片段更通用:If trusts(X, Y) 对任何 X 成立code> 和 Y 与前面的片段，然后 trusts(X, Y) 也 与此定义一致.

我使用了 strikeout 文本来表示不相关的目标(因为它们被概括掉了).所以，这在声明上等同于:

<预>信托(A，C):-信托(B，C).

让我们声明性地阅读:

<块引用>

trusts(A, C) 持有 if trusts(B, C) 持有.

但是什么时候trusts(B, C) 成立?当然(通过简单地再次应用定义)，if trusts(B', C') 成立.什么时候会这样?当然(通过简单地应用定义)，if ... 等.从这里，很容易看出我们将永远找不到任何 A 和 C 以便 trusts(A, C) 保持全部.

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

这回答了我们的问题:我们需要一个实际成立的案例，还有什么比谈论 trust_direct/2 更简单，这是真正最简单的案例我们绝对期待更普遍的关系trusts/2也.

因此很自然地从这个案例开始，然后说:

<块引用>

如果 trust_direct(X, Y) 成立则 trusts(X, Y) 成立.>

在序言中:

<预>信任(X，Y):- trust_direct(X，Y).

这正是你的第一个子句！

For the given facts:

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

This solution:

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

...was given to improve my stack overflow issue described in Prolog: check transitivity for simple facts.

The solution itself works like a charm. However, I am confused by the doubled trust_direct(A, B). Why is this necessary?

Shouldn't the trusts(A, C) predicate already cover the trust_direct(A, B) relationship?

解决方案

That's a great question!

To show the reason for this, I use the following definition to enable declarative debugging:

:- op(950,fy, *).

*_.

I can now put * in front of any goal to generalize it away. Declaratively, this means that I can simply ignore the goal (recall that a goal is always a constraint, restricting any solution). I could of course also simply comment goals away, but that does not work nicely for the last goal of a clause body.

Now consider your definition:

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

Now, to answer your very legitimate question, suppose we only had the second clause, i.e.:

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

To make our life simpler, I now generalize this definition as follows:

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

This is more general than the immediately preceding snippet: If trusts(X, Y) holds for any X and Y with the preceding snippet, then trusts(X, Y) also holds with this definition.

I have used strikeout text to indicate goals that are not relevant (because they are generalized away). So, this is declaratively equivalent to:

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

Let us read this declaratively:

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

But when does trusts(B, C) hold? Of course (by simply applying the definition again), if trusts(B', C') holds. And when does this hold? Of course (by simply applying the definition), if ... etc. From here, it is easy to see that we will never find any A and C so that trusts(A, C) holds at all.

And that despite the fact that this is actually the significantly more general version of the original clause! Thus, there is not the slightest hope to satisfy the more specific version!

This answers our question: We need a case that actually holds, and what could be simpler than talking about trust_direct/2, which is really the simplest case in which we definitely expect the more general relation trusts/2 to hold too.

It is thus very natural to start with this case, and say:

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

In Prolog:

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

And that's exactly your first clause!

这篇关于简单传递性检查的不必要谓词定义?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！