Semantical Considerations on Nonmonotonic Logic

ABSTRACT

Commonsense reasoning is "nonmonotonic" in the sense that we often draw conclusions on the basis of partial information that we retract when we are given more complete informatlon. Some of the most interesting products of the recent attempts to formalize nonmonotonic reasoning are the nonmonotonic logics of McDermott and Doyle [McDermott and Doyle, 1980] [McDermott, 1982]. These logics, however, all have peculiarities that suggest they do not quite succeed in capturing the intultions that prompted their development. In this paper we give a reconstruction of nonmonotonic logic as a model of an ideally rational agent's reasoning about his own beliefs. For the resultlng system, called autoepistemic log!~, we define an intuitively based semantics for which we can show autoepistemic logic to be both sound and complete. We then compare the McDermott and Doyle logics to autoeplstemlc logic, showing how it avoids their peculiarities.

I INTRODUCTION

It has become generally acknowledged in recent years that one important feature of ordinary commonsense reasoning that standard logics fall to capture is its nonmonotoniclty. An example frequently given to illustrate the point is the following: If we know that Tweety is a bird, in the absence of evidence to the contrary, we will normally assume that Tweety can fly. If, however, we later learn that Tweety is a penguin, we will withdraw our prior assumption. If we try to model this in a formal system, we seem to have a situation where a theorem P is derivable from a set of axioms S, but is not derivable from some set S' that is a superset of S. Thus the set of theorems does not increase monotonically with the set of axioms; hence this sort of reasoning is said to be "nonmonotonic." As Minsky [1974] has pointed out, standard logics are always monotonic, because their inference rules make every axiom permissive. That is, the inference rules are always of the form "pis a theorem 1f Q 1 , ·.· ,Qn are theorems," so new axioms can only make more theorems derivable; they can never result in a previous theorem being invalidated.

Robert c. Moore

Artlficial Intelligence Center SRI International, Menlo Park, CA 94025

Recently, there have been a number of attempts to formalize this type of nonmonotonlc reasoning. The general idea is to allow axioms to be restrictive as well as permissive, by employing inference rules of the form "P is a theorem lf Ql' ··· ,Qn are not theorems." The inference that birds can fly ~handled by having, in effect, a rule that says that for any X, "X can fly" is a theorem if "X is a bird" is a theorem and "X cannot fly" is not a theorem. If all we are told about Tweety is that he is a bird, then we will not be able to derive "Tweety cannot fly," and the inference to "Tweety can fly" will go through. If we are told that Tweety is a penguin and we know that no penquln can fly, we will be able to derive the fact that Tweety cannot fly, and the inference . that Tweety can fly will be blocked.

One of the most interesting embodiments of this approach to nonmonotonic reasoning is McDermott and Doyle's "nonmonotonlc logic" [McDermott and Doyle, 1980] [McDermott, 1982]. McDermott and Doyle modify a standard first-order logic by introducing a sentential operator "M" whose informal interpretation is "is consistent." Nonmonotonic inferences about birds being able to fly would be licensed in their system by the axiom [McDermott, 1982, p. 33]

(ALL X)(BIRD(X) /\ M(CAN-FLY(X)) -> CAN-FLY(X)).

This formula can be read informally as "For all X, if X is a bird and it is consistent to assert that X can fly, then X can fly." McDermott and Doyle can then have a single, general nonmonotonlc inference rule, whose intuitive content is "MP is

derivable 1f -p is not derivable."

McDermott and Doyle's approach to nonmonotonic reasoning seems more interesting and ambitious than some other approaches in two respects. First, since the principles that lead to nonmonotonlc inferences are explicitly represented in the logic, those very principles can be reasoned about in the logic. That is, if P is such a principle, we could start out believing Q -> P or even MP -> P, and come to hold P by making inferences, either monotonic or nonmonotonlc. So, if we represent the belief that birds can fly in McDermott and Doyle's way, we could also represent various inferences that would lead us to adopt that belief. Second, since they use only general inference rules, they are able to provide a formal semantic interpretation with soundness and completeness proofs for each of the logics they define. In formalisms that use content-specific nonmonotonic inference rules dealing with contingent aspects of the world (i.e., it might have been the case that birds could not fly), it is difficult to see how this could be done. The effect is that the logics are justified by the meaning of the nonmonotonic inferences in McDermott and Doyle's formulas involved.

