A Semantics for Default Logic

1. Introduction

In his development of default logic. Reiter [1980] pro­ vides a fixed-point characterization of the extensions of a default theory, but no model-theoretic semantics. Default logic has attracted attention as a formal system for non· monotonic reasoning. This is due, in part, to the intuitive clarity with which default information can be expressed. This clarity has ameliorated the delayed development of a semantics for the formalism; people have tended to be satisfied with intuitive characterizations of the extensions of default theories, together with the Tarskian semantics of the individual extensions.

While this transition to model-theory may be relatively painless, there is still a need for a semantic characterization of default logic as a whole. Etherington [1982, 1983]Ioosely characterized the semantics of default logic , observing that defaults "can be viewed as extending the first-order knowledge about an incompletely-specified world. [They] select restricted subsets of the models of the underlying first-order theory". Lukaszewicz [1985] recently formalized this idea for a restricted class of default theories. In this paper, we generalize this work to cover the entire class of default theories . We also recast the semantics in a more intuitive and familiar form, making it more useful and accessible . Proofs of the results quoted here may be found in [Etherington 1986].

In what follows , we present a semantics for default logic . This is subsequently evaluated and shown to provide useful insight into the formalism. We begin by providing the briefest of introductions to default logic . More details can be found in (Reiter 1980].

1 Parts of this work were done at the University of British Columbia, and supported in part by an I.W. Killam Predoctoral Scholarship and by NSERC grant A 7642.

A Semantics for Default Logic

David W. Etherington 1

Artificial Intelligence Principles Research Department AT&T Bell Laboratories 600 Mountatn Avenue Murray Hill, NJ 07974-2070 ether%allegra@btl .csnet

2. Default Logic

Default logic allows new inference rules to be added to a standard first-order logic. These rules sanction their con­ clusions provided the set of beliefs satisfies the conditions outlined in their premises. Unlike standard Jo,~~;ic, these premises may refer both to what is known and to what is not known. The latter property allows rules to be added that specify inferences to be made only when specific infor· mation is missing.

A default is any expression of the form: 2

where a(i). the 131(i) , and w(i) are all formulae whose free variables are among those in i = x 1, . . .· x,.. a. the 131, and w are called the prerequisite, justifications, and consequent of the default, respectively. Two classes of single-justification defaults are distinguished. Those with l3(i) ""w(.r) are said to be normal; those with l3(i) ""w(i) A -y(i) are called sem· inormal.

Defaults serve as rules of inference or conjecture , aug­ menting those provided by first-order logic . Under certain conditions, they sanction inferences that could not be made within a conventional framework . If their prerequisites are known and their justifications are "consistent" (i .e. , their negations are not provable), then their consequents can be inferred. A default theory is an ordered pair consisting of a set of defaults , D. and a set of first-order formulae , W. D can be viewed as extending the definite knowledge of W to provide information not derivable from W.

Since defaults allow reference to what is not provable in the determination of what is provable, the , ''theorems".of a default theory are not so easy to generate as are those of a first-order theory . What is provable both determines and is determined by what is not provable . To avoid this apparent circularitv , the theorems of a default theorv are defined by a fixed-point construction. An extension. E _-for a default theory is required to contain all the known facts . be closed under the 1- relation. and contain the consequent of any default whose prerequisite is satisfied by E and whose justifications are consistent with £. Furthermore . E con· tains only those facts required by the above conditions .

2 We omit the "M" preceding each !31, since they are redun· dant in the positional notation .

3. A Semantics for Default Theories

As mentioned earlier, default logic's semantics can be viewed in terms of restrictions of the set of models of the underlying theory. The first-order theory partially specifies a world, which is further specified by the defaults. Each default can be viewed as extending the world-description by restricting the set of possible worlds assumed to contain the "real" world. at the same time constraining how other defaults may further extend the world-description. Lukaszewicz [1985) formalizes this intuition for normal default theories . Because of the well-behaved nature of these theories, this is straightforward. The resulting seman­ tics amounts to considering the Tarskian semantics of each of the partial extensions constructed by proceeding mono­ tonically from W toward an extension by repeatedly satisfy­ ing the next (according to some arbitrary ordering of the defaults) applicable normal default by making its conse­ quent true. If ever no more defaults from Dare applicable, the resulting set of models characterizes an extension. Since each step affirms a formula consistent with those affirmed previously, the set of models contracts monotoni­ cally. The intersection of the sets of models from each stage (or the last set, if there are only finitely many) is pre­ cisely the set of models of the extension.

Lukaszewicz' approach applies only to normal defaults, since the required property of semi-monotonicity, which allows each normal default to be treated independently, does not hold for non-normal defaults [Reiter 1980. Theorem 3.2]. Lukaszewicz proposes addressing this prob­ lem by translating non-normal defaults to normal defaults. He argues that, of single-justification defaults, only normal and seminormal defaults have reasonable interpretations. Other defaults are therefore translated to seminormal defaults by conjoining the consequent to the justification:

