CSCI 330: Prolog negation

Syntax for not in prolog

There are two ways of expressing the same thing: not(X) and \+(X).

Each gives false if X is provably true, true otherwise.
Note that this isn't quite the same thing as saying it gives the opposite of X. (More discussion on this is given below.)

The 'preferred' choice in SWI prolog is \+, based on the assumption that it more clearly identifies "not provable" than "not" does (just becuase not's connotations in natural language is slightly different/misleading in a prolog context).

Why we cannot have true negation in Prolog

Prolog is based predominantly on the Horn clause,

   A :- B, C, D, ...

This tells us A is true if B is true and C is true and ... etc.

IT DOES NOT TELL US THE CIRCUMSTANCES UNDER WHICH A IS FALSE

We can only assume that the rules describing the truth of A are exhaustive, and therefore if we cannot prove A is true from the knowledge base then A must be false.

Consider the following:

A :- not(not(B)).

In normal human logic we would assume this is the same as

A :- B.

However, what this really says for Prolog is

A is true if we fail to prove that we cannot prove B.

>>From positive logic one can only obtain positive logic, hence the complications with negation in Prolog.

Other limitations of Prolog

In many cases, there is no easy way to efficiently solve a problem using logic programming.

Consider the sorting of lists:

We can easily specify a sorted list:

sorted([]).
sorted([x]).
sorted([First|Second|Tail]) :- First =< Second, sorted([Second|Tail]).

From a purist point of view, this should be sufficient for a logic programming solution
However, the only way Prolog can generate a solution from this is by generating every possible permutation of the list until it happens upon a sorted version
We can come up with a (much) more involved set of rules to specify a sorting mechanism in Prolog, but this certainly goes against one of the major intended advantages of Prolog - that we need not concern ourselves with algorithms to achieve goals