There are a number of problems with McDermott and Doyle's nonmonotonic logics, however. The first logic they define [McDermott and Doyle, 1980] gives such a weak notion of consistency that, as they point out, MP is not inconsistent with -p, That is, it is possible for a theory to assert simultaneously that P is consistent with the theory and that P is false. Subsequently McDermott [1982] tried basing nonmonotonic logics on the standard modal logics T, S4, and SS. McDermott discovered, however, that the most plausible candidate for capturing the notion of consistency that he wanted, nonmonotonic SS, collapses to ordinary SS and is therefore monotonic. In the rest of this paper we show why these problems arise and how to avoid them.

II NONMONOTONIC LOGIC AND ----- AUTOEPISTEMIC REASONING

The first step in analyzing nonmonotonic logic is to determine what sort of nonmonotonic reasoning it is meant to model. After all, nonmonotonicity is a rather abstract syntactic property of an inference system, and there is no a priori reason to believe that all forms of nonmonotonic reasoning . should have the same logical basis. In fact, McDermott and Doyle seem to confuse two quite distinct forms of nonmonotonic reasoning, which we will call default reasoning and autoepistemic reasoning. They talk as though their systems are intended to model the former, but they actually seem much better suited to modeling the latter.

By default reasoning, we mean drawing plausible inferences from less than conclusive evidence in the absence of any information to the contrary.. The examples about birds being able to fly are of this type. If we know that Tweety is a bi~d, that gives us some evidence that Tweety can fly, but it is not conclusive. In the absence of information to the contrary, however, we are willing to go ahead and make the assumption that Tweety can fly. Now even before we do any detailed analysis of nonmonotonic logic, we can see that there will be problems in interpreting it as a model of default reasoning: In the formal semantics McDermott and Doyle provide for nonmonotonic logic, all the nonmonotonic inferences are valid. Default reasoning, however, is clearly not a form of valid inference. 1

Consider the belief that lies behind our willingness to infer that Tweety can fly from the fact that Tweety is a bird. It is probably something like most birds can fly, or almost all birds can fly, or a typical bird can fly. To model this kind of reasoning, in a theory whose only axioms are "Tweety is a bird" and "Most birds can fly," we ought to be able to infer (nonmonotonically) "Tweety can fly." Now if this were a form of valid inference, the conclusion would be guaranteed to be true provided that the premises are true. This is manifestly not the case. The premises of this inference give us a good reason to draw the conclusion, but not the iron-clad guarantee that validity demands.

Now reconsider McDermott's formula that yields nonmonotonic inferences about birds being able to fly:

(ALL X)(BIRD(X) /\ M(CAN-FLY(X)) -) CAN-FLY(X))

McDermott suggests as a gloss of this formula "Most birds can fly," which would indicate that he thinks of the inferences it licenses as default inferences. But lf we read M as "is consistent" as McDermott and Doyle repeatedly tell us to do elsewhere, the formula actually says something quite different: "For all X, if X is a bird and it is consistent to assert that X can fly, then X can fly." Since the inference rule forM is intended to convey "MP is derivable lf -p is not derivable" the notion of consistency McDermott and Doyle have in mind seems to be that P is consistent if -p is not asserted. McDermott's formula, then, says that the only birds than cannot fly are the ones that are asserted not to fly. If we have a theory whose only axioms are this and an assertion to the effect than Tweety is a bird, then the conclusion that Tweety can fly would be a valid inference. That is, if it is true that Tweety is a bird, and it is true that only birds asserted to be unable to fly are in fact unable to fly, and Tweety is not asserted to be unable to fly, then it must be true that Tweety can fly.

This type of reasoning is not a form of default reasoning at all; it rather seems to be more like reasoning about one's own knowledge or belief. Hence, we will refer to it as autoepistemic reasoning. Autoepistemic reasoning, while different from default reasoning, is an important form of commonsense reasoning in its own right. Consider my reason for believing that I do not have an older brother. It is surely not that one of my parents once casually remarked, "You know, you don't have any older brothers," nor have I pieced it together by carefully sifting other evidence. I simply believe that if I did have an older brother I would surely know about it, and since I don't know of any older brothers, I must not have any. This is quite different from a default inference based on the belief, say, that most MIT graduates are oldest sons, and that, since I am an MIT graduate, I am probably an oldest son.