The translation from seminormal to normal, which is some­ what more controversial, strengthens the consequent to make it identical to the justification:

This makes sense, Lukaszewicz argues, so long as a's that are also -y's are typically j3's. That is. so long as one could al\-y · j3 reasonably augment the theory with: !i ·

One can imagine situations where this is not appropri­ ate. For example, a system for legal reasoning might have a rule suggesting that those with motives who might be guilty should be suspects:

It is clearly reasonable to translate this to:

allowing that there may be reasons not to suspect someone even without knowing their innocence. It is not reasonable to follow through by assuming the guilt of all suspects:

Furthermore - for whatever purpose they may serve - the scheme does not apply to defaults with multiple justifica­ tions. Thus, while Lukaszewicz' semantics covers many cases, there are reasons to want a semantics that cover-s more than normal defaults. To this we now turn.

Because of the failure of semi-monotonicity for non­ normal theories, simply applying one default after another does not, in general, lead to extensions . It is necessary to ensure that the application of each default does not violate· the justifications of already-applied defaults. In the seman· tic domain, this means that Lukaszewicz' simple approach of sequentially restricting the set of models of the first­ order theory, to satisfy each default in turn, will not neces­ sarily lead to the set of models of an extension. Ethering­ ton [1986) develops extra machinery that , essentially , intro­ duces a backtracking (or prunin~) mechanism to the semantics to deal with this problem. While this extension is not particularly difficult conceptually. the technical details are somewhat formidable and the result appears (superfi­ cially) ad /roc . This is partly because the resulting semantics looks radically different from familiar Tarskian or Krip­ kean (or even circumscriptive) model-theories. We present an equivalent semantics below. in a very different guise. This new presentation makes the salient features of the semantics more apparent.· as well as easing comparisons with the semantic theories of other nonmonotonic systems.

Definition: f 1 2:a f1 (&prefers f 1 to f 2)

a : J3l ..... J3,. Consider a default, a = · a set of models,

w f. and ft. f1 E zr . The partial-order corresponding to a, 2:a, over zr is defined as follows:

Intuitively, 2:8 captures a·s preference for more spe­ cialized world-descriptions. in which its consequent holds. over those in which its prerequisite holds and its justifica­ tions are each consistent . but which do not necessarily satisfy its consequent . The idea of preference extends to sets of defaults in the obvious way.

