erase On the Consistency of Commonsense Reasoning

On the Consistency of Commonsense Reasoning

Donald Perlis

University of MarylandDepartment of Computer ScienceCollege Park, Maryland 20742

perlis@maryland.arpa(301) 454-7931

Abstract: Default reasoning is analyzed as consisting (implicitly) of at least three further aspects, that wecall oracles, jumps, and fixes, which in turn are related to the notion of a belief.Beliefs are then discussedin terms of their use in a reasoning agent.Next anidea of David Israel is embellishedto showthat cer-tain desiderata regarding these aspects of default reasoninglead to inconsistent belief sets, and that as aconsequence the handling of inconsistencies must be taken as central to commonsense reasoning. Finally,these results are applied to standard cases of default reasoning formalisms in the literature (circumscription,default logic, and non-monotonic logic), where it turns out that evenweaker hypotheses lead to failure toachieve commonsense default conclusions.

descriptors: beliefs,consistency, introspection, knowledge representation, defaults, circumscription, non-monotonic logic, commonsense reasoning, ornithology

I.Introduction

Much of the present paper will focus on default reasoning. Wewill primarily consider a stylized formof default reasoning that appears to be current in the literature, and try to isolate aspects of this stylizationthat are in need of modification if deeper modelling of commonsense reasoning is to succeed. Specifically,we will showthat default reasoning as has been studied in particular by McCarthy[1980,1984], McDer- mott-Doyle [1980], and Reiter [1980] in their respective formalisms (Circumscription, Non-MonotonicLogic, and Default Logic), will lead to inconsistencyunder rather natural conditions that we callSocraticandrecollectivereasoning. Roughly,aSocratic reasoner is one that believesits default conclusions in gen-eral to be error-prone, and a recollective reasoner is one that can recall at least certain kinds of its previousdefault conclusions.We will showthat the standard approaches, based on what we termjumps,(as injump-ing to a conclusion)are inconsistent with these desiderata.1

This is not to say that research into these formalisms has been misguided, or that their authors haveassumed that theywere adequate for all contexts. On the contrary,these studies have been essential firststeps into an area of high complexity demanding a ‘‘spiralling’’approach of more and more realistic set-tings. Here then we hope to showone further stage of development that is called for.Infact, elsewhere[Drapkin-Miller-Perlis 1986] we have argued that inconsistencyisasomewhat normal state of affairs incommonsense reasoning, and that mechanisms are needed for reasoning effectively in the presence ofinconsistency.

Note that there are at least twogeneral frameworks in which such formal studies can proceed: we canseek a specification of formal relations that might hold between axioms and inferences in a supposeddefault reasoner (the ‘‘spec’’approach); or we can seek to identify specific actions that constitute the pro-cess of drawing default conclusions (the ‘‘process’’approach). Thatthese are related is no surprise. Ineffect, the first is a more abstract study of the second, aimed at providing a characterization of what sort ofthings we are talking about in our study of defaults. However, there is a hidden further difference, namely

1

‘‘Jumping to conclusion can lead to unpleasant landing.’’ Chinese fortune cookie, 1986.

that in pursuing the former,one is naturally led to consider idealized situations in which features irrelevantto the particular phenomenon at hand are deliberately left out of consideration.Such an approach has beencustomary in much research in commonsense reasoning, most conspicuously in the assumption of logicalomniscience: that an agent knows (and eveninstantly) all logical consequences of his beliefs, generallyregarded as part of the notion of epistemological adequacy. That is, although no one believesthat agentsactuallycan reason this way,ithas seemed to be a convenient test-bed for ideas about what reasoning islike,apart from the ‘‘noise’’ofthe real world.

While this has come under criticism lately,and while authors of default formalisms acknowledge theimportanceto their very topicof the process nature of defaults,2still the latter has remained conspicuouslyabsent from the continuing development of such formalisms. Here we argue that the very essence of defaultreasoning, and of commonsense reasoning in general, derivesfrom its being embedded in the real world,and in agents evolved to deal with such by means of an appropriately introspective viewoftheir own falli-bility and corrigibility overtime. This in turn will be seen to pose problems for logical omniscience.The‘‘spec’’viewofanideal thinker,which we are critiquing, we refer to as that of an ‘‘omnithinker’’(or OTfor short).

To facilitate this discussion, we first present an extended illustration of default reasoning along linesfound in the literature.Reasoning by default involves reaching a conclusion C on the basis of lack of infor-mation that might rule out C.3Forexample, giventhat Tweety is a bird, and no more, one might, ifprompted, conclude (at least tentatively) that Tweety can fly.4Here C is the statement that Tweety can fly.Such a conclusion may be appropriate when ‘‘typical’’elements of a givencategory (in this case, birds)have the property under consideration (ability to fly).

At least regarding their context of an overall process of reasoning going on overtime within a changing environment of inputs.

E.g., McDermott and Doyle [1980, p 41] speak of ‘‘...modelling the beliefs of active processes which, acting in the presence of incom-plete information, must makeand subsequently revise assumptions in light of newobservations.’’ Reiter [1980, p 86] mentions ‘‘...theneed for some kind of mechanism forre vising beliefs[his emphasis] in the presence of newinformation. Whatthis amounts to is theneed to record, with each derivedbelief, the default assumptions made in deriving that belief. Should subsequent observations invali-date the default assumptions supporting some belief, then it must be removedfrom the data base.’’

342

Doyle [1983,1985] has presented interesting views on this phenomenon, relating it to group decision-making.

Tentativity is the obvious key,which all default formalisms are designed to capture, as opposed to other more robust kinds of

inferences. And it is this that our analysis will focus on most.

In the bird example, additional information, such as that Tweety is an ostrich, or that Tweety has abroken wing, should block the conclusion that Tweety can fly.Just howitistobedetermined that the con-clusion is or is not to be blocked, is still a matter of debate. Nonetheless, we can usefully discuss the phe-nomenon of default reasoning in the form of a sequence of steps in a suitable formal deduction, as follows:We simply list the ‘‘beliefs’’that a reasoning agent may consider in drawing the default conclusion. Thiswill be done first in a very sparse form, and then later in more amplified form. The following list is intendedto be in temporal order as our reasoner ‘‘thinks’’first one thought (belief) and then another.Step (2) is theusual default conclusion, givenbelief (1), and steps (3) and (4) illustrate the apparent non-monotonicity inwhich additional data (3) can seemingly block or contradict an earlier conclusion.

(1) Bird(Tweety) [this simply comes to mind, or is told to the agent]

(2) Flies(Tweety) [this ‘‘default’’comes to mind, perhaps prompted by a question]

(3) Ostrich(Tweety) [observed, remembered, or told to the agent]

(4) ¬Flies(Tweety) [this comes to mind]

Now, the above sketch of reasoning steps ignores several crucial points.In particular,the direct passagefrom (1) to (2) obscures several possible underlying events,5namely (a) a recognition that it is not knownthat Tweety cannot fly (i.e., Tweety is not known to be atypical regarding flying), (b) an axiom to the effectthat flying is indeed typical for birds (so that if a bird can be consistently assumed typical, it is likely that itcan fly,and therefore a reasonable tentative assumption), and (c) the willingness to go ahead and use thetentative assumption as if it were true.6

Similarly,the passage from (3) to (4) obscures the necessary information that ostriches cannot fly.Finally,(4) leavesunsaid the implicit conclusions that (a) Tweety must be atypical and that (b) the assertion

with emphasis on ‘‘possible’’. It is not claimed that these events must occur; but we will argue that for certain commonsense

situations theyare appropriate.

Note that Nutter [1982,83a] in effect cautions against careless use of this latter step. Toanextent the present paper can be con-strued as illustrating howbadly things can go wrong if Nutter’swarning goes unheeded.

65

that Tweety can fly is to be suppressed. The following sequence illustrates this more explicit description.

7