Default reasoning and autoeplstemlc reasoning are both nonmonotonlc, but for different reasons. Default reasoning ls nonmonotonlc because, to use a term from philosophy, lt ls defeasible. Its conclusions are tentative, so, given better information, they may be withdrawn. Purely autoepistemlc reasoning, however, ls not defeasible. If you really believe that you already know all the instances of birds that cannot fly, you cannot consistently hold to that belief and at the same ~!me accept new instances

of birds that cannot fly.

Autoeplstemlc reasoning is nonmonotonlc because the meaning of an autoeplstemlc statement ls context-sensitive; lt depends on the theory ln which the statement ls embedded. If we have a theory whose only two axioms are

BIRD(TWEETY)

(ALL X)(BIRD(X) /\ M(CAN- FLY(X)) -> CAN-FLY(X))

then MP does not merely mean that P is consistent, lt means that P ls consistent with the nonmonotonlc theory that contains only those two axioms. In this theory, we would expect CAN­ FLY(TWEETY) to be a theorem. If we change the theory by adding -cAN-FLY(TWEETY) as an axiom, then we change the meaning of MP to be that P is consistent with the nonmonotonlc theory that contains only the axioms

-cAN-FLY(TWEETY) BIRD(TWEETY) (ALL X)(BIRD(X) /\ M(CAN-FLY(X)) -) CAN-FLY(X)),

and we would not expect CAN-FLY(TWEETY) to be a theorem. The operator M changes lts meaning with context just as do English words such as "I," "here," and "now. The nonmonotonlclty of autoeplstemlc theories should therefore be no more puzzllng than the fact that "I am hungry" can be true when uttered by a particular speaker at a particular time, but false when uttered by a different speaker at the same time or the same speaker at a different time. So we might say that autoeplstemlc reasoning ls nonmonotonlc because it ls indexical.

III THE FORMALIZATION OF AUTOEPISTEMIC LOGIC

Rather than try directly to analyze McDermott and Doyle's nonmonotonlc logic as a model of autoeplstemlc reasoning, we will first define a logic that we can show does capture what we want to model about autoepistemlc reasoning and then compare nonmonotonlc logic to that. We will call our logic, naturally enough, autoepistemlc logic. The language will be much like McDermott and Doyle's, an ordinary logical language augmented by autoeplstemic modal operators. McDermott and Doyle treat consistency as their fundamental notion, so they take M as the basic modal operator and define lts dual L to be ~-. Our logic will be based on the notion of belief, so we will take L to mean "ls belleved," treat lt as prlm! tive, and define Mas -L-. In any case, this gives us the same notion of consistency as theirs: A formula is consistent lf lts negation ls not believed. There are some problems about the meaning of quantifying into the scope of an autoeplstemlc operator that are not relevant to the main point of this paper, so we will llmlt our attention to propositional autoeplsteml~ logic.

Autoeplstemlc logic ls intended to model the beliefs of an ideally rational agent reflecting upon hls own beliefs. The primary objects of interest are sets of formulas of autoeplstemlc logic which are interpreted as the total beliefs of such agents. We will call such a set of formulas an autoeplstemlc theory. The truth of an agent's beliefs, expressed as a propositional autoeplstemlc theory, will be determined by (1) which propositional constants are true ln the external world and (2) which formulas the agent believes. A formula of the form LP will be true for an agent just ln case P ls ln hls set of beliefs. To formalize this, we define notions of interpretation and model as follows:

We proceed in two stages. First we define a propositional interpretation of an autoeplstemlc theory T to be an assignment of truth-values to the formulas of the language of T that ls consistent with the usual truth-recursion for propositional logic and any arbitrary assignment of truth-values to propositional constants and formulas of the form LP. A propositional model (or simply model) of an autoeplstemlc theory ls a propositional interpretation of T ln which all the formulas of T are true. So the propositional interpretations and models of an autoeplstemlc theory are just those we would 'get in ordinary propositional logic by considering all formulas of the form LP to be propositional constants. We therefore inherit the soundness and completeness theorems of propositional logic; !.e., a formula P ls true ln all the propositional models of an autoeplstemlc theory T lf and only if lt ls a tautological consequence of T (i.e., derivable from T by the usual rules of propositional logic) . Next we define an autoeplstemlc interpretation of an autoeplstemlc theory T to be a propositional interpretation of T ln which for every formula P, LP is true lf and only lf P is in T. An autoeplstemlc model of T ls an autoeplstemlc interpretation of T ln which all the formulas of T are true. So the autoeplstemlc interpretations and models of T are just the propositional models and interpretations of T that conform to the

