The complete picture
8.4. The complete picture#
In this chapter we studied several ways of dealing with incomplete information. Incompleteness occurs whenever there is a ground fact in the Herbrand base of which we do not know the truth value. In order to extend our knowledge, we need to make assumptions about the truth value of such ground facts. The simplest approach is to assume that everything that is not known to be true must be false. The procedural equivalent of this is negation as failure: everything that is not provable is assumed to be false. Thus, a negated literal not L in the body of a general clause is assumed to be proved if a proof of L fails. The resulting proof procedure is called SLDNF-resolution1.
If we strengthen our proof procedure, we must strengthen the semantics accordingly. Since the original program is incomplete it has several models, one of which we need to choose. One way to do this is to transform the original program into a new, complete program, which we declare to be the intended program. The only model of this complete program is taken as the intended model of the original program. The Closed World Assumption is a rather naive way to achieve this, while Predicate Completion can also handle a restricted subclass of the class of general programs (so-called stratified programs).
The relation between SLDNF-resolution and Predicate Completion is as follows. Let \(P\) be a general program, let \(Comp(P)\) denote the completion of \(P\), and let \(\vdash_{\mathrm{SLDNF}}\) denote provability by SLDNF-resolution, treating negated literals in the body of clauses by negation as failure; then the following relation holds:
This is a soundness result for SLDNF-resolution. The corresponding completeness result is not so easily proved, and holds only for specific sub-classes of programs.
Default reasoning is reasoning with typical cases and exceptions. A practical approach to default reasoning is by explicitly listing the exceptions to a rule by means of abnormality predicates. The rule describing the typical case is represented by a general clause, containing the negation of the abnormality predicate. An alternative approach is to distinguish between rules which always hold, and rules which typically hold (so-called defaults). A default is applicable whenever it does not lead to inconsistencies. In order to prevent the applicability of defaults in certain cases, they are assigned names. These names can then be used in other rules to refer to a specific default.
There is a close relation between abnormality predicates and names of defaults, demonstrated by the following translation of default rules to general clauses. The default rule
default(bats_fly(X),(flies(X):-bat(X))).
is first translated to a clause
flies(X):-bat(X),bats_fly(X).
after which the predicate bats_fly/1, indicating the normal case, is converted to a negated abnormality predicate:
flies(X):-bat(X),not nonflying_bat(X).
Furthermore, for each negated conclusion in a rule like
default(dead_things_dont_fly(X),(not flies(X):-dead(X))).
a new predicate is introduced:
notflies(X):-dead(X),not flying_deadthing(X).
Thus, the complete set of rules and defaults about Dracula is translated to the following general program:
notflies(X):-mammal(X),not flying_mammal(X).
flies(X):-bat(X),not nonflying_bat(X).
notflies(X):-dead(X),not flying_deadthing(X)
mammal(X):-bat(X).
bat(dracula).
dead(dracula).
flying_mammal(X):-bat(X).
nonflying_bat(X):-dead(X).
What this shows is the close relationship between assuming that something is false unless the opposite can be proved (negation as failure), and assuming that a default rule is applicable unless this leads to inconsistencies.
Exercise 8.5 #
Draw the SLD-trees for the queries ?-flies(X) and ?-notflies(X).
Abduction generalises negation as failure by formulating assumptions about either truth or falsity of specific literals (abducibles). For instance, the Dracula example can be handled by the abductive meta-interpreter of Section 8.3 without any problem, if we declare the abnormality predicates as abducibles:
abducible(flying_mammal(_X)).
abducible(nonflying_bat(_X)).
abducible(flying_deadthing(_X)).
?-abduce(flies(X),E).
No.
?-abduce(notflies(X),E).
X = dracula
E = [not flying_deadthing(dracula)];
No more solutions.
This shows that negation as failure is a special case of abduction. Moreover, it shows that making assumptions about the applicability of a default rule is a form of abduction. We can therefore conclude that abduction is the most general form of reasoning with incomplete information among the ones discussed in this chapter. However, inductive reasoning extends abduction by hypothesising complete predicate definitions rather than sets of ground literals. This will be the subject of the next chapter.
Exercise 8.6 #
Remove the last two clauses from the program, and again determine the answers to the queries ?-abduce(flies(X),E) and ?-abduce(notflies(X),E).
- 1
In SLDNF resolution,
notis treated as belonging to the language of general clauses, rather than as a meta-predicate.