(sec: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-resolution*[^19_].
+++
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:
$$
P \vdash_{\mathrm{SLDNF}} q \;\;\;\; \Rightarrow \;\;\;\; Comp(P) \models q
$$
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
```Prolog
default(bats_fly(X),(flies(X):-bat(X))).
```
is first translated to a clause
```Prolog
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:
```Prolog
flies(X):-bat(X),not nonflying_bat(X).
```
Furthermore, for each negated conclusion in a rule like
```Prolog
default(dead_things_dont_fly(X),(not flies(X):-dead(X))).
```
a new predicate is introduced:
```Prolog
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:
```Prolog
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} ex:8.5
```
+++
*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 {numref}`sec:8.3` without any problem, if we declare the abnormality predicates as abducibles:
```{swish} swish:8.4.1
---
source-text-start: 8.x.x-1-start
source-text-end: 8.4.1-end
---
```
```Prolog
?-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} ex:8.6
```
[^19_]: In SLDNF resolution, `not` is treated as belonging to the language of general clauses, rather than as a meta-predicate.