intended meaning of the modal operator L.

Given this semantics for autoeplstemlc logic, what do we want from a notion of inference for the logic? From an epistemological perspective, the problem of inference is the problem of what set of beliefs (theorems) an agent ought to adopt on the basis of hls initial premises (axioms). Since we are trying to model the beliefs of a rational agent, we want the agent's beliefs to be sound with respect to hls premises: We want a guarantee that the beliefs are true provided that the premises are true. Moreover, as an ideally rational agent, we want the agent's beliefs to be semantically complete: We want the beliefs to contain everything that the agent would be semantically justified in concluding from the assumption that his beliefs are true and the knowledge that they are his beliefs. An autoepistemic logic that meets these conditions can be viewed as a competence model of reflection upon one's own beliefs. Like competence models generally, it assumes unbounded resources of time and memory, and is therefore not a plausible model of any finite being. It is, however, the model to which the behavior of rational agents ought to converge as their time and memory resources increase.

Formally, we will say an autoepistemic theory T is sound with respect to an initial set of premises A if and only if every autoepistemic interpretation of T which is a propositional model of A is a model of T. This notion of soundness guarantees that all of the agent's beliefs are true whenever all his premises are true. Given our semantic definitions, the world will always be an autoepistemic interpretation of an autoepistemic theory T. So if all the formulas of T are true in every autoepistemic interpretation of T where all the formulas of A are true, it follows that if all the formulas in A are true in the world then all the formulas in T will be true in the world. However, if there is an autoepistemic interpretation of T in which all the formulas of A are true but some formulas of T are false, if that model is the way the world actually is, then all the formulas of A will be true in the

world and some formulas of T will not.

Our formal notion of completeness is that an autoepistemic theory T is semantically complete if and only if T contains every formula that is true in every autoepistemic model of T. If a formula P is true in every autoep1stemic model of an agent's beliefs, then it must be true if all the agent's beliefs are true, and an ideally rational agent should be able to recognize that and infer P. On the other hand, if P is false in some autoepistemic model of the agent's beliefs, for all he can tell that model might be the way the world actually is, so he should not believe P.

The next problem is to give a syntactic characterization of the autoepistemic theories that satisfy these conditions. In a monotonic logic, the usual procedure is to define a collection of inference rules to apply to the axioms. In a nonmonotonic logic this is a nontrivial matter. Much of the technical ingenuity of McDermott and Doyle's system lies in simply coming up with a coherent notion of nonmonotonic derivability. The problem is that nonmonotonic inference rules do not yield a simple iterative notion of derivability the way monotonic inference rules do. We can view a monotonic inference process as applying the inference rules in all possible ways to the axioms, generating additional formulas to which the inference rules are applied in all possible ways, and so forth. Since monotonic inference rules are monotonic, once a formula is generated at a given stage, it stays in at every subsequent stage. Thus the theorems of a theory in a monotonic system can be defined simply as all the formulas that get generated at any stage. The problem with attempting to follow this pattern with nonmonotonic inference rules is that we cannot reliably draw nonmonotonic inferences at any particular stage, since something inferred at a later stage may invalidate them. Lacking such an iterative structure, nonmonotonic systems use nonconstructive "fixed point" definitions, which do not directly yield algorithms for enumerating the "derivable" formulas, but do define sets of formulas that respect the intent of the nonmonotonic inference rules (e.g., In McDermott and Doyle's fixed points, MP is included whenever -p is not included.)

For our logic, it is easiest to proceed by first giving the closure conditions that we would expect the beliefs of an ideally rational agent to possess. Informally, the beliefs should include whatever the agent could infer by ordinary logic, and whatever he could infer by reflecting on what he believes. To put this formally, an autoepistemic theory T that represents the beliefs of an ideally rational agent should satisfy the following conditions:

1. If P 1 , ... ,Pn are in T, and Pl, ... ,Pn 1- Q, then Q is in T (where "I-" means ordinary tautological consequence).

II. If p is in T, then LP is in T.

III. If p is not in T, then -LP is in T.

Stalknaker [1980, p. 6] describes the state of belief characterized by such a theory as stable "in the sense that no further conclusions could be drawn ~y an ideally rational agent in such a state." We will therefore describe the theories themselves as stable autoepistemic theories.

There are a number of interesting observations that we can make about stable autoepistemic theories. First we note that, if a stable autoepistemic theory T is consistent, it will satisfy two more intuitively sound conditions:

IV. If LP is in T, then Pis in T.

V. If -LP is in T, then P is not in T.

If LP is in T and P were not in T, then by condition III -LP would be in T, and T would be inconsistent.4 If -LP is in T and P were in T, then by condition II LP would be in T, and T would be inconsistent.

Conditions II - V imply that any consistent stable autoepistemic theory will be both sound and semantically complete with respect to formulas of

the form LP and -LP: If T is such a theory, then LP will be in T lf and only if P is ln T, and -LP will be in T if and only if P ls not in T. Stability Implies a soundness result even stronger than this, however. We can show than the truth of a stable autoeplstemlc theory depends only on the truth of the formulas of the theory that contain no autoeplstemlc operators. (We wlll call these "objective" formulas.)

Theorem 1. If T ls a stable autoepistemlc theory, then any autoeplstemlc interpretation of T which Is a propositional model of the objective formulas of T is an autoeplstemic model of T.s

In other words, if all the objective formulas ln an autoepistemlc theory are true, then all the formulas in that theory are true. Given that the objective formulas of a stable autoepistemic theory determine whether the theory is true, lt is not surprising that they also determine what all the formulas of the theory are.

Theorem 2. If two stable autoepistemic theories contain the same objective formulas, then they contain exactly the same

formulas. 6

Finally, theorems, we criterion of with these characterization the syntactic the semantic can prove that stability captures criterion of completeness.

Theorem 3. semantically An autoeplstemic theory T is complete if and only if T ls

stable.

By Theorem 3, we know that stability of an agent's beliefs guarantees that they are semantically complete, but stability alone tells us nothing about whether they are sound with respect to his initial premises. That is because the stability conditions say nothing about what an agent should not believe. They leave open the possibility of an agent's believing propositions that are not in any way grounded in his initial premises. What we need to add is a constraint that the only propositions the agent believes are his initial premises and those required by the stability conditions. To satisfy the stability conditions and include a set of premises A, an autoepistemic theory T must Include all the tautological consequences of A U {LP I P is In T} U {~P I P is not in T}. Conversely, we will say that an autoepistemic theory T ls grounded in a set of premises A just in case every formula of T U {LP I P is ln T} U {-LP I P is not In T}. The following theorem shows that this syntactic constraint on T and A captures the semantic notion

is included In the tautological consequences of A of soundness.

Theorem 4. sound with premises A An autoepistemic theory T is respect to an initial set of if and only if T ls grounded in

A.

We have shown, then, that the stable autoepistemic theories grounded in a set of premises A exactly characterize the possible sets of beliefs that an Ideally rational agent might be expected to hold given A as his premises. We will call these the stable expansions of A. Notice that we say "sets" (plural), because there may be more than one stable expansion of a given set of premises. Consider {-LP -> Q, -LQ -> P} as an initial set of premises. 7 The first formula says that, if P is not believed, then Q is true, and the second says that, lf Q is not believed, then P is true. In any stable autoepistemlc theory that includes these premises, lf P is not In the theory then Q will be, and vice versa. But lf the theory is grounded ln these premises, lf P is in the theory there will be no basis for Including Q, and vice versa. So, a stable expansion of {-LP -> Q, -LQ -> P} will contain either P or Q, but not

both.

It can also happen that there are no stable expansions of a given seg of premises. Consider for instance {-LP -> P}~ No stable autoeplstemlc theory that contains this formula can fall to contain P. If P were not in the theory, -LP would have to be in the theory, but then P would be In the theory--a contradiction. On the other hand, if P is in the theory, then the theory wlll not be grounded ln the premises. So no stable autoeplstemic theory can be grounded In

