Inaccessible Worlds and Irrelevance: Preliminary Report

1 Introduction

Recently, the focus of much research on default reasoning has centered on the representation of default rules as con­ ditional sentences in various conditional logics. While the motivation and underlying semantics for these logics often diverge, most allow "In the most normal situations in which A is true, B is true" as a profitable interpreta­ tion of the conditional A- B . Each of these logics can be viewed as enforcing some type of normality ordering on states of affairs, or possible worlds. For instance, the logic of £~semantics (Adams 1975; Pearl 1988) is based on a probability distributions over sets of worlds, and a conditional A - B is true iff B is true at the most prob­ able (as£ approaches 0) A-worlds; hence, more probable worlds can be viewed as more normal under such an or­ dering. The preferential logics of (Kraus, Lehmann and Magidor 1990) embody an explicit normality ordering on situations, and the conditional logics of (Boutilier 1990) are similar, incorporating normality as a modal accessi­ bility relation.

Given that these logics can be regarded in such a similar fashion, it is not surprising that they have been shown to be essentially equivalent (Boutilier 1990; Kraus, Lehmann and Magidor 1990), giving credence to their underlying motivation. Unfortunately, while each can be considered a "core" for default reasoning (Pearl 1989), they are too weak to sanction all of the patterns of default inference we would like. In particular, the con­ clusions authorized by such systems are often rendered invalid in the face of irrelevant information. For exam­ ple, given that birds fly (B - F) we cannot conclude that green birds fly (GAB- F).

To circumvent such difficulties, many schemes have been proposed which augment the logics under consid­ eration with extra-logical machinery for deriving the ap­ propriate conclusions (Delgrande 1988; Lehmann 1989; Pearl 1990; Goldszmidt, Morris and Pearl 1990) . Gold­ szmidt and Pearl (1990) have shown that Pearl's !­ entailment corresponds to Lehmann's rational closure, demonstrating that these reasonable extensions (as well as the logical cores) of £-semantics and preferential logics determine the same default conclusions.

