Default reasoning
8.1. Default reasoning#
Consider the following argument:
‘Tweety is a bird.’
‘Normally, birds fly.’
‘Therefore, Tweety flies.’
There are several ways to translate this argument into logic. One is to read the second statement as ‘normal birds fly’, such that the following clauses represent the premises of the argument:
bird(tweety).
flies(X):-bird(X),normal(X).
Can we draw the conclusion that Tweety flies? There are three models:
{ bird(tweety) }
{ bird(tweety), flies(tweety) }
{ bird(tweety), flies(tweety), normal(tweety) }
In the first two models, Tweety is a bird but not normal; hence, it might or might not fly. In the third model, Tweety is a normal flying bird. Since flies(tweety) is not true in every model, it is not a logical consequence of the program.
If we want to conclude that Tweety flies, we must explicitly state that Tweety is a normal bird, thus ruling out the first two of the above models. However, in default reasoning we do not want to say that a case is normal: rather, we assume a case to be normal, unless it is known to be abnormal. Therefore, it is more natural to use a predicate abnormal/1 representing the negation of normal/1. Adding abnormal(X) to the head of the clause leads to the indefinite clause
flies(X);abnormal(X):-bird(X).
As has already been indicated in Section 2.4, such indefinite clauses can be transformed into ‘pseudo-definite’ or general clauses by moving all but one of the positive literals to the body of the clause, preceded by the negation symbol not. This results in the following program:
bird(tweety).
flies(X):-bird(X),not abnormal(X).
Since general clauses extend the language of definite clauses, we must extend both proof theory and semantics to deal with the negation symbol not. A practical way to do this has been discussed in Section 3.3, where we treated not/1 as a Prolog meta-predicate, implemented by means of cut. Under this interpretation, we can prove that Tweety flies (Figure 8.1).
Figure 8.1 Tweety flies by negation as failure.#
What happens if we learn that Tweety is an ostrich, and that ostriches are non-flying birds? We should add a clause which says that ostriches are abnormal (when it comes to flying):
bird(tweety).
ostrich(tweety).
flies(X):-bird(X),not abnormal(X).
abnormal(X):-ostrich(X).
As the SLD-tree in Figure 8.2 shows, Prolog is now unable to prove that Tweety flies, since Tweety is provably abnormal. We say that the default rule ‘normally birds fly’ is cancelled by a more specific rule (about ostriches).
Figure 8.2 Tweety doesn’t fly, since it is an ostrich.#
Give the models of this program (interpreting the general clause as the corresponding indefinite clause). Which one is the intended model (see Section 2.4)?
This example shows that in default reasoning, new information can invalidate previous conclusions, if these conclusions are based on unprovable assumptions which are contradicted by the new information. This property clearly distinguishes default reasoning from deductive reasoning, which is monotonic in the following sense:
That is, adding \(AnyFormula\) to a set of formulas \(Theory\) does not invalidate any \(Conclusion\) drawn from \(Theory\) alone. If we define the deductive closure of a theory as the set of conclusions that can be drawn from it:
then the property of monotonicity can also be stated as a relation between theories and their closures:
This formulation clearly demonstrates the use of the term ‘monotonic’. Since default reasoning lacks this property, it is often called non-monotonic reasoning.
Although Prolog’s not/1 meta-predicate can handle default arguments such as the above, there are a couple of problems. First of all, as has been shown in Section 3.3, the implementation of not/1 by means of cut may misbehave if the goal to be negated contains variables. The second problem is that, since cut is a procedural feature without declarative semantics, we likewise have no declarative semantics for not implemented by means of cut. Thus, even if we avoid the first problem by a clever re-ordering of literals in a clause, we do not know what we are computing! This problem will be addressed in the next section.
An alternative to handling possible exceptions to rules via negation as failure, is to distinguish between two possible types of rules, those with exceptions, and those without exceptions. For instance, the rule ‘penguins are birds’ is a rule without exceptions, whereas the rule ‘birds fly’ is a rule with exceptions. Let us call a rule with exceptions a default rule, or simply a default. Rules and defaults are then treated differently when trying to prove something: a rule is applied whenever possible, while a default is applied only when it does not lead to an inconsistency. So, if we only know that Tweety is a bird, the default ‘birds fly’ can be used to conclude that Tweety flies, but if we also know that Tweety is a penguin and that penguins don’t fly, the default cannot be applied. Thus, instead of expressing our knowledge as a general program and using Prolog to derive conclusions, we will extend the syntax of clausal logic to distinguish between defaults and rules. We will develop a meta-interpreter which implements the inference rules for this extended logic.
The Tweety example can be expressed in terms of rules and defaults as follows.
default((flies(X):-bird(X))).
rule((not flies(X):-penguin(X))).
rule((bird(X):-penguin(X))).
rule((penguin(tweety):-true)).
rule((bird(opus):-true)).
In order to explain why Opus flies but Tweety doesn’t, we use two meta-interpreters. One is the familiar prove meta-interpreter for definite clauses, extended with two arguments to collect the rules used in the proof. The other meta-interpreter applies a default whenever it does not lead to a contradiction.
:-op(900,fy,not).
% explain(F,E) <- E explains F from rules and defaults
explain(F,E):-
explain(F,[],E).
% meta-interpreter for rules and defaults
explain(true,E,E):-!.
explain((A,B),E0,E):-!,
explain(A,E0,E1),
explain(B,E1,E).
explain(A,E0,E):-
prove_e(A,E0,E). % explain by rules only
explain(A,E0,[default((A:-B))|E]):-
default((A:-B)),
explain(B,E0,E),
not contradiction(A,E). % A consistent with E
% meta-interpreter for rules
prove_e(true,E,E):-!.
prove_e((A,B),E0,E):-!,
prove_e(A,E0,E1),
prove_e(B,E1,E).
prove_e(A,E0,[rule((A:-B))|E]):-
rule((A:-B)),
prove_e(B,E0,E).
% check contradiction against rules
contradiction(not A,E):-!,
prove_e(A,E,_E1).
contradiction(A,E):-
prove_e(not A,E,_E1).
The query ?-explain(flies(X),E) has only one answer:
X = opus
E = [ default((flies(opus):-bird(opus))),
rule((bird(opus):-true)) ]
Tweety does not fly, since not flies(tweety) is provable from the rules:
?-explain(not flies(X), E).
X = tweety
E = [ rule((not flies(tweety):-penguin(tweety))),
rule((penguin(tweety):-true)) ]
Sometimes, both a fact and its negation can be explained. Consider the following set of defaults and rules:
default((not flies(X):-mammal(X))).
default((flies(X):-bat(X))).
default((not flies(X):-dead(X))).
rule((mammal(X):-bat(X))).
rule((bat(dracula):-true)).
rule((dead(dracula):-true)).
Does Dracula fly or not? One explanation claims he does, because he is a bat, and bats typically fly:
?-explain(flies(dracula),E).
E = [ default((flies(dracula):-bat(dracula))),
rule((bat(dracula):-true)) ]
However, there are also two explanations stating that Dracula doesn’t fly; after all, he’s not only a mammal, and mammals typically don’t fly, but he’s also dead, and dead things typically don’t fly either:
?-explain(not flies(dracula), E).
E = [ default((not flies(dracula):-mammal(dracula))),
rule((mammal(dracula):-bat(dracula))),
rule((bat(dracula):-true)) ];
E = [ default((not flies(dracula):-dead(dracula))),
rule((dead(dracula):-true)) ]
It seems that only the third of these explanations is acceptable. Thus, we need a way to cancel particular defaults in certain situations.
This can be done by attaching names to defaults, which are parameterised with the variables in the default. Then, we can refer to a default in the conclusion of a rule:
% default(Name,Rule)
default(mammals_dont_fly(X),(not flies(X):-mammal(X))).
default(bats_fly(X),(flies(X):-bat(X))).
default(dead_things_dont_fly(X),(not flies(X):-dead(X))).
rule((mammal(X):-bat(X))).
rule((bat(dracula):-true)).
rule((dead(dracula):-true)).
% bats are flying mammals
rule((not mammals_dont_fly(X):-bat(X))).
% dead bats don't fly
rule((not bats_fly(X):-dead(X))).
We change the fourth clause of the explain/3 predicate accordingly:
explain(A,E0,[default(Name)|E]):-
default(Name,(A:-B)), % explain by default rule
explain(B,E0,E),
not contradiction(Name,E), % default applicable
not contradiction(A,E). % A consistent with E
There are two changes: (1) when applying a default, its name is tested for consistency with the rules, and (2) the name of the default is added to the explanation, instead of the default itself. The above queries are now handled correctly:
?-explain(flies(dracula),E).
No.
?-explain(not flies(dracula), E)
E = [ default(dead_things_dont_fly(dracula)),
rule((dead(dracula):-true)) ];
No more solutions.
We thus see that it is the programmer’s responsibility to avoid inconsistencies by specifying appropriate cancellation rules.