Negația ca eșec (not/1, \+)

În universul închis al Prolog-ului, „nu se poate demonstra P” este tratat ca „P e fals”. Așa implementăm negația — prin eșec.

Sumar

În Prolog toate demonstrațiile sunt făcute într-un univers închis. Dacă nu putem demonstra o proprietate P, înseamnă doar că nu am reușit să îi găsim demonstrația — nu că P este falsă.

Negația ca eșec (negation as failure) este modul pragmatic prin care Prolog tratează ¬P: not(P) este adevărat dacă P nu se poate demonstra.

Sintaxă

not(P).      % SWI-Prolog, forma clasică
\+ P.        % forma ISO standard, echivalentă

Ambele formulări sunt acceptate în SWI-Prolog. Materialele folosesc preponderent not/1.

Exemplu

?- member(a, [a, b, c]).
true.

?- not(member(d, [a, b, c])).
true.

?- not(member(a, [a, b, c])).
false.

Idiom — filtru de duplicate

Din breviar (remove_duplicates/2):

remove_duplicates([], []) :- !.
remove_duplicates([H | T], [H | TR]) :-
    not(member(H, T)),
    remove_duplicates(T, TR), !.
remove_duplicates([_ | T], TR) :-
    remove_duplicates(T, TR).

Păstrează H în rezultat doar dacă nu mai apare în coadă.

Idiom — căutare evitând nodurile vizitate

Din breviar.pl (BFS):

extend([Node | Path], NewPath) :-
    findall([NewNode, Node | Path],
            (succesor(Node, NewNode), not(member(NewNode, [Node | Path]))),
            NewPath).

not(member(NewNode, ...)) previne ciclarea — nu extindem drumul cu un nod deja prezent.

Idiom — „toate elementele ≠”

all_different([]) :- !.
all_different([H | T]) :-
    not(member(H, T)),
    all_different(T).

(Din Lab 4, word puzzle.)

Capcana universului închis

parent_of(sandra, sam).
parent_of(ben, sam).

% Nu există parent_of(alex, X). Prolog nu știe nimic despre alex.
?- not(parent_of(alex, sam)).
true.       % — dar nu fiindcă am demonstrat că NU e părinte;
            %   ci fiindcă nu putem demonstra că este.

Negația ca eșec nu e aceeași cu negația clasică. Folosește-o conștient.