4

我有以下代码：

neighbor(C1, C2, [C1, C2|L]).
neighbor(C1, C2, [C2, C1|L]).
neighbor(C1, C2, [H|L]) :- neighbor(C1, C2, L).

not_neighbors(C5, C2, E, R) :-
    not_neighbor(C5, C2, E).

not_neighbors(C5, C2, E, R) :-
    not_neighbor(C5, C2, R).

/* THIS DON'T WORK */
not_neighbor(C5, C2, E) :-
    \+ neighbor(C5, C2, E).

或者 ：

same_position(I, J, [I|U], [J|V]).
same_position(I, J, [M|U], [N|V]) :-
    I \== M,   % optimisation
    J \== N,   % optimisation
    same_position(I, J, U, V).

/* THIS DON'T WORK */
not_under(C4, C1, R, E) :-
    \+ same_position(C4, C1, R, E).

我知道问题是否定的，我想得到相反的结果，same_position例如。

M. @CapelliC 建议我使用dif/2，但我不知道如何在我的具体示例中应用它。

4

2 回答 2

3

让我们首先从逻辑上思考一下列表中的“邻居”意味着什么：在什么情况下A， B列表中的相邻元素是什么？

回答：如果列表具有以下形式[...,X,Y,...]并且至少满足以下一项：

  • A = X 和 B = Y
  • A = Y 和 B = X。

用逻辑术语来说：( A = X∧ B = Y) ∨ ( A = Y∧ B = X)。

我们想说明与此相反的情况，即否定公式：

   ¬ ( ( A = X∧ B = Y) ∨ ( A = Y∧ B = X) ) ≡

≡ ¬ ( A = X∧ B = Y) ∧ ¬ ( A = Y∧ B = X) ≡

≡ (¬ A = X∨ ¬ B = Y) ∧ (¬ A = Y∨ ¬ B = X) ≡

≡ ( A≠ X∨ B≠ Y) ∧ ( A≠ Y∨ B≠ X)

谁会想到德摩根定律有任何实际应用，对吧？

为了在 Prolog 中声明X≠ Y，我们使用强大的dif/2约束，正如@CapelliC 已经建议的那样。如果它的论点是不同的术语，dif/2则为真。它是一个纯谓词，可以在各个方向正确工作。如果您的 Prolog 系统还没有提供它，请确保让您的供应商知道您需要它！在那之前，如有必要，您可以用 来近似它。iso_dif/2

在 Prolog 中，上述内容因此变为：

（差异（A，X）；差异（B，Y）），（差异（A，Y）；差异（B，X））

因为(',')/2表示连接，并且(;)/2表示分离。

所以我们有：

not_neighbours(_, _, [])。
not_neighbours(_, _, [_])。
not_neighbours(A, B, [X,Y|Rest]) :-
        （差异（A，X）；差异（B，Y）），
        （差异（A，Y）；差异（B，X）），
        not_neighbours(A, B, [Y|Rest])。

一些测试用例让我们对谓词的正确性更有信心：

?- not_neighbours(a, b, [a,b])。
错误的。

?- not_neighbours(A, B, [A,B])。
错误的。

?- not_neighbours(A, B, [_,A,B|_])。
错误的。

?- not_neighbours(A, B, [_,B,A|_])。
错误的。

?- not_neighbours(a, b, [_,a,c,_])。
真的 。

请注意，如果所有参数都是变量，则此定义也可以正常工作，我们称之为最一般的情况。

该解决方案的一个缺点是(;)/2创建了许多替代方案，其中许多根本不重要。我们可以通过另一个代数等价来显着提高效率，让我们摆脱不需要的替代方案：

¬ A ∨ B ≡ A → B

因此，在我们的例子中，我们可以将 (¬ A = X∨ ¬ B = Y) 写为A = X → B≠ Y。

我们可以用强大的元谓词在 Prolog中表达含义：if_/3

impl(A, B) :- if_(A, B, true).

所以我们可以声明式地等价地把我们的解决方案写成：

not_neighbours(_, _, [])。
not_neighbours(_, _, [_])。
not_neighbours(A, B, [X,Y|Rest]) :-
        实现（A=X，差异（B，Y）），
        impl(B=X, 差异(A, Y)),
        not_neighbours(A, B, [Y|Rest])。

示例查询：

?- not_neighbours(a, b, [x,y])。
真；
错误的。

还有一个更一般的情况：

?- not_neighbours(a, b, [X,Y])。
X = 一个，
差异（Y，b）；
X = b,
差异（Y，一）；
差异（X，b），
差异（X，一）；
错误的。

您可以使用此谓词来检查和生成答案。尝试例如迭代深化以公平枚举所有答案：

?- length(Ls, _), not_neighbours(A, B, Ls).

值得注意的是，纯逻辑推理因此将我们引向了一个通用且高效的 Prolog 程序。

dif/2起初你可能觉得不寻常，因为它出现在第一个 Prolog 系统中，然后被一些供应商忽略了一段时间。如今，dif/2作为一个重要的内置谓词，在越来越多的实现中（再次）变得可用，它允许您以声明方式声明两个术语是不同的。使用dif/2.

于 2016-09-05T21:08:37.270 回答
1

如果要生成非邻居，\+请不要按照定义semidet 进行操作，并且从不绑定变量。你需要一些可以构建答案的东西。一种选择是生成所有对，然后使用您的\+ neighbor(...)来过滤非邻居。一个直接的建设性方法也不是那么难，尽管需要有两个排序使代码有点复杂：

not_neighbor(C1, C2, List) :-
    append(_, [C10,_|Postfix], List),
    member(C20, Postfix),
    swap(C1,C2, C10,C20).

swap(X,Y, X,Y).
swap(X,Y, Y,X).

见http://swish.swi-prolog.org/p/njssKnba.pl

于 2016-09-05T21:03:52.797 回答