Commonsense Entailment: A Modal Theory of Non-monotonic Reasoning

1. Introduction

Potatoes contain vitamin C, amino acid, protein and thiamin expresses a true generalization about potatoes. John smokes a cigar after dinner, understood in its generic sense as expressing a regularity in John's behaviour after dinner, can be true, and it can be false. This realist conviction inspires the theory of generic propositions which is the subject of this paper. The difficulty with generic propositions is that their truth is loosly but clearly connected with particular facts. For instance, potatoes contain vitamin C, even though large numbers of them are boiled for so long that it is lost Potatoes would contain vitamin C even if all of them were to be boiled for so long that it is lost Nevertheless, the generic fact that potatoes contain vitamin C furnishes all the evidence we need to be justified in concluding that this potato, in the abscence of any other conflicting information, contains vitamin C. The curious relation between generic and particular facts has for a decade or more frustrated efforts in artificial intelligence, linguistics, and philosophy to provide generic sentences with a rigorous semantics. We offer such a semantics here for one kind of genericity.

Researchers in AI have produced many theories of non­ monotonic reasoning that be seen also as attempting to give a semantics for genericity. As motivation for our theory, we argue for three desiderata of a semantics for genericity and defaults which other theories of genericity do not simultaneously satisfy. A frrst requirement is that any theory of genericity should explain the ways in which we reason with generic sentences. Logical entailment is one form of reasoning. We think that the truth conditions of generic sentences can be captured by using ordinary quantification and a non-monotonic conditional operator; so in what follows Michael Morreau IMS, University of Stuttgart Keplerstrasse 17 7000 Stuttgart 1, Deutschland mimo@adler.philosophie.uni-stuttgart.de we shall write qJ's nonnally yt as 'v'x( <p > 'lf).l There are a few forms involving generic sentences that seem clearly to be cases of logical entailment (lo). One is WEAKENING OF THE CONSEQUENT. Suppose C is a logical consequence of 'If; then:

'v'x(<p >'If)~ 'v'x(<p >C).

Among the intuitively valid generic sentences, those which are entailed by everything, we count Lions are lions, and the nested generic sentence People who don't like to eat out don't like to eat out. We take this last sentence to be nested because it says that people possessing a characteristic property -­ namely the property of typically not liking to eat out-­ typically have this property.

While the logic of generic sentences seems to support few valid argument forms, it does seem to support many "reasonable inference patterns." Among the things not entailed by the generic statement that potatoes contain vitamin C is the particular conclusion that this potato contains vitamin C. Nevertheless, the generic fact makes it somehow reasonable to expect this potato to contain vitamin C, without at the same time making it reasonable to expect any number of other things which are not entailed, like say that the moon is made of green cheese. Researchers in the field of nonmonotonic reasoning have discovered a wealth of such patterns of invalid but reasonable generic inference, of which some examples are given below. We will symbolize reasonable inference by 1=.

The main patterns come in three distinguishable groups. In this paper we will present in some detail an interpretation of generic sentences in which the following generally acknowledge patterns of nonmonotonic reasoning hold.

DEFEASIBLE MODUS PONENS \fx( <p >'If), <p{~) I"' 'If(~). but not 'v'x( <p > 'If), <p(~).--, 'If(~) 1 ... '!'(~) NIXON DIAMOND not{ 'v'x( <p > 'If), 'v'x(C >-.'If), <p(d), C(d) 1 .. 'If( d) (or -. 'If( d))} POINI'WISE DEFEASIBLE TRANSmviTY 'v'x(<p >'If), 'v'x('lf >C)· <p(~) I· C(~)

but not { 'v'x( <p >'If), 'v'x('lf >C). 'v'x( <p > -.C). <p(~) I= <p(~)}

1 Asswning a generic quantifier makes more linguistic sense than what we have done above; however, such a quantifier is definable in terms ofV and>, given our semantics.

• POINfWISE DEFEASIBLE STRENGTIIENING OF TIIE ANTECEDENT: \fx(cp >'If), cp(5) & ~(5) I= '1'(5), but not (\fx(cp >'If), cp(5) & ~(5), \fx(( cp & 0 > -.'If) I= '1'(5)}.
• PENGUIN PRINCIPLE: V'x( cp >'If), V'x('lf' >~), V'x( cp > -,~), cp(5) 1 .. -,'1'(5).
• EMBEDDED DEFEASIBLE MODUS PONENS: \fx(~ > \fy(cp >'If)), ')(5), \fu(y > 3ycp) I= 3Y'If(5).

In all of these forms of reasoning, we observe that I= is very sensitive to "relevant premises" that may affect conclusions that may be reasonably drawn from a subset of those premises. Capturing such inferences has been a major challenge for AI. But further these forms of reasoning may interact, but they should not interact in "bizarre" ways. Here is one bizarre interaction that we want to avoid. For while we have

\fx(cp >'If) 1- \fx(cp >('If v 0)

and we have defeasible modus ponens, we do not get the undesirable inference,

DEFEASIBLE IRRELEVANCE: \fx(cp >'If), cp(5),-, 'lf'(5) I= ~(5)

for then we would defeasibly conclude that from birds fly and Tweety is a bird that does not fly, that Tweety is a locomotive!

A second class of inferences that we believe to be plausible are the following "rule versions" of the pointwise, defeasible transitivity and strengthening of the antecedent rules.

• DEFEAsiBLE TRANSITIVITY V'x(cp >'If), \fx('lf' >O I= \fx(cp > O. but not (\fx(cp >'If), \fx('lf' >~). \fx(cp > -,Q I=- \fx(cp > 0}.
• DEFEASIBLE STRENGilJENING OF TIIE ANTEcEDENT: \f x( cp > 'If) I= \fx((cp & ~)>'If) but not (\fx(cp >'If), \fx((cp & 0 >-.'If) I= \fx((cp & 0 >'If).

Finally there is a third group of reasonable inferences that depend on a view of normality on which normality comes in degrees.

• GRADED NORMAUTY AND DEFASIBLE MODUS PONENS: \fx(cp > '1'·), ... , \fx(cp > 'l'n), cp(5), -,'l't(5) 1 .. 'l'z(5) & ... & 'l'n(5) but not (\fx(cp > 'lf'1), ··· , \fx(cp > 'lf'n). cp(5),-, '1'1 (5) I= '1'1 (5) & ... & 'lf'n(5)}.
• GRADED NORMAUTY AND DEFASIBLE TRANSITIVITY: \fx( cp > 'If), \fx('l' > O. \fx('lf' > 'lf't). \fx(cp >-.'1ft) I= \fx(cp > 0. but not (\fx(cp >'If), \fx('l' > 0. \fx('lf' > 'lf't). \fx(cp > -.'If·) I= \fx( cp >'If 1)}.

Although we have worked out a semantics on which these last two groups of inferences hold, we cannot give a detailed account here. We give a brief description in the penultimate section of the paper; we will concentrate on presenting a minimal system of commonsense entailment

In any case, an acceptable theory of genericity will respect the distinction between logical entailment and reasonable inference, and it must realistically model the reasoning belonging to each area. In particular, the semantics must capture the feature that these defeasible patterns of inference introduce a dependence on epistemic contexts which is not at all present in the case of the valid patterns. Their conclusions are defeated as one obtains information which brings them into doubt, not as the world changes in whatever way. Realistically modelling such defeasible reasoning will lead us to model these epistemic contexts explicitly· in the semantics of generic sentences.

A second requirement for theories of genericity is that they be sufficiently general. The correct theory must provide interpretations not only for simple generic sentences like most of those we have seen up until now, but also for composite sentences in which genericity mixes with counterfactuality, belief, knowledge, and even with more genericity, as in the case of nested generic sentences like healthy cats jump at stTUJll moving objects, or people who worlc late at nights do not wake up early. Here is an example of generics interacting with counterfactuality and propositional attitudes: John knows that Mary loves kissing him, and he would be unhappy if she were were to like it less. A theory of what generics mean ought at least to extend to a theory of what they mean in such contexts.

The third desideratum for theories of genericity is a methodological one. In one respect most of the formalisms (including the one to be presented below) for representing and reasoning with generic information are alike: they are empirically inadequate. In another respect, however, they differ greatly. Some theories cover up the deficiencies of the underlying mechanisms that purport to explain nonmonotonic reasoning by introducing devices foreign to those mechanisms. One case in point is the way in which theories treat the penguin principle, the pattern of reasoning where specific information takes precedence. This is the familiar problem of multiple extensions. Formalizing the premises of the penguin principle in the way done in circumscription by means of a multitude of "abnormality predicates," for example, we find that minimization of abnormality results in two kinds of minimal models: there are models where Tweety is an abnormal bird but a normal penguin, and so does not fly. But in addition there are others where he is a normal bird but an abnormal penguin, and does fly. Because of these latter, undesirable models it then does not follow that Tweety does not fly, and we see that circumscription does not handle the penguin principle adequately. Similar problems confront default logic and autoepistemic logic. The solution which proponents of these theories have suggested is as familiar as the problem: the order in which default rules fire needs to be constrained; the predicates to be minimized in the case of circumscription need to be prioritized. They thus commit themselves to the

HYPOTHESIS OF THE GHOST IN THE MACHINE

That specific information takes precedence over general information is not to be accounted for by the semantics of generic statements itself. Rather, it is due to the intervention of a power which is extraneous to the semantic machinery, but which guides this machinery to have this effect (by ordering the defaults, deciding the priorities of predicates to be minimized, or whatever).

Whatever kind of reasoning generic reasoning is, more specific information takes precedence is intrinsic to it. The penguin principle should emerge naturally from the semantics of generic sentences without the intervention of a user who decides how the reasoning is to be applied. We want to exorcise the ghost from the machine.

Emulating the possible worlds analysis of conditional sentencel!. we construct first a semantics assigning truth values to (nested) generic sentences relative to possible worlds. The truth conditional part of our semantics, with its standard notion of entailment, accounts for the valid argument forms we mentioned. Because it is a conventional possible worlds theory, we can insert the semantics of generics within general, possible worlds frameworks that yield semantics for counterfactuals, propositional attitudes and so on. It is thus in principle very clear how to interpret complex sentences such as those discussed above.

On top of the truth conditional semantics, we build a second, dynamic, partial theory, which accounts for defeasible patterns of reasonable inference. Our intuitive picture of what goes on when one reasons by defeasible modus ponens is this: first one assumes the premises birds fly and Tweety is a bird, and no more than this. Second, one assumes that Tweety is as normal a bird as is consistent with these premises. Finally, one then looks to see whether one believes that Tweety flies or not, and fmds that he does. In our view all of the patterns of defeasible reasoning outlined in the introduction arise in this way, from assuming just their premises, then assuming everyone and everything as normal as is epistemically possible, and fmally seeing whether one believes their conclusions. The dynamic semantic models such epistemic reasoning by means of information states, which are sets of possible worlds taken from the truth conditional model theory. We define two functions on these information states: updating and normalization. The first of these is eliminative, simply removing from information states all those possible worlds where the sentences with which one is updating are not true. Assuming just the premises of an argument can then be modelled as updating a distinguished

informationally minimal state@ with those premises. The second of these functions, normalization, encodes in the semantics the notion of assuming everyone and everything as

normal as possible. NormaliZing the result of updating @ with a set of premises r yields a set of information states which are fixpoints of the normalization process. The conclusions of reasonable inferences from premises r are all those sentences that are true at all the worlds in all of these fixpoints. The figure below graphically depicts our dynamic theory of reasonable inference;+ represents update, the arrows the normalization process. @ Tweety flies

2. The Truth Conditional Semantics of Generics

2.1 The Language

In the following we are working with a first-order language L augmented with a binary conditional operator>.

The formulas of the language L> are defined by the usual clauses, t.Ogether with the following one:

If cp and 'I' are formulas, then cp >'I' is a formula. This definition allows for arbitrarily deep nesting of the conditional > in formulas.

2.2 The Truth Conditional Semantics

The underlying semantic idea in interpreting the language L> is that a generic sentence lr;/x(<p >'I') is true at a possible world just in case, at that world, being a normal cp involves being a 'I'· The modal frames encode what being a normal <p invariably involves by means of a worlds accessibility function *, which assigns to each possible world w and proposition p a set of worlds. This gives a basic semantics for L> and a simple system of commonsense entailment

DEFlNITION: A L> frame is a triple F= <W, D, *>where

1. W is a non-empty set of worlds,
2. ii) D is a non-empty set of individuals, and
3. iii)*: W X ~(W) __. ~(W)

*(w, p) contains only worlds in which, intuitively speaking, the proposition p holds together with everything else which, in world w, is normally the case when p holds. For example, let p be the proposition that Big Bird of Sesame Street fame is a bird. Let w be the actual world, where it is true that birds fly, that birds have feathers, and that birds lay eggs. Then *(w, p) contains only worlds where Big Bird flies, has feathers and lays eggs. World w may in fact not be in *(w, p), given that the television character is, as birds go, not at all typical.

Note that what is normally the case when a proposition p holds is allowed to vary from possible world to possible world. We want there to be, for example, possible worlds where Tweety is a perfectly normal bird and doesn't fly, these quite simply being those possible worlds where it is not true that birds fly. Note also that it is important that we do not suppose any absolute normality order on possible worlds. In particular, we explicitly reject the idea that *(w, p) is to be identified with those most normal of all possible worlds where p holds.

Up until now * has been left virtually unconstrained, and indeed in view of the weak logic of generics only a few constraints are needed. 2 The first of these is

FACllCITY: *(w, p) f p

Worlds where p holds together with other propositions which are normally associated with p are, no matter how few of these other propositions hold, in any case worlds where p holds. One of the most important patterns of defeasiple reasoning which we want to capture is the penguin principle. We capture the penguin principle by introducing a constraint on *. When we build the dynamic semantics, this constraint

2one constraint on · which is familiar from the literature on conditional logic but which we certainly do not want to impose here is

CENTERING

Ifwep, then we *(w, p)

That w is a world where p holds is no guarantee that w is a world where everything holds which is normally associated with p.

will interact with the normalization function in such a way as to give us the penguin principle.

Suppose that p is the proposition that Tweety is a penguin, q the proposition that he is a bird; suppose further that if Tweety is a nonnal bird he flies but that if he is a normal penguin he doesn't fly. Then specificity says that for any world in which Tweety is a normal bird, he's not a penguin. We don't think specificity is all that intuitive by itself, but it yields plausible results when combined with our operation of normalization. In all of the following we will restrict L:> to those which satisfy facticity and specificity.

We now define L> interpretations in L> frames in the standard way.

DEFINITION: A base model M is a pair M = <.F, U >, where

1. Pis an L> frame, and
2. ii) [D is a function from nonlogical constants of L to appropriate intensions (functions from worlds to appropriate extensions)

The satisfaction definition for L> sentences islargely familiar and uses assignments ai: Var - DM. Truth is deiined as satisfaction with respect to all assignments.

DEFINITION: For any possible world w e WM and model M: M, w, ai ~ <p, as usual, for <pan atomic formula ofFOL.

M, w, ai ~ <p >'I' iff *(w,lcpiM, a 1 ) f I'JfiM. a 1 The usual clauses for complex formulas involving 'V, 3, v, &, .... ,-..

This truth definition implies that a generic sentence is true in a model Mat a world w iff for all~ e DM. *(w,I~_Thi) f 1\Jf.§IM. One important novelty in this definition is that unlike the usual definitions in modal or conditional logic, the semantics for generics exploits the instances of the formulas on the left and the right As a result, the truth of birds fly does not imply the existence of worlds where all birds are normal fliers. This is an unnatural assumption in many cases.

L> logical consequence, ~. is defined in a completely standard way: r ~ <p iff in all L> models M extending L> frames satisfying facti city and specificity, if 'Vy e r M ~ y, then M ~ <p. A corresponding derivability notion 1- is given by the following rules and axioms; the resulting derivability notion is denoted 1-.

TheLogicT1

(AI) Truth functional L:> tautologies (A2) 'Vx<p - <p[t/x] for any tenn t (A3) 'Vx <p- -,3x-.<px (A4) 'Vx(<p- 'I')-(3x<p- 'I') (A5) <p> <p. (A6) (<p >"' & "'> c & <p > -.o- "'> -.<p. (A 7) 'Vx( <p > 'I') - ( <p > 'Vx'Jf), for x not free in <p. (Rl) 1- <p and 1- <p - 'I' - 1- 'I'

(R2) 1- ('I' I & · · & 'l'n)- 'I' -1- (<p > '1'1 & · · & <p> 'l'n) -<p>'Jf

(R3) 1- <p- 'Jf[t/x], where tis a constant not in <p or 'I' -1<p- 'VX'Jf

(R4) 1- <p -1- <p[t/x] where tis a term not in <p.

(RS) 1- <p- 'I' and <p a subformula of C- 1- C- C['Jf/<p]

Using a slight extension of the present language so as to express the Penguin principle and Henkin's technique to construct a canonical model yields the following completeness theorem for T1·

nmOREM 1: r 1- <p iff r ~ <p

3. The Dynamic Semantics of Generic Reasoning

We now show how to model the patterns of invalid but reasonable inference by building on top of the truth conditional semantics a dynamic semantics. We will use four concepts: information states, updating, the state of ignorance, and normalization, which we now spell out

3.1. Information States, Updates and Ignorance

We take information states to be sets of possible worlds taken from the base models already defined. Accordingly, our approach to updating information states with new information is very simple and follows Stalnaker's definition. On updating with Sam is a dodo, the set of one's informational possibilities is reduced to those possible worlds where Sam is a dodo. We will define update functions + of this kind. We also will define a support relation~ between belief states and sentences of L>.

In order to capture the notion of believing no more than one has been told, we must define a very particular information state. This is the informationally minimal state of

the introduction, @. This informationally minimal state must support only logical truths. This state must have some particular properties: it must contain enough worlds to verify every possible consistent combination of L sentences, for instance. Furthermore, it must contain worlds w to which are assigned sets of p normal worlds for every proposition p so that the T 1 axioms hold at every w. The Henkin construction procedure for the canonical T 1 model yields the appropriate model Mo in which to define ignorance. W o, the set of worlds

in Mo, is just@. "Knowir~10 more than r" comes to being in the information state~+ r.

3.2 Normalization

Normalization is the most complex part of our dynamic semantics. In normalization we assume that various individuals in a certain situation are normal. Situations contain objects with properties and standing in relations to each other. In normalizing with respect to a possible situation, we will be assuming the individuals in that situation to be normal with respect to the properties they have in that situation. Since such situations need not be actual, the individuals may not actually possess those properties. We limit ourselves here to simple situations. A simple situation is one in which a single individual has a simple atomic property; in virtue of the canonical model in which we are working, we may identify a simple situation with an atomic formula or a negation of an atomic formula paired with an individual. To model the notion of assuming everything to be as normal as epistemically possible, we iterate normalization with respect to a set of simple situations.

To get an intuitive feel for normalization with respect to a single, simple situation consider for example a state which contains only the information that birds fly and that Tweety is a bird. Strengthening such a state with the assumption that Tweety is as normal a bird as is consistent with that state will return the information that Tweety flies. An initial state which contains the additional information that Tweety does not fly will, when thus strengthened, not return the information that Tweety flies, since in this case the new assumption is not consistent

The normalization function makes use of the information about normality contained within whole information states. So we define the notion of a set of normal worlds for information states as follows:

DEFINITION: *(s, p) := Uwe s *(w, p).

Consider a simple situation 'I' 'If= «p{x), 5> and 5 e DM 0 · We will write l'lfl to denote the set of worlds in which 5 has the property of being a <P· !::!f...s, 'If), defined below, stands for the result of strengthening s by assuming 5 to be a normal 'If, if this is consistent with s. The definition of normalization uses inforination about normality to characterize worlds that the state does not take to be normal. For 'If as defined above, I'JII \ * ( w, I'JII) stands for the set of possible worlds in which, according to an isolated w, an individual 5 is, though a <Jl, not a riormal <P· So l'lfl \ *(s, I'JII)) is the set of worlds where, according to all of the worlds in s, 5 is not a normal <P· They all agree that in each world in l'lfl\ *(s,I'JII)), 5 lacks at least one of the properties had by a normal <P·

DEFINITION: N (s, 'If) : = { W E S : W ~ {l\jtl \*{s,I'JII})), if S () *{s,lljll) ':1: llr. : = s, otherwise.

N isolates those worlds in s where 5 is a normal <Jl, if this is consistent with s: a world v is excluded from N(s, 'If) just in case 5 is, at v itself, not a normal <Jl, if this is consistent with s. To see what this means concretely, let us for the moment suppose that it is, intuitively speaking, consistent with s that 5 is what (in s) is taken to be a completely normal <P· For example, where <P is bird(x) and s contains the information bird(f>) and bird(x) >x fly{x), we are supposing the sentence fly@ to be consistent with s. This state of affairs amounts formally to the case where s () *(s,I'JII) ':1: 111. so then, given the above explanation of what l'lfl \*(s,lljll) stands for, N (s, 'If) clearly contains only those worlds in s where 5 is, if at all a <Jl, then as normal a <P as is consistent with s (namely a completely normal one). It is not always consistent with s that 5 is a normal <P· This is the case in which s () *(s,lljll) = f/1. Assuming 5 to be a normal <P is in this case hopeless, so the normalization function "gives up" and simply returns the original state s.

Let us now turn to iterated normalization. In normalizing with respect tO many individuals and many properties, we iterate the normalization function on information states. One factor affecting such iterated normalization is the order in which the normalizations of the sort discussed in the previous section are performed. Consider for instance a Nixon diamond situation, where the outcome depends on the order in which the different respects in which individuals are assumed normal show up in the iteration. If one first assumes that Dick is a normal republican and only then assumes that he is as normal a quaker as possible, then one will end up with the information that he is a non-pacifist If one frrst assumes him to be a normal quaker and then assumes that he is as normal a republican as possible, then one will end up with the information that he is a pacifist So it is desirable that the order sensitivity of the iterated normalization be cancelled out by taking all different orderings of the iterations into account A second point about iterated normalization concerns the situations relevant to normalization. The relevant situations are defmed with repsect to the premises r in a nonmonotonic inference that one wishes to verify. The relevant situations relative to a set of premises r are those situations <<P{x), 5> where 5 e DM 0 and <P(x) is either the antecedent of a "positive" occurrence of a universally quantified> conditional in r* or identical with S{x/t), where 5 is the antecedent of a non quantified > conditional in r*, where r* contains the conjunctive normal form of each sentence in r. We call the set of such antecedents Subst(Ant(f)).

DEFINITION: For r f L>, the T-normalization chain with respect to an enumeration v of Subst(Ant(Ij) is defined

to be the following sequence: N>v =s N«+1v = N(N«v. <P,), where a= A.+ n +1, and v{cp,) =n+ 1.

There is one such r -normalization chain for each state and each enumeration of Subst(Ant(r)). Every r-normalization chain beginning in a state s reaches a frxed point That is: for all s and v, 3a'v'J3 ;;:: a NIJv = N<lv.

3.3 Reasonable Inference

Armed with the notions of information states, ignorance, updating and maximal normality, we can now put together our model theory of non-monotonic reasoning. We defme the relevant dynamic information model, as well as the support relation for information states, and then finally our notion of commonsense entailment

DEFINITION: The dynamic information model J.lo is a triple <P<WM 0 ), +, !::!.>, and:

• (i) +: P<WM 0 ) X P(L>)- P<WM 0 ) is defmed such that 'v's E P<WMJ. 'v'r f L> S+ r = s () ( flye ri "''Mo>·

(ii) !Yis the normalization function on information states.

DEFINITION: For s e fJ{WM 0 ), s ~ <P iff for all we s, Mo, w ~ <P·

DEFINITION: r I= <Jl iff for any r-normalization chain C beginning from @ + r, C* ~ <Jl, where C* is the fixpoint of C.

Since r 1- cp - r I= cp, our non-monotonic consequence relation is supraclassical. Further all the T 1 theorems are also I= valid. Theorem 2 shows that 1=. captures the first group of reasonable inference patterns from the introduction.

• DEFINmON: cp, 'I' and l;are independent formulas just in case for all §, each boolean combination containing at most one instance of each of cp§, 'If§, ~ is satisfiable.
• THEOREM 2: When cp, 'If, and C are restricted to independent formulas, Defeasible Modus Ponens, Pointwise Defeasible Transitivity, Pointwise Defeasible Strengthening of the Antecedent, Nixon Diamond, Penguin Principle, the Embedded Normality patterns as they are stated in the introduction all hold given our interpretation of 1=.

Another welcome fact about our interpretation of I= is that Defeasible Irrelevance does not hold While this fact follows straightforwardly from the defmition of 1=, the proof of theorem 3 exploits a construction of particular worlds for each inference pattern that (a) verify the premises of the inference pattern and exist in the state of ignorance, (b) survive the process of normalization, and (c) have the requisite properties to force the normalized state to verify the desired conclusion.

4. Subtheories and Extensions

There are several extensions and subtheories of the basic system. of commonsense entailment we have just described that we will describe at length in a longer paper. For instance, there is a quantifier free version of our system in which the set of nonmonotonic consequences of a finite set of premises r is decidable.

We can also extend the system of commonsense entailment in L> with stronger monotonic inferences. We think, for example, that this inference pattern is valid

Vx(cp >'I') & Vx(C >'I') 1- Vx((cp v 0 >'I') The constraint on * required to validate the Dudley Doorite argument scheme in an L> complicates, however, the construction of a canonical model. ·

We may also extend the system by complicaing the definition of normalization.

oEFINmoN: !::!"' (s, 'If) =!f.{s, 'I') rl X, where

X:= ( we s: for all situations C *(w, 11;1) = *(w, 10)\ *(s, 1'1'1)}, if*(w, 10)\ *(s, 1\vl) :;tllf; := s otherwise.

Where 'If= <cp(x), S> and S e DM 0 , a world vis excluded from !f.{s, 'I') just in case S is, at v itself, not a normal cp and this is consistent with s. A world v is excluded from set X just in case the set of normal C worlds of v contains worlds where S is not a normal cp if this is consistent with other normality information in s. Each set of C llormal worlds for worlds of s should encode as much normality information of s as . is consistent with it A nonmonotonic consequence relation I=* based on N* extends I= and verifies the rule forms of defeasible transitivity and strengthening of the antecedent .

Ye~ another extension refines the basic semantics by replacmg the sets of normal worlds *(w, p) in L> models with concentric spheres of worlds $(w, p ). to capture a limited version of the graded normality inferences}

5. Comparisons with Other Work

The theory presented above derives heavily from two traditions in logic which many have thought closely related: modal logic and the theories of nonmonotonic and default reasoning developed during the last decade. Our theory differs considerably from Reiter's default logic. Reiter's default logic augments classical logic with default rules of the form: if cp and it is not inconsistent to assume 'If, then C. ~e~. rules offer a representation of generiC facts, but stgniftcantly the theory has no representations for generic sentences in the object language. Thus, there seems to be no way to write down sensible representations for nested defaults and nested generic statements or to reason about them within Reiter's formalism. McCarthy's original proposal concerning circumscription-- or the model theoretic minimization of certain predicates-- has in principle the resources to represent nested generic sentences, on the other hand; but the formalism does not capture most of the desired inferences. Further, the original system as well as subsequent re~mements are very unstable. Defeasible modus ponens falls, for example, as soon as we add the new premise that tOOI:e is~ bird that doesn't fly. Fmther, the refinements get the ~sired inf~rences only to the extent that ghosts are imported mto the logtc. We get the inferences without ghosts. .

~ith ~!grande, we exploit an analogy with conditional logtc .. Agam, however, Delgrande does not give a theory that perm1~ us to reason about or even assign meanings to nested genenc statements. Delgrande's theory does not, insofar as we understand it, handle adequately inferences like defeasible strengthening of the antecedent The reason we get defeasible strengthening in the same breath (though it's a deep one) as default transitivity is because of ,the very special use of the informationally minimal state and updating. Whereas Delgrande has to appeal to complicated mechanisms to test for "irrelevance," the update of the informationally minimal state with birds fly will yield upon normalization that white birds fly.