Definition: ft 2:o fz (D prefers f1 to f 2l

'2:0 , over zr is defined as the union of the partialorders given by the defaults of D. I .e. ,

Consider a set of defaults, D. a set of models, r. and f~o f2 E zr. The partial-order corresponding to D,

For a normal default theory, ~ = (D, W). it is suffi­ cient at this point to consider the 2:0 -maximal elements of zMOD(II'J, where MOD (W) is the set of all models of W. Each of these corresponds to the set of all models of an extension of A, and vice versa. 3 As mentioned earlier. the failure of semimonotonicity for non-normal defaults means a more complex approach is necessary for full generality. We must semantically account for non-normal defaults' abil­ ity to require the continued consistency of their justifica­ tions without their explicitly acting to ensure this . We have identified a property of sets of models. which we call srabil­ iry. that provides such an account .

3 Lukaszewicz proves this for an equivalent (though superfi­ cially quite different) formulation .

Definition: Stability

Let .i =(D. W) be a default theorv. and let r be a

~o-maximaJ element of 2J/OD(II') . f is STable for ~ if and onlv if there is a D' CD such that - a:~[ ..... ~, r ~o· MOD(W). and for each ED'. w

In other words. a set of models is stable for a default theory. (D.W). if it is a maximal specialization of the set of models of W. and does not refute the justifications of any of the defaults used in the specialization. This notion of stabil­ ity is related. but not directly analogous. to stability in autoepistemic theories [Moore 1985]. In particular. it incor­ porates elements of what Moore calls "groundedness". For a detailed discussion of the relationship between default logic and autoepistemic logic . see [Konolige 1987].

The stable sets of models for a default theory provide a semantic interpretation for the theory. The soundness and completeness results for this semantics are given by Theorems 1 and 2. respecth·ely.

Theorem 1 - Soundness

If E is an extension for ~. then r = {M IM F £} is stable for .l. I

Theorem 2 - Completeness

If r is stable for ,l, then r is the set of models for some extension of .l. (I.e .. { w I 'if 'Y E r . 'Y f= w} is an extension for .1.) I

Example 1

Consider the default theory:

This theory has the following maximal world­ descriptions: { M I M f= A.B }, { M I M f= A.C } · both of which are stable, so the theory has two extensions, Th ({A, B}) and Th ({A, C}). I

Example 2

has only one maximal world-description: { M I M f= A } , which is not stable . Hence this theory has no exten­ sion. I

4. Discussion

We are now faced with the question of how well motivated this semantics is. It is clearly different from traditional semantic theories. For example, in Tarskian semantics the truth values of the atomic formulae deter­ mine those of every other formula. Similarly. in Kripke semantics. a set of worlds. an accessibility relation, and an assignment of truth values to the atomic formulae deter­ mine what is true in the structure. It is common to have some notion of a structure. and of what it means for any primitive construct of the language to be satisfied by a structure . Logical operators and connectives are also given interpretations. allowing the truth of any construct of the language to be determined l'is-a-vis any structure . Finally. validity and satisfiability are defined in terms of these other notions .

Because of the indexical nature of defaults. it does not seem possible to provide them with such static interpreta­ tions. The proof-theory of default logic places upper-. as well as lower-. bounds on the states of knowledge that can be taken as satisfying the theory. These bounds, however. are determined by the "·ay knowledge is extended. This requires information that is not inherent in typical semantic structures.

For example. imagine the defaults:

Assuming a semantics that interprets defaults in terms of partial world-descriptions. the world-descriptions them­ selves clearly provide insufficient information. Consider a world-description. r. such that r F= ex. 13 and r ~ -(13/\ "Y). Although it seems that the second default should be applica­ ble, this really depends on why r f= ~: because W +-13. or because r is the result of applying the first default. In the former case, the result should be f' = r - {M I -'Y} . In the latter, this is inappropriate , since the assumption of -'Y pre­ cludes the prior assumption of 13. and r· is unstable .

Another justification for a model-theory such as this comes from viewing defaults as operators that transform theories. On this view. the sets of models that make up each world-description correspond to particular theories (in the usual Tarskian sense). The partial-orders associated with the defaults encode the transformations that the defaults induce on these theories. This view helps explain both why individual world-descriptions alone are insuffi­ cient to determine the satisfaction of defaults and why the semantics deals with satisfaction of default theories as a whole, rather than of individual defaults in isolation.

There are related semantic characterizations in the literature . For example. there are the minimal-model semantics of circumscription [McCarthy 1980) and of vari­ ous other forms of closed-world reasoning [Etherington 1986]. These characterize the semantics of certain non­ monotonic formalisms in terms of the minimal elements of an ordered set of structures. The presentation above goes beyond this in the complexity of the structures concerned and in the "post-filtering" of the set of minimal models, but is closely related in spirit. This topic is taken up in detail in [Etherington 1986, 1987). but some of the flavour can be given in the space available here .

The semantics of a theory under the various forms of "closed-world" assumption can be defined in terms of a res­ triction of the set of models of the underlying theory. according to some principle of minimization (typically according to the subset inclusion partial-order over the extensions of some predicates). The above model-theory for default logic similarly provides a principle for determining which models of a first-order theory characterize acceptable belief-sets. in this case based on maximal satisfaction of the set of defaults . There are several significant differences. however . First. rather than an ordering on individual models, an ordering is imposed on sets of models . Second. the ordering is defined in terms of accessibility via a default, rather than strictly in terms of general criteria and intrinsic features of the models themselves. Finally. each extension is determined by a single extremum of the order­ ing, rather than by the set of all extrema .

The first of these differences . as mentioned previously. is necessary to encode the constraints of the theorv . It allows a distinction between what is believed and what is merely consistent with what is believed. It also allows a natural representation of the incompleteness of default theories, which - unlike the models of a first-order theory -do not decide every formula .

The second deviation arises because defaults are gen­ eral. non-homogeneous. inference rules. Consequently. the partial-order relation is potentially more complex for default logic . Lifschitz' (1984. 1986] recent work allowing more general orderings may void this difference, but the question remains open .

Individual extrema determine extensions as a result of the ··brave" (in McDermott's [1982] terminology) character of default logic. Default logic treats each extension as an acceptable ·et of beliefs. with the intention that a reasoner will somehow "choose" a sinele extension within which to reason about the world. Other nonmonotonic formalisms (such as circumscription [McCarthy 1980. 1986]) are based on ··cautious" approaches that accept a default conclusion only if it occurs in all acceptable sets of beliefs. One can easllv construct a variant of default logic that pursues a "cautious" course. (The converse is not obviously true for all "cautious" systems; see (Etherington 1987].) Such a sys­ tem would define the theorems of a default theory to be those formulae true in all extensions. with the obvious change to the semantics: the theorems would then be defined as those formulae true in all models of all stable world-descriptions.

5. Conclusions

Default logic has occasionally been criticized for its lack of a general model-theoretic semantics. To answer this criticism we have presented such a semantics. We have also tried to show the appropriateness and utility of this seman­ tics . We showed that it has merits that justify its use, and suggested it is a useful tool for comparing default logic with other nonmonotonic formalisms .

Our semantics differs from traditional. Tarskian, model-theoretic semantics in two respects: it is global, and it is not structure-oriented. By "global" we mean that there is no notion of satisfaction of individual defaults indepen­ dently of the theory in which they occur (and hence no notion of satisfaction of a theory as incremental satisfaction of its components). The "non-structure-oriented" nature corresponds to the observation that defaults serve less as components of theories than as operators taking theories into other, more complete, theories . We argue that these facets of the semantics are not only justifiable, but serve to highlight important features of the operation of the syntac­ tic mechanisms of default logic.