We can view these logics as being able to express what is true at "more normal" possible worlds; hence, sen­ tences can force worlds (which don't satisfy these con­ straints) to be less normal. The meta-logical extensions of these systems, conversely, attempt to force worlds to be more normal than is required. In this paper, we will show that the conditional logics of (Boutilier 1990) can also be extended in a manner which corresponds exactly to these systems. This extension is based on a sim­ ple preference relation over modal structures, one that prefers structures in which possible. worlds are as nor­ mal as possible. Furthermore, we extend the logic itself such that we can make reference to inaccessible worlds in addition to accessible worlds; thus we can express truth at less normal worlds and force worlds to be more nor­ mal. With this capability, we can axiomatize a default theory making the derivable conclusions exactly those sanctioned by the preferential semantics. Just as the second-order circumscription axiom conforms to truth in (predicate) minimal models (McCarthy 1986), so too does this closure correspond to preferred models. We suggest that, to the extent any meta-logical default sys­ tem forces worlds to be more normal, it can be axioma­ tized within this extended conditional logic.

A more detailed presentation and proofs may be found in (Boutilier 199lc).

2 Inaccessible Worlds and the Logic CO

As in (Boutilier 1990), we will present a Kripke-style pos­ sible worlds semantics for a conditional logic capable of representing and reasoning with statements of normal­ ity or prototypicality. A sentence A ~ B is intended to mean "A normally implies B". Following a suggestion of Delgrande (1988), we will interpret the truth conditions for such a statement roughly as "In the most normal situ­ ations in which A holds, B is true as well". The ordering of normality presupposed by such a reading will be rep­ resented as an accessibility relation on possible worlds; world v is accessible tow ( wRv) iff v is at least as normal as w. In (Boutilier 1990), it is argued that such a relation should be, at a minimum, reflexive and transitive, and that a further restriction of total-connectedness 1 gives rise to a reasonable extension, namely the logic CT4D. It is also shown that CT4D is equivalent to the standard modal logic S4.3, in the sense that the conditional con­ nective ~ can be defined in terms of the modal operator o, and vice versa. In the sequel, we will take the modal connective to be basic and define the conditional within the modal language.

In (Boutilier 1990) it is shown that CT4D captures many of the properties we expect of normal implica­ tion, such as allowing exceptions to prototypical state­ ments, and capturing rules such as cautious and rational monotony. It is also shown that (a fragment of) CT4D is equivalent to the logic of ranked preferential models of (Lehmann 1989).

The following approach to default reasoning using CT4D immediately presents itself. Let K B be (the conjunction of) a finite knowledge base of sentences of CT4D. It is reasonable to ask what is true at the most normal worlds in which all the facts in K B hold; that is a default reasoner could conclude a whenever l-cT4D KB ~a (see also Delgrande's (1988) Assump­ tion of Normality). However, a serious problem arises when we consider certain classes of default inferences, specifically those involving irrelevant properties. If K B consists of two facts, Bird and Bird ~ Fly, then KB ~ Fly is derivable. However, if we add Green to KB, then KB ~ Fly is no longer a theorem, for the most normal Green A Bird-worlds need not satisfy Fly, as long as these are not among the most normal Bird-worlds. In other words, greenness may be an ex­ ceptional property of birds (with respect to flying), as "penguinness" is.

The problem of irrelevance has been addressed using a number of extra-logical techniques, such as rational clo­ sure, assumptions of irrelevance (Delgrande 1988), and !-entailment. We will approach the problem from a per­ spective which may in the future lead to a purely logical account of default inference, and, at present, provides some new insights into irrelevance.

Consider some normality ordering on all possible states of affairs, W, and refer to the most normal Aworlds in this ordering as n(A) . Then A ~ Cis true iff n(A) ~ IICII. 2 Of course, A must hold at all such worlds, so we can write this as n(A) ~ JJA A Cll . Now, to say that B is irrelevant to the truth of this conditional is to say (roughly) that A A B ~ C is true. For this to ?e the case it is sufficient to insist that some B-world exist among those in n(A), making this a most normal A A B­ world. In general, we want this to be true for arbitrary properties a (consistent with AAC), so that AAa ~ C holds. Hence, we need only insist that IIA A Cll ~ n(A). Together with the converse, this implies that A A a ~ C for any such a. In other words, we would like to assume, if we know A~ C, that the most normal A-worlds are exactly all A A C-worlds.

1 R is total-connected iff vRw or wRv for all v, w. In (Boutilier 1990) we use forward-connectedness, but this stronger condition results in an equivalent logic (Hughes and Cresswell 1984), and the distinction is important later.

These constraints are analogous to those used by Levesque (1990) to define the semantics of OL, the logic of "only knowing". In an entirely similar fashion, A ~ C can be read as "at the most normal A-worlds, at least A A C is known" . 3 Supposing a new connective >, we say A > Cis true iff IIA A CJI ~ n(A). We can read this, then, as "at the most normal A-worlds, at most A A C is known". Together, A ~ C and A > C tell us that ex­ actly A A Cis known at the most normal A-worlds, and allow us to conclude that all (consistent) properties are irrelevant. This captures the intuition that if some fact (other than A) were relevant to concluding C we would know this to be the case. Since we "haven't been told", we assume nothing else should affect our deliberations.

In order to formalize this discussion, we will provide a semantics and axiomatization for the connectives ~ and >. As mentioned, we can define ~in terms of the standard modal operator 0. However, in a similar man­ ner we can define > in terms of a new modal connective 5. This connective corresponds to Levesque's N, and 5 a will hold exactly when a is true at all inaccessible worlds.

Our language L will be formed from a denumerable set P of propositional variables, together with the connectives -., ~. 0 and 5. The connectives A, V and = are defined in terms of these in the usual way.

Definition A CO-model is a triple M = {W, R, cp}, where W is a set (of possible worlds), R is a tran­ sitive totally-connected binary relation on W (the accessibility relation), and cp maps Pinto 2w (cp(A) is the set of worlds where A is true).

The truth of a formula a at win M is defined in the usual inductive manner, with the interesting cases being:

M l=w Oa iff for each v such that wRv, M Fv a.

M l=w 5 a iff for each v such that not w Rv, M l=v a.

2 Forinally, n(A) need not exist, but the technical details which follow will not depend on this. We use this notation only informally, to illustrate the ideas which follow. llall stands for the set of all possible worlds which satisfy a, and again, in our informal discussion, we take this to mean all logically possible worlds rather than those from the set W of some formal structure.

3 We use "known" here in a much less technical sense than Levesque. More accurately, we could say if n{A) were the only worlds an agent considered possible, then it would know at least A 1\ C.

We can define several new connectives as follows: <>a :=dr -,0-,a; 0 a :=dr ..., 0 -,a; 0 a :=dr DaA 0 a; and 0 a =dr <>av 0 a. It is easy to verify that these connectives have the following truth conditions: <>a (0 a) is true at some world if a holds at all accessi­ ble (inaccessible) worlds; 0 a (0 a) holds iff a holds at all (some) worlds, whether accessible or inaccessible. Va­ lidity is defined in a straightforward manner, a sentence a being CO-valid (f=co a) just when every CO-model M satisfies a. Finally, we define the connectives:

A ::} B will be true vacuously if there is no world in the model at which A holds. Otherwise, it is true iff there is some world where A holds, and B holds at all more normal A-worlds The dual of this is A > B which states that at most A A B is known at the most normal A-worlds. This is only true if A holds at some world (condition 0 A), otherwise there would exist no such worlds and everything would be trivially satisfied ("known") by this (empty) set. Furthermore, A > B can only hold if, at each A-world, A ::> ...,B is true at every inaccessible world (otherwise this world would be strictly more normal than some A A B-world); and if at each A-world, A A B is true at some more normal world (since such worlds are the most normal A-worlds, each A-world should "see" one). It is easy to verify that A > B holds iff all A A B-worlds are mutually accessible (equally normal) and no A-world is strictly more normal than these. In other words, by asserting that -,B holds at each inaccessible A-world, we force all A A B-worlds to be accessible to, or at least as normal as, every other A-world.

We call the logic associated with this semantics CT4D0, or CO for short, the extension of CT4D allowing con­ ditionalized "only knowing" . Completeness is proven us­ ing a technique of Humberstone (1983).

Definition The conditional logic CO is the smallest S ~ L such that S contains classical propositional logic and the following axiom schemata, and 1s closed under the following rules of inference:

K D(A ::> B) ::> (DA ::> DB)

K' 5 (A ::> B) ::> (D A ::>D B)

·This definition of A => B is different from that of (Boutilier 1990). It is more similar in spirit to the connec­ tive 1- of (Kraus, Lehmann and Magidor 1990}, whereby if A => B holds at any world in a model then it holds at all worlds. Previously, A => B could hold "vacuously" if there were no acceuible worlds at which A is true. While this is in accord with an epistemic reading of the relation R, it does not conform to our normative interpretation. It is eptirely unreasonable to expect only more normal worlds to deter­ mine which normative statements we take to be true. Worlds which are exceptional should also play a role in such deliber­ ations. One advantage of our approach is that the connective a allows us to define the truth conditions of::} at individual worlds, whereas the truth conditions of r- can only be defined with respect to entire structures.

