Wednesday, 1 March 2023

15 - Negation



Up to this point we've only seen prolog used to define properties that are true. We've not yet seen how prolog expresses a property is not true.

We'll start with a simple example that builds on familiar ground.


% Example 15 - Negation By Failure

% fruit
fruit(apple). 
fruit(orange). 
fruit(banana).

% colour
yellow(banana).

% Mary likes all fruit 
likes(mary, X) :- fruit(X).

% James likes all fruit, as long as it is yellow
likes(james, X) :- fruit(X), yellow(X).

% Sally likes all fruit, except yellow fruit
likes(sally, X) :- fruit(X), negation(yellow(X)).

% negation as failure
negation(G) :- call(G), !, fail. 
negation(_).

Our program first defines three simple facts about apples, oranges and banana being fruit. It also defines a banana as being yellow.


Mary Likes All Fruit

The next part of the program defines which fruit Mary, James and Sally like. 

Mary likes all fruit. This is easily expressed in prolog.


% Mary likes all fruit
likes(mary, X) :- fruit(X).

Let's test it to leave no doubt.


?- likes(mary,X).

X = apple
X = orange
X = banana

As expected, prolog finds Mary likes apples, oranges and bananas.


James Likes Only Yellow Fruit

James is more particular in his taste, and likes all fruit as long as it is yellow. Again, this is easy to express in prolog.


% James likes all fruit, as long as it is yellow
likes(james, X) :- fruit(X), yellow(X).

The first part of the rule fruit(X) is satisfied by all fruit, the second part yellow(X) imposes the constraint that it must be yellow.


?- likes(james,X).

X = banana

Prolog finds that only bananas satisfy James' requirements.


Sally Likes All Fruit, Except Yellow Fruit

Sally has a broader taste than James, and likes all fruit, except yellow fruit. Expressing the idea of “except” in prolog is not something we've seen before. 

  • We're familiar with creating general rules, for example likes(mary,X). 
  • We know how to add positive constraints, for example likes(james,X) has the positive requirement that fruit is yellow. 
  • We haven't yet seen how to add negative constraints, exceptions. 

These three scenarios are illustrated as follows.



We need a way to say “and not this property” in prolog. For now, let's imagine we have a property negation/1 that does this. So negation(yellow(X)) is true when the property yellow(X) is not true. 


% Sally likes all fruit, except yellow fruit
likes(sally, X) :- fruit(X), negation(yellow(X)).

The first part of the rule fruit(X) is satisfied by all fruit, but this time the second part negation(yellow(X)) is only satisfied if yellow(X) is not true. 


?- likes(sally,X).

X = apple
X = orange

Prolog correctly finds that Sally likes apples and oranges, but not bananas. 


Negation/1

Let's see how negation/1 works. 


% negation as failure
negation(G) :- call(G), !, fail. 
negation(_).

The property negation/1 has two rules. 

The first part of the first rule is call(G). The call/1 is a built-in prolog property which executes whatever property G represents. This is a new use for variables. Previously variables could represent things like apple, or lists like [1, 2, 3]. Here, the variable G is intended to unify with a prolog property.

It is worth pausing to really appreciate this. The ability of a variable to represent prolog code, code that can be executed, is quite powerful. It opens up new ways of programming called meta-programming that we'll explore later.

If the property G is satisfiable, then the next part of the rule is a cut, which always succeeds, but prevents backtracking across it. The last part of the rule is fail, which causes the entire rule to fail. The cut prevents prolog from backtracking to find another way to make the rule succeed. So, if G is satisfiable, then negation(G) fails.

The second rule is only executed if call(G) from the first rule fails. The rule has no body which means it is always true. That is, if G is not satisfiable, negation(G) is true. The second rule has an underscore _ in its head because some prologs don't like a variable in the head of a rule not being used in its body.

We can see how negation(G) acts like a logical inversion.

  • If G is true, negation(G) is false.
  • If G is false, negation(G) is true.

So negation(yellow(X)) is only true if yellow(X) is not satisfiable. This is what we wanted for our likes(sally,X) rule.

This form of negation is called negation as failure. It works by intentionally failing after a goal is shown to be true, and succeeding otherwise.


Negation As Failure Is Not Logical Negation

Negation as failure is useful, but it is not equivalent to logical negation. Let's see why.

The order of goals in a purely logical rule should not matter. The following query unifies X=fish and then tests negation(fruit(X)).


?- X=fish, negation(fruit(X)).

X = fish

Clearly fish is not a fruit, because it is not listed in the database of facts, and so fruit(X) fails. This leads to negation(fruit(X)) succeeding. Prolog reports the query succeeds with X=fish as a valid solution. 

Now let's swap the goal order.


?- negation(fruit(X)), X=fish.

false

This time, the variable X does not have a value when fruit(X) is called. Because there are valid solutions to fruit(X), it succeeds, which means negation(fruit(X)) is false. This leads to the entire query failing. Remember, the second goal X=fish is not reached if the first goal fails. So prolog reports false. A purely logical reading of this result would incorrectly suggest fish is indeed a fruit. 

The apparently contradictory responses from prolog demonstrate that negation/1 is not a purely logical property. A safe way to use failure by negation is to ensure the property being tested is fully grounded, that is, all variables have values.


\+ Not Satisfiable

Despite the caution, negation as failure is useful, and most prologs include it as standard. In swi-prolog it is provided as \+, which is read as “the following goal is not satisfiable”. Some prologs retain a not/1 property, but \+ is encouraged to emphasise that it is not logical negation.

The following shows how \+ can simplify our likes(sally,X) rule.


likes(sally, X) :- fruit(X), \+ yellow(X).

The body of the rule is read as “fruit(X) is satisfied, but yellow(X) is not satisfiable”. 


Key Points

  • Negation as failure is a test that intentionally fails when a property is satisfiable, and succeeds otherwise. 
  • Negation as failure is not logical negation, and should be used with care. 
  • Negation as failure can be used safely if all variables in the property being tested are grounded.
  • Prolog provides \+ for negation, and is read as “the following property is not satisfiable”. For example, \+ yellow(X) means “yellow(X) is not satisfiable”.
  • Prolog variables can be unified with a prolog property, and call/1 can be used to execute its code.

at