{-LP -> P}.

This seemingly strange behavior ls the result of the indexicality of the autoeplstemic operator L. Since L ls Interpreted relative to an entire set of beliefs, its interpretation will change with the various ways of completing a set of beliefs. In each acceptable way of completing a set of beliefs, the interpretation of L will change to make that set stable and grounded in the premises. Sometimes, though, no matter how we try to complete a set of beliefs, the set of beliefs and the Interpretation of L never coincide In a way that gives us a stable set of beliefs grounded in the premises.

This raises a question of how to view autoepistemic logic as a logic. If we consider a set of premises A as axioms, what do we consider the theorems of A to be? If there Is a unique stable expansion of A, then it is clear that we want this expansion to be the set of theorems of A. But what lf there are several, or no, stable expansions of A? If we take the point of view of the agent, we have to say that there can be alternate sets of theorems, or no set of theorems of A. This may be a strange property for a logic to have, but, given our semantics, it ls clear why this happens. An alternative (adopted by McDermott and Doyle with regard to their fixed points) is to take the theorems of A to be the Intersection of the entire language with all the stable expansions of A. This gives us the formulas that are In all stable expansions of A if there is more than one, and lt makes the theory inconsistent if there is no stable expansion of A. This, too, is reasonable, but lt has a different interpretation. It represents observer would know, given only agent's premises and that he rational agent. what an outside knowledge of the is an ideally

IV ANALYSIS OF NONMONOTONIC LOGIC

Now we are in a position to give an analysis of nonmonotonic logic that will explain its peculiarities in terms of autoepistemic logic. Briefly, our conclusion will be that the original nonmonotonic logic of McDermott and Doyle [1980] is simply too weak to capture the notions they wanted, but McDermott's [1982] attempt to strengthen the logic does so in the wrong way.

McDermott and Doyle's first logic is very similar to our autoepistemic logic with one glaring exception; they have nothing in their logic corresponding to our condition II (if' P is in T, then LP is in T). Analogous to our stable expansions of a set of premises A, McDermott and Doyle define the nonmonotonic fixed points of A. In the propositional case, their definition is equivalent to the following:

T is a fixed point of A just in case T is the set of tautological consequences of A U

{~P I P is not in T}.

Our definition of a stable expansion of A, on the other hand, could be stated as:

T is a stable expansion of A just in case T is the set of tautological consequences of A U {LP I P is in T} U {-LP I P is not in T}.

In nonmonotonic logic, {LP .I P is in T} is missing from the "base·· of the fixed points. This admits fixed points of nonmonotonic logic that contain P but not LP. So, under an autoepistemic interpretation of L, McDermott and Doyle's agents are omniscient as to what they do not believe, but they may know nothing as to what they do believe.

This explains essentially all the peculiarities of McDermott and Doyle's original logic. For instance, they note [1980, p. 69] that MC does not follow from M(C /\D). Changing the modality to L, this is equivalent to saying that -LP does not follow from ~(P \/ Q). The probl~m is that, lacking the ability to infer LP from P, nonmonotonic logic permits interpretations of L more restricted than simple belief. Suppose we interpret L as "inferable in n or fewer steps" for some particular n. P might be inferable in exactly n steps, and P \/ Q in n+l. On this interpretation -L(P \/ Q) would be true and ~p would be false. Since this interpretation of L is consistent with the definition of a fixed point, -LP does not follow from ~(P \/ Q). The other example of this kind they note is that {MC, -c} has a consistent fixed point, which amounts to saying simultaneously that P is consistent with everything asserted and that P is false. of premises is equivalent to {-LP, P}, would be inconsistent if LP were forced every fixed point that contains P. This set but this to be in On the other hand, McDermott and Doyle consider it to be a problem that {MC -> D, -D} has no consistent fixed point in their theory. In autoepistemic logic, there are consistent stable theories that contain these premises, but none of them are grounded in the premises, so they do not characterize appropriate sets of beliefs for a rational agent. Thus, our analysis justifies nonmonotonic logic in this case, against the intuitions of McDermott and Doyle.

