Syntactic Conditional Closures for Defeasible Reasoning

1 Introduction

A continuing problem in Artificial Intelligence is dealing with general generic sentences that admit exceptions. For example: suppose we are given that birds fly, birds have wings, penguins are birds, and penguins don't fly. We can write this in a propositional gloss 1 as:

In nonmonotonic reasoning with such statements there are several principles that one would want to hold. Ac­ cording to the principle of specificity, a more specific de­ fault should apply over a less specific default. Thus given that Pis true, we would want to conclude -.F by default, since being a penguin is a more specific notion than that of being a bird. Second, one should obtain trans~tivity of default conditionals, or inheritance of properties by default. So, given that P is true, one would also want to conclude by default that W was true, and so penguins have wings by virtue of being birds. Third, irrelevant properties should be properly handled and so, all other things being equal, we would want to conclude that. a green bird flies. Fourth, one should be able to reason m the presence of exceptions, and so given that B, -.F was true one would still conclude that W was true.

1 That is to say, we will eventually have to deal with first­ order issues but do not do so here. For this paper B => F can be give~ the reading "if x-is-a-bird then normally x-flies".

It, has proven difficult to specify an approach that achieves all of these properties. Earlier systems (such as Circumscription and Default Logic) provide accounts of general mechanisms for nonmonotonic inference that generally handle inheritance and relevance well, but do not deal with specificity. Rather, it is up to the user to hand-code specificity information. For example, in the naive representation of the above example in Default Logic, if P is true we obtain a set of default conclusions in which -.F is true and another set in which F is true.

Recently, much attention has been paid to conditional systems of default inferencing. The starting point here is not so much to provide a general mechanism for non­ monotonic inference, as it is to provide a theory of some phenomenon, based on intuitions concerning, for . exam­ ple, possibility, exceptionalness, or nonmonotomc con­ sequence operators. The initial systems were, on the whole, quite weak; subsequent work has focussed on means to extend the system's basic inferences. As dis­ cussed in the next section, while these systems generally handle specificity well, none satisfactorily handles all of inheritance, relevance, and reasoning in exceptional cir­ cumstances.

This paper explores approaches to syntactically clos­ ing off a conditional knowledge base. The idea is to for­ malise directly notions corresponding to the incorpora­ tion of irrelevant properties and, separately, to the inher­ itance of properties. Essentially then "proof-theoretic" approaches to default reasoning are investigated, based on intuitions regarding desirable properties for a non­ monotonic reasoning system. I begin with a specific conditional logic capable of expressing relations among defaults. So, given our initial example, we can derive the fact that birds are normally not penguins (i .e. B => -.P) . This logic however does not address the problems of ir­ relevant properties or inheritance. Thus we cannot con­ clude that a green bird flies, nor that a penguin has wings by "transitivity". We address this by defining an extension of a theory, or a plausible "extended" default theory. In the first place, an extension includes conditionals incorporating irrelevant properties. In the sec­ ond place, an extension includes conditionals obtained from (default) transitivities among conditionals, and so accounts for inheritance.

The appropriateness of the approach is argued in a number of ways. First, the approach formalises plausi­ ble, familiar intuitions concerning properties of default inference. Second, various canonical and non-canonical examples are shown to be appropriately handled here. Third, it proves to be the case that incorporating ir­ relevant properties corresponds exactly to incorporat­ ing transitivity of conditionals. Hence the same (non­ monotonic) phenomenon underlies these seemingly dis­ tinct notions. The approach then is of independent in­ terest; nonetheless, it is intended ultimately to serve as a proof-theoretic analogue to an extant semantic ap­ proach, based on preference orderings among possible worlds. The next section discusses related work. In Sec­ tion 3 the logic of defaults on which the present approach is based is presented. Section 4 gives the formal details of the approach. This is followed by a discussion and a concluding section. Proofs of theorems and further details are found in [Delgrande, 1995].

2 Background