Certain of the newsteps have been labelled with the termsoracle,jump,andfix.Forthe moment, we limitourselves to the following brief remarks; later we will elaborate on them: Oracles are what makedefaultreasoning computationally difficult and also what makeitnon-monotonic; jumps are what makeitshaky(unsound); and fixes keep it stable. Only the work of McCarthy[1980,1984] has seriously addressed theoracle problem; McDermott and Doyle [1980] and to some extent Reiter [1980] have characterized jumps;and Doyle [1979] has the only work on fixes.

(1) Bird(Tweety) [axiom]

(1a) Unknown(¬Flies(Tweety)) [oracle]

(1b) Unknown(¬Flies(x)) & Bird(x) .→Tentative(Flies(x)) [default]

(1c) Tentative(Flies(x))→Flies(x) [jump]

(2) Flies(Tweety) [consequence of 1, 1a, 1b, 1c]

(3) Ostrich(Tweety) [newaxiom]

(3a) Ostrich(x)→¬Flies(x) [axiom]

(4) ¬Flies(Tweety) [consequence of 3, 3a]]

(4a) Flies(x) & ¬Flies(x) .→.Suppress(Flies(x)) & Atypical(x) [fix]

(4b) Atypical(Tweety) [consequence of 2, 4, 4a]

(4c) Suppress(Flies(Tweety)) [consequence of 2, 4, 4a]

Here we are relaxing the ‘‘spec’’approach a bit; but still it fits the philosophyfor an omnithinker: no claims are being made re-garding actual implementations, and the newsequence corresponds to technical features of the three standard formalisms, as will bepointed out later.Thus we have a kind of meta-example of the spec approach.

7

To restate quickly (and a bit oversimply) our aims in this paper,wewill argue that anymechanism fordefault reasoning that utilizes jumps will be inconsistent if it also is Socratic (believesitcan makemis-takes) and recollective (recalls its past conclusions). Moreover, the above expanded scenario with fixesstrongly suggests the need for precisely these kinds of additional features (Socratic and recollective).

It is nowtime to turn to an extended look at the nature of beliefs, since the cursory treatment ofdefaults above should makeclear that beliefs are the stuffthat defaults are made of, and that if we do notknowwhat beliefs are, at least in rough form, then we will remain in the dark about defaults as well. Morespecifically,addressing the issue ofconsistencyof an agent’sset of beliefs makes it essential to decide, atleast informally,what counts as a belief.

II.Apreliminary analysis of beliefs

Much AI literature purports to be about the beliefs of reasoning agents, e.g., Moore [1977], Perlis[1981], Konolige [1984]. Yet little in this literature has been said as to what actually makes something abelief.8While it is acknowledged that the ontological character of beliefs is unclear,and that at least twoapproaches are worth considering (the syntactic and the propositional), not much attention has been givento the issue of what distinguishes a statement or proposition that is a belief from one that is not. Agents areendowed with a fairly arbitrary setBel,subject perhaps to the requirements of being internally consistentand deductively closed, and that is that. It is as if anystatement whatevermay count as a belief.Forourpurposes, this is insufficient; therefore we shall spend some time discussing this matter,and especially howit relates to the issues of consistencyand tentativity in commonsense reasoning.

In everyday language, the word ‘‘believe’’ isused in several rather different ways. For instance, onemight hear anyofthe following statements: ‘‘I believe you are right.’’ ‘‘Ibelieve Canada and Mexico arethe only countries bordering the United States,’’ ‘‘Ibelieve this is the greatest country in the world,’’ and ‘‘Ibelieve gravity causes things to fall.’’ These seem not to employthe same sense of the word ‘‘believe.’’

8

Among philosophers, Dennett [1978] and Harman [1973, 1986] have studied this question in ways congenial to our approach.

Moreover, ‘‘Two plus twoequals four’’can be regarded as a statement believedbywhoeverasserts it, andyet ‘‘I believe two plus twoequals four’’seems to convey a sense of less assurance than the bald assertionof the believedstatement without the self-conscious attention to the fact that it is believed. Anespeciallythornyaspect of this is that evenwhen the statement of belief seems unambiguous, what is it that makes ittrue (or false)? That is, I may claim to believe x,but howdoImean this? That x is ‘‘in my head’’, seemsboth the obvious answer,and yet completely misguided, for manythings can be in my head without mybelieving them. That 2+2=5 is surely in my head nowasIwrite it, yet as something Idon’tbelieve.Soitisaspecial ‘‘mark’’ofbelief that makes certain things in the head beliefs. What ‘‘mark’’isthis, and what hasit to do with reasoning?

We need then a definition of beliefs, so that we can makeprecise claimshere and attempt to defendthem. Unfortunately,aprecise definition will not be forthcoming here; it is a subject of considerable diffi-culty.Howev er, a tentative but useful answermay be as follows: certain things in the head (or within a rea-soning system) may beused in reasoningas steps in drawing conclusions as to plans of action; let us calltheseuse-beliefs.Ineffect, use-beliefs are simply potential steps in proofs of plans.(Note that these mustbegenuinesteps, not convenient hypotheses, as in a natural deduction case argument, which later are dis-charged. That is, anysuch step must itself be a possible terminal step, i.e., a theorem.)Such entities wouldseem to form an interesting class of objects, relevant to the topic of commonsense reasoning. It is notoffered as a matter of contention or empirical verification, but rather as an aspect of reasoning worth study.The main issue we wish to address then, is the mutual consistencyofuse-beliefs in a commonsense reason-ing system. For somewhat greater definiteness, we codify our ‘‘definition’’below:

Definition:αis(use-)believedby agent g, if g is willing to useαas a step in reasoning when drawing con-clusions as to plans of action.9

An anonymous referee suggested the friendly amendment: ‘‘agent A believesthat p in case, if A desires e, A is disposed to act

in a way that will produce e giventhat p is true.’’ I reg ard this as in the spirit I am aiming for; however, see belowonceteris paribusconditions.

9

Whether an assertion A is to be a use-belief, may depend on the context in which it is to be used.Thus in some contexts one and the same assertion ‘‘I believe X’’ may correspond to the presence of a beliefXinour sense, and in another not, depending on the speaker’swillingness to use X in planning and acting.Roughly speaking,the word ‘‘belief ’’will be used to refer to anystrong notion that the agent is willing totrust, and does trust and use in planning and acting, ‘‘as if it were true.’’ Now,this is not without its murkyaspects. Manyassertions can be sincerely doubted and sincerely taken as plausible at the same time (see[Nutter 1982,83a,83b] for a well-argued point of viewonthis). Instead of attempting to provide a fool-proof analysis of beliefs by defining precisely the words ‘‘willing’’, ‘‘conclusion’’, ‘‘plan’’, etc., in theabove definition, we will rely on examples.

Consider the following: that my car is still where I last parked it, seems very likely,and I may wellbehave asifIreg arded this to be the case, and yet I also recognize it is merely highly probable. Our pro-posal is to takesuch a statement to be a beliefifIamprepared to use it as if true, and not otherwise. That is,if I regard it as highly probable but also hedge my bets by checking to see whether a bus will pass by incase the car is missing, then I do not have the belief that my car is where I last parked it; rather I may havethe belief thatthe probability is high thatmy car is where I last parked it.However, ifIignore the possibil-ity that my car may not be where I last parked it, andbase my actionson the assumption that it is still there,then eventhough I may admit that I am not certain where it is, I have the belief that it is where I last parkedit. That is, we are defining the word ‘‘belief ’’inthis manner (which incidentally seems consistent with onefairly common usage: one might very well say,‘‘I realize my car may somehowhav emoved, but I nonethe-less believe ithas not’’).

