Nonmonotonic Logics: Meaning and Utility

1 Introduction

The last decade or so has seen many logical systems which sup­ port so-called nonmonotonic inferences. In these formalisms one is allowed not only traditional inferences of classical logiC; but also more "speculative" ones. It is often said that in those sys­ tems one may "jump to a conclusion" in the absence of evi­ dence to the contrary, or tha.t one may assign formulas a · !'de­ fault value," or that one may make a "defeasible inference." The prototypical example is inferring tha.t a particular individual can fly from the fact that it is a bird, but retracting that inference when an additional fact is added, that the individual is a pen­ guin. This is why such formalisms a.re called nonmonotonic: a fact entailed by a theory might no longer be entailed by a larger theory. Of course, classical logic is monotonic.

The original and best-known nonmonotonic logics are Mc­ Carthy's circumscription [10], Reiter's default logic [14], Mc­ Dermott and Doyle's nonmonotonic logic I [11], McDermott's nonmonotonic logic II [12], and Clark's predicate completion [2]. In recent years many more systems have been suggested, and the old ones were further explored. Lifschitz provided new results on circumscription [7] . Further investigations of default logic include Etherington's work [3] and Lukaszewicz' [9]. Moore's autoepistemic logic [13] is an adaptation of McDermott's NML II, and a version of it was further investigated by Halpern and Moses [4].

These various formalisms are very different superficially. For example, circumscription amounts to adding a second-order ax­ iom to a given first-order theory. A default theory, on the other hand, contains a collection of default rules, a notion quite out­ side classical logic, and its meaning is defined using a fixed-point construction which relies on those default rules. McDermott's and Moore's logics are still different, and formulas in those logics contain modal operators, which are meant to capture the notions of consistency and belief, respectively. The nonstandard nature of the variousE.stems and their diversitv bas made it hare! t.o

1The work described here was carried out when the author was a graduate student at YaleUniversity.

However, the main problem with existing nonmonotonic for­ malisms is not their overwhelming complexity, as much as it is their limited expressiveness. In particular, they were all shown to fail to capture nonmonotonic temporal inferences. The prob­ lems were first reported by Hanks and McDermott [5], in re­ sponse to which several solutions were offered, One such solution was proposed by Lifschitz, and it was to generalize circumscrip­ tion to so-called pointwise circumscription [9] . My approach has been to construct the iogic of chronological ignorance [16), and in doing I defined a very general framework for nonmono­ tonic logics. The purpose of this paper is to present this general framework.

This paper has two distinct parts. The :first part is more technical, and consists of the next two sections. The next sec­ tion introduce the general framework of nonmonotonic logics, the result being a simple system to which on the one hand all existing nonmonotonic logics .can be reduced (and thus easily understood and easily compared to one another), and which on the other hand suggests radically new nonmon.otonic logics. The section following that briefly shows how some previous non mono­ tonic formalisms can be viewed as special cases of the general framework. The second part of the paper is more held at the intuitive level, and consists of the last section. It discusses the intuitive meaning behind nonmonotonic inferences, and argues that the proposed distinction between default inferences and au­ toepistemic ones should be abolished.

2 Formal construction of nonmonotonic logics

The basic idea behind the construction is the following. In tra­ ditional logic, the meaning of a formula is the set of interpre­ tations that satisfy it, or its set of models (where "interpreta­ tion" means truth assignment for PC, a first-order interpretation for FOPC, and a (Kripke interpretation, world)-pair for modal logic). One gets a nonmonotonic logic by changing the rules of the game, and focusing on only a subset of those models, those that are "preferable" in a certain respect (these preferred mod­ els are sometimes called "minimal models," a term introduced by McCarthy in connection with circumscription). The reason this transition makes the logic nonmonotonic is as follows. In classical logic A F= C if C is true ill all models of A. Since all models of A A B are also models of A, it follows that A A B F= C, and hence that the logic is monotonic. In the new scheme we have that A F C if C is true in all preferred models of A, but A II B may have preferred models that are not preferred models of A. In fact, the class of preferred models of A II B and the class of preferred models of A may be completely disjoint.