T DA ::>A 4 DA ::> DDA 4' i5 A :>DO A S A ::>D <>A H 0 (DA/\ i5 B) ::>0 (A VB) Nes From A infer 0 A. MP From A ::> B and A infer B.

Theorem 1 The system CO is characterized by the class of CO-models.

That the connective ::}, as defined, captures a reason­ able notion of normal implication has been discussed in (Boutilier 1990). It should also be clear that the connec­ tive > captures the dual notion of (conditional) "know­ ing at most", and that together, A ::} B and A > B allow us to extend the conditional to include all irrele­ vant properties. Consider the following theorem of CO (for propositional A, B, and a):

This theorem states that if both A ::} B and A > B are true, then we can conclude that all properties a are irrelevant to the truth of the original conditional.

Notice that the extension of A::} B is conditional on the possibility of A ABA a . If we insist that all logically possible worlds be contained in W, then we can derive A 1\ a ::} B directly (provided A 1\ B 1\ a is logically con­ sistent) . Levesque (1990) enforces a similar constraint. This gives rise to the following extension of CO:

Definition CO* is the smallest extension of CO closed under all rules of CO and containing the following:

LP 0 a for all satisfiable propositional a. 5

Definition A CO*-model is any CO-model M =

(W, R, If'}, such that

{w·: wE W} 2 {!: f maps Pinto {0, 1}V

Theorem 2 The system CO* is characterized by the class of CO*-models.

The logic CO* addresses the difficulty of having to conditionalize extensions of normative conditionals on the possibility of the antecedent (since all consistent such antecedents are possible). Hence a theorem of CO* (for satisfiable AABAa) is (A::} BAA> B)::> (AAa::} B).