Another example illustrating the difficulties in pinning down use-beliefs is the following (due toMichael Miller): Individual X believes(or so we wish to say) that smoking is dangerous to one’shealth, yetXdoes not give upsmoking. Can we fairly say X is using that ‘‘belief ’’inplanning and acting? I think thatthe answer is yes, but in a qualified sense. X will makeuse of Dangerous(smoking) as a fact to reason with,butthis need not mean going along with (putting into action) the conclusion that X ‘‘should’’giv eup smok-ing. (Compare Newell’sPrinciple of Rationality [1981], in which ‘‘action P causes Q’’and ‘‘Want Q’’lead

to ‘‘Do P’’.) Whatwe need to do is to create (perhaps only as a thought experiment) a ‘‘neutral’’orceterisparibus(‘‘other things being equal’’) situation in which X’sactions can be supposed to be influenced onlyby the relevant ‘‘beliefs’’weare testing. Weare not in anyway taking the viewthat X’sbehavior is deter-mined only by a set of formulas in X’shead (rather than by,say,stubbornness or competing concerns).

In other words, there may be manycompeting use-beliefs in one agent; this is not to be construed asall of them leading independently to givenactions. Only in rarefied circumstances will this be the case.Forinstance, we may imagine a situation in which the belief that smoking is unhealthywould lead to a directaction in the givenagent. For instance, if the agent’s12-year-old niece wishes to begin smoking, and if theagent is very concerned about her health, and if the agent livesthousands of miles awayand would deriveno comfort from another smoker in the family,and so on,thenthe givenbelief will lead to action to dis-courage the niece from smoking. Of course, the trick here is the ‘‘and so on’’. The definition then serves apurpose in being suggestive rather than definitive.What we need is a far deeper understanding of ‘‘what isin the head’’, perhaps something along the lines of Levesque’s[1985] notion of ‘‘vividness’’.

Are there situations where a more definitive kind of belief is available? Perhapsin the realm of sci-entific law, one can have beliefs that are held to be certain.It is worth exploring further examples. Forinstance, a belief in the actuality of gravity.Asaphysical theory,this is well supported, and yet most physi-cists will likely say that anytheory of gravity is after all only an approximation that will almost surely bereplaced by a better theory in the future, and indeed perhaps a theory in which gravity as such does not fig-ure at all. Now, gravity may become a derivednotion in such a future theory,but then it plays the role ofnaming a class of macroscopic phenomena such as ‘‘when I release a cup I have been holding, it will drop.’’But in what way is this a belief? Surely in the same sense as anyeveryday claim.That is, we expect thecup to drop, but do not regard it as absolutely beyond question. It may stick to our fingers, someone maycatch it, a gust of wind may carry it upwards, and so on. If we try to eliminate ‘‘extraneous’’factors such asthese, we simply end up with the familiar qualification problem. It is not clear that anyassertions of a gen-eral nature having practical consequences can be stated with certainty outside the realm of basic sciencewhere extraneous factors can be stipulated in full (at least relative tothe theory one is using), and this lies

faroutside the realm of commonsense reasoning. Moreover, eveninbasic science, as we have illustrated,so-called laws are usually taken to be tentative.

We can envision someone saying, ‘‘I definitelybelieve this cup will fall when I release my hold onit.’’ And yet that same person will certainly grant our exceptional cases above,perhaps howeverprotestingthat these aren’twhat he or she had in mind. But that’sjust the point of the frame problem: we do not, andcannot, have inmind all the appropriate qualifications. Wetakethe statement as asserted (the cup will fallwhen released) to be (or represent) the belief.Perhaps such thinking is more in the form of visual imagerythan explicit statements to oneself, and perhaps visual imagery allows a certain loose notion of generic situ-ations appropriate to commonsense reasoning. Be that as it may,people are often willing to assert boldly,ev enwhen questioned, that theybelieve such-and-such, and yet afterwards will agree that it is not so certainafter all.

However, the ‘‘bare’’unqualified assertions in Bel, by their definition as use-beliefs, are in fact sig-nificant as elements of thought, and it is also significant whether twoormore elements of Bel conflictinand of themselves.To illustrate this, consider Reiter and Criscuolo’sexample [1983] of interacting defaultsfor Quakers and Republicans. Quakers (typically) are pacifists; Republicans (typically) are not. Nixon is aQuaker and a Republican. One might then tentatively conclude that Nixon is a pacifist, and also that he isnot. Now, there is a sense in which this is quite reasonable: it does appear appropriate to consider that, onthe one hand, Nixon might very well be a pacifist since he is a Quaker; and on the other hand, that he mightvery well not be a pacifist since he is a Republican. That is, speculation about the origins and influences onhis status regarding pacifism may be of interest for a givenconcern.

However, itwill not do to entertain both that he is and that he is not a pacifist in one and the sameplanned sequence of actions. If one is using the assumption that Nixon is a pacifist, then one is not simulta-neously willing to use the assumption that he is not a pacifist. That is, eventhough the expanded statements-- that there is some evidence that Nixon might be a pacifist and some evidence that he might not -- are notcontradictory,nonetheless one would not be willing to assume, evenfor the sakeofavery tentative kind ofplanning, that he both is and is not a pacifist. Moreover, ifprobabilities are used so that, let us suppose,

Quakers have a 99% chance of being pacifists, and Republicans a 90% chance of not being pacifists, thenthe recognition that these should not both be used separately to form tentative conclusions as to Nixon’spacifism depends on noting that such unexpanded conclusions -- Nixon is a pacifist and Nixon is not a paci-fist -- indeed do conflict.

Consider again the released cup that may or may not fall. The speaker who claimed it would fall mayenact a plan to cause the cup to fall, by releasing the cup. But if there is honeyonthe edge of the cup sothat when released it remains stuck to the fingers, this plan will not be effective.Howev er, when the honeyis pointed out, thereby creating a belief that the cup will not fall when released, the direct contradictionwith the earlier claim becomes important for the correct forming of a newplan. Nowone must remove thehoneyoruse more force in separating cup from fingers, etc. However, ifthe original claim were to be quali-fied so that it accounted for the possible presence of honey, then the original plan of releasing the cup is notso easily accounted for.The point is that we do try to keep our unexpanded (use-) beliefs consistent, eventhough we may recognize that theyare not strictly justified. A plan involves a package of tentative beliefswhich are intended to be internally consistent, so that theycan be enacted. Thus evenifthe planning agentmay not firmly believe,say,the cup will definitely fall when released, still, his willingness to act as if he sobelievedappears to mandate hisnotbelieving, evententatively,that the cup will alsorisewhen released.

The point we are illustrating is that we usually do not tolerate direct10contradictions in the use-beliefs that enter into anyone plan. If we decide to takeastatement A as an assumption for purposes of acertain tentative line of reasoning, we ordinarily will not allowourselves to also assume some other state-ment B that contradicts A in that same line of reasoning, evenifwerealize that both A and B are merelypossibilities. Nonetheless, weshall argue belowthat contradictions do arise within our use-beliefs. Ourprevious arguments about the undesirability of contradictions among use-beliefs are intended to showthatthe presence of such a contradiction cannot be taken lightly.Once we have presented the form of contradic-tion we have inmind, we then will discuss its significance for formalizing commonsense reasoning.

10

More on this later.

The notion of use-beliefs has been described here at considerable length.This may have seemedoverkill, especially on a topic that remains quite befuddled evenaswecome to an end of this section.Nonetheless, it has been a necessary exercise, for we wish to offset a possible objection to the analysis ofdefault reasoning we will nowpursue. In particular,weintend to analyze defaults in terms of beliefs.Now,it can be argued that the consequences of default reasoning, such as that Tweety can fly,are more properlyregarded as tentative notionsthat arenot actual beliefs(see [Nutter 1982,82a]).However, the discussion ofuse-beliefs was intended to showthat evententative conclusions of this sort, if theyare potentiallyusedinanysignificant way in planning activity,should be treated much as if theywere simply asserted flatly with-out qualification of tentativity.11That is, in particular,inconsistencies among such beliefs is a serious mat-ter,more so than would be suggested by treating them as ‘‘shielded’’bya‘‘Tentative’’ modality.Sowecontend that, far from believing very little, commonsense reasoners will have very manyuse-beliefs.

III.Apreliminary analysis of defaults

We now return to our earlier extended example of default reasoning, and analyze it more carefully.The expanded sequence of steps giveninsection I was as follows:

(1) Bird(Tweety) [axiom]