McDermott and Doyle recognized the weakness of the original formulation of nonmonotonic logic, and McDermott [1982] has developed a group of theories that are stronger because they are based on modal logic rather than classical logic. McDermott's nonmonotonic modal theories alter the logic in two ways. First, the definition of fixed point is changed to be equivalent to

T is a fixed point of A just in the set of modal consequences case T is of A U

{-LP I P is not in T},

where "modal consequence" means that P 1- LP is included as an inference rule. Second, McDermott considers only theories that have the axioms of the modal logics T, S4, or SS among the premises.

Changing the definition of fixed point by itself brings McDermott's logic much closer to autoepistemic logic. In particular, ading P 1LP as an inference rule means that all modal fixed points of A are stable expansions of A. However, adding P 1- LP as an inference rule rather than adding {LP I P is in T} to the base of T, means that not all stable expansions of A are modal fixed points of A. The difference is that, in autoepistemic logic, LP only has to be true to be in a set of beliefs; in McDermott's logic it must be grounded in a derivation of P that does not rely on LP. So, in autoepistemic logic there is a stable expansion of {LP -> P} that includes P, but in McDermott's logic there is no modal fixed point of {LP -> P} that includes P. It is as if, in autoepistemic logic, one can acquire the belief that P and justify it later by the premise that, if P is believed, then it is true. In nonmonotonic logic, however, the justification of P has to precede its belief. From the point of view of the autoepistemic interpretation of L, modal nonmonotonic logic is more conservative than

1t has to be.

Since we have already shown that autoepistemic logic requires no specific axioms to capture a competence model of autoepistemic reasoning, we might wonder what purpose is served by McDermott's second modification to nonmonotonic logic, the addition of the axioms of various modal logics. The most plausible answer is that, in addition to behaving in accordance with the principles of autoepistemic logic, an ideally rational agent might well be expected to know what some of those principles are. For instance, the modal logic T has all instances of the schema L(P -> Q) -> (LP -> LQ) as axioms. This says that the agent's beliefs are closed under modus ponens, which is certainly true, so the agent might as well believe it. S4 adds the schema LP -> LLP, which means that, if the agent believes P, he believes that he believes it--condition II. S5 adds the schema -LP -> L-LP, which means that, if the agent does not believe P, he believes that he does not believe it--condition III. Since all these formulas always are true for any ideally rational agent, it seems plausible to expect him to adopt them as premises. Thus S5 seems to be the most plausible candidate of the nonmonotonic logics as a model of autoepistemic reasoning.

The problem is that all of these logics also contain the schema LP -> P, which means that if the agent believes P then P is true, and that is not generally true for ideally rational agents. It turns out that LP -> P will always be contained in any stable autoepistemic theory (that is, ideally rational agents always believe that their beliefs are true), but making it a premise allows beliefs to be grounded that otherwise would not be. As we have seen, as a premise the LP -> P can itself be justification for believing P, while, as a "theorem," 1t must either be derived from -LP, in which case P is not believed, or from P, in which case P must be independently justified, or from some other grounded formulas. In any case, as a premise schema, LP -> P can license ~ belief whatsoever in autoepistemic logic. This is not generally true in modal nonmonotonic logic, as we have also seen, but it is true in nonmonotonic S5. The S5 axiom schema ~P -> L-LP embodies enough of the model theory of autoepistemic logic to allow LP to be "self grounding": The schema -LP -> L-LP is equivalent to the schema -L-LP -> LP, which allows LP to be justified by the fact that its negation is not believed. This inference is never in danger of being falsified, but, from this and LP -> P, we get an unwarranted justification for believing P.

The collapse of nonmonotonic S5 into monotonic S5 immediately follows. Since LP -> P can be used to justify belief in any formula at all, there are no formulas that are absent from every fixed point of S5, so there are no formulas of the form ~p that are contained in every fixed point of S5 ; hence there are no theorems of the form ~P in any theory based on nonmonotonic S5. (Recall that the theorems are the intersection of all the fixed points.) Since these formulas are just the ones that would be produced by nonmonotonic inference, nonmonotonic S5 collapses to monotonic S5. In more informal terms, an agent who takes it as a premise that he is infallible is liable to believe anything, so an outside observer can conclude nothing about what he does not

bell eve .

The real is not the problem with nonmonotonic S5, then, S5 schema, so McDermott's rather