The notion of irrelevance sketched here is rather un­ dermotivated. While it's clear in examples such as the case of green birds that Green should be irrelevant to Fly, the question remains: what do we mean by irrele­ vance? Space limitations preclude anything resembling a reasonable discussion of this point, but a few words are in order. Gardenfors (1978) has presented and discussed a number of postulates which should be satisfied by any notion of relevance, motivated by the consideration that pis relevant tor (given evidence e), written p'Rer, iff the conditional probability of r given p 1\ e is different than that of r given e alone (i .e. P(rip 1\ e) -::f P(rle)). Pos­ tulates (RO) to (R4) are presented as reasonable restric­ tions on the relevance relation. 7 In (Boutilier 1991b) we define a notion of statistical relevance ( s-relevance) which roughly states that p'Re r iflearning the truth (or falsity) of p affects our judgement as to the truth of r. Assuming e ~ r means we are willing to accept r based on evidence e, p is relevant to r if p 1\ e ~ r or -,p 1\ e ~ r (similar definitional clauses apply when e ~ -,r, or e ~ r and e ~ -,r). We show this definition to satisfy the postu­ lates, and that asserting e > r ensures that any sentence contingent on e 1\ r is irrelevant to r in this sense.

5 Alternatively, we could use Levesque's schema: a 01 :::> -,001 for all falsifiable 01.

6 For all w E W, w· is defined as the map from P into {0, 1} such that w·(A) = 1 iff wE tp(A); in other words, w· is the valuation associated with w.

We also define a weaker notion of commonsense rele­ vance ( c-relevance), violating the postulate (R2) which asserts that p'Rer iff -,p'Rer. Defined in terms of con­ ditional independence, s-relevance must satisfy (R2). If learning p increases the probability of r, then learning -,p must decrease it. If the magnitudes of the changes are vastly different, this may seem a counterintuitive no­ tion of relevance. For instance, if I'm about to cross a bridge a someone tells me to go ahead because there will be no earthquakes ( -,Q) in the next minute, I'm liable to dismiss my informant as a lunatic and discount -,Q as being irrelevant. However, if I am told there will be an earthquake (Q), I will surely consider this informa­ tion to be relevant. Intuitively, -,Q is irrelevant because (statistically) it changes the probability of a safe cross­ ing negligibly (assuming the prior probability of Q is very low), while Q changes the probability radically. We capture this potential failure of (R2) by saying that p is c-relevant to r if, e.g., p 1\ e ~ r when e ~ r, and dis­ counting the possible effect oflearning -,p, It often seems that p is only regarded as relevant if its truth can change the status of r as an accepted belief, not its falsehood.

Other reasons for disassociating conditional indepen­ dence and irrelevance are mentioned in (Gardenfors 1978) and we discuss our definition of irrelevance and how inaccessible worlds capture this concept in detail in (Boutilier 1991b ).