(1a) Unknown(¬Flies(Tweety)) [oracle]

(1b) Unknown(¬Flies(x)) & Bird(x) .→Tentative(Flies(x)) [default]

(1c) Tentative(Flies(x))→Flies(x) [jump]

(2) Flies(Tweety) [consequence of 1, 1a, 1b, 1c]

(3) Ostrich(Tweety) [newaxiom]

11

Much as if, but not wholly as if. This distinction will be brought out more later.

(3a) Ostrich(x)→¬Flies(x) [axiom]

(4) ¬Flies(Tweety) [consequence of 3, 3a]]

(4a) Flies(x) & ¬Flies(x) .→.Suppress(Flies(x)) & Atypical(x) [fix]

(4b) Atypical(Tweety) [consequence of 2, 4, 4a]

(4c) Suppress(Flies(Tweety)) [consequence of 2, 4, 4a]

The fact thatin order to takeadvantage ofthe absence of information to the contrary,that absencemust be recognized12,iscodified in step (1a).This recognition in general is not decidable13,and so appealis made to an outside source of wisdom, an ‘‘oracle,’’ which tells us that a givenproposition (e.g.Flies(Tweety)) is consistent with what we know. Inthe Non-Monotonic Logic (NML) of McDermott &Doyle, and the Default Logic (DL) of Reiter,such an oracle is explicitly represented, although in signifi-cantly different ways: NML presents an axiom including a modal operator M (for consistency), whereas DLuses M as a meta-symbol in a rule of inference.In McCarthy’sCircumscriptive Logic (CL), a ‘‘weak’’ora-cle appears in the form of the circumscriptive axiomatization itself, which is a source of both advantage anddisadvantage: it is computationally more tractable and less prone to suffer inconsistencyofcertain sorts (aswe will see later), but also fails to recognize certain typical situations for the same reason.

Note that (1b) and (1c) are combined into a single default axiom or rule in NML and DL. Wehav edrawn out the presumed underlying notions, to focus attention on (1c) in particular -- thejump.That is, upto that point, the reasoning is fairly clearcut; but at the jump, something that is only tentative istreated as ifit were outright true.Herein is the source of the familiar unsoundness of non-monotonic forms of reason-ing. The agent whose reasoning is being stylized in the above sequence has jumped to a (firm) conclusion,albeit with plausible grounds to do so; but in the very jump is thepossibility of error.This can be regarded

1213

This is not to say that such recognition need be conscious, but merely that some mechanism or other must perform it.byanydeterministic mechanism, of a logical stripe or no.

as the point at which tentative conclusions are elevated into use-beliefs. However, the earlier discussion ofuse-beliefs indicates that evententative beliefs (un-elevated into ‘‘truths’’) can be use-beliefs.

In step (4a) recognition is made of the fact that an earlier conclusion has been contradicted and thatthe situation must be fixed. Actually,much more than what has been recorded in (4a) is necessary in orderto thoroughly deal with the clash, but for nowwewill leave itatthat.

We then arrive atthe following preliminary characterization of default reasoning: it is a sequence ofsteps involving, in its most general form, oracles, jumps, and fixes. That is, it is error-prone reasoning dueto convenient but unsound guesses (jumps), in which therefore fixes are necessary to preserve(or re-establish) consistency, and which makes the mentioned guesses by means of appeals to undecidable proper-ties (oracles). Wewill makeuse of this characterization in what follows. The general thrust of our line ofargument will be that contradictions (such as between Flies and ¬Flies) generate the need for fixes, and thatboth then are necessary for the evolution of self-reflective reasoning. That is, we claim that a kind of tempo-rary inconsistencypervades commonsense reasoning, and is one of its principal drivers.

IV.Israel’sargument

Israel [1980] offers an argument for the inconsistencyofcommonsense reasoning.Recall that we usethe initials ‘‘OT’’tostand for an ‘‘omnithinker,’’i.e., an idealized reasoning agent that is intended to beable to carry out an appropriate form of default reasoning and other desiderata as will be specified later.Israel begins by stating that OTwill have some false beliefs, and will have reason to believe that is the case,i.e., OTwill believe what we shall designate asIsrael’sSentence,IS:

—(——x)[Bel(x) and False(x)]

where Bel refers in the intended interpretation to the very set of OT’sbeliefs, i.e., Bel(x) means that x is abelief of OT. (Note thatIS,ifitistobeabelief itself, requires that beliefs be representable as terms, e.g.,quoted wffs, and that a certain amount of self-reference is then at least implicit in whateverlanguage isused.)

Now, ifISis true in the intended interpretation, it follows that OThas a belief that is not true, namely,one of theotherbeliefs. On the other hand, if all the other beliefs are true in the intended interpretation,thenISis paradoxical in the sense that, in this interpretation, it is equivalent to its own denial. However, thisdoes not force OT’sbelief set to be inconsistent, for the intended interpretation is not the only possible one.Moreover,ISmay well be true there, i.e., other beliefs of OTmay be false, and indeed this is the muchmore likely situation, and apparently the one Israel has in mind.

One might think (and Israel suggests) that evenwhenISis true, more is forthcoming, namely thatsince OTbelievesall OT’sbeliefs (i.e., OTbelievesthem to be true) and yet also believesone of them notto be true, then OTbelievescontradictory statements and therefore has an inconsistent set of beliefs. How-ev er, this does not follow, and for interesting reasons. The hitch is in the necessity of pinning down all OT’sbeliefs (or at least a suitable subset containing the supposedly false belief). That is, the phrases ‘‘all OT’sbeliefs’’and ‘‘one of them not to be true’’donot refer directly,inOT’sasserting them, to the same things.

Forexample, suppose OThas three beliefs:α,β,andIS,and let us further supposeαis false. Tofol-lowthe above suggestion for deriving a contradiction, we would liketoargue as follows: OTbelievesoneofα,β,andISto be false: ¬(α&β&IS). Also OTbelievesαandβandIS,hence believes(α&β&IS).But these are contradictory.Howev er, this argument makes exactly the oracle fallacythat many(including

—x)[Bel(x) &Israel) have inv eighed against. For OTtoconclude False(α&β&IS)fromIS(i.e., from (—

—

False(x)]), OTmust believe,inaddition toα,β,andIS,that these are OT’sonly beliefs. But thiswould beanother belief! Of course, a cleverencoding ofαmight allowittostate that it itself along withβandISareOT’s only beliefs, thereby avoiding the trouble of an extra belief unaccounted for.(Alternatively,OTmaymistakenly believe the aforementioned three to be its only beliefs.)But this does not resolvethe difficultyat hand, for it is not plausible to argue in generalthat OTwill at anygiv enmoment have a belief such asthis, unless a means is presented by which OTcan deduce such a belief. This is exactly where oracles comeinto the picture.OT must knowthat it doesn’tknow(or believe)anything other than the three statedbeliefs.

NowifOTrefers to its beliefs by means of a term S for the set of these beliefs, then OTmay have a