Many different preference criteria are possible, all resulting in different nonmonotonic logics. Circumscription, default logic and autoepistemic logic all assume implicitly very specific (and different) preference criteria. In (15] I look into other preference criteria that are suitable for temporal reasoning. In this paper I look more closely at the general framework, and at the meaning in it of notions such as satisfiability and entailment.

The following discussion here will be most general, and when I talk of a "standard logic" I allow in principle any logic with the usual compositional, model-theoretic semantics. Rather than give a precise definition of this condition, however, let me in the following assume that by a "standard logic" one means the propositional calculus or first-order predicate logic, either clas­ sical or modal (i.e., one of four logics); extension to other cases (such as higher-order logic) will be obvious. 2

In order to have the following discussion apply u.niformly to the classical and modal logics, let me misuse the terminology slightly by calling anything which goes to the left of the F an interpretation. In the classical cases this is what is indeed usually called an interpretation. In the modal cases it is a pair (Kripke structure, world).

The transition to nonmonotonic logic puts into question no­ tions that are well understood in logic, such as satisfaction, en­ tailment, satisfiability, validity, and proof theory. To see what these might mean in the context of nonmonotonic logic, it will be helpful to recall some definitions from the standard case.

Definition 1 (Reminder)

Let£ be a standa!Yllogic, and A and B two sentences in£. The fact that an interpretation M satisfies A is denoted by M F A. In this case we say that M is a model of A. A is satisfiable if A has a model. A is valid if A is satisfied by all interpretations. Clearly A is satisfiable iff ·A is not valid. A entails B (written A F B) if B is satisfied by all models of A, or equivalently, if all models of A are also models of B.

From these definitions, the deduction theorem foRows very eas­ ily:

Theorem 1 (Reminder)

Let£ be a stcmdard logic, cmd A, B and C sentences in£. Then A " B F c iff A F B :J c.

Clearly all standard logics are monotonic, in the sense that for any A, B and C in the logic, if A F C then also A II B F C.

Nonmonotonic logics are the result of associating with a stan­ dard logic a preference relation on models. More specifically, we make the following definitions. Let £ be a standard logic and A a sentence in it, and let e be a strict partial order on inter­ pretations for £. Intuitively, M1eM2 will mean that the interpretation M2 is preferred over the interpretation Mt. £ and e define a new logic £e. I will call such logics preference logics. The syntax of £e is identical to that of £.In order to define the semantics of £e we must define the notions of satisfaction (of a formula by an interpretation), satisfiability, validity, and entailment .

2 When I say 'a modal logic' I deliberately do not commit myself to a particular modal system; that too is not essential here. Again, rather than define the class of all modal systems to which the following applies, let me in the following assume an SS system whenever a modal logic is mentioned, and leave it to the reader to extend it to other systems.

Definiti9n 2 An interpretation M preferentially satisfies A {writ­ ten M Fe A) if M F A, and if there is no other interpretation M' such that MeM' and M' F A. In this case tve say that M is a preferred model of A.

Clearly, if M Fe A then also MFA.

In the full paper I define the notions of preferential sotisfi­ ability and preferential entailment. Since those are on the one hand somewhat problematic and on the other hand somewhat unimportant, I will proceed directly to the notion of preferential entailment, and that has a very intuitive definition:

Definition 3 A preferentially entails B (written A Fe B) if for any M, if M Fe A then M F B, or equivalently, if the models of B (preferred and otherwise) a1·e a superset of the pre­ ferred models of A.

Observation. If£ is a preferential logic, it may contain sen­ tences A and B such that both A Fe B and A Fe ·B. Fur­ thermore, A need not be inconsistent for this to be the case - it is sufficient that it have no preferred models. Indeed, in preferential logic the role played by preferential satisfiability is exactly analogous to that played by satisfiability in standard logics, witness the following obvious lemma:

Lemma 2 Let £e be a preferential logic, and A a sentence in it. Then A is preferentially satisfiable iff there does not exists a sentence B in £e such that both A FeB and A Fe ·B.

Definition 4 £e is monotonic if for all A,B,C E £, if A Fe C then also A II B Fe C.

Observation. The above definition is equivalent to saying that a logic is monotonic if all preferred models of A II B a.re also preferred models of A. Viewing £ as the special case £.p, where cP is the empty relation, we note that £.p is monotonic.

It is interesting to see what happens to the deduction the­ orem in light of the new definition of entailment. It turns out that while the theorem is false in general, a weaker version of it still holds, in which the 'iff' is changed to an 'if':

Theorem 3 Let £e be a preferential logic, cmcl A, B a11d C three sentences in it. Then, if A II B Fe C, then also A Fe B :J C.

The converse to this theorem does not hold: if A Fe B :J C then it does not necessarily follow that A II B Fe C. It is not hard to construct a counterexample, for example one in which C is identically false, A II B is not identically false , and B is false in all preferred models of A. In fact, it is easy to show that if the converse to the theorem holds then the logic is necessarily monotonic:

Theorem 4 Let Cc be a preferential logic. Then the following two statements are equivalent:

1. For all A,B,CECc, if A l=c B :::> C then also A A B l=c c.
2. Cc is 11ionotonic.

3 Special cases

In [15] I discuss previous nonmonotonic systems in some detail, and show how they can be viewed as special cases of the proposed general framework. In particular, I discuss both McCarthy's and Lifschitz' versions of circumscription, Bossu and Siegel's formalism [1], Reiter's default logic, and a version of Moore's autoepistemic logic due to Halpern and Moses [4]. Here I will be able to provide a comparison with only three of those, and very sketchily at that.

3.1 Circumscription

Circumscribing a formula amounts to adding a second order ax­ iom to a theory. McCarthy's original circumscription axiom (and I am using Lifschitz' recent reconstruction of it) was:

where p is a predicate variable with free variables x, and p<P stands for

This axiom is one way of defining a preference criterion on mod­ els, according to which M1CM2 if

1. For all x, M1 and M2 agree on the interpretation of func­ tion symbols and all relation symbols other than P,
2. for all x, if M2 I= P(x) then also M1 I= P(x), and
3. there exists a y su.ch that M1 I= P(y) but M2 ~ P(y).

Other circumscription axioms embody similar preference crite­ ria. To avoid giving the wrong impression, it must be said that the notion of preferred models was implicit in McCarthy's work from the start. In fact, in .his original paper he gave a min­ imality criterion similar to the one stated above, although in subsequent publications the model-theoretic discussion seemed to play a diminishing role. Other researchers too have addressed the model theory of nonmonotonic logics, such as Lifschitz in [8] and Etherington in [3].

My formulation can be viewed as a suggestion to generalize McCarthy's approach in three ways:

1. Start with any standard logic, not necessarily FOPC. For example, I base my formulations on a standard modal logic.
2. Allow any partial order on interpretations, not only the one implied by a particular circumscription axiom. For

example, in [15] I suggest a preference criterion that relies on temporal precedence.

1. Shift the emphasis to the semantics, stressing the partial order on models and not the particular way of defining that partial order. In fact, allow the definition of this partial order in any way that leaves no room for ambiguity. The various circumscription axioms, either McCarthy's original ones or Lifschitz's more recent ones, are one way of doing so, and they are most elegant. In my own formulations I have chosen other means of defining preference criteria.

3.2 Bossu and Siegel

At the time this work was conducted I was unaware of related previous work by Bossu and Siegel [1], or I would have made an effort to use their terminology where possible. As things are, I renamed some of the concepts they had come up with, and by now I am too fond of my definitions to let go of them. Let me, however, make clear the connection between the two treatments. The summary of it is that they share the basic semantical approach, although there are some minor technical differences between the two, but that Bossu and Siegel thor­ oughly investigated what turns out to be a very special case of my general formulation. In a little more detail the connection is as follows.