Related Work Many of the earlier systems of default reasoning deal with mechanisms for effecting nonmono­ tonic reasoning. Autoepistemic Logic [Moore, 1985], Circumscription [McCarthy, 1980], Default Logic [Re­ iter, 1980], and, for our purposes, Theorist [Poole, 1988] are examples of such approaches. In this group, issues of specificity are not addressed within the system, al­ though other properties, such as inheritance, are ade­ quately handled. Various modifications have been pro­ posed to handle specificity in these systems, but these modifications are build on top of the system. Without a formal theory, it is not clear if such modifications are ap­ propriate or in any sense complete. Since defaults per se are not part of the formal system, one also cannot reason about defaults. Thus, one could not conclude from our initial example that birds are normally not penguins.

Recently, much attention has been paid to conditional systems of default inferencing. Such systems address specific forms of nonmonotonic inference, or deal with specific defeasible conditionals based, for example, on notions of preference or exceptionalness. There has been a remarkable convergence or agreement on what con­ stitutes a core set of inferences that ought to be com­ mon to all nonmonotonic systems. Systems such as f.­ entailment [Pearl, 1988] (or 0-entailment or p-entailment [Adams, 1975]), possibilistic logic [Dubois and Prade, 1994], preferential entailment [Kraus et al., 1990], and CT4 [Boutilier, 1992], among others, essentially allow the same inferences, and may be taken as specifying a conservative core [Pearl, 1989] that ought to be com­ mon to all nonmonotonic inference systems. These ap­ proaches deal satisfactorily with specificity. However, not unexpectedly, they are much too weak. In particu­ lar, relevance and inheritance of properties are not han­ dled. Hence, even though a bird may be assumed to fly by default, a green bird cannot be assumed to fly by default (since there may be models of a theory where a green bird does not fly).

Equally surprising, there has also been a strong con­ vergence on a means of strengthening these systems. Ap­ proaches including System Z and !-entailment [Pearl, 1990], CO* [Boutilier, 1992], possibilistic entailment [Benferhat et al., 1992], and rational closure [Kraus et al., 1990] all assume, in a semantic sense, that a world is as unexceptional as possible. Thus essentially, since there is no reason to suppose that greenness has any bearing on flight, one assumes that greenness has no ef­ fect on flight. While this assumption seems reasonable enough, its realisation in these systems is not unprob­ lematic, as described below. In brief, these approaches fail to allow full inheritance of properties; as well they allow unwanted specificity relations. In the next sub­ section, System Z is described as a representative of these approaches. These approaches have been extended in various ways, including [Goldszmidt and Pearl, 1991; Goldszmidt et al., 1990; Benferhat et al., 1993]. However these extensions allow the unwanted specificities found in the original approach( es).

Of other work, [Delgrande, 1988] gives an iterative strengthening of defaults using meta-theoretic assump­ tions. However, since it provides an iterative procedure for strengthening, it is difficult to formally characterise the set of default inferences. This approach is strictly subsumed by the first approach described here. [Geffner and Pearl, 1992] presents another strengthening of the above-mentioned systems, called conditional entailment. There are two difficulties with this approach: first, it is quite complex in its formulation and, second, it does not sanction full inheritance of default properties.

System Z This subsection describes System Z as a representative of the set of systems mentioned above for forming the closure of a conditional knowledge base. As well as being simple to describe, System Z has the advan­ tage that its description does not rely on prior knowledge of any system corresponding to the "conservative core". In System Z, a set of rules R representing defaults is partitioned into an list of mutually exclusive sets of rules Ro, ... , Rn. One begins with a set R = {r I ar --+ f3r} where each ar and f3r are propositional formulas . A set R' ~ R tolerates a rule r if { ar A f3r} U R' is satisfiable. From this, an ordering on the rules in R is defined:

1. Find all rules tolerated by R, and call this set Ro.
2. Next, find all rules tolerated by R- R0 , and call this set R1.
3. Continue in this fashion until all rules have been accounted for.

We obtain a partition (R0 , ... , Rn) of R, where R; = {r Iris tolerated by R- R 0 - ... - R;_l}. The rank of ruler, written Z(r), is given by: Z(r) = i iff r E R; . For our example, we obtain the ordering