—x)[x∈S→—x)[x∈S&False(x)] as well as (\\/belief such as (←Bel(x)]. But this is not contradictory,for—

—

OT will presumably not believe Bel(x)→True(x), giventhat OTbelievesIS.For each belief x of OT,indeed OTbelievesx(to be true). But that is not the same as believing the conjunction of these beliefs to betrue. This is a peculiar situation. OTindeed uses full deductive logic, but cannot prove the conjunction of itsbeliefs (axioms), not because of deductive limitations so much as descriptive power: OThas no name that istied formally to its actual set of beliefs. If a super-fancybrand of oracle is invokedtopresent such a nameand the assertion that all elements named by that term are true, then indeed a contradiction follows. Butthere is no obvious argument that such an oracle is a part of commonsense reasoning.

Another way to state this is that getting OT’shands on itssetof beliefs is not trivial, if this is to bedone in a way that makes OT’sterm for that set correspond effectively to the elements (and no others) ofthat actual set.

—x)(Bel(x)→True(x)), when coupled(An interesting counterpoint is that thenegationofIS,namely,(\\/

with a relatively uncontroversial rule of inference -- from x infer Bel(x) (i.e., OTmay infer that it believesx, if it has already inferred x) -- oftendoesproduce inconsistency! Essentially,ifTisasuitable first-ordertheory subsuming the mentioned rule, thenISis atheoremof T,quite the opposite of contradicting T.SeePerlis [1986] for details on this and related results.)

Nevertheless, we shall presently see that Israel’sargument can be revised in such a way as to bearsignificantly on formalisms for default reasoning.In order to address this, we return nowtoour analysis ofdefault reasoning.

V.Default reasoning and commonsense

The current breed of formal default reasoning tends to ignore the eventuality of errors cropping up inthe course of reasoning, attention having focussed more on the semantics of getting the right initial defaultconclusion. But it is clear that if this can be done, then a mechanism is required to ‘‘undo’’such a conclu-sion in the light of further evidence, as our example with Tweety indicates. Indeed, to denyinformationabout errors to OTamounts to allowing OTthe following kind of clumsy reasoning hardly suitable for an

ideal reasoner:

Tweety is a bird; so (perhaps in Reiter’sorMcCarthy’sversion) Tweety can fly.Why doIthinkTweety can fly? I do not know. But Tweety turns out to be an Ostrich, so Tweety can’tfly. Did Isay Tweety could fly? I do not knowwhy I said that. Do I think anybird can fly unless knownotherwise? No, I do not think that.

While this may contain no inconsistency, italso seems not to be a very impressive instance of common-sense. Weare not here trying to pokefun at proposals in the literature, but rather simply to illustrate howfarindeed theyare from the ideal of commonsense that apparently motivates their study.This will not benews, but it is nonetheless worthwhile to drawthe boundaries in order to see where to go next. Aslightlymore commonsensical version is as follows:

Tweety is a bird; so (because I do not knowotherwise, perhaps in McDermott and Doyle’sver-sion) Tweety can fly: Bird(x) & ¬Known(¬Flies(x)) .→

Flies(x), and also

¬Known(¬Flies(Tweety)); but Tweety is an Ostrich, so Tweety can’tfly. Did I say Tweetycould fly?Idonot knowwhy I said that, for I believe birds fly if I do not knowotherwise, butin Tweety’scase I knowotherwise. Did I say ¬Known(¬Flies(Tweety))? I wonder why, for it’snot true.

Or,astill smarter version, one that appears to deal with errors appropriately,and keeps track of its reason-ing overtime:

Tweety is a bird; so (I may as well assume) Tweety can fly; but Tweety is an Ostrich and socannot fly after all; my belief that Tweety could fly was false, and arose from my acceptance ofaplausible hypothesis. Do all birds that may fly (as far as I know) in fact fly? No, that’sjust aconvenient rule of thumb.

Note that here too a contradiction (between past and present) arises, but out of an explicit recognitionthat the default rule leads to other beliefs some of which are false. Which are the ‘‘real’’facts? OTmust be

able to stand back from (some of) its beliefs in order to question their relative accuracy, temporarily sus-pending judgement on certain matters so theycan be assessed, without thereby giving up other beliefs (suchas general rules of reason) which may be needed to assess the ones in question.

Nowthe above scenarios strongly suggest that for OTtobecapable of appropriate commonsense rea-soning, it must be able to reflect on its past errors, indeed, on its potential future errors. This observationwill form the basis of our next section, in which we consider ‘‘Socratic’’reasoners, i.e., ones that knowsomething of their own limitations, and in particular the fallibility of their use of defaults.

VI.Israel’sargument revisited

There is a way to makeIsrael’sargument good after all, by reformulatingISinto a version, sayIS’, tomakeitrefer to a particular proscribed set, indeed a finite one that can be listed. It is not essential at all forIS’torefer to all beliefs of OT, nor eventoitself. It is sufficient thatIS’refer to a finite set S of beliefs ofOT that OTcan explicitly conjoin into a single formula; this will then produce a contradiction if OThas thefull deductive power of logic and ifIS’isabelief of OTthat states that at least one of the elements of S isfalse. Now, what reason can be givenfor OThaving such a belief asIS’? Indeed, whywould an intelligentreasoner such as OTconcede that some subset S of its beliefs holds an error; indeed, not justsomesubset,and not just a finite one, but one that can be explicitly divulged?

Our answer to this is that it is precisely default reasoning, i.e., reasoning by guess, or uncertainty,orjumps that makes such a concession inevitable. For OT, tobetruly intelligent, must realize that its defaultbeliefs are just that: error-prone, and therefore at times just plain wrong. Indeed, the very necessity of mak-ing fixes blatantly exposes the error-prone quality of default reasoning.Nowwecan get an explicit formalcontradiction, for we can argue thatIS’will reasonably be believedbyOT. All OTneeds is a handle on itsownpast, e.g., that it has judged manyinstances of a default to be positive (such as 1000 birds to fly).

Forthe purpose of the following definitions, we consider OTtobea‘‘reasoning system,’’ i.e., someversion of a formal theory (actually,asequence of such theories) that varies overtime as it interacts withnewinformation. Thus in our earlier example, at the point at which it is learned that Tweety is an ostrich,the reasoning system is considered to have evolved into another formal state. However, aswill be seen

below, time and the elements of defaults (oracles, jumps, and fixes) serveonly a motivational role, notneeded for the formal treatment. Wework then within an appropriate first-order theory,supplemented withnames for wffs to allowquotation and unquotation as in [Perlis 1985].

Definition:Areasoning system OTisquandaried(at a giventime) if it has an axiom (belief) that says notall of an explicitly specified finite set of its beliefs are true.

Theorem1: No quandaried reasoner can be consistent.

Proof:Let OTbeaquandaried reasoner,for which the explicitly specified set of beliefs is{B1,...,Bn}, and having in addition the axiom (belief) ¬(B1&... &Bn). The result followsimmediately.

Nowwhile Theorem 1 may seem trivial, it does hold an interesting lesson.Forany reasoner that hasperfect recall of its past reasoning will be able to explicitly specify its past default conclusions, and in par-ticular those that have not been revoked(fixed). If it then also believesongeneral principles that one ormore ofthesebeliefs is false, it will be quandaried and hence inconsistent.This we presently codify in fur-ther definitions and a theorem. Note howeverthat Theorem 1 does not necessarily spell despair for quan-daried reasoners. For the spirit of the Tweety example that has motivated much of our discussion is pre-cisely that of an inconsistencygiving rise to a fix that restores consistency. That is, it is to be expected thatOT may fluctuate between quandaried and non-quandaried states, as it finds and corrects its errors.

Definition:OTisrecollectiveif at anytime t it contains the belief

—/x)(Dflt(x)←(\\ →x=b1v...v x=bn)

whereb1,...,bnare (names of) all the beliefsB1,...,Bnderivedbydefault prior to t (i.e.,bi=‘‘Bi’’), and iffor each i either OTretains the beliefBias well as Bel(bi), or elseBihas been revoked(e.g., by a fix) andthen it contains the belief ¬Bel(bi).

—x)(Dflt(x) & Bel(x) & False(x)) as well as the beliefsDefinition:OTisSocraticif it has the belief (——

False(‘‘α’’)→¬αfor all wffsα.

Theorem2: No recollective Socratic reasoner can be consistent.

Proof:Any such reasoner OTwill be quandaried and so by Theorem 1 will be inconsistent. Tosee that OTwill indeed be quandaried, simply observethat in being Socratic and recollective,OT will believe

—

—x)((x=b1v...v x=bn)&Bel(x) & False(x)).(i) (—

But also (in being recollective)OTwill believe either

(ii)

or

Bi&Bel(bi)

(iii) ¬Bel(bi)

for eachbi.Now consider thosebisuch that Bel(bi)isbelieved(i.e., is a theorem of OT), say,bi1,...,bik.Since OTbelieves¬Bel(bi)for theotherbeliefs amongb1,...,bn,then by (i) OTbelievesone ofbi1,...,bikto be false, yet each is believed; so OTisquandaried. [It is also nothard to form a direct contradiction without exploiting the notion of a quandary; we have pur-sued this route simply to illustrate the application of Israel’s(modified) argument.]

As an example, OTmay believe a rule such as that ‘‘typically birds can fly’’, and operationalize itwith a (second) rule such as thatgivenBird(x) and if Flies(x) is consistent with OT´s beliefs, then Flies(x)is true. But OTwill also believe (since it is smart enough to knowwhat defaults are about) that this veryprocedure is error-prone, and sometimes Flies(x) will be consistent with its beliefs and yet be false. Indeed,it will reasonably believe that one of itspast(and yet still believed) default conclusions is such an excep-tion, and these it can enumerate (suppose it has reasoned about 1000 birds) and yet it will also believe ofeach of them that it is true! So OTisinconsistent. Of course, the very realization of the clash (which OTalso should be capable of noticing) should generate a fix which calls the separate default conclusions into

question, perhaps to be relegated again to their more accurate status of tentativity.Wewill see in the nextsection howthese results relate to the standard default formalisms in the literature.

It is necessary here to address a possible objection: that OTwill not be able to enumerate its pastdefaults, and so will refer to them only generically,defusing the contradiction as we did with Israel’sorigi-nal argument. However, itisnot at all unreasonable to suppose that OTkeeps a list of its defaults, especiallyin certain settings. For instance, if OTworks as a zookeeper,and keeps a written record of the animalsthere, 1000 North American (i.e., ‘‘flying’’) birds may have been recorded by OTasingood health (and soable to fly), and OTmay continue to defend these judgements evenwhile granting that some of them will be errors. More will be said on this in the following section. (Readers may recognize this as a version of theParadoxes of the Preface or of the Lottery14.See [Stalnaker 1984].)

VII.Analysis of three formalisms

We are nowinaposition to present rather striking examples of the situation that has been dealt within the earlier sections. Namely,wewill showthat major weakenings occur when the standard ‘‘epistemo-logical adequacy’’approaches to commonsense reasoning are combined with a recollectiveorSocratictreatment of use-beliefs. Wewill examine McCarthy’sCircumscription (CL), McDermott and Doyle’sNon-Monotonic Logic (NML), and Reiter’sDefault Logic (DL).Recall (Theorem 2) that anySocraticandrecollective default reasoner is inconsistent. This of course applies as well to CL, NML, and DL; that is, ifanyofthese is endowed with Socratic and recollective powers, it will become inconsistent. This already isunfortunate, in that it seems to suggest that quite a different sort of formalism will be required to handledefaults ‘‘realistically’’. But evenmore damaging observations can be made, namely,relaxing in variousways the Socratic and recollective hypotheses still produces undesired results in these formalisms.

We begin by reviewing the extent to which our three default ‘‘keys’’(oracles, jumps, and fixes) comeinto these treatments. The case of circumscription, or CL, is slightly complicated by the fact that the

McDermott [1982] mentions this paradox as one giving trouble for monotonic logics; here we see that it is also problematicfor non-monotonic logics.)