While the logic CO* seems able to express the con­ cept of irrelevance, it is not clear how a default reasoner should proceed given such a logic and a set of facts K B. A modest proposal is to simply assert A > B for each A ~ B in K B, so long as the result is consistent. This works on a wide variety of examples; for instance, if KB = {Bird~ Fly}, then asserting Bird > Fly, we can derive conditionals such as Bird 1\ �reen~ Fly. If Penguin ~ -,Fly and D(Penguin :::> Bird) are added to KB, B > F is no longer consistent. However, B 1\ ...,p ~ F and B 1\ P ~ -,F are both derivable and it is consistent to assert B 1\ P > -,F and B 1\ -,p > F. Adding these to KB, we obtain the following theorems:

1. (K B 1\ Bird) ~ Fly
2. (KB 1\ Bird 1\ �reen)~ Fly

1 Gardenfors also presents postulate {R5) - which leads to a. triviality result - a.nd two possible replacements, one of which {R7) is deemed acceptable. The notion of relevance defined below is a. simple one, but ca.n be extended easily to incorporate {R7) (see (Boutilier 199Ib) for details).

1. (KB 1\ Penguin)~ -,Fly
2. (K B 1\ Penguin 1\ �reen)~ -,Fly

Such an approach, however, has limitations. Con­ sider a K B of two independent conditionals A ~ B and C ~ D. In this case, it is inconsistent to assert both A > B and C > D, and it is not clear what "ex­ tendible" conditionals of interest are derivable from such a K B. Thus, the use ofthe connective> for dealing with irrelevance requires further investigation. Another sim­ ple proposal, which adequately handles this K B, can be described as follows: since the material counterparts of these sentences, A :::> B and C :::> D, must be normally true (that is T ~ (A :::> B 1\ C :::> D)), it should be the case that T >(A:::> BI\C :::>D) holds as well. Extending this idea, we will show that the connective > is capable of representing a certain form of default reasoning, namely !-entailment or rational closure.

3 A Simple Preference Relation

A common approach to default reasoning is to use the notion of preferred models (Shoham 1986). Given a set of CO-models, we will suggest the preferred models are those in which possible worlds are as normal as possible. Consider again a K B containing only Bird ~ Fly. A model of K B will contain some Birdi\Fiy-world which is more normal than any Birdi\-,Fiy-world. In general, we want to derive sentences like Bird 1\ �reen~ Fly, but the most normal worlds with green birds need not satisfy Fly. However, assuming that some Green 1\ Bird 1\ Fly­ world is as normal as the most normal Bird-worlds vi­ olates no constraints imposed by K B . This assumption forces such a world to be more normal than we origi­ nally supposed, so if preferred models force worlds to be as normal as possible, Bird 1\ Green ~ Fly will be derivable.

We must formulate the conditions under which one model will be more normal than another. Let M1 = {W, R1, cp} and M2 = {W, R2, cp} be CO-models. 8 To ensure that M1 is at least as "normal" as M2, each world in W should be as normal in M1 as in M2; so we will insist (in general) that each world "see" at least as many worlds in R1 as in R2 · There are two cases to consider when a world w has fewer accessible worlds in R1. First, some world v might be less normal in R1 than in R2 , in which case it is inaccessible to (some) w in R1 to which it was accessible in R2. In such a case M1 should not be preferred to M2 · However, in the second case, w may have become more normal in R1, in which case it should see fewer worlds (since fewer will be more normal than it) . In this circumstance, M1 may well be preferable to M2, and we relax the restriction that w see as many worlds in Rt. More formally, assume M1 and M2 are defined as above.

Definition w E W is more normal in Rt than in R2 (written N(w, R1, R2)) iff there is some v E W such that vR1 w, wR1 v, and not vR2w.

8 We will only compare models which agree on possible worlds; however, it should be clear that the idea. ca.n be ex­ tended by taking preference relative to the subset of worlds two models have in common. See {Boutilier 1991c).

• Definition M1 is as preferable as M2 (written M1 :::; M2) iff for all wE W, N(w,R1,R2 ) is false only if {v : wR2v} ~ {v: wR1v}. M1 is preferred to M2 (M1 < M2) iff M1:::; M2 and M2 1:. M1 .
• Definition Let T C L be a set of facts. M is a minimal model of T iff-M f= T and for all M' such that M' f= T, M' 1:. M . a is a default conclusion based on T (written T F< a) iff M f= a for each minimal model M of T. 9 -