An interpretation Misgiven a Z-rank, Z(M), according to the highest ranked rule it falsifies: Z(M) = min{ n I M f= ar :J f3r, Z(r) 2: n}. The rank of a formula <pis defined as the lowest Z-rank of all interpretations sat­ isfying tp: Z( <p) = min{ Z( M) I M f= <p}. A form of default entailment, 1-entailment, is defined by:

This gives a form of default inference that has some very nice properties. Irrelevant facts are handled well and for example we have B t\ G 1-1 F, so green birds fly. There are two weaknesses with this approach. First, one cannot inherit properties across exceptional subclasses. So one cannot conclude that penguins have wings (since ·W will be true at some least-ranked P world). Second, un­ desirable specificities may be obtained: consider where we add to our example the default that calm animals (C) have low blood pressure (L) . Intuitively, C -+ L is irrelevant to the other defaults, yet we obtain the de­ fault conclusion that calm animals aren't penguins, since Z( C t\ ·P) < Z( C t\P). The first difficulty is addressed in [Benferhat et al., 1993]; the second is not. Moreover, this seems to be a problem endemic to all such approaches.

3 A Logic for Default Properties

The approach is founded on a specific conditional logic. This logic corresponds to an extension of the aforemen­ tioned "conservative core" for default inferences. 2 See [Delgrande, 1987; Boutilier, 1992] for details. The fun­ damental idea is straightforward: possible worlds are ar­ ranged according to a notion of "exceptionalness"; a de­ fault a => (3 is true just when there is a world in which a t\ (3 is true and a :J (3 is true at all worlds that are not more exceptional. Thus, "birds fly", B => F, is true if, in the least B-worlds, B :J F is true. Intuitively, we disregard exceptional circumstances such as being a penguin, having a broken wing, etc.

More formally, our language is that of propositional logic augmented with a binary operator =>. We reserve :J for material implication. For readability (especially in Section 4) conjunction is sometimes represented by juxtaposition; hence A t\ B and AB stand for the same formula. For simplicity there are no nested occurrences of the => operator. Sentences are interpreted in terms of a model M = (W, E, P) where:

1. W is a set (of worlds),
2. E is a binary accessibility relation on worlds, with properties:

Reflexive: Eww for every wE W.

Transitive: If Ew1 w2 and Ew2w3 then Ew1 w3.

Forward Connected: If Ew1 w2 and Ew1 w3 then Ew2w3 or Ewaw2.

1. P is a mapping of atomic sentences and worlds onto {true ,false}.

Truth at a world w in model M (f=~) is as for propo­ sitional logic, except that:

2 There are two reasons for adopting a slightly stronger system. First this system includes (in the author's opinion) other essential relations governing generic statements (most importantly that a => i :J ( (a 1\ f3 => 1') V (a 1\ ·/3 => 1')) is valid). Second, it has a simpler semantics. However the results presented here apply equally to these weaker systems.

f=~ a => (3 iff there is a w1 such that Ew, w 1 and F=!", a t\(3 and for every w2 where Ew1, w2, we have f=~ a :J (3.

In addition, Da ("necessarily a") is defined as ·a => a, and Th(T) is the set of formulas logically entailed by default theory T .

The accessibility relation between worlds is defined so that from a particular world w one "sees" a sequence of successively "less exceptional" sets of worlds. For a => f3 to be true we require that there be a world in which a is true, and so we exclude the case of a vacuously-true default. 3 This has no effect on the expressibility of the language (and indeed the following exposition can be developed allowing vacuously-true conditionals), but it does simplify things somewhat.

This logic supplies us with a weak, but semantically justified, system of default inferencing: Given a set of defaults and necessitations T, (3 follows by default from a just when a=> (3 is true in all models ofT. Thus:

Definition 3.1

(3 follows from a by default in T iff T f= a=> (3.

Hence (as previously discussed) we can conclude that a penguin does not fly, while a bird does, and if some­ thing flies then it is not a penguin. However we cannot conclude that green birds fly, since there are models in which green birds do not fly. Nor can we conclude that penguins, by virtue of being birds, have wings. In both these cases it seems that, plausibly, we would want to make the given inference, from green bird to fly, and from penguin to winged. In the next section we describe two approaches for extending a default theory, wherein relevance and inheritance are properly handled.

4 The Approach

In what follows , I will identify a default theory T with a set of default conditionals (corresponding to assertions such as "birds fly") together with a set of assertions taken to be necessarily true (corresponding to assertions such as "penguins are necessarily birds" ). A default the­ ory then contains information that is taken to be true across all domains of interest. Contingent world knowl­ edge (such as "individual x flies") is not part of a default theory, but rather represents case-specific information.

The logic of Section 3 supplies us with a means of de­ termining the relative specificity of default conditionals. (3 is strictly more specific than a, written a -< (3, can be defined as follows:

Definition 4.1 T f= a -< (3 iff T f= a V (3 => ·f3

The right side of the definition says that for every model ofT, at some a V (3 world, w, ·f3 is true, and a V (3 :J ·f3 is true at all equally- or less-exceptional worlds. Thus a is true at w, and there are no equivalently­ exceptional or less-exceptional worlds in which (3 is true. We have that-< is irreflexive, asymmetric, and transitive; also, -< and => are interdefinable [Lewis, 1973].

a~ (3 is defined as ·((3-< a). Using this, the following notion of specificity is defined:

3 Thus this conditional corresponds to the "would" condi­ tional of [Lewis, 1973] .

Definition 4.2

{3 is more specific than a in theory T, written a <t:.r f3 iffT Fa~ f3 and it is not the case that T F f3 ~a .

The general idea of the approach is straightforward. Beginning with a default theory T, we "appropriately" extent this theory, so that we obtain "reasonable" con­ clusions in the extension. Default reasoning is given as in Definition 3.1, but with respect to extensions. Thus, since birds fly and we have no reason to believe that a green bird does not fly, we would include B 1\ Gr => F in an extension. However there is a good reason to be­ lieve that a bird that is a green penguin does not fly, namely that penguins do not fly, and so we would not include B 1\ P 1\ Gr => F. The issue then is to distinguish "reasonable" from "unreasonable" additions to a theory.

In this regard, there are two common notions for aug­ menting a default theory. These are: strengthening the antecedent of a conditional, which I will call STR, and transitivity among conditionals, or TRANS. Informally, these notions correspond to the incorporation of irrele­ vant properties in a conditional and inheritance of prop­ erties, respectively. In what follows I first develop a def­ inition for STR. Following this, a definition for TRANS is given and the two notions are shown to be equivalent.

For STR, there are three properties that can be expected to hold for an extension E of default theory T:

1. It should contain the original theory.
2. It should be logically closed.
3. If a => f3 cf. T then a => f3 E E iff:
4. (a) There is a reason to accept the conditional.
5. (b) There is no equally strong (or stronger) reason to not accept the conditional.

Thus in the case of green penguins there is a reason to suppose that such an animal flies (since birds fly) and a reason to suppose that it does not (since penguins don't fly). Since the notion of penguinhood is more specific than that of being a bird, we would conclude that a green penguin does not fly by default.

More formally, we have the following definition:

Definition 4.3 (STR)

An extension E from strengthening a default theory T is a minimal set of formulas such that

1. If a' => f3 E E then a 1\ a' => f3 E E if~ a 1\ a' :J l_ and whenever F a 1\ a' :J a" and a" => -.{3 E E

For default transitivity, we can again identify three properties that can be reasonably expected to hold for any extension E . In addition to Properties 1 and 2:

1. If a => 1 cf. T but a => {3, {3 => 1 E E then a => 1 E E if
2. (a) There is a reason to accept a=> 1 E E .
3. (b) There is no equally strong or stronger reason to not accept a=> 1 E E.

Hence, appropriately realised, these properties would permit the inference that a penguin has wings, based on the fact that penguins are birds and birds have wings. We have the definition:

Definition 4.4 (TRANS)

An extension E from transitivity of a default theory T is a minimal set of formulas such that

1. T~ E,
2. Th(E) = E,
3. If a => a', a' => f3 E E then a => f3 E E if whenever a => a" E E and a" => -.{3 E E then a" <t:.E a'.

In this case, for the third part, a => f3 E E if

1. there is a reason to accept the conditional via tran­ sitivity: we have conditionals a' => a E E, and a=> f3 E E, and
2. if there are also formulas a' => a" and a" => -.{3 in E, then a" is less specific than a'. That is, we would conclude a' and a" from a. However, since a" 4:.E a' we would conclude {3 and not -.{3.

Informally, this definition allows us to assert that "birds fly" based on the defaults "birds normally have wings" and "winged things normally fly" . Hence birds inherit the property of flight from that of winged things.

Interestingly, these two notions for constructing an ex­ tension are equivalent:

Theorem 4.1 E is an extension ofT from strengthen­ ing iff E is an extension ofT from transitivity.

In light of Theorem 4.1, we need not distinguish ex­ tensions obtained from strengthening versus extensions obtained from transitivity. Consequently I will simply refer to extensions of a default theory, and will just make use of Definition 4.3. 4

The next theorem provides a quasi-iterative specifica­ tion for an extension. While this may be oflimited use in constructing an extension (since the extension appears ·in the specification), it does provide a means of verifying whether a set of formulas is an extension of a default theory.

Theorem 4.2 Let T and E be sets of conditionals. Define:

Eo =T and for every i 2:: 0 E;+l Th(E;) U { a => {3 I ~ a :J l_ and (i) there is a 1 such that F a :J a 1 where a' => f3 E E;, and (ii) if F a :J a" and a" => -.{3 E E then a" 4:.E a' } .

4 It is worth noting that for any sufficiently strong system of defeasible inferencing these notions coincide, in that any system that "reasonably" implements STR will also obtain TRANS, and vice versa. See [Delgrande, 1995) for details.

Default inference is defined as follows.

Definition 4.5

f3 follows from a by default in theory T, a f---T /3, 5 iff for every extension E ofT, we have E f= a=> /3.

The remainder of this section presents examples and discusses properties of the approach. The first example is a variant on an example presented at the outset of the paper.

Example 4.1

So birds have wings; winged things fly; penguins are nonflying birds. The extension E of T contains the fol­ lowing sentences:

In the notation of Definition 4.5 this could be written as:

In the first formula, birds fly by transitivity, and green­ ness is irrelevant, so green birds fly. Green is also irrele­ vant with respect to a penguin's being able to fly, and so green penguins don't fly. While penguins are exceptional birds, in that they do not fly, nonetheless penguins have wings by default.

Note that there are two sources of "nonmonotonic­ ity". The first is in a sense illusory, deriving from the properties of the conditional logic itself. For the above example we have B => F, B 1\ P => ..,F E Th(T) and so B f-.-T F, and B 1\ P f-.-T ..,F. That is, despite appear­ ances, we are here dealing with an underlying monotonic system. However there is a second source, deriving from the definition of an extension. Thus if Tis as above and T' = {B => F}, then we have T' ~ T, and B 1\ P f---T' F but B 1\ P f"--T ..,F.

This is a familiar example involving conflicting de­ faults. There is one extension E ofT; we have, among other conclusions: Q 1\ ..,R => P, Q => ..,R E E.

Example 4.3

This is an extension of the previous example: there are three defaults which cannot be simultaneously applied. Again there is only one extension. The formula A1A2 => B1 is in the extension, as is A1A2 => B1B2. Clearly we would not want A1A2Aa => B1 to be in the exten­ sion, since by symmetry we would also have the same antecedent support B2 and B3 · But these statements together are only trivially satisfiable. Note that in order to block the presence of A1A2Aa => B1 E E based on A1 => B1 E T, we use the fact that A2Aa => B2Ba E E, whence A2A3 => -,B1 E E . However we do have that the following formula is in the extension:

5 By rights a should be a set of formulas. For simplicity I will sometimes abuse notation and write a formula to the left of f--T·

That is, given A1A2Aa we have that two of B1 , B2, B3 hold, but we don't know which. Furthermore we have that

are in the extension. Thus, in the presence of falsified conditionals, we obtain the desired conclusions. Finally if we were to add the information that A2 -< At and A3 -< At toT, we would obtain AtA2A3 => Bt in the extension (in fact we also obtain AtA2Aa => Bt(B2 V Ba)).

There are default theories where there is more than one extension. Perhaps the simplest such theory is the following:

Example 4.4

The third default asserts that one of the first two does not hold; however it does not specify which does not hold. We obtain one extension which contains A 1\ Bt => Ct (and A 1\ B2 => ...,C2) and a second which contains A 1\ B2 => C2 (and A 1\ Bt => ...,Ct)· Both extensions contain A=> ...,(Bt :J Ct) = (B2 :J C2).

Extensions have quite reasonable properties. The fol­ lowing theorems are fundamental.

Theorem 4.3 If T is a default theory then T has an extension.

Theorem 4.4 For extension E ofT, E is inconsistent iff T is inconsistent.

Theorem 4.5 If Et, E2 are extensions ofT and Et =f. E2 then Et U E2 f= L

Thus extensions exist, and are inconsistent only if the underlying theory is inconsistent. Further, if there is more than one extension of a theory then the extensions are mutually inconsistent.

A default theory may be ambiguous or incomplete with respect to specificity in the following sense:

Definition 4.6 T is ambiguous with respect to speci­ ficity if there are /1 , /2 , a such that T f= 'Yt V /2 -< a but T ~ 'Yt -< a and T ~ /2 -< a .

We obtain:

Theorem 4.6

No extension is ambiguous with respect to specificity.

Thus specificity ambiguities are resolved in one fashion or another in forming an extension. In Example 4.4 we have T f= Bt V B2 -< A but T ~ Bt -< A and T it= B2 -< A. In one extension we obtain Bt -< A and in another B2 -< A. In Example 4.2, on the other hand, T f= Q V R -< Q 1\ R but T ~ Q -< Q 1\ R and T ~ R -< Q 1\ R. In the resulting (single) extension we obtain both Q -< Q 1\ R and R -< Q 1\ R .

Finally, for a conditional belonging to an extension, either a given property is irrelevant with respect to the conditional or its negation is.

Theorem 4.7

Thus, given that B => F is in an extension, then either B 1\ P => F is in the extension or B 1\ ..,p => F is. Also presumably we would obtain that both B 1\ Gr => F and B 1\ -,Gr => F are in the extension.

5 Discussion

Comparison with Related Work: The technical de­ velopment of the last section is somewhat reminiscent of that of Default Logic [Reiter, 1980], and it is worth­ while outlining the similarities and differences. In De­ fault Logic (DL) a default theory is given by a pair (D, W) where D is a set of default rules (expressed as domain-specific "rules of inference") and W is a set of classical (first-order or propositional) formulas, giving information about the domain at hand. An extension is a maximal acceptable set of beliefs, obtained by "apply­ ing" as many rules from D (given W) as possible. An extension then is a superset of W.

In our case the object is to extend the set of default conditionals; in DL this would correspond to augment­ ing D. An extension in the present approach then is intended to be "applicable" to any domain of applica­ tion (i .e. to any "W").

In both approaches three properties are given that can be expected to hold for any extension:

1. The thing extended (W in DL; T here) should be contained in an extension.
2. The extension should be deductively closed.
3. As many "rules" as possible should be applied or added.

In both cases a nonconstructive definition of an exten­ sion is given; the present approach does not require a fixed-point definition as DL does (roughly) due to the comparatively restricted form of the conditional defaults.

With respect to more recent and more closely-related work the present approach can be compared to ap­ proa~hes exemplified by System Z [Pearl, 1990]. 6 !'>-s mentioned in Section 2, there are two weaknesses with these systems: one cannot inherit properties across ex­ ceptional subclasses, and undesirable specificities are sometimes obtained. The first difficulty has been rec­ tified in, for example, [Benferhat et a/., 1993]. How­ ever since this system subsumes System Z, the second problem remains. The difficulty here (and the difference with the approach at hand) is that System Z assumes that things are as "unexceptional" (i.e. ranked as low) as consistently possible. Hence for our birds and pen­ guins example, any irrelevant conditional (e.g. "students like cheap but good restaurants") is ranked at level 0, and consequently lower than any conditional involving penguins. This, as described previously, leads to unde­ sirable specificities. In the approach at hand, unrelated conditionals remain unrelated and so there are no direct inferences between penguins and students.

As mentioned, the approach of strengthening pre­ sented here strictly subsumes one of the approaches given in [Delgrande, 1988], where an iterative means of aug­ menting a theory is given.

6 Recall from Section 2 that systems such as CO* [Boutilier, 1992], possibilistic entailment [Benferhat et al., 1992], or rational closure [Lehmann and Magidor, 1992] are essentially equivalent with respect to derivability.

further work: There are two major areas for further work. The first concerns a semantics for the approach, while the second deals with implementation issues.

The assertion was made at the outset that this ap­ proach is of independent interest. Nonetheless, it has been formulated with a specific semantic development in mind [Delgrande, 1994]. In this latter development, a conditional in a theory T prefers a world in which the classical counterpart of the conditional is true, over a world in which it is false . That is, B => F prefers a world in which B :::> F is true over one in which B 1\ ·F is true. Following on this intuition, a set of condition­ als T determines an ordering (or orderings) on a set of possible worlds. In this approach {J follows by default from o: just if {J is true in the most preferred worlds in which o: is true. It is conjectured that these approaches are equivalent; they were formulated with this equiva­ lence in mind, but it remains to be shown that they are equivalent.

With respect to implementation concerns, although the definitions for an extension involve the addition of an infinite number of defaults, it is clear that an im­ plementation would not need to contend with the full set of defaults in an extension. 7 Rather, in determining whether o: i""T {3, given a theorem prover for the logic (see [Lamarre, 1992] for example), the issue is to find a set of supported conditionals which when added to T al­ lows o: => {J to be derived. Second, we might expect that when the form of sentences in a theory is appropriately restricted (say, to something looking like Horn clauses) we would obtain good complexity results.

6 Conclusion

This paper has presented an approach for extending a default theory so as to obtain a system for default in­ ferencing via the incorporation of irrelevant properties or inheritance of properties. The approach takes as a starting point an extant (monotonic) logic of defaults. From this, given a default theory, definitions for an ex­ tension were given corresponding to intuitions regarding irrelevant properties and inheritance of properties. In addition to the logic of defaults described in Section 3, the results of this paper apply also to the "conserva­ tive core" for default inferences. Arguably the notion of an extension satisfactorily formalises intuitions concern­ ing augmenting a default theory. That the approach captures a reasonable notion of "extension" is also sup­ ported by the fact that the concepts of irrelevance and inheritance prove to be interdefinable. The approach also handles standard and non-standard examples of de­ fault reasoning, and avoids the difficulties encountered by other approaches. Finally, it is conjectured that an extant semantic approach is equivalent to the present work.

The approach is intended to be applicable to defea­ sible conditionals, or to generic sentences which allow possible exceptions. Consequently it will not be, nor is it intended to be, applicable in all areas. For exam­ ple, in this approach defaults are implicitly "applied" wherever possible. Consequently, given a chain of de­ faults T = {A1 :=} A2,A2 :=} Aa, ... ,An-1 :=}An}, lacking contradictory information we would obtain that A1 f-.-T An. This may be fine for default reasoning, but it leads to unintuitive results for temporal reasoning, as has been noted for example for chronological ignorance. Hence the present approach would appear to produce results too strong for such reasoning.

7 Any more so than in classical logic, in determining whether r f-- a, one would first form the deductive closure of r.

There are two principal areas for further work. First a provably equivalent semantics, presumably based on preference orderings among worlds, is obviously desir­ able. Second, computational concerns have not been ad­ dressed. However the immediate goal of this paper has been to characterisation proof-theoretic approaches to default inference. Given this, computational issues can subsequently be addressed.

Acknowledgements

This research was funded by the Nat ural Science and Engineering Research Council of Canada grant A0884. The author was a visitor at IRISA, Rennes, France while part of work was being carried out. The author wishes to thank Philippe Besnard and Repco for their hospitality, and Torsten Schaub for comments on the initial draft.