14

predicate ‘‘Unknown’’(that is, Unknown(¬Flies(x)) in our example), is not explicit, and indeed, CL doesnot quite test fully for whether Flies(x) is already entailed by the givenaxioms, but rather uses a substitute(known as the method of inner models). This has the advantage of being semi-decidable (i.e., the oracle isactually represented somewhat algorithmically,inthe form of a second-order axiom schema), though it hasthe disadvantage of being incomplete (see Davis [1980] and Perlis-Minker [1986]).Thus steps 1a, 1b, and1c are implicit in CL, whereas in NML and DL step 1a is implicit (with an ineffective oracle used to supplyfull consistencyinformation for Unknown) and steps 1b and 1c are combined into a single step (an axiomof NML and an inference rule of DL) stating directly (in the case of our example) that if Tweety is a birdand it is consistent to assume Tweety flies, then Tweety does fly.Inother respects, however, the threeapproaches are much the same.Steps 4a, 4b, and 4c are simply not present in anyform in anyofthem,since once Ostrich(Tweety) is added as a newaxiom, the previous axiomatization is no longer under con-sideration and it and its conclusions (e.g., Flies(Tweety)) are ignored.

It is clear then that in order to address the issues urged here, these approaches must be supplemented,and in particular with ‘‘histories’’oftheir conclusions. More generally,far greater explicitness of worldknowledge and of their own processes is required. But we have seen that when such information is allowedin a default reasoner,ithas a high chance of becoming inconsistent. In particular,ifitcan represent the factthat it is using default rules, and that some of its default conclusions will therefore be erroneous, and if itcan recall its default conclusions, then it is recollective and Socratic and so falls preytoTheorem 2, andwill be inconsistent. However, the particular features of CL, NML, and DL are such that simpler meansexist to derive implausible conclusions within an intuitively commonsense framework. Thisis most easilyillustrated in the case of NML, for of the three formalisms mentioned already it alone has enough apparatuspresent to express the required concept of default fallibility directly.15

And this is its downfall regarding our present discussion. In effect, NML makes an axiom out of DL’s rule. ThusDL’s ability

to refuse to believe the rule as a truth, is not available to NML. Of course, this is indulging in an introspectivist fantasy,for neither for-malism represents reasons for its conclusions. But this fantasy does I think accurately pinpoint the critical distinction that allows DL tosurvive the threat of inconsistencyinthe present example.

15

In NML, the Tweety example might be handled as follows: we could specify the axiom

