Control & the database · Lesson 28 of 43

Negation as failure

What `\+` really means, and why goal order matters.

Prolog's \+ Goal ("not provable") succeeds when Goal fails, and fails when Goal succeeds. It's negation as failure: Prolog doesn't know the goal is false, it just can't prove it. This only makes sense under the closed-world assumption you met in lesson one.

male(tom). male(bob). male(carl).
female(liz).
married(tom). married(liz).

% a bachelor is a male who is not married
bachelor(X) :- male(X), \+ married(X).

?- \+ married(bob)

?- \+ married(tom)

?- bachelor(X)

Order matters: negate only when things are bound

\+ can't generate values, it only tests. If the variable is still unbound when \+ runs, the result is probably not what you meant. Swap the two goals:

bad_bachelor(X) :- \+ married(X), male(X).

?- bad_bachelor(X)

Why false? With X unbound, \+ married(X) asks "is there no X that is married?", there is (tom), so the negation fails before male(X) gets a chance.

Rule: put the generating goals first, the negated test last.

Not-equal has the same trap

X \= Y is also a test ("these can't be unified") and behaves badly with unbound variables:

?- X \= a, X = b

?- X = b, X \= a

SWI-Prolog's dif/2 is the order-independent alternative: it delays the check until both sides are known well enough.

?- dif(X, a), X = b

?- dif(X, a), X = a

?- dif(X, a)

Negation and "everything not listed"

\+ is how you write "for all except…" and "no such thing exists" queries:

parent(tom, bob).
parent(bob, ann).
parent(bob, pat).

has_children(X) :- parent(X, _).
childless(P) :- member(P, [tom, bob, ann, pat]), \+ has_children(P).

?- childless(P)

Exercise: Only children

The family facts are loaded. Define only_child(C): C has a parent, and that parent has no other child. Remember, generate first, test last.