On the Relation Between Default Theories and Autoepistemic Logic

1 Introduction

Default reasoning can be informally described as jumping to conclusions based on what is normally the case. To say that "power corrupts," for example, is to say that for typical x, in typical situations, x will be corrupted by the exercise of authority.

Default logic [9] is a formalization of default reasoning. An agent 's knowledge base (KB), its collection of facts about the world, is taken to be a first-order theory. De­ fault reasoning is expressed by default rule" of the form

which can be read as, roughly, "if a is provable from the KB, and {3 is consistent with it, then assumew as a default." Unlike ordinary first-order i~ference rules, default rules are

*This research was supported in part by contract N00014-80-C0296 from the Office of Naval Research , and in part by a gift from the System Development Foundation.

ON THE RELATION BETWEEN DEFAULT THEORIES AND AUTOEPISTEMIC LOGIC·

Kurt Konolige

Artificial Intelligence Center and CSLI, SRI International 333 Ravenswood, Menlo Park, Ca. 94025 ( 415)859-2788 KONOLIGE@AI.SRI.COM

defea.,ible: given KB containing just a, for example, the rule above would allow the inference of w, but if ·f3 is added to the KB, then the default rule is no longer applicable. Default rules are thus nonmonotonic inference rules.

In default logic, the default rules operate at a metathe­ oretic level, as they are not expressed in the language of the KB, and are not inference rules within the KB. Rather, they can be thought of as a means of taking a KB and transforming it into another one by the addition of sen­ tences which are not logically derivable from the original. The transformation is defined in terms of a fix-point op­ erator. This formulation of default reasoning leads us to ask several questions, which do not have readily apparent answers. The· first concerns the expressiveness of the logic. Certain simple types of defaults can be readily stated; for example, "power corrupts" could be expressed as

But it is not clear that more complicated constructs could be accommodated. A case in point is conditional defaults, where a default rule is the conclusion of an implication; or defaults whose consequent is itself a default. Because the default rules are not part of the logical language, there is no obvious, straightforward expression of these concepts.