The main part common to both Bossu and .Siegel's treat­ ment and my own is the model-theoretic approach, which posits a partial order on interpretations. There are some minor differ­ ences in the precise definitions. For example, whereas I defined 'f! to be preferentially satisfiable (or, in their terminology, min­ imally modelable) if 'f! has a preferred model, Bossu and Siegel require in addition that any non preferred model of if! have a bet­ ter model than it which is preferred. Or, as another example, they explicitly reject the definition I chose for preferential entail­ ment (which they call subim]Jlication and denote by ]= ), since if 'f! is not preferentially satisfiable (i.e., it has no maximally pre­ ferred models) then it entails both {) and -,f) . I don't view that as a disadvantage, since preferential satisfiability plays a role that is completely analogous to satisfiability. Thus by the same argument one should object to the regular notion of entailment, since inconsistent (i.e., unsatisfiable) theories entail both {) and -,{).

These are fairly minor differences, and they are overwhelmed by the similarity in the semantical approach to nonmonotonic logics. There is, however, a big difference between the two treat­ ments, and that is in their generality. Whereas I .allow starting with arbitrary standard logics as a basis, Bossue :tnd Siegel re­ quire starting with FOPC. More crucially, whereas I allow any partial order on interpretations, Bossu and Siegel assume one fixed such partial order. As they themselves say,

The difference between [John McCarthy's] definition and ours is that McCarthy 'minimizes' on some lit­ erals only, whereas we 'minimize' on every literal.

Circumscription was discussed in the previous subsection. As we have seen, in the simplest version of the logic, preferred models are those in which P1 (x1), ··· ,Pn(xn) are true for as few x;'s as possible, where the P;'s are predicate symbols specified sepa­ rately, and x; are the arguments to P; . What Bossu and Siegel do is fix the P; 's to be all the predicate symbols that appear in the theory that is being modeled.

3.3 Minimal knowledge

In (4), Halpern and Moses construct a nonmonotonic modal logic, which is a direct adaptation of Moore's autoepistmic logic (which in turn was the outgrowth of McDermott's NML II). In (15) this logic is discussed in more detail; Here let me just provide the preference criterion on (Kripke interpretation, world}-pairs inherent in their logic. According to it , M1CM2 if (in the fol­ lowing, a base wff is one containing no modal operators):

1. for a.ll base wffs cp, if M2 f= Dcp then also M1 f= Dcp, and
2. there exists a base wff cp such that M1 f= Dcp but M2 ~ Dcp.

Since Dcp is interpreted in the logic as "cp is known," the result is to prefer models in which as few base wffs as possible are known.

4 Two kinds of nonmonotonic inferences?

My treatment of nonmonotonic logics so far has been purely technical. This section is devoted to discussing the intuitive meaning behind nonmonotonic inferences. I will try to clarify some of the confusion arising from the apparent connection be­ tween probabilistic information and nonmonotonic inferences, and in the process argue against the suggestion that there are two fundamentally different sorts of nonmonotonic inferences.

The distinction I am a.lluding to was suggested by Robert Moore in (13). He contrasts default inferences, which are based on some statistical facts (e.g., that most birds can fly), with autoepistemic inferences, which are based on the lack of some particular knowledge. Says Moore,

Consider my reason for believing that I do not have an older brother. It is surely not that one of my par­ ents once casua.lly remarked, "you know, you don't have any older brothers," nor have I pieced it to­ J!;ether by carefully sifting other evidence. I simply believe that if I had an older· brother I would surely know about it ... This is quite different from a de­ fault inference based on the belief, say, that most MIT graduates are oldest sons ...

On the face of it this distinction is quite appealing (certainly I was convinced for a while), but upon closer examination it seems to break down completely.

