序言 : get the opposite result

我有以下代码:

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

最佳答案

让我们首先从逻辑上思考列表中的“邻居”意味着什么:在什么情况下 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 中，上述内容变为:

( 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)中引起的大量困惑。

关于序言 : get the opposite result，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39336904/