—/x)((Bird(x) & MFlies(x))→Flies(x))(\\

where M is a modal operator interpreted as meaning that the wfffollowing it is consistent with the axiomsof the formalism itself. Since this involves an apparent circularity,McDermott and Doyle go to somelengths to specify a semantics for M. However, for our purposes, it is not essential to followthem in suchdetails; we can form a ‘‘Socratic’’version ofIS’easily for this case:

—x)(Bird(x) & MFlies(x) & ¬Flies(x))(——

This at least partly expresses that for some bird, NML has the needed hypotheses to infer by default that thebird flies, and yet it will not fly.One could hardly ask for a more direct statement of the fallibility ofdefaults. Yet nowNML is in trouble: it will immediately find the following direct contradiction:

—x)(Flies(x) & ¬Flies(x)).(——

Note that we do not here need the recollective hypothesis: a Socratic16extension of NML is already incon-sistent. (Nutter [1982] and Moore [1983] have pointed out that the formalization of NML seems to commitan error of representation vis-a-vis intuitive semantics, and it is this in effect that we are exploiting here.)

Even though, as we have seen above,inNML it is possible to express a Socratic-type axiom thatsomedefaultconclusion has gone awry,thereby producing inconsistency, one can makeaneven(appar-ently) weaker assumption and still achieve distressing results.In all three formalisms, a simple additional‘‘counterexample’’axiom seems to underminethe ability of the reasoning system to makeappropriatedefault conclusions consistently,surrendering the full Socratic condition but (for DL and NML) employingthe recollective condition.

Forinstance, giventhe axiom

—x)(Bird(x) & ¬Flies(x) & x=b1v... v x=b1000)(——

Reiter’sDL‘‘sanctions’’the conclusion Flies(bi)for each birdbiseparately.Now a problem arises: howarewe to interpret these sanctions?Reiter apparently intends that anywffsentailed byalldefault extensions

We use the term ‘‘Socratic’’somewhat loosely here, since it is not precisely the same as the formal definition givenearlier.

However, intuitively it still expresses the idea of self-error.

16

are to be treated as default conclusions, and that othersmaybe so treated if we are careful not to mix suchfrom distinct extensions. In anycase, we are stuck, because we need the zookeeper to makeasequence ofsuch conclusions that donotfall into anyone extension. Thatis, DL augmented by sufficient axioms tospecify all the (finitely many) birds in the zoo, might conclude of each one by one that (it is ‘‘ok’’tosup-pose that) it flies, up until the last one, and since it also has the belief that one of them does not then it willbe forced to conclude of the last thatitis the culprit that does not fly.SoDL, so construed, is preytothe‘‘Paradox of the Zookeeper’’inthat, although avoiding inconsistency, it’sability to derive the intuitivedefault conclusions is compromised.17The same arguments apply to NML and counter-example axioms.Alternatively,ifthe time-sequence is finessed, these formal specifications of default reasoning can beviewed as producing the conclusion that precisely one bird of the 1000 does not fly,without committingthem, selves to evenasingle default conclusion about anyindividual bird. This howeveramounts to avoid-ing drawing anyatomic defaults, largely defeating the prime motivation for such reasoning18.This willarise evenmore dramatically when we examine CL below.

Here our earlier treatment of use-beliefs comes in handy.For we can argue that the zookeeper‘‘really’’believesofeach separate bird at the zoo that it can fly,inthat he is highly unwilling to leave anyof their cage doors open, and is also unwilling to call anyone of them to the attention of the zoo veterinar-ian. Yet, he is also very concerned at the veterinarian’sfailure to arrive for work at the usual hour,becausethe zookeeper also believesthatsome(unspecified) birds in the zooareill (and unable to fly).

There is an intuitive appeal to this, in that a zookeeper might very well defend each separate conclu-sion of the form Flies(bi), and yet not agree to the statement that all the birds fly.Indeed, the zookeeper hasuse-beliefsFlies(bi)for each i, as well as the use-belief

That is, the zookeeper concludes ofnobird that it does not fly: only the existence of such is believed. I grant that, in order to

get DL, NML, and CL to takethe job of zookeeper,Iamstretching them in unintended ways and making arbitrary choices in the pro-cess. But that is the point: we must devise formalisms that do lend themselves to introspection, and when we do, there will be difficul-ties of the sorts described here.

It also seems related to Reiter’ssuggestion that DL has a representation of the notion of ‘‘few’’or‘‘many’’. However, the ac-tual inferences sanctioned by DL (or by NML or CL, for that matter) seem to miss much of the import of these terms, in that a strictminimum is determined. E.g., that most birds fly,when represented as a default, leads to the conclusion thatallbirds fly if no coun-terexamples are known, and thatall butknown counterexamples fly in other cases. But there is an intended indefiniteness in the words‘‘few’’and ‘‘many’’. See our discussion of CL below.

1817

—x)(¬Flies(x) & x=b1v... v x=b1000).(—

—

Forconsider his concern when the zoo bird-veterinarian fails to arrive for work on schedule, and his simul-taneous unwillingness to leave open anyofthe birdcage doors.The problem is that whereas the zookeepermay refuse to apply an inference rule to form the conjunction of givenbeliefs (recognizing, in effect, thatthere is a contradiction afoot and that his beliefs are tentative), DL and NML are formal extensions of first-order logic and will have such conjunctions as theorems, with no means to control the usual disastrous con-sequences of this in logically closed formalisms. That is, zookeepers and others commonsensical beings areperhaps not obedient to slavish rules of formal logic regarding their use-beliefs.19

One might seek to alter the logic as a way around this, for instance by not allowing arbitrary conjunc-tions of theorems. Such alternativeshav ebeen raised in connection with the Lottery and Preface Paradoxes(see [Stalnaker 1984]).However, this does not affect our conclusion that the beliefs of anyagent fully inthe zookeeper’sshoes would in fact be mutually (but not directly) contradictory,whether or not there aremechanisms in place to keep the contradiction from being deduced. Moreover, anintelligent agent shouldbe able to recognize the contradiction, and conclude, perhaps, that its conclusions of the form Flies(x) wereafter all only tentative (that is, undo the ‘‘jump’’). For this, a record must be kept of the origin of conclu-sions, a point utilized in [Doyle 1979] and emphasized in [Nutter 1983a].

It is worth contrasting the zookeeper scenario with another,the ‘‘detective’’ scenario. Here there are,say,10suspects in a murder case, each of whom has an alibi and is apparently a very nice person.Yetinstead of concluding separately of each that he or she is (tentatively) innocent, our detective instead tenta-tively suspects each (separately) of being guilty.But if there were 1000 or more suspects (e.g., if relativelylittle at all existed in the form of clues, so thatanyonemay have been the murderer), then it is no longerreasonable to tentatively treat each individual as guilty.That is, in the case of 10 suspects, it may be life-preserving to be wary of all 10, but in the case of 1000, it surely is counter-productive.This seems to say

We might say the zookeeper isquasi-consistent(andquasi-inconsistent): his belief set Bentailsacontradiction X&¬X, but

does notcontainone directly (X and ¬X are not both elements of B). It follows that such an agent cannot be logically omniscient, butin a way that is no weakness at all: the entailed contradiction need not bemissedout of logical ignorance, but rather can be deliberate-ly rejectedon the basisof having been duly (and logically) noted and judged impossible and attributed to an error.

19

that rawnumbers do (should) affect the course of default reasoning, a matter we will not pursue furtherhere.

The case of CL is still more interesting.Here, the defaults are not as explicitly represented as inNML (or evenDL)20.So, following the cue of our additional axiom above,wesay simply that there is abird that does not fly,aswell as circumscribing non-flying birds. Thus

—

—x)(Bird(x) & ¬Flies(x))}{Bird(Tweety), (—

when circumscribed with respect to ¬Flies (letting Flies be a ‘‘variable’’circumscriptive predicate), insteadof providing the expected and usual (when the second axiom is not present) conclusion that Tweety flies,allows us no conclusion at all about Tweety not already contained in the axioms before circumscribing.21That is, from Bird(Tweety)alonecircumscription of ¬Flies produces Flies(Tweety), as desired. Yet with theadditional axiom present, this no longer is the case.This is easily seen, for the above axiom set has a mini-mal model in which Tweety is precisely the claimed exceptional bird. Here we do not evenneed the recol-lective condition.

We wish to regard Tweety as a typical bird, since nothing else is known explicitly about Tweety;however, the additional axiom raises the possibility that Tweety may not fly,i.e., Tweety may be the intran-sigent non-flying bird that is asserted to exist. The result is thatnobirds will be shown (evententatively) tofly by circumscribing in such a context. Clearly this is not what we wish of a default reasoner.Interms ofour analysis of default reasoning, CL does not perform step 1a; the circumscriptive schema (oracle), whenfaced with a weak-Socratic axiom, no longer recognizes the ‘‘typical’’case. Theresult claimed above isformalized below.

Althoughformulacircumscription does provide at least part of a mechanism for expressing within the logic the fact of self-error,and if this is teased out by means of suitable metalogical devices then in close analogy with the following treatment common-sense is compromised.

That is, about Tweety in isolation. As seen above with NML and DL, shotgun results about the whole set of birds may be

derivable, such as that there is only one non-flying bird, but no conclusion specific to anyparticular bird follows. Indeed, the easilyprovedcircumscriptive result that there is only one bird that does not fly (also derivable in NML and DL when interpreted as in ourearlier discussion in the recollective case for zoo birds) runs counter to intuition: the existence of a non-flying bird suggests ‘‘few’’, not‘‘only one’’. It would be much more satisfactory if there were a way to remain non-committal on the exact number.

2120

Theorem3: The set

—x)(P(x) & ¬Q(x))}T={P(c), (—

—

when circumscribed with respect to ¬Q, does not have Q(c) as theorem, eveninformula cir-cumscription with P and Q allowed as variable predicates.

Proof:Bythe soundness theorem for circumscription (see [McCarthy80, Etherington 84,Perlis-Minker 86]) if Q(c) were a theorem of Circum(T,¬Q), then Q(c) would hold in all mini-mal models of T (with respect to ¬Q). But this is not so: there are minimal models of T inwhich ¬Q(c) holds, namely ones in which c is the only P-entity that is not a Q-entity.(Intu-itively,c=Tweety is the only bird (P) that does not fly (Q).)

One might try to ‘‘disconnect’’Tweety from the existentially asserted non-flying bird, for instance bySkolemizing the additional axiom as

Bird(c) & ¬Flies(c).

However, this will not work either: we still cannot prove Flies(Tweety) by circumscription, unless we adoptthe further axiom that Tweety≠c. Butto do this amounts to begging the question, i.e., to assuming wealready know(before we circumscribe) that Tweety is not to be exceptional in regard to flying.Moreover,we can then simply consider the wff¬Flies(x) & x≠cinstead, and assert (reasonably) that some bird satis-fiesthis.For if c were the only non-flying bird, then we would not need defaults in the first place. Thewhole point is that evenamong those birds which seem typical as far as we can tell, still there lurk excep-tions.

This can be seen in a more dramatic form by postulating thatb1,...,bnareallthe birds in the world(where n is some large known integer,say 100 billion, and distinctbi’s may or may not represent distinct

—x)(Bird(x) & ¬Flies(x)) cannot be Skolemized with a constant that is alsobirds). Then the axiom (—

—

assumed to have a distinct reference from everybi.Note that this is similar to Reiter’sunique nameshypothesis [1980a] that likewise is not handled directly by circumscription. Wesuggest that a solution to

one of these problems may harbor a solution to the other.Note however, that evenifnames are introducedinto CL in such a way that one can circumscriptively prove ¬Flies(Tweety) (i.e., so that jumps are rein-stated), then CL immediately falls preytoinconsistencyifitisalso recollective.(See [Etherington-Mercer-Reiter 1985] for the crucial role of existential quantifiers in circumscriptive consistency.)

What we have found, then, regarding ‘‘realistic’’default reasoning and three standard formalisms inthe literature, can be represented in the following table:

formalismhypotheses

MXCL MYDLMZNML

Socratic .spRecollective

.sp Socratic-.br Recollective

CtrExample .spCtrExample- .brRecollective

Here ‘‘compromised’’means that the formalism in question will not produce the intuitively correctcommonsense default conclusions, and ‘‘--’’means that no apparent difficulties arise. So we see that anyofthe three formalisms can be made recollective without upsetting the intended usage.On the other hand, theSocratic or Counter-example conditions, which are what express thetentativity(i.e., the default-hood) ofdefaults, tend to spell trouble. It is of interest that Reiter’sversion, DL, comes out ‘‘best’’ofthe three: itsuffers the least affront to its default integrity as a specification for an omnithinker.

Finally,innocase can the ‘‘ideal’’ofaSocratic recollective default reasoner be achievedwithin theframework of the epistemological adequacyapproach, since that approach is based on the assumption of aconsistent, logically closed axiomatization. This is of course relative toour definition of use-beliefs; that is,the inconsistencymay lie hidden inside tentativity predicates, as Nutter [1983b] urges. But the three for-malisms discussed in this section all employjumps, i.e., theybaldly assert their default conclusions, andtherefore the implicit use-belief inconsistencythat will arise when theyare endowed with Socratic-recollective features will become an explicit logical inconsistency.

VIII.Conclusions

We need formalisms adequate to the task of capturing ‘‘introspective’’ default reasoning. This isessential to performing certain kinds of fixes. Furthermore,the latter often cannot be done at all withoutsacrificing consistencyinfavorofakind of quasi-consistency.

The thrust of our remarks has been that desiderata underlying commonsense reasoning simply areinconsistent, and that we nowmust devise and study systems having such characteristics.Specifically,the‘‘jump’’phenomenon, so central to most work on default reasoning (and, notably,attacked by Nutter[1982]), will not withstand simultaneous admission of fallibility implicit in a ‘‘fix’’. Onthe other hand,dealing with inconsistent formalisms seems to force us toward deeper analysis of processes of memory,inference, and focus overtime. Theseare the topics of work in progress [Drapkin-Miller-Perlis 1986] and[Drapkin-Perlis 1986].Nutter [1983b] prefers to avoid jumps and seek other means of utilizing defaultconclusions, such as relevance logic.The extent to which the term ‘‘logic’’isappropriate at all for such anundertaking is also a matter of debate; see [Doyle 1983, 1985] and Harman [1986].It will be interesting tosee whether anyofthese approaches bear fruit.

ACKNOWLEDGEMENT

Iwish to thank James Allen, Jennifer Drapkin, Jerry Feldman, Rosalie Hall, Jim Hendler,Hector Levesque,Vladimir Lifschitz, Ron Loui, Michael Miller,Jack Minker,Dana Nau, Rich Pelavin, Jim des Rivieres,John Schlipf, and Jay Weber for useful discussion on the topic of this paper.Special thanks to Pat Hayesand Ray Reiter,who challenged me to write down and clarify my spoken claims.

This research has been supported in part by the following institutions:

The U.S. Army Research Office (DAAG29-85-K-0177)

The Martin Marietta Corporation.

REFERENCES

Davis, M. [1980] The mathematics of non-monotonic reasoning. AIJ 13(1,2) 73-80.Dennett, D. [1978]Brainstorms.300-309. Bradford Books, Montgomery,VT.Doyle, J. [1979] A truth maintenance system. AIJ 12(13) 41-72.Doyle, J. [1983] A society of mind. IJCAI-83 309-313.

Doyle, J. [1985] Reasoned assumptions and Pareto optimality.IJCAI-85 87-90.

Drapkin, J., Miller,M., and Perlis, D. [1986] A memory model for real-time default reasoning. Technicalreport, University of Maryland.

Drapkin, J. and Perlis, D. [1986] Step-logics: an alternative approach to limited reasoning. ECAI-86,Brighton, UK.

Etherington, D. [1984] Week on logic and AI, Univ. ofMaryland. Personal communication

Etherington, D., Mercer,R., and Reiter,R.[1985] On the adequacyofpredicate circumscription for closed-world reasoning. Computational Intelligence 1,1, pp.11-15Harman, G. [1973]Thought.Princeton University Press.Harman, G. [1986]ChangeinView.MIT Press.

Israel, D. [1980] What’swrong with non-monotonic logic? AAAI-80 99-101.Konolige, K. [1984] Belief and incompleteness. SRI Tech Note 319.Levesque, H. [1985] Computers and Thought Lecture, IJCAI-85.

McCarthy, J.[1980] Circumscription--a form of non-monotonic reasoning.AIJ 13(1,2) 27-39.

McCarthy, J.[1986] Applications of circumscription to formalizing common-sense knowledge. AIJ 28(1)-116.

McDermott, D. [1982] Non-monotonic logic II. JACM29(1) 33-57.

McDermott, J. and Doyle, J. [1980] Non-monotonic logic I. AIJ 13(1,2) 41-72.Moore, R. [1977] Reasoning about knowledge and action. IJCAI-77 223-227.

Moore, R. [1983] Semantical considerations on non-monotonic logic.IJCAI-83 272-279.Newell, A. [1981]The knowledge level. AI Magazine 2 1-20.

Nutter,J.T.[1982] Defaults revisited, or ‘‘Tell me if you’re guessing’’. Proceedings, Fourth Conference ofthe Cognitive Science Society,67-69.

Nutter,J.T.[1983a] What else is wrong with non-monotonic logic?Proceedings, Fifth Conference of theCognitive Science Society,

Nutter,J.T.[1983b] Default reasoning using monotonic logic: a modest proposal. AAAI-83, 297-300.Perlis, D. [1981] Language, computation, and reality.Ph.D. Thesis, Univ. ofRochester.Perlis, D. [1985] Languages with self-reference I: foundations. AIJ 25(3) 301-322.

Perlis, D. [1986] Languages with self-reference II: knowledge, belief, and modality.Technical report, Uni-versity of Maryland.

Perlis, D. and Minker,J.[1986] Completeness results for circumscription. AIJ 28(1) 29-42.Reiter,R.[1980] A logic for default reasoning. AIJ 13(1,2) 81-132.

Reiter,R.and Criscuolo, G. [1983] Some representational issues in default reasoning.Int. J.ofComputersand Mathematics (Special issue on computational linguistics)9(1), 15-27.Stalnaker,R.[1984]Inquiry.pp. 90-92. MIT Press.