Prolog : get the opposite result

Question

I have the following code :

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

Or :

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

I know the problem is the negation and I want to get the opposite result of same_position for example.

M. @CapelliC suggested me to use dif/2 but I don't know how to apply this on my specific example.

Sry, here my "neighbor" fonctions : neighbor(C1, C2, [C1, C2|L]). neighbor(C1, C2, [C2, C1|L]). neighbor(C1, C2, [H|L]) :- neighbor(C1, C2, L). — E. Yas, Sep 05 '16 at 19:59

score 3 · Answer 1 · edited May 23 '17 at 12:32

Let us first think logically about what it means to be "neighbours" in a list: In what cases are A and B neighbouring elements in a list?

Answer: If the list is of the form [...,X,Y,...] and at least one of the following holds:

A = X and B = Y
A = Y and B = X.

In logical terms: ( A = X ∧ B = Y) ∨ (A = Y ∧ B = X).

We want to state the opposite of this, which is the negated formula:

¬ ( ( 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)

Who would have thought that De Morgan's laws had any practical application, right?

To state X ≠ Y in Prolog, we use the powerful dif/2 constraint, exactly as @CapelliC has already suggested. dif/2 is true iff its arguments are different terms. It is a pure predicate and works correctly in all directions. If your Prolog system does not yet provide it, make sure to let your vendor know that you need it! Until then, you can approximate it with iso_dif/2, if necessary.

In Prolog, the above thus becomes:

( 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 &rightarrow; B

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

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

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

And so we can declaratively equivalently write our solution as:

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

Remarkably, pure logical reasoning has thus led us to a general and efficient Prolog program.

dif/2 may at first appear unusual to you, because it appeared in the very first Prolog system and was then for a time ignored by some vendors. Nowadays, dif/2 is becoming available (again) in an increasing number of implementations as an important built-in predicate that allows you to declaratively state that two terms are different. The massive confusion that its impure alternatives usually cause in Prolog courses can be avoided with dif/2.

score 1 · Answer 2 · answered Sep 05 '16 at 21:03

If you want to generate the not-neighbors, \+ won't do as it is by definition semidet and never binds a variable. You need something that constructs answers. One option is to generate all pairs and then use your \+ neighbor(...) to filter the non-neighbors. A direct constructive approach isn't that hard either, although the need to have both orderings complicate the code a little:

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

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

Prolog : get the opposite result

2 Answers2