unmotivated suggestion to drop back to nonmonotonic S4 [1982, p. 45] is not the answer. The S5 schema merely makes explicit the consequences of adopting LP -> P as a premise schema that are implicit in the logic's natural semantics. If we want to base nonmonotonic logic on a modal logic, the obvious solution is to drop back, not to S4, but to what Stalnaker [1980] calls "weak S5"--S5 without LP -> P. It is much better motivated, and has the advantage of actually being nonmonotonic.

In autoepistemic much is unneccessary. of weak S5 as premises can be derived. The theorem: logic, however, even this Adopting any of the axioms makes no difference to what key fact is the following

Theorem 5. If P is true autoepistemic interpretation of a stable expansion of A U {P} stable expansion of A. in every T, then T is iff T is a

The modal axiom schemata of weak S5,

L(P -> Q) -> (LP -> LQ) LP -> LLP

-LP -> L-LP,

simply state conditions I - III, so all their instances are true in every autoepistemic interpretation of any stable autoepistemic theory. The nonmodal axioms of weak S5 are just the tautologies of propositional logic, so they are true in every interpretation (autoepistemic or otherwise) of any autoepistemic theory (stable or otherwise). It immediately follows by Theorem 5, then, that a set of premises containing any of the axioms of weak S5 will have exactly the same stable expansions as the corresponding set of premises without any S5 axioms.

V CONCLUSION

McDermott and Doyle recognized that their original nonmonotonic logic was too weak, but, when he tried to strengthen it, McDermott misdiagnosed the problem. It appears that, because he was thinking of nonmonotonic logic as a logic of provability rather than belief, he thought the problem was the lack of a connection between provability and truth. At one point he says "Even though ~-p (abbreviated LP) might plausibly be expected to mean 'p is provable,' there was not actually any relation between the truth values of P and LP," [1982, p. 34], and later he acknowledges the questionability of the schema LP -> P, but says that ''lt is difficult to visualize any other way of relating provability and truth," [1982, p. 35]. If one interprets nonmonotonic logic as a logic of belief, however, there is no reason to expect any connection between the truth of LP and the truth of P. And, as we have seen, the real problem with the original nonmonotonic logic was that the "if" half of the semantic definition of L--LP is true if and only if L is believed--was not expressed in the logic.

ACKNOWLEDGMENTS

This research was supported by the Air Force Office of Scientific Research under Contract No. F49629-82-K-0031.

NOTES

• 1 In their informal exposition, McDermott and Doyle [1980, pp. 44-46] emphasize that their notion of nonmonontonic inference is not to be taken as a form of valid inference. If this is the case, then their formal semantics cannot be considered to be the "real" semantics of their nonmonotonic logic. At best, it would provide the conditions that would have to hold for the inferences to be valid, but this leaves unanswered the question of what formulas of nonmonotonic logic mean.
• 2 Of course, autoepistemic reasoning can be mixed with default reasoning; we might believe that we know about most of the birds that cannot fly. This could lead to defeasible autoepistemic inferences, but their defeasibility would be the result of their also being default inferences.
• 3 Stalnaker's note, which to my knowledge remains unpublished, grew out of his comments as a respondent to McDermott at a conference on Artificial Intelligence and Philosophy, held in March 1980 at the Center for Advanced Study in the Behavioral Sciences.
• 4 Condition IV will, of course, also be satisfied by an inconsistent stable autoepistemic theory, since such a theory would include all formulas of autoepistemic logic.
• 5 Space does not permit the inclusion of of the proofs of the theorems. They are given in full in elsewhere [Moore, 1983].
• 6 This theorem implies that our autoepistemic logic does not contain any purely self-referential formulas a·s one finds in what are usually called "syntactical" treatments of belief. If, instead of a belief operator, we had a belief predicate, there might be a term p that denotes the formula Bel(p). Whether Bel(p) is believed or not is clearly independent of any objective beliefs. The lack of such formulas is a characteristic difference between sentence-operator and predicate treatments of propositional attitudes and modal! ties.
• 7 McDermott and Doyle [1980, p. 51] present this example as {MC -> -D, MD-> -c}.
• 8 McDermott and Doyle (1980, p. 51] present this example as {MC -> -c}.