We examine the consequences of these definitions in the following section.

4 Equivalence to !-entailment

Pearl (1990) describes a natural ordering on default rules named the Z-ordering, and uses this to define a non­ monotonic entailment relation, !-entailment. While put forth as an extension of e-semantics, this entailment re­ lation is essentially based on using preferred models of a sort similar to those described in the previous section. In fact, we will show these notions correspond exactly, and that, while !-entailment is defined in terms of a par­ ticular theory T and orders only models ofT, it can be described in terms of our theory-independent preference criterion, whereby all logical interpretations are ordered.

In this section, we will assume a language with a finite set of propositional variables, and CO*-models only will be treated. The default rules r of (Pearl 1990) have the form a - {3, where a and f3 are propositional formulae. These will correspond to our conditional sentences a => {3. We say a valuation (possible world) w verifies the rule a - f3 iff w f= a A /3, falsifies the rule iff w f= a A -.{3, and satisfies the rule iff w f= a :::> {3. Let T be a finite set of such rules. From (Pearl 1990):

• Definition T tolerates a - f3 iff there is some world which verifies a- /3, and falsifies no rule in T; that is, {a A /3} U { 'Y :::> 6 : 'Y - 6 E T} is satisfiable.

This notion of toleration can be used to characterize probabilistic !-consistency (Adams 1975; Pearl 1988) in a manner that also captures the CO-consistency of a set of rules. 10 Furthermore, toleration can be used to define a natural ordering on default rules (or conditionals) by partitioning T as follows (Pearl 1990):

Definition T; = { r : r is tolerated by T - To - T1 - · .. r;_l}, fori~ 0.

Assuming T is !-consistent, this results in an ordered partition 1.' = T0 U T1 U · · · Tn. Now to each rule r E T we assign a rank (the Z-ranking), Z(r) = i whenever r E T;. The idea is that lower ranked rules are more general, or have lower priority. Given this ranking, we can rank possible worlds according to the highest ranked rule they falsify:

9 Strictly speaking, T should consist only of conditional sentences and cr should be conditional as well. See (Boutilier 1991c) for details on how to extend this relation.

10 T is t:-consistent iff every non-empty subset ofT contains some rule tolerated by all others. If T is the corresponding set of conditionals, this condition holds iff Tis "non-vacuously" satisfiable; that is, if Tu { ¢ cr : cr * {3 e T} is CO-consistent.

Lower ranked worlds are to be considered mote normal. Now, a propositional formula a can be ranked according to the lowest ranked world which satisfies it: Z(a) = min{Z(w) : w f= a} . Given that lower ranked worlds are considered more normal, we can say that a normative conditional a => f3 should hold iff the rank of a A f3 is lower than that of a A -.{3. This leads to the following definition (Pearl 1990):

Definition Formula f3 is 1-entailed by a with respect to T (written a h /3) iff Z(a /1. /3) < Z(a A -.{3).

For details regarding the types of conclusions !­ entailment draws, see (Pearl 1990). It should be fairly clear that !-entailment can be viewed as asserting a pref­ erence on models of theory T, namely that worlds should have their lowest possible rank (without violating the rules of T). In other words, worlds should be as nor­ mal as possible. Not surprisingly then !-entailment cor­ responds to the preferential entailment relation of the preceding section. For a fixed theory T, we define the CO*-model ZT as:

Definition ZT = (W, R, rp} where wRv iff Z( w*) ~ Z(v*).

Theorem 3 T f=s a=> f3 iff a 1-1 f3 with respect toT.

This means that the minimal Z-ranking of worlds cor­ responds to a theory-dependent instance of the more gen­ eral preferential ranking of CO*-models. Furthermore, the explicit nature of this Z-ranking allows us to cap­ ture the exact nature of the (unique) preferred model ZT. In particular, if T is !-consistent and is partitioned as To, ···, Tn, then ZT consists of n + 2 "clusters" of mutually accessible (or equally normal) worlds; cluster 0 consists of all worlds of rank 0, cluster 1 consisting of all worlds of rank 1, and so on, with the most exceptional worlds being those of rank n + 1.

Since the preferred model ofT is unique, we can cap­ ture the exact structure of ZT using sentences in the logic CO containing the connective >, since worlds in each cluster can be characterized by the rules they vio­ late (see (Boutilier 1991c) for details) .

Let T be a finite set of conditionals, partitioned as To, T1, · · ·, Tn.

Definition Let R~ 1 =dr .L For 0 :::; i :::; n + 1, let Rf =:dr /\{a:::> /3: a=> /3 E T- To- .. ·Ti-d­ We assume A 0 =dr T (hence R~+1 = T) .

Definition For theory T as above, the closure ofT is CI(T) = TU {-.Rf > Rf+l: -1:::; i:::; n} .

Theorem 4 CI(T) F=co. a=> f3 iff T F=s a=> {3.

Corollary 1 CI(T) F=co. a => f3 iff a 1-1 f3 with respect to T.

Just as the (second-order) circumscriptive axiom ap­ plied to a theory T closes that theory to correspond to (predicate) minimal models, so too does this closure cor­ respond to our notion of minimality. Theorem 4 shows that CI(T) can be regarded as an axiomatization of the notion of preference described in the previous section, and of the implicit preference ordering determined by System-Z. Hence, the types of conclusions sanctioned by !-entailment (see (Pearl 1990)) are also determined by this form of closure. This implies, given the results of (Goldszmidt and Pearl 1990), that Cl(T) determines the same consequence relation as that of rational closure (Lehmann 1989).

5 Concluding Remarks

We have presented a modal logic CO in which truth at inaccessible worlds is expressible. In this logic we can define not only the normative conditional => of condi­ tional "knowing at least", as in (Boutilier 1990), but also the dual connective > of conditional "knowing at most". This provides us with a conditional version of Levesque's (1990) "only knowing". We discussed briefly the relationship of conditional only knowing to the prob­ lem of irrelevance in default reasoning, and have shown how a simple preference relation (corresponding to !­ entailment and rational closure) which deals with irrele­ vance can be axioniatized within this logic.

Much work remains to be done on the application of conditional only knowing to problems in default rea­ soning. Levesque's characterization is semantically very clear and elegant, but has the drawback of relying on an autoepistemic interpretation of default rules (see e.g. (Reiter 1987) for problems with this interpretation) . Ul­ timately, we would like to push the "closure" of our de­ fault theories into the logic via some connective analo­ gous to Levesque's 0 operator, thereby consolidating the semantic clarity of only knowing with the compelling conditional interpretation of default rules. We expect the expressive power gained by the use of inaccessible worlds makes this goal achievable.

In this connection, we have begun exploring the use of the logic CO to capture a number of other types of reasoning. In (Boutilier 1991a) we provide a logical cal­ culus for belief revision within CO, and show how re­ vision, subjunctive reasoning and default reasoning (in­ cluding such varied approaches as autoepistemic logic, c-semantics and normative conditionals) can be unified using a framework which exploits the power of inacces­ sible worlds.

Other avenues to pursue include the weakening of these logics, along the same lines suggested in (Boutilier 1990), providing other versions of "only knowing" (e.g. based on S4) . A further task is to investigate how the logic CO can be used to capture other default reason­ ing systems, such as the maximum entropy formalism of (Goldszmidt, Morris and Pearl1990), which makes finer­ grained distinctions on the ordering of possible worlds. We suggest that most approaches to default reasoning which can be viewed as restricting the degree of abnor­ mality of worlds may be axiomatized using some logic of inaccessible worlds, or conditional only knowing.

Acknowledgements

Thanks to Ray Reiter, Hector Levesque and especially Moises Goldszmidt for helpful discussion and criticism.

Financial support of NSERC and the University of Toronto is gratefully acknowledged.