序言 : get the opposite result

Question

我有以下代码:

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 但我不知道如何将其应用到我的具体示例中。

Answer 1

让我们首先从逻辑上思考列表中“邻居”的含义:在什么情况下 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 为 true 当且仅当其参数是不同术语。它是一个纯谓词，并且在所有方向上都能正确工作。如果您的 Prolog 系统尚未提供它，请务必让您的供应商知道您需要它!在此之前，如有必要，您可以使用 iso_dif/2 来近似它。

在 Prolog 中，上面的内容就变成了:

( dif(A, X) ; dif(B, Y) ), ( dif(A, Y) ; dif(B, X) )

because (',')/2 denotes conjunction, and (;)/2 denotes disjunction.

So we have:

not_neighbours(_, _, []).not_neighbours(_, _, [_]).not_neighbours(A, B, [X,Y|Rest]) :-        ( dif(A, X) ; dif(B, Y) ),        ( dif(A, Y) ; dif(B, X) ),        not_neighbours(A, B, [Y|Rest]).

A few test cases make us more confident about the predicate's correctness:

?- not_neighbours(a, b, [a,b]).false.?- not_neighbours(A, B, [A,B]).false.?- not_neighbours(A, B, [_,A,B|_]).false.?- not_neighbours(A, B, [_,B,A|_]).false.?- not_neighbours(a, b, [_,a,c,_]).true .

Note that this definition works correctly also if all arguments are variables, which we call the most general case.

A drawback of this solution is that (;)/2 creates many alternatives, and many of them do not matter at all. We can make this significantly more efficient by another algebraic equivalence that lets us get rid of unneeded alternatives:

¬ A ∨ B ≡ A → B

So, in our case, we can write (¬ A = X ∨ ¬ B = Y) as A = X →B≠Y.

We can express implication in Prolog with the powerful if_/3 meta-predicate:

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

因此我们可以以声明方式等效地将我们的解决方案编写为:

not_neighbours(_, _, []).not_neighbours(_, _, [_]).not_neighbours(A, B, [X,Y|Rest]) :-        impl(A=X, dif(B, Y)),        impl(B=X, dif(A, Y)),        not_neighbours(A, B, [Y|Rest]).

Sample query:

?- not_neighbours(a, b, [x,y]).true ;false.

And a more general case:

?- not_neighbours(a, b, [X,Y]).X = a,dif(Y, b) ;X = b,dif(Y, a) ;dif(X, b),dif(X, a) ;false.

You can use this predicate for checking and generating answers. Try for example iterative deepening to fairly enumerate all answers:

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

值得注意的是，纯粹的逻辑推理使我们得到了一个通用的且高效的 Prolog 程序。

dif/2 乍一看可能对您来说很不寻常，因为它出现在第一个 Prolog 系统中，然后一度被一些供应商忽略。如今，dif/2 在越来越多的实现中(再次)成为可用的，作为一个重要的内置谓词，它允许您以声明方式声明两个术语是不同的。使用 dif/2 可以避免其不纯的替代方案通常在 Prolog 类(class)中引起的巨大困惑。