Search code examples
prologlogic

Negation by Failure and Logical Monotonicity in Prolog?


I am learning prolog.

It seems to me that prolog's rules (relations and simple facts) are "positive" - they say what is or can be true.

Adding new such rules to a prolog program only adds "positive" knowledge. It can't add "negative" facts to say something isn't true.

Question

  1. Is this called monotonic logic?

  2. The procedural (not logical) construct called "negation by failure" is the hack needed to add "negative" facts to break the otherwise monotonicity of purely logical prolog eg exceptions to rules.

Am I correct?


Update

A comment asked for an example.

likes(mary, X) :- reptile(X), !, fail.
likes(mary, X) :- animal(X).

Without the procedural cut, there is no way in purely logical prolog to define that Mary likes animals except reptiles. (Is this correct?)


Solution

  • As far as Prolog is concerned, a monotonic program is one where adding further clauses does not reduce the set of solutions of a predicate*. Conversely, removing clauses will never increase solutions found in such a program. Assuming the definition of @brebs

    likes(mary, X) :- animal(X), \+ reptile(X).
    

    if you add further facts to reptile/1, the set of animals Mary likes may decrease. So this is an example of non-monotonic behaviour. Note however, that this form of simplistic negation only works if X is sufficiently instantiated when calling \+ reptile(X). Even seemingly trivial changes like reordering will make this program incorrect for certain uses.

    likes(mary, X) :- \+ reptile(X), animal(X).
    
    ?- X = cat, likes(mary, X).
       X = cat.
    ?- likes(mary, X), X = cat.
       false, unexpected.
    ?- likes(mary, X).
       false, unexpected.
    

    In general as a beginner, stick to the pure monotonic subset of Prolog first. It is already quite difficult to master and only if you really understood this does it make sense to include non-monotonic constructs.


    1 modulo non-termination and errors