The second question, related to the first, concerns these­ mantics of default theories. Because defaults are expressed as inference rules operating in conjunction with a fixed­ point construction, it is not clear what the meaning of such objects as M {3 is. In some recent work, there have been proposals for a semantics for a restricted class of de­ fault theories [6] and for default theories in general [1] . In both cases, the "semantics" is a reformulation of the KB­ transformation induced by the defaults in terms of restric­ tions on the models of the KB. Although. such a reformu­ lation can provide an alternative view of the construction of default theories, it does not provide a semantics in the sense of providing an interpretation for default rules in a model structure (an interpretive .5emantic.5). Indeed, be­ cause defaults are expressed as inference rules , they are not amenable to interpretation in this fashion.

Our idea in this paper is to define default reasoning within the theory of the KB itself, rather than as a trans­ formation of the KB. If we take the sentences of a KB to be the knowledge or beliefs of an agent, then defaults can be expressed by referring to what an agent doe.m't know. The default that "power corrupts" could be stated informally as:

If x is powerful, then assume x is corrupt if nothing known contradict3 it.

(3)

It is easy to see that such reasoning is defeasible in the presence of additional information about the integrity of x. From a formal point of view, it is clear that to assert this statement, the language of the KB must be augmented by a construction that refers to the KB as a whole.

Let us call a theory containing an operator that refers to the theory itself an indexical theory. We will use the expression L¢> within a theory to mean that the sentence ¢>is part of theory itself. Now we can rephrase the default rule (1) in the following manner, using the operator L:

The intent of a rule of this form is something like: "if a is in the KB, and -.(3 is not in the KB, then w is true." The negation sign in -.(3 arises because we have chosen to use provability operator L which is the dual of the consis­ tency operator M. Because L is an operator of the KB language, we have been able to express the default within the language of the KB itself, rather than as a metatheo­ retic construct.

The introduction of an indexical operator is an added complexity, for now we allow our initial KB to contain not only statements about the world, but also about its own contents. Indeed, even interpreting the modal opera­ tors of ( 4) is problematical. Fortunately, the mathematical properties of indexical theories have recently been stud­ ied by Moore (8] as a formalization for a another type of nonmonotonic reasoning, called autoepi3temic rea3oning, in which an agent reasons about the relationship of her knowl­ edge to the world. He has derived an elegant and natural interpretive semantics for indexical theories incorporating the self-referential operator L. This semantics gives an in­ terpretation to the operator L based on individual model structures.

We are naturally led to ask what relationship exists be­ tween default theories and their corresponding expression in AE logic. Are they essentially different in the sense that agents using each one would have widely differing sets of beliefs? The answer, which is the main result of this pa­ per, is no: default logic and AE logic sanction the same inferences on corresponding initial inputs. This has several important consequences. Since default rules are expressible in AE logic, both default and autoepistemic reasoning can be combined within this single formalism. Also, the formal expression of defaults gains the benefits of an interpretive semantics.

A second and more surprising consequence is that AE logic is no more expressive than default logic, even though the L operator is part of the language: there exists a trans­ lation from every set of AE logic premises into a corre­ sponding default theory. As we shall see, by translating the appropriate AE logic statements, it is possible to construct default theories with the effect of conditional defaults, de­ faults whose conclusion is a default, and so on. The expres, sion of these concepts is still much more natural in terms of the £-operator, but the mathematical properties of the corresponding default theories are the same.

Of independent interest are some results in the theory of AE logic, especially the characterization and equivalence of 3trongly grounded and minimal extensions.

2 A utoepistemic logic

Autoepistemic ( AE) logic was defined by Moore (8] as a for­ mal account of an agent reasoning about her own beliefs. The agent 's beliefs are assumed to be a set of sentences in some logical language augmented by a modal operator L. The intended meaning of L¢> is that ¢> is one of the the agent's beliefs; thus the agent could have beliefs about her own beliefs. For example, consider a space shuttle flight director who believes that it is safe to launch not because of any positive information, but by reasoning that if some­ thing were wrong, she would know about it from her engi­ neers. This belief can be expressed using sentences of the augmented language. If P stands for "it is safe to launch the shuttle," then

expresses the flight director's self-knowledge. Equation (5) is a logical constraint between a belief state ( L-.P) and a condition on the world (P) .

The primary focus of AE logic is a normative one: given an initial (or bau) set of beliefs A about the world, what final set T should an ideal reflective agent settle on? If we restrict ourselves for the moment to languages without the self-belief operator, then clearly an ideal agent should believe all of the logical consequences of her base beliefs, a condition sometimes referred to as logical omni3cience (2]. More formally, let the expression r f= ¢> mean that the sentence ¢> is logically implied by the set of sentences r. Then, if the base set is A, the belief set T of an ideal agent is given by:

The presence of a self-belief operator complicates mat­ ters. Because the intended meaning of L¢> depends on the helief set of the agent, the definition of the belief set' itself becomes circular, which necessitates the use of a fixed-point equation to define T. In this section we will present this definition and give several alternative formulations that will prove useful.

We begin with a language £ for expressing self-belief, and introduce valuations of£. The treatment generally follows and extends Moore [8], but differs in two ways. First, the base language is first-order rather than propositional; but this is a minor change, because no quantifying-in is permit­ ted. Second, ideal belief sets are defined with a fixed-point equation over valuations of the language. This definition is equivalent to Moore's original one, but leads to different insights on the nature of the ideal belief set, simpler proofs of many results, and several natural extensions. Because of space limitations, no proofs are included; they may be found in the fuller version of the paper (Konolige [4]).

Let Lo be a first-order language with functional terms. The normal formation rules for formulas of first-order lan­ guages hold. A ~entence of £ 0 is a formula with no free variables; an atom is a sentence of the form P(tt, · · ·, tn)· We extend £ 0 by adding a unary modal operator L; the ex­ tended language is called£. £ can be defined recursively as containing all the formation rules of £ 0 , plus the following:

An expression Lt/> is a modal atom. Sentences and atoms of Lo are called ordinary. Note that nestings such as LLt/> are modal atoms (and hence sentences) of £ . A sentence has a modal depth n if its modal operators are nested to a depth of n , e.g., L(P V LP) has a modal depth of 2, We use the abbreviation Ln for the set of all sentences of modal depth n or less. Because the argument of a modal operator never contains free variables, there is no quantifying into the scope of a modal atom, e.g., 3xLPx is not allowed.

From the point of view of first-order valuations, the modal atoms Lt/> are simply nilary predicates. Our intended interpretation of these atoms is that 4> is an element of the belief set of the agent. So we will consider valuations of£ to be standard first-order valuations, with the addition of a belief set r. The atoms L</> are interpreted as true or false depending on whether 4> is in r.

The interaction of the interpretation of L with first-order valuations is often a delicate matter in this paper, and so a perspicuous terminology for talking about valuations is necessary. In particular, it is often useful to decouple the interpretation of modal and ordinary atoms. First-order valuations are built upon the truthvalues of atoms: for or­ dinary atoms, this is given by a structure (U, <p, 'R), where <p is a mapping from terms to elements of the universe U, and n is a set of relations over U, one for each predicate. We will refer to any such structure as an ordinary index, and denote it with the symbol I . Modal atoms are given a truth value by a belief set r' which is called a modal index.

The truthvalue of any sentence in £ can be determined by the normal rules for first-order valuations, given an or­ dinary and modal index. We write FI.r </> if a valuation (I, r) satisfies </>. The valuation rule for modal atoms can be written as:

A valuation which makes every member of a set of sen­ tences true is called a model of the set. A sentence which is true in every member of a class of valuations is called valid with respect to the class. The following classes of valuations are useful:

A sentence </> is a fir~t-order con~equence (FOC) of a. set of sentences E if it is true in all models of E. E is clo&ed under fir&t-order con&equence if it contains all sentences that are true in all of its models.

2.2 Autoepistemic extensions

Now we return to the original question of what an ideal reflective agent should believe. Obviously, we want to use equation (6), with an appropriate choice for logical impli­ cation. Given that the intended meaning of L is &elf-belief, it becomes obvious that we should consider all models in which the interpretation of L</> is the belief set of the agent itself, that is, the valuations we consider all have a modal index which is the belief set of the agent. Following Moore, we call such valuations autoepi&temic (or AE), and define the concept of an extension of a base set of beliefs.

Definition 2.1 Any &et of &entence& T which &ati&fie& the equation

i& an autoepistemic extension of A.

This is a fixed-point equation for the belief set T of a reflective agent, given premises A. 1 It is similar to the belief set definition for a nonreflective agent (equation 6) in that it contains A and is closed under first-order consequence. AE extensions are candidates for the belief sets of ideal reflective agents; however, as we will show in section 2.4 below, there is an additional restriction which such sets should obey.

Example 2.1 A base set A may give rise to one, no, or several AE extensions. As ~e show below, any set of or­ dinary sentences has exactly one extension. The extension for the base set A= {P} contains all the first-order conse­ quences of P, but no other ordinary formulas. It contains modal atoms of the form L</>, where 4> is a FOC of A, and ...,£1/J, where 1/J is not a FOC of A.

The base set A = {LP} has no extensions. For suppose T is such an extension; either P E T or P fl. T. Clearly the latter cannot be the case, for then for any sentence 4>, A ~T ¢> (because ~I,T A is false for any I). Now suppose P E T. In this case, we can construct an interpretation which satisfies A but falsifies P, namely one in which I makes P false. Therefore it cannot be that A ~T P, and soP is not in T, a contradiction.

1 Moore (8] originally defined the concepts of soundness and com­ pleteness of a belief set relative to a base set, using AE valuations. AE extensions are an equivalent definition; see Konolige [4).

The base set {LP :::> P} has two extensions, one of which contains P, and the other of which does not.

The base set { -,£p :::> Q, -,£Q :::> P} has two extensions; in one of them, LP is true and LQ is not, and in the other the reverse.

Suppose an agent has only ordinary sentences in her base set A. This base set can be used to construct a belief set in an iterative fashion, starting with ordinary formulas and continually adding sentences with deeper nestings of modal operators.

Proposition 2.2 (Marek) If A i~ a ~et of ordinary ~en­ tence~, then it ha~ exactly one AE extension T. To i~ the fir~t-order clo~ure of A.

We now turn our attention to an alternative characteri­ zation of AE extensions. Essentially, we seek to remove the self-referential index T in the implication operator of Defi­ nition 2.1. To do this, we introduce and analyze a special type of belief set, the ~table ~et.

2.3 Stable sets

Following Stalnaker (10), we call a belief set r .stable if it satisfies the following three properties:

1. r is closed under first-order consequence. 2
2. If t/> E r, then Lt/> E r.
3. If t/> ¢ r, then-,£¢> E r.

The connection between stable sets and AE extensions is the following:

Proposition 2.3 (Moore) Every AE exten~ion of A i~ a ~table ~et containing A.

The strict converse of this proposition is not true, since there can be stable sets containing A which are not AE extensions of A. The simplest example is A= {LP}, which has no AE extension (see example 2.1). Yet there are many stable sets which contain LP.

A partial converse is available if we consider stable sets as AE extensions of their own ordinary sentences.

Proposition 2.4 Every ~table ~et r ~ an AE exten~ion of ro.

2 Stalnaker considered propositional languages and so used tauto­ logical consequence.

Stable sets are thus AE extensions of their ordina.ry sen­ tences. From proposition 2.2, we know that every such AE extension is unique; hence every stable set is uniquely determined by its ordinary sentences. .

Proposition 2.5 (Moore) If two ~table ~et~ agree on or· dinary formulu, they are equal.

The set of ordinary formulas contained in a stable set is closed under first-order consequence. Different .stable sets thus have different sets of FO-closed ordinary formulas. We now show that stable sets cover the sets of FO-closed ordinary formulas, that is, every such FO-closed set is the ordinary part of some stable set.

Proposition 2.6 Let W be a ~et of ordinary formula~ clo~ed under fir~t-order con~equence. There i~ a unique ~ta­ ble ~et r ~uch that ro = w. w i~ called the kernel of the ~table ~et.

We are now ready to give a second semantic character­ ization of AE extensions. Since AE extensions are stable, let us consider restri<;,ting the range of modal indices on the logical implication operator to just stable sets; we indicate this by ~SS· From proposition 2.5, we know that the or­ dinary formulas of a stable set uniquely determine it. As usual, let T0 be the set of ordinary formulas ofT, and T0 the set of ordinary formulas not in T . Then, if Tis stable, it must be the case that ~Tis equivalent to LToU..,LTo ~ss, because LT0 and ...,£if0 specify only those models in which the modal index is the unique stable set containing exactly the ordinary formulas To. This suggests how we can replace ~T in the definition of AE extensions.

Proposition 2. 7 T i~ an AE exte~ion of A if and only if it ~ati~fie~ the equation

By using a stronger type of implication (~ss over stable sets), we have been able to eliminate all self-referential as­ sumptions except for those involving the ordinary formulas of T . This proposition also hints that the nesting of £­ operators gives no extra expressive power to the language, since only ordinary formulas are important in character­ izing the fixed point. This is indeed so, and we have the following proposition.

Proposition 2.8 Every ~entence in .C i~ equivalent {under ~ss) to a ~entence who~e modal ato~ are of the form L¢>, with t/> E Co.

2.4 Strongly grounded extensions

One way of looking at the equation of proposition (2.7) is to see what type of reasoning it sanctions for reflective agents. An agent is justified in believing at least the conse­ quences (under F=ss) of her base set A, together with the assumptions LT0 and ...,L'f0 · Moore has called belief sets defined in this way grounded in A, because they are derived from A and assumptions about self-belief. 3 However, this notion of groundedness is a fairly weak one, and we may wish to strengthen it. Conside~, for example, the base set A= {LP :::> P}. A has two AE extensions, which we call T and T' (see example 2.1). T contains P and LP, while T' does not contain P, but has ...,LP. The difference between these is precisely whether LP is introduced as an assump­ tion in the fixed-point equation (2.7). For the belief set T, the agent's belief in Pis grounded in her assumption that she believes P. If she chooses to believe P , she is justified in believing it precisely because she made it one of her be­ liefs. This certainly seems to be an anomolous situation, since the agent can, simply by choosing to assume that a fact about the world is true, be justified in that assumption without any objective information.

We would like to define a stronger notion of groundedness to eliminate this circularity of justifications. Now consider the belief set definition· given in proposition 2. 7:

The set of ordinary sentences in the belief set is T0 · LT0 is the assumption that the agent believes all of these sen­ tences. There would be no circular justifications if we re­ place LTo by LA in the fixed-point definition: we are as­ sured that the derivation of facts about the world does not depend on the assumption of belief in those facts . The inclusion of LA is necessary because an ideally reflective agent should at least believe that her base beliefs are be­ liefs.

From this discussion, we define the following notion of Jtrongly grounded.

Definition 2.2 A Jet of JentenceJ r iJ strongly grounded in A if it obeyJ the conJtraint:

A certain natural class of AE extensions is strongly grounded, as we will shorty show. But not every AE ex­ tension is strongly grounded.

Example 2.9 The base set A= {LP :::> P} has two exten­ sions, only one of which is strongly grounded. The exten­ sion containing P cannot be strongly grounded, because P cannot be derived without the assumption of LP.

3 Moore actually used a different but equivalent definition of ground­ edness; in his version, a set r is grounded in A if it satisfies:

A more complicated case is the base set A = { LP :::> Q, LQ :::> P}. Again there are two extensions, one con­ taining the ordinary formulas P and Q, and one without them. For the former, LP and LQ must be assumed to­ gether in order to justify P and Q. Because they cannot be derived without this assumption, this extension is not strongly grounded.

The extension of a set of ordinary formulas A is strongly grounded, because every ¢> E T0 is in the first-order closure of A, and so in the stable set containing LA.

Strongly grounded extensions are conservative in what they assume about the world, given the base beliefs. As shown in example 2.9, the base set {LP :::> P} has oniy one strongly grounded extension, for which P is not a belief. In fact, strong groundedness is closely related to another con­ cept, the minimality of ordinary sentences in an extension.

Definition 2.3 An AE extenJion T of A iJ minimal for A if there iJ no other extenJion T' of A Juch that T'o C T0 ·

Minimal extensions always exist for a base set A that has extensions. Note that there can be more than one minimal extension for a given base set, e.g., A = { ...,LP :::> Q, ...,LQ :::> P} has two extensions, both of whiCh are minimal for A. The base set A = {LP :::> P} has a single minimal exten­ sion, the one which doesn't contain P. Minimal extensions have a natural appeal as candidates for ideal reflective be­ lief sets, because they limit the assumptions an agent makes about the world.

We now prove that, in fact, the minimal AE extensions of A are exactly the extensions strongly grounded in A. Thus we have two independent motivations for choosing these extensions as ideal belief sets.

Proposition 2.10 An AE extension of A iJ Jtrongly grounded in A if and only if it iJ minimal. Strongly­ grounded extenJionJ obey the equation:

2.5 Normal form

The base sentences A of an AE extension can be put into a normal form that will be useful in the next section. We will use the following two facts about sentences of C in establishing a normal form.

1. Every AE sentence is equivalent to a sentence contain­ ing modal atoms only of the form L¢> or ...,L¢>, where ¢> is an ordinary sentence.
2. L¢> II Lt/J is equivalent to L( ¢> II t/J ).

These equivalences hold when considering interpretations whose modal indices are stable sets; see Konolige [4] .

The first of these facts enables us to consider only base sets A with no nesting of modal operators. As we hinted in the last section, the nesting of £-operators lends no extra expressive power to the language.

In deriving a normal form for a set of sentences A, we first convert A to an equivalent set without nesting of modal op­ erators, and then, using first-order valid operations, extract all modal atoms from the scope of quantifiers.

Proposition 2.11 Every 3et of .C-3entence3 iJ equivalent (under f=ss) to a 3et in which each 3entence iJ of the form:

with a, {3;, and w all being ordinary 3entence3. Any of the di3ju.nct3, except for w, may be ab3ent.

3 Default and AE extensions

In this section we briefly review default theories, and then present an effective syntactic translation of an arbitrary de­ fault theory W into a set of sentences W' of AE logic. The main results of this paper are: {1) every default theory has a corresponding AE logic base set A whose minimal exten­ sions are exactly the extensions of the default theory; and {2) every AE logic base set A has a corresponding default theory whose extensions are the minimal AE extensions of A. The translation between the two systems is effective and local, that is, each sentence or default rule is translated in isolation from the others. 4

3.1 Default extensions

As defined by Reiter [9], a default theory is a pair (W, D), where W is a set of first-order sentences, and D is a set of defaults, each of which has the form:

A default dis satisfied by a set of sentences r if either {1) a is not in r or some ...,pi is in r (the premisses of the rule are not satisfied), or {2) w. is in r (the conclusion is satisfied). A default extension of (W, D), informally, is a minimal set of sentences containing W, closed under first­ order consequence, and satisfying all the defaults D.

If none of a, {3;, or w contain free variables, then the default is called clo3ed. An open default is treated as a schema for the set of closed defaults that are·its substitution instances. We thus need only consider closed defaults, as long as we allow default theories to contain a denumberably infinite set of them.

Default extensions have many of the same properties as AE extensions. There may be one, no, or many extensions of a default theory. The following examples are analogous to the AE extensions in example 2.1.

4 Imielinski (3] defines the weaker notion of a modular translation: the defaults and first-order parts must be translated independently. Obviously, any local translation is modular.

Example 3.1 The default extension for the theory ({P},0) (no defaults) is exactly the first-order conse­ quences of P .

The theory (0, P : I P) has one extension, the set of all first­ order valid sentences. P i~ not an element of this extension. This differs from the case of AE extensions for {LP :::> P}; there is an extension which contains P.

The theory (0, {M...,PIQ, M...,QIP}) has two extensions; in one of them, P is true and Q is not, and in the other the reverse .

These examples are instructive by comparison to AE ex­ tensions. If the theory (W, D) contains no defaults (D empty), then there is exactly one extension, which is the first-order part of the AE extension of W. In general, a default of the form a: Mf31w corresponds to the AE sen­ tence La II ...,£...,{3 :::> w; thus, in the third default theory of the example, there are two default extensions, correspond­ ing to the first-order parts of the two AE extensions of { -,£p :::> Q, -,£Q :::> P}. However, note the difference in the case of the second default theory of this example. The default P : I P has only one extension, in which P does not appear. The AE set { LP :::> P} has two extensions; the one in which P appears arises from the ability of AE exten­ sions to support circular justifications (assuming LP, the sentence LP :::> P gives a derivation of P). So although it appears that default extensions have corresponding AE ex­ tensions for a suitable transformation of the defaults, not all AE extensions will have corresponding default extensions. In fact, as we show below, default extensions correspond to minimal AE extensions.

3.2 Defaults as self-belief

We now define a simple transformation from a default the­ ory (W, D) to a set of AE sentences A, such that the default extensions of (W, D) are exactly the kernels (the first-order part) of the minimal AE extensions of A. Thus (as we prove), there is an exact correspondence between default extensions for (W, D) and minimal AE extensions for A.

The transformation is:

As we mentioned in the introduction, this is the natural interpretation of defaults in terms of introspective knowl­ edge. A paraphrase of the AE sentence for agent would be something like the following: "If I know that a is true, and I have no knowledge that any of the {3; are fal3e, then w must be true." The key phrase has been emphasized; it is in reasoning about what is not known that the nonmono­ tonic character of AE logic appears. However, the role of the other parts of the sentence (La and w) also deserves closer scrutiny; for example, why does w appear as the consequent, and not Lw? As it stands, this is the trans­ formation that yields the correspondence between default

t

and AE extensions. We will comment more extensively on the form transformation later, after the basic results are presented.

In a default, we allow either a or any of the M {3; to be missing; the corresponding AE sentence just deletes the appropriate conjunct in the antecedent. The conclusion of the default must always be present (defaults with no conclusion are senseless). Let D' be the set of sentences formed by taking the transforms of defaults D; we call the set {W, D'} the AE transform of (W, D).

Default extensions are the fixed points of an operator r(V). This operator is meant to formalize the informal criteria given above for the extensions of (W, D), namely, it should contain W, be closed under first-order consequence, and satisfy all of D. Let V be an arbitrary set of first­ order sentences. Then r(V) is the smallest set satisfying the following properties:

D2. r(V) is closed under first-order consequence. 5

Extensions are fixed-points of r, i.e., any set E satisfying E = r(E). As a fixed-point definition, it is similar to the fixed-point account of minimal AE extensions (proposition 2.10). The parameter of r(V) essentially fills the role of the assumptions .,L'f0 , since .,{3 must not be present in order for the default to be satisfied. Minimality is part of the definition of r(V) (the least set satisfying the conditions D1-D3); if it were excluded, then default extensions coiTe­ sponding to non-minimal AE extensions would be present.

Now consider a particular default theory (W,D} and an associated extension E = r(E). E is closed under first­ order consequence, and hence is the kernel of a unique sta­ ble set . This stable set is closely related to the AE trans­ form of (W, D) : it is a minimal stable set containing the AE transform. We prove this result as the following propo­ sition.

Proposition 3.2 Let (W, D) be a default theory, with A = {W, D'} it3 AE transform. Suppose E i3 an extension of the default theory. Then E is the kernel of a minimal 3table .5et containing A and .,LE.

Using this result, we can show that a default theory and its AE transform have the same extensions.

Theorem 3.3 Let A be the AE transform of a default the· ory !::!.. A set E is a default exten.5ion of 1::!. if and only if it is the kernel of a minimal AE extension of A .

5 In the original definition, this is stated in terms of deduction rather than logical consequence.

3.3 Semantics

The semantics of AE sentences is an interpretive seman­ tics, in the sense that a sentence ¢1 is true or false in an interpretation FI.r· The interpretation of modal atoms is given by the modal index r, according to equation 8. The interpretations themselves are straightforward augmenta­ tions of standard first-order interpretations. The problem­ atic characteristics of AE logic, from semantical point of view, occur in the fixed-point definition of extensions {2.1), in which only interpretations containing a certain modal index are considered. So, although it is hard to construct and analyze extensions, all of our ordinary intuitions about the meaning of the language C, its semantics with respect to individual interpretations, is still available.

To give an example of this sort: consider the difference between the two default sentences

The first of these states that in any interpretation in which Bird( Tweety) is a belief, and ...,Fly( Tweety) is not a belief, Fly( Tweety) will be true. The antecedent of the second de­ fault is less strict: it states only that Bird( Tweety) must be true. The second default permits case analysis of a type not sanctioned by the first. For example, suppose it is known that either Tweety is a bird, or that Tweety is housebro­ ken (Houseb(Tweety)). In every interpretation in. which -,Fly( Tweety) is not a belief, and the second default sen­ tence is true, Houseb( Tweety) V Fly( Tweety) is true. On the other hand, nothing can be concluded by assuming the first default sentence is true, because Bird(Tweety) may not be a belief. As Etherington [1, p. 34] has noted, the second sentence seems more in accord with our intuitions about the way defaults should work.

Another example of the utility of interpretive semantics is in the concepts of equivalence and substitution. Two for­ mulas ¢1 and t/J' of C are equivalent if they have the same truthvalue in all models. Because the definition of AE ex­ tensions is framed in terms of the interpretive semantics, ¢/ can be substituted anywhere ¢1 occurs in a base set A, without changing the AE extensions of A. We used this fact extensively in arriving at the normal form for AE sentences in section 2.5.

3.4 Expressiveness

The question of expressiveness can be phrased as follows: Is it the case that default sentences of the type (13), or per­ haps other AE sentences involving complicated construc­ tions such as embedded £-operators, have no counterpart in default theories? On the face of it this would seem a. plausible conjecture, since the L-opera.tor is part of the language, while default rules are not. However, it turns out that AE logic is no more expressive than default logic: there is an effective transformation of ~y base set of AE sentences into a default theory, such that the default exten­ sions are exactly the kernels of the minimal AE extensions. To show this, we rely on the fact (see proposition 2.11) that every set of sentences of .C has an equivalent normal form in which every sentence looks like:

where all of a, /3;, and ware ordinary sentences, w is always present, and any of the modal atoms may be missing,.

Given any set of £-sentences A in normal form, it is pos­ sible to effectively construct a corresponding default theory (W, D), in the following way. Any w that appears without other disjuncts is put into W. All other sentences are trans­ formed into defaults, in the manner indicated by equation 11. It is easy to see that A is the AE transform of (W, D); by theorem 3.3, these two have essentially the same exten­ sions. More precisely, we have proven the following theo­ rem:

Theorem 3.4 For any Jet of JentenceJ A of .C, there i.9 an effectively comtructable default theory (W, D) Juch that E i.9 a default extenJion of (W, D) if and only if it u the kernel of a minimal extenJion of A .

So, suprisingly, default theories have precisely the same expressiveness as AE logic over the modal language .C. However, two caveats should be noted.

The first is that the expression of various statements about defaults or autoepistemic reasoning may be much more natural in .C, because the form of sentences is much less constrained than that of the default inference rules. For example, the second type of default (equation 13) is translated into the default rule:

The atom Bird( Tweety) does not appear in the antecedent of the default, but somewhat unnaturally in the consequent.

The second caveat is that, if we extend .C by allowing quantifying-in (i.e., expressions such as 3x.L<P(x)), in all likelihood theorem 3.4 will no longer hold. There are a number of reasons to think this; perhaps the most com­ pelling is Levesque's observation [5] that in the presence of quantifying-in, there are sentences with nested belief oper­ ators that cannot be reduced to sentences without them.

4 Conclusion

Given the current proliferation of nonmonotonic for­ malisms, it seems wise to establish comparisons among them, especially regarding expressiveness. The results pre­ sented here show that there is an exact correspondence be­ tween AE logic over .C and default theories. There is an effective, local translation between the two that preserves theoremhood, in that the default extensions are the first­ order part of the minimal AE extensions.

5 Acknowledgements

Many thanks to David Etherington, Joseph Halpern, Hec­ tor Levesque, Karen Myers, and Raymond Reiter for read­ ing and commenting on drafts of this paper.