To begin with, one may note that Moore applies his own logic, labelled an autoepistemic one, to the flying birds example, which he himself characterizes as a default case. Furthermore, consider Moore's own older brother example. If one accepts the statement "if I had an older brother then I'd know it," surely one must also accept the statement "if I didn't have an older brother then I'd know it ." Yet if we adopt this latter sentence rather than the first one, the opposite inference will follow, namely that I have an older brother. On what basis does one prefer the first sentence to the second one, if at all? Notice that if you adopt both sentences, then you end up with two distinct preferred models - one in which you have an older brother and know it, and another in which you don't have an older brother and know it - which isn't much help.

Let me suggest a different distinction than the one made by Moore. Rather than distinguish between different kinds of de­ fault inferences, one should distinguish between the meaning of sentences on the one hand, and the (extra logical) reason for a.dopting that meaning on the other. The meaning, I argue, can be viewed epistemically. The reason for adopting that mean­ ing is computational economy, which often relies on statistical information.

Consider the flying birds example. The meaning of "birds fly by default" is that if I don't know that a particular bird can­ not fly, then it can. The computational reason for adopting this meaning is that now whenever a bird can indeed fly, we need not mention the fact explicitly - either in external communica­ tion with other reasoners, or in "internal communication," i.e., thought - it will follow automatica.lly. Of course, if we happen to be talking about a penguin, we had better a~d the knowled!!;e that penguins cannot fly, or else we will make wrong inferences. In the long run, however, we win: the overwhelming percentage of birds about which we are likely to speak can indeed fly, and so on average this default rule saves us work. If this gain seems sma.ll, consider a realistic situation in which we apply thousands and thousands of such rules.

Can we identify a similar rationale behind the rule "by de­ fault, I do not have an older brother"? It is less obvious here, which is why the two cases seem superficia.lly different. Yet such motivation must exists, or else one wouldn't prefer this rule to the opposite one. Perhaps the rationale is again a simple count­ ing argument - on average a couple has two children, so the speaker has a 50% chance of being the younger one, in which ose there is a 50% chance that the older sibling is male. Thus in 75% of the cases the speaker does not have an older brother,. which is not quite as overwhelming as the percentage of flying birds, but still is higher than 50%. 3 Perhaps in fact the moti­ vation for adopting the default rule is more sophisticated, but some motivation must exist.

I am not at a.ll arguing that one makes cp true by default just in case cp is true most of the time. As I have said, the flipside of making a default assumption is the danger of making faulty inferences. For example, if a bird is being discussed and its type is unknown, we will infer that it can fly even though it might turn out to be a penguin. If this seems harmless, think of making the default inference "people you'll meet on the street will not stab you in the back" in a city in which only 5% of the population are back stabbers. In this ca.Se the relativ~ly sma.ll. chance of being badly hurt seems to outweigh the computational resources needed to reason about individual people on the street, and the discomfort of wearing a steel-plated vest. Notice that if the 5% dropped to 0.00000000005%, we'd take off the armor and stop looking darkly at passers by. Indeed, that is exactly how we treat the possibility of a nuclear war. Clearly, one must maximize his expected utility when selecting a nonmonotonic theory.

3 This argument was suggested by Drew McDermott, half in jest, after he was convinced of its conclusia:n.

I offer no general guidelines for making such a selection. All I am suggesting here is to separate the two issues, that of defining the meanings of nonmonotonic logics, and that of selecting one.

Notice. The remainder of this section, in which two ~ore ar­ guments are offered in support of the proposed meaning/utility distinction, assumes acquaintance with McCarthy's circumscrip­ tion, and with modal logics of minimal knowledge. Those were referred to briefly in the previous section, but the reader who is unfamiliar with them may find the following a bit cryptic. In (15] a more detailed discussion of those logics is offered.

The reader may still be bothered by the fact that circum­ scription involves only classical sentences, and it is not clear how epistemic notions enter into it. It is not hard, however, to convert circumscription into a logic of minimal knowledge. The basic idea is instead of circumscribing a formula r.p(x), to add the axiom \/x r.p(x) :J Dr.p(x). (For example, in the flying birds case we add the axiom \/x CAIFLY(x) :J DCAJFLY(x).) Since we pre­ fer models in which as few propositional formulas as possible are known, the effect is to have r.p true of as few x's as possible. The natural reading of the axiom r.p :J Dr.p is indeed "if r.p were true then I'd know it." However, if we take the contrapositive form of the axiom, we get the familiar "default rule": ()-,r.p :J "'"~'· or "if it is possible that r.p is false then it is."

As a final clincher in the argument for the meaning/utility distinction, let me show how this distinction resolves the Lottery Paradox, discussed, for example, in (12]. The paradox is as follows:

A lottery is held with 1 million participants, includ­ ing our friend John. The odds of John's winning are so low that we infer by default that he won't. Yet by the same token we can infer that none of the other 999,999 members will win, which contradicts our knowledge that at least one person must win.

In the logic of minimal knowledge (which, as we have just seen, can be translated back into circumscription) we describe the situation bv

[WII(JOKI) V WII(Pt) V WII(P2) V ..· V WII(P999,999)] A \/x WII(x) :J DWII(x)

The most ignorant models are ones in which one of the million people wins and we know that he won it, but the identity of that person varies among models. We are therefore not justified in concluding that a.ny particular individual will not win, since there are models in which he does. True, those models are vastly outnumbered by those in which he does not win, but nonmono­ tonic logics do not let us express the property of a. proposition being true in "most" models. This once again shows that such probabilistic information plays a. role in choosing the meaning but not in defining it.

So in the above formulation we cannot conclude that John will not win, nor should we want to. If one claims that such a conclusion is one that corresponds to default reasoning people use, one must agree to the conclusion that no rational person would ever buy lottery tickets, a prediction that obviously isn't born out in rea.litv. 4 However. the above formnla.tion is not ;u;

4 The argument that indeed no rational person should, given that in all lotteries the expected winning amount is negative, is irrelevant. The exam­ ple would ·still hold if some bored millionaire organized the lottery, charging each participant one dollar and giving the winner one million and one dollars.

useless as it might appear. We can still make inferences in­ volving the possibility of people winning, in which rather than condition a.n inference on their not winning, we condition it on the possibility of their not winning. For ex·ample, we may add the sentence ·

()..,WII(ME) :J ..,SKOULD-RESIG!f-JOB(ME)

The rationale here is again statisticaL Although there is a model in which I win the lottery a.nd therefore needn't bother teaching a. course on AI, it would be foolish for me to resign on that basis.

5 Summary

I have presented a uniform approach to constructing and under­ standing nonmonotonic logics. The value in the formulation has not been its mathematical sophistication, but rather the oppo­ site: the only notion added to traditional logic was that of a partial order on interpretations. The simplicity of the formula­ tions makes transparent what in other systems is less immediate. The formulation is not only simple but also very general, and subsumes previous systems. I briefly indicated how previous systems are a. special case. of this general framework; in (15], a more detailed comparison with previous nonmonotonic systems is provided. Also, I have argued against the proposed distinction between different kinds of nonmonotonic inferences.

Sev!!ral open questions remain. One of them has to do with the relation to other nonstandard logical formulations. In partic­ ular, Johan van Benthem has drawn my attention to the close parhllels between my formulations and formulations in Condi­ tional Logic, as pioneered by D. Lewis (6,18]. In CL one has, instead of a partial order on interpretations, a similarity measure on possible worlds, and the notion of counterfactual entailment is similar to my notion of preferential entailment. I would like to understand this connection better.

Another open question is which particular instances of the general framework I have outlined are interesting from the prac­ tical point of view. As I have said, the general treatment of non­ monotonic logics offered here grew out of limitations of existing systems. It is still the case, however, that very few concrete preference criteria on models have been investigated. The most common ones are those embodied in the various circumscription axioms and in some default theories. One preference criterion transcending those is that of chronological ignorance, presented in (16]~ Lifschitz too has investigated an ·instance of pointwise circumscription that does not collapse into "old" circumscrip­ tion. All these, however, are still a drop in the bucket, and we have yet to understand which of the many possible partial orders on models are of practical importance.