A Tutorial on Default Logics.

1. INTRODUCTION: DEFAULT REASONING

When an intelligent system (either computer-based or human) tries to solve a problem, it may be able to rely on complete information about this problem, and its main task is to draw the correct conclusions using classical reasoning. In such cases, classical predicate logic may be sufficient.

However, in many situations the system has only incomplete information at hand, be it because some pieces of information are unavailable, or because it has to respond quickly and does not have the time to collect all relevant data. Classical logic indeed has the capacity to represent and reason with certain aspects of incomplete information. But there are occasions where additional information needs to be "filled in" to overcome the incompleteness, because certain decisions must be made. In such cases the system has to make some plausible conjectures, which in the case of default reasoning are based on rules of thumb, called defaults. For example, an emergency doctor has to make some conjectures about the most probable causes of the symptoms observed. Obviously, it would be inappropriate to await the results of possibly extensive and time-consuming tests before beginning with treatment.

When decisions are based on assumptions, these may turn out to be wrong in the face of additional information that becomes available; i.e., medical tests may lead to a modified diagnosis. The, phenomenon of having to take back. some previous conclusions is called nonmonotonicity; it says that if a statement [Psi] follows from a set of premises M and M [subset or equal to] M', [Psi] does not necessarily follow from M'. Default Logic, originally presented in Reiter [1980], provides formal methods to support this kind of reasoning.

Default Logic is perhaps the most prominent method for nonmonotonic reasoning, basically because of the simplicity of the notion of a default, and because defaults prevail in many application areas. However, there exist several alternative design decisions which have led to variations of the initial idea; actually, we can talk about a family of default reasoning methods because they share the same foundations.

In this paper we present the motivations and basic ideas of some of the most important default logic variants, and compare them both with respect to interconnections and the fulfillment of some properties. When designing a tutorial, it is good to have some aims against which the final product can be tested. The particular aims of this tutorial paper are the following:

--To present the basic ideas of Default Logic to persons without prior knowledge in the area. Only basic understanding of classical logic is required.

--To equip the reader with skills and methods so that they can apply the concepts of Default Logic to concrete situations. This is achieved by the use of operational models which can be applied in a straightforward manner to examples without having to make any guesses, as is the case with the usual fixpoint or quasiinductive definitions.

--To give the reader a sense of the diversity of the topic.

The paper is organized as follows: Section 2 presents the basics of Reiter's Default Logic. Section 3 discusses properties and design decisions of this approach, and outlines some alternative intuitions on these issues. Sections 4-6 describe some basic default logic variants: Justified Default Logic [Lukaszewicz 1988], Constrained Default Logic [Schaub 1992], and approaches to prioritization [Brewka 1994]. In Section 7 we briefly discuss some further default logics, namely Cumulative Default Logic [Brewka 1991], Rational Default Logic [Mikitiuk and Truszczynski 1995], Disjunctive Default Logic [Gelfond et al. 1991], and weak extensions [Marek and Truszczynski 1993].

No prior knowledge of Default Logic is required since this is a tutorial paper. However, we assume that the reader is familiar with notation and the basic concepts of classical logic.

2. DEFAULT LOGIC

2.1 The Notion of a Default

A rule used by football organizers in Germany might be: "A football game shall take place, unless there is snow :in the stadium." This rule of thumb is represented by the default

football : ??snow/takesPlace.

The interpretation of the default is as follows: If there is no information that there will be snow in the stadium, it is reasonable to assume ??snow and conclude that the game will take place (so preparations can proceed). But if there is a heavy snowfall during the night before the game is scheduled, then this assumption can no longer be made. Now we have definite information that there is snow, so we cannot assume ??snow, therefore the default cannot be applied. In this case we need to refrain from the previous conclusion (the game will take place), so the reasoning is nonmonotonic.

Before proceeding with more examples, let us first explain why classical logic is not appropriate to model this situation. Of course, we could use the rule

football [conjunction] ??snow [right arrow] takesPlace.

The problem with this rule is that we have to definitively establish that there will be no snow in the stadium before applying the rule. But that would mean that no game could be scheduled in the winter, which would create a revolution in Germany! It is important to understand the difference between having to know that it will not snow, and being able to assume that it will snow. Defaults support the drawing of conclusions based upon assumptions.

The same example could have been represented by the default

football : takesPlace/takesPlace,

together with the classical rule snow [right arrow] ??takesPlace. In case we know snow then we can deduce ??takesPlace in classical logic, therefore we cannot assume takesPlace, as required by the default. In this representation, the default says "Football matches usually takes place," and exceptions to this rule are represented by classical rules such as the above one.

Defaults can be used to model proto-typical reasoning, which means that most instances of a concept have some property. One example is the statement "Typically, children have (living) parents" which may be expressed by the default

child(X) : hasParents(X)/hasParents(X).

A further form of default reasoning is no-risk reasoning. It concerns situations where we draw a conclusion even if it is not the most probable, because another decision could lead to a disaster. Perhaps the best example is the following main principle of justice in the Western cultures: "In the absence of evidence to the contrary assume that the accused is innocent." In default form:

accused(X) : innocent(X)/innocent(X).

Defaults naturally occur in many application domains. Let us give an example from legal reasoning. According to German law, a foreigner is usually expelled if they have committed a crime. One of the exceptions to this rule concerns political refugees. This information is expressed by the default

criminal(X) [conjunction] foreigner(X): expel(X)/expel(X)

in combination with the rule

politicalRefugee(X) [right arrow] ??expel(X).

Hierarchies with exceptions are commonly used in biology. Here is a standard example:

 
   Typically, molluscs are shell-bearers. 
   Cephalopods are molluscs. 
   Cephalopods are not shell-bearers. 

It is represented by the default

mollusc(X) : shellBearer(X)/shellBearer(X)

together with the rule

cephalopod(X) [right arrow] mollusc(X) [conjunction] ??shellBearer(X).

Defaults can be used naturally to model the Closed World Assumption [Reiter 1978], which is used in database theory, algebraic specification, and logic programming. According to this assumption, an application domain is described by certain axioms (in form of relational facts, equations, rules, etc.) with the following understanding: a ground fact (that is, a nonparameterized statement about single objects) is taken to be false in the problem domain if it does not follow from the axioms The closed world assumption has the simple default representation

true: ??[Psi]/??[Psi]

for each ground atom [Psi]. The explanation of the default is: if it is consistent to assume ??[Psi] (which is equivalent to not having a proof for [Psi]) then conclude ??[Psi].

Further examples of defaults can be found in, say, Besnard [1989]; Etherington [1987b]; Lukaszewicz [1990]; and Poole [1994].

2.2 The Syntax of Default Logic

A default theory T is a pair (W, D) consisting of a set W of predicate logic formulae (called the facts or axioms of T) and a countable set D of defaults. A default 8 has the form

[Psi] : [[Psi].sub.1], ..., [[Psi].sub.n]/[Chi]

where [Psi], [[Psi].sub.1], ..., [[Psi].sub.n], [Chi] are closed predicate logic formulae, and n [is greater than] 0. The formula [Psi] is called the prerequisite, [[Psi].sub.1], ..., [[Psi].sub.n] the justifications, and [Chi] the consequent of [Delta]. Sometimes [Psi] is denoted by pre([Delta]), {[[Psi].sub.1], ..., [[Psi].sub.n]} by just([Delta]), and [Chi] by cons([Delta]). For a set D of defaults, cons(D) denotes the set of consequents of the defaults in D. A default is called normal iff it has the form [Psi]: [Psi]/[Psi].

One point that needs some discussion is the requirement that the formulae in a default be ground. This implies that

bird(X) : flies(X)/flies(X)

is not a default according to the definition above. Let us call such rules of inference open defaults. An open default is interpreted as a default schema, meaning that it represents a set of defaults (this set may be infinite).

A default schema looks like a default, the only difference being that [Psi], [[Psi].sub.1], ..., [[Psi].sub.n], [Chi] are arbitrary predicate logic formulae (i.e., they may contain free variables). A default schema defines a set of defaults, namely

[Psi][Sigma] : [[Psi].sub.1][Sigma], ..., [[Psi].sub.n][Sigma]/[Chi][Sigma]

for all ground substitutions [Sigma] that assign values to all free variables occurring in the schema. That means flee variables are interpreted as being universally quantified over the whole default schema. Given a default schema

bird(X): flies(X)/flies(X)

and the facts bird(tweety) and bird(sam), the default theory represented is ({bird(tweety), bird(sam)}, {bird(tweety) : flies(tweety)/flies(tweety), bird(sam) : flies(sam)/flies(sam)}).

2.3 Informal Discussion of the Semantics

Given a default [Psi] : [[Psi].sub.1], ..., [[Psi].sub.n]/[Chi], its informal meaning is the following:

 
   If [Psi] is known, and if it is consistent to assume [[Psi].sub.1], ..., 
   [[Psi].sub.n], then conclude [Chi]. 

In order to formalize this interpretation we must say in which context [Psi] should be known, and with what [[Psi].sub.1], ..., [[Psi].sub.n] should be consistent. A first guess would be the set of facts, but this turns out to be inappropriate. Consider the default schema

friend(X, Y) [conjunction] friend(Y, Z) : friend(X, Z)/friend(X, Z)

which says "Usually my friends' friends are also my friends". Given the information friend(tom, bob), friend(bob, sally) and friend(sally, tina), we would like to conclude friend(tom, tina). But this is only possible if we apply the appropriate instance of the default schema to friend(sally, tina) and friend(tom,) sally}. The latter formula stems from a previous application of the default schema.(1) If we did not admit this intermediate step and used the original facts only, then we could …