Negation as Failure

Negation in Prolog is implemented based on the use of cut. Actually, negation in Prolog is the so-called negation as failure, which means that to negate p one tries to prove p (just executing it), and if p is proved, then its negation, not(p), fails. Conversely, if p fails during execution, then not(p) will succeed. The implementation of not/1 is as follows:

not(Goal) :- call(Goal), !, fail.
not(Goal).

(fail/0 is a builtin predicate which always fails. It can be trivially defined as fail:- a = b.)

not/1 is usually available as the (prefix) predicate $\backslash$+ / 1 in most Prolog systems. I.e., not(p) would be written $\backslash$+ p .

Since not(p) will try to execute p, if the execution of p does not terminate, the execution of not(p) will not terminate, either. Also, since not(p) succeeds if and only if p failed, not(p) will not instantiate any variable which could appear in p. This is not a logically sound behavior, since, from a formal point of view, not(p) should succeed and instantiate variables for each term for which p is false. The problem is that this will very likely lead to an infinite number of solutions.

But using negation with ground goals (or, at least with calls to goals which do not further instantiate free variables which are passed to them) is safe, and the programmer should ensure this to hold. Otherwise, unwanted results may show up:

unmarried_student(X):-
    not(married(X)), student(X).

student(joe).
married(john).

This program seems to suggest that joe is an unmarried student, and that joe is not an unmarried student, and indeed:

?- unmarried_student(joe).

yes
?- unmarried_student(john).

no

But, for logical consistence, asking for unmarried students should return joe as answer, and this is not what happens:

?- unmarried_student(X).

no

The reason for this is that the call to not(married(X)) is not returning the students which are not married: it is just failing because there is at least a married student.

Problem 4.3   Change the unmarried_student/1 predicate so that it works correctly in the three queries shown above. $\blacklozenge$

$\mathbf\therefore$

The use of cut and a fail in a clause forces the failure of the whole predicate, and is a technique termed cut-fail. It is useful to make a predicate fail when a condition (which may be a call to an arbitrary predicate) succeeds. An example of cut-fail combinations is implementing in Prolog the predicate ground/1, which succeeds if no variables are found in a term, and fails otherwise. The technique is recursively traversing the whole term, and forcing a failure as soon as a variable is found:

ground(Term):- var(Term), !, fail.
ground(Term):-
    nonvar(Term),
    functor(Term,F,N),
    ground(N,Term).

ground(0,T).
ground(N,T):-
    arg(N,T,Arg),
    ground(Arg),
    N1 is N-1,
    ground(N1,T).