Negation as failure
3.3. Negation as failure#
The following program computes the maximum of two integers:
max(M,N,M):- M >= N.
max(M,N,N):- M =< N.
>= and =< are built-in predicates with meaning ‘greater than or equal’ and ‘less than or equal’, respectively1. Declaratively, the program captures the intended meaning, but procedurally there are two different ways to solve queries of the form ?-max(N,N,M). The reason for this is that the bodies of the two clauses are not exclusive: they both succeed if the first two values of the max predicate are equal. We could of course remove one of the equality symbols, but suppose that we use a cut instead:
max(M,N,M):- M >= N,!.
max(_M,N,N).
With a red cut, this program can only be understood procedurally. The question is: does the procedural meaning correspond to the intended meaning? Perhaps surprisingly, the answer is no! For instance, the query
?-max(5,3,3).
succeeds: the cut is never reached, because the literal in the query does not unify with the head of the first clause. The second program is in fact a very bad program: the declarative and procedural meanings differ, and neither of them captures the intended meaning.
Exercise 3.4 #
Show that this cut is red, by drawing an SLD-tree in which a success branch is pruned.
The procedural meaning of the program would be correct if its use is restricted to queries with uninstantiated third argument. It illustrates a very common use of cut: to ensure that the bodies of the clauses are mutually exclusive. In general, if we have a program of the form
p:-q,!,r.
p:-s.
its meaning is something like
p:-q,r.
p:-not_q,s.
How should not_q be defined, in order to make the second program work? If q succeeds, not_q should fail. This is expressed by the following clause:
not_q:-q,fail.
where fail is a built-in predicate, which is always false. If q fails, not_q should succeed. This can be realised by the program
not_q:-q,!,fail.
not_q.
The cut in the first clause is needed to prevent backtracking to the second clause when q succeeds.
This approach is not very practical, because it only works for a single proposition symbol, without variables. We would like to treat the literal to be negated as a parameter, as in
not(Goal):- /* execute Goal, */ !,fail.
not(Goal).
The problem now is to execute a goal which is passed to the predicate not as a term. Prolog provides two facilities for this. One is the built-in predicate call, which takes a goal as argument and succeeds if and only if execution of that goal succeeds. The second facility2 is merely a shorthand for this: instead of writing call(Goal), one may simply write Goal, as in
not(Goal):- Goal,!,fail.
not(_Goal).
This is a slight abuse of the syntax rules, because a variable (a term) occurs in a position where only atoms are allowed. As long as the variable is instantiated to a goal before it is reached, this will, however, cause no problem (if it is not correctly instantiated, Prolog will generate an error-message). Predicates like not and call are called meta-predicates, that take formulas from the same logical language in which they are written as arguments. As we will see in later chapters, meta-predicates play an important role in this book.
We illustrate the operation of not by means of the following propositional program:
p:-q,r.
p:-not(q),s.
s.
and the query ?-p. The SLD-tree is shown in Figure 3.9. The first clause for p leads to a failure branch, because q cannot be proved. The second clause for p is tried, and not(q) is evaluated by trying to prove q. Again, this fails, which means that the second clause for not is tried, which succeeds. Thus, not(q) is proved by failing to prove q! Therefore, this kind of negation is called negation as failure.
Figure 3.9 SLD-tree with not.#
Figure 3.9 shows, that Prolog tries to prove q twice. Consequently, the program with not is slightly less efficient than the version with cut:
p:-q,!,r.
p:-s.
s.
which leads to the SLD-tree shown in Figure 3.10. Here, q is tried only once. However, in general we prefer the use of not, because it leads to programs of which the declarative meaning corresponds more closely to the procedural meaning.
Figure 3.10 Equivalent SLD-tree with cut.#
In the following program, :-not(q) fails because :-q succeeds:
p:-not(q),r.
p:-q.
q.
r.
The SLD-tree for the query ?-p is shown in Figure 3.11. Since q succeeds, fail ensures that not(q) fails. The cut is needed to ensure that everything following the not is pruned, even if it contains a success branch.
Figure 3.11 :-not(q) fails because :-q succeeds.#
The implementation of not illustrated above can lead to problems if variables are involved. Take a look at the following program:
bachelor(X):-not(married(X)),man(X).
man(fred).
man(peter).
married(fred).
Consider the query
?-bachelor(X).
for which the SLD-tree is depicted in Figure 3.12. According to negation as failure, Prolog tries to prove not(married(X)) by trying married(X) first. Since this succeeds for X = fred, the cut is reached and the success branch to the right (representing the correct answer { X → peter }) is pruned. Thus, :-not(married(X)) fails because :-married(X) succeeds for one value of X. That is, not(married(X)) is interpreted as ‘it is false that somebody is married’, or equivalently, ‘nobody is married’. But this means that the clause
bachelor(X):-not(married(X)),man(X).
is interpreted as ‘X is a bachelor if nobody is married and X is a man’, which is of course not as intended.
Figure 3.12 There are no bachelors?!#
Negation as failure vs. logical negation#
Negation as failure is not the same as logical negation: if we cannot prove q, we know that q is not a logical consequence of the program, but this does not mean that its negation :-q is a logical consequence of the program. Adopting negation as failure is similar to saying ‘I cannot prove that God exists, therefore I conclude God does not exist’. It is a kind of reasoning that is applicable in some contexts, but inadequate in others. Logical negation can only be expressed by indefinite clauses, as in the following program:
p:-q,r.
p;q:-s.
s.
Semantically speaking, if we don’t have enough information to conclude that a formula \(F\) is true or false, the truth value of its logical negation will also be undecided, but not\((F)\) will be true. This property of negation as failure can be very useful when dealing with exceptions to rules: if we don’t know that something is an exception to a rule, we assume that it’s not, so we only have to list the exceptions and not the normal cases. This approach will be extensively discussed in Chapter 8 on reasoning with incomplete information.
Thus, if G is instantiated to a goal containing variables at the time not(G) is called, the result may be not in accordance with negation as failure. It is the programmer’s responsibility to avoid this. A simple remedy that will often work is to ensure the grounding of G by literals preceding not(G) in the body of the clause, i.e.
bachelor(X):-man(X),not(married(X)).
man(fred).
man(peter).
married(fred).
Show that the modified program produces the right answer, by drawing the SLD-tree for the query ?-bachelor(X).
Thus, we see that changing the order of the literals in the body of a clause does not only affect the order in which answers to a query are found, but it may also change the set of answers! Of course, this is very much against the spirit of declarative programming, because the declarative interpretation of a clause does not depend on the order of the literals. Therefore, some Prolog interpreters provide a mechanism which defers the evaluation of not(G) until G is ground. However, with standard Prolog it is the programmer’s duty to ensure that not is never called with a non-ground argument.
Let’s summarise the points made about negation in Prolog. It is often used to ensure that only one of several possible clauses is applicable. The same effect can be achieved by means of cut, but in general we prefer the use of not, although it is somewhat less efficient3. not is supplied by Prolog as a meta-predicate (i.e. a predicate which takes formulas from the same logical language in which it is written as arguments). It is only a partially correct implementation of negation as failure, since it does not operate correctly when its argument is a goal containing variables.