Weak Conditional Logics of Normality

1 Introduction

A major approach in nonmonotonic reasoning has been to represent a default as an object that one can reason about, ei­ ther as a conditional as part of some object language, or as a nonmonotonic consequence operator. Thus for example "an adult is (typically or normally) employed" might be repre­ sented a ---+ e, where ---+ represents a default conditional, dis­ tinct from the material conditional:::>. Given a suitable proof theory and semantics, one can derive other defaults from a given set of defaults. There has been widespread agreement concerning just what principles should constitute a minimal logic, a suggested "conservative core," of defaults. However, the resulting conditional is quite weak, at least compared with the material conditional, in that it does not (in fact, should not) fully support principles such as strengthening of the an­ tecedent, transitivity, and modus ponens.

Since one would want to obtain these latter properties "by default," such logics are extended nonmonotonically by a "closure" operation or step. This closure operation has, for example, been defined by selecting a (preferred) subset of the models of a theory; in the resulting subset of the mod­ els one obtains strengthening of the antecedent, transitivity, or (effectively) modus ponens, wherever feasible. Essentially then, there are two components to default reasoning within such a system. First, there is a standard, monotonic logic of conditionals that expresses relations among defaults that are deemed to always hold. Second, there is a nonmonotonic mechanism for obtaining defaults (and default consequences) where justified. Representative (but not even remotely ex­ haustive) work in this area includes [Geffner and Pearl, 1992; Pearl, 1990; Kraus eta/., 1990]. In essence, these approaches treat the default conditional like its classical counterpart, the material conditional, where "feasible" or "by default".

While this work captures an important notion of default entailment - perhaps the most important notion - it is not without difficulties. As described in the next section, some principles of the "core" logic are not uncontentious; as well, there are examples of default reasoning in which one obtains undesired results. Lastly, there are more recent approaches, notably addressing causality, in which one requires a weaker notion of default inference, rejecting, for example, contrapos­ itive default inferences. In response to these points, we sug­ gest that there is a second, distinct, interpretation of default conditionals, in which a default is regarded more like a rule, with properties more in line with a rule of inference, than a weakened classical conditional.

In the following sections we describe our proposed ap­ proach informally and formally. We begin by proposing an exceptionally weak logic of conditionals; from this basis a family of conditional logics is defined. Given a default con­ ditional a ---+ {3, the underlying intuition that is formalised is that a supplies a context in which, all other things being equal, f3 normally holds or, more precisely, in the context of a, a 1\ f3 is more "normal" than a 1\ ·/3. Notably, all of the logics that we consider are weaker than the aforementioned "conservative core". It proves to be the case however that a nonmonotonic operation is very easily defined; this non­ monotonic step essentially specifies that a property is irrele­ vant with respect to a default unless it is known to be rele­ vant. This nonmonotonic step easily admits inferences that in other approaches have taken significant formal machinery to obtain. As well, we show that the aforementioned diffi­ culties that arise in interpreting a default as a weak classical conditional do not arise here.

This distinction between treating a default as a condi­ tional or as a rule has been noted previously; see for example [Geffner and Pearl, 1992]. As well, work on inheritance net­ works [Horty, 1994] can be viewed as investigating proof the­ ories for the latter interpretation; and work on causality such as [McCain and Turner, 1997] falls in the rule-based frame­ work. However a logic (that is, with both semantics and proof theory) capturing this interpretation has not (to our knowl­ edge) been investigated previously, nor has a fully general nonmonotonic closure operator been developed under this in­ terpretation. Last, we suggest in the conclusion that this alter­ native interpretation may be widely applicable, extending to areas such as counterfactual reasoning, generally treated via the stronger interpretation.

2 Background

In recent years, much attention has been paid to conditional systems of default reasoning. Such systems deal with defeasi­ ble conditionals based on notions of preference among worlds or interpretations. Thus, the default that a bird normally flies can be represented propositionally as b --+ f . 1 These ap­ proaches are typically expressed using a modal logic in which the connective --+ is a binary modal operator. The intended meaning of a --+ j3 is approximately "in the least worlds (or most preferred worlds) in which a is true, j3 is also true". Possible worlds (or, again, interpretations) are arranged in at least a partial preorder, reflecting a metric of "normality" or "preferredness" on the worlds. Given a set of defaults r, de­ fault entailment with respect tor, f--' r· can be defined via:

There has been a remarkable convergence or agreement on what inferences ought to be common to all nonmonotonic systems; space considerations preclude a full listing of ap­ proaches and references. The resulting set of principles has been called the conservative core in [Pearl, 1989]. It was originally considered in [Adams, 197 5], and has been studied extensively, as the system P, in [Kraus eta!., 1990]. One ex­ pression of the logic of conditionals is as follows. The logic includes classical propositional logic and the following rules and axioms: 2

1 An alternative is to treat the conditional as a nonmonotonic in­ ference operator, b r.- f. In a certain sense these approaches can be considered equivalent; here, for simplicity, we remain within the conditional logic framework.

2 Two systems of nomenclature have arisen, one associated with conditional logic and one with nonmonotonic consequence opera­ tors. We list both (when both exist) when first presenting an axiom or rule; for example the conditional logic rule for substitution of logical equivalents in the antecedent is called RCEA; its nonmono­ tonic consequence operator, Left Logical Equivalence is abbreviated LLE. Hence we first list the rule as RCEAJLLE.

These principles are not uncontentious; for example, [Poole, 1991] can be viewed as arguing against a derived principle CC/And (viz. ((a--+ {3) 1\ (a--+ 1)) :::> (a --+ /31\1 ) obtained via RT and ASC). Likewise, [Neufeld, 1989] suggests against CA in some cases.

Nonetheless, the resulting logic (and proposed strengthen­ ings of the logic) are weak. A central difficulty is that seem­ ingly irrelevant properties will block a desired inference. For example, given that a bird is asserted to fly by default, one cannot thereby conclude that a green bird flies by default. The problem, essentially, is that there is nothing requiring preferred worlds in which birds fly to include among them green-bird worlds. Consequently, various means of strength­ ening the logic to incorporate irrelevant properties in a prin­ cipled fashion have been proposed. Thus for "birds fly," since being green is presumably irrelevant with respect to flight, one would want to have, among the preferred worlds in which birds fly, a (preferred) subset in which there are green birds.

Rational closure [Lehmann and Magidor, 1992], for exam­ ple, assumes that a world is ranked as unexceptional as pos­ sible. In conditional entailment [Geffner and Pearl, 1992], a partial order on possible worlds is detem1ined by ranking worlds based on the highest-ranked default that distinguishes between the worlds. In both cases, defaults are evaluated with respect to the resulting ranking. Thus, since there is no rea­ son to suppose that greenness has any bearing on flight, one assumes that greenness has no effect on flight.

However there are difficulties with both approaches. Ra­ tional closure employs a very strong minimization criterion; see [Geffner and Pearl, 1992] for a number of problematic ex­ amples. As well, consider an elaboration of an example given by John Horty:

(Normally one does not eat with the fingers (f), but one does when eating asparagus (a); normally one uses a napkin (n), but not when one is out of napkins (o).) The rational closure of these conditionals gives that, if one is not out of napkins (·o), one is not eating asparagus (·a). Clearly this inter­ action between unrelated defaults is undesirable. As well, in neither conditional entailment nor rational closure does one obtain inheritance of properties (however see [Benferhat eta!., 1993]). In addition, consider the following example [Geffner and Pearl, 1992]:

(That is, adults are normally employed, university students are normally adults but are not employed, and Frank Sina­ tra fans are normally adults.) In both conditional entailment and rational closure we obtain the default inference that Frank Sinatra fans are not university students. But this is a curious inference, since there is nothing in the example that would seem to relate Frank Sinatra fans to university students.

We suggest that at least some of these examples do not nec­ essarily reflect a problem with the approaches per se. Rather, our thesis is that there are (at least) two distinct interpreta­ tions that can be given to a default. First, there is the intuition that a default is essentially a weak version of the material conditional (or, in more recent approaches, necessary entail­ ment), and should behave as such a conditional, except that it is defeasible. This intuition is seen most clearly in the ex­ pression of defaults by circumscriptive abnormality theories [McCarthy, 1986]. In this case a default a ---+ f3 is repre­ sented as the formula a 1\ -.Abi ::::> (3. The circumscription of Abi asserts that Abi is false (roughly) if consistently pos­ sible. Obviously, if Abi is asserted to be false, the result is exactly the material conditional. As well, conditional entail­ ment adopts this intuition: the default a ---+ f3 is basically the same as T ---+ (a ::::> !3) (and so T ---+ ( -.(3 ::::> -.a)), together with specificity information implicit in a [Geffner and Pearl, 1992, p. 232]. This interpretation also underlies approaches that assume that defaults are founded (formally or informally) on notions of probability. 3

The second interpretation regards a default more as an (object-level) rule, whose properties are closer to those of a rule of inference. Thus, given a conditional a ---+ /3, if the antecedent a happens to be true, we conclude f3 by default. Given -.(3 we specifically do not want to conclude -.a. This latter interpretation covers an important class of defaults that have not been addressed as a logic of conditionals per se (al­ though this distinction has been noted in [Geffner and Pearl, 1992]; and inheritance networks [Horty, 1994] can be viewed as proof theoretic accounts of this interpretation). A further motivation for exploring this interpretation is that there has been recent interest in conditional accounts of causality (for example [McCain and Turner, 1997]), in which reasoning via a default contrapositive is explicitly rejected. Thus, from "a causes b" we don't want to conclude "-.b causes -.a."

3 Defaults as Rules

The general approach is the same as those described in the previous section: we begin by specifying a logic of defaults and subsequently provide a principled, nonmonotonic, means to extend the logic to account for irrelevant properties. Our point of departure is that we informally treat defaults more like rules of inference; in particular, defaults are intended to be applied in a "forward" direction only. Our interpretation, roughly, is that the antecedent of a default establishes a con­ text in which the consequent (normally) holds, or holds all other things being equal. Thus, for default a ---+ /3, our in­ terpretation is roughly that, in the context established by a, it is the case that f3 is more normal (typical, etc.) than -.(3. We express this semantically by

that is, the proposition (see the next section) llaA/311 M is more normal (typical, etc.) than lin 1\ ·/311M. It seems reasonable that our binary relation of relative normality < be asymmetric and transitive, and so we generally assume that these condi­ tions hold. We note that the form of (3) has appeared regu­ larly in the literature, going back at least to [Lewis, 1973]. 4

3 We note in passing that there are examples of defaults that have nothing to do with probability, for example (1).

4 We use < in the opposite sense of Lewis and many other au­ thors. For our interpretation, it seems to make more sense to express

The difference is that usually the interpretation of(3) is along the lines of "the least worlds where a 1\ -.(3 is true are less nor­ mal than the least a 1\ f3 worlds"; our interpretation refers to the proposition expressed by these formulas. Consequently, our relation < is not an accessibility relation in the normal sense, since it is a relation on sets of worlds.

Filling in the (formal) details yields a weak logic of condi­ tionals, significantly weaker than the so-called "conservative core". We also consider various strengthenings of the logic, but these strengthenings are still weaker than this "core" set of defaults. We subsequently define a notion of nonmonotonic inference with respect to these logics. It proves to be the case that this is very easy to do in our approach. Basically, the (semantic) relation X < Y asserts that in the "context" (set of possible worlds) XU Y, partitioned by X,Y, we have that Y is more normal than X. Our nonmonotonic assumption is that this obtains in all "feasible" subcontexts. That is, for proposition Z, unless there is reason to conclude otherwise, we assert that Z n X < Z n Y. The next section develops the formal details.

4 The Approach

4.1 The Base Logic

Let Lpc be the language of propositional logic defined, for simplicity, over a finite alphabet P = {a, b, c, ... } of propo­ sitional/etters or atomic propositions, and employing the log­ ical symbols-., V, /\,::::>,and=· The symbol Tis taken to be some propositional tautology, and ..l is defined as -. T. The language £ is £PC extended with the binary operator ---+ as a weak conditional. For convenience, arguments of ---+ are members of£ PC; hence, we do not allow nested occurrences of---+. Formulas are denoted by the Greek letters a, /3, ... and sets of formulas by upper case Greek letters r, /:1, .... Sentences are interpreted with respect to a comparative condi­ tional model M = (W, < , P) where:

1. W is a set (of states or possible worlds);
2. < s;; W x 2w x 2w with properties described below;

We use the upper case letters X, X 1, Y, .. . to denote sets of possible worlds. P maps atomic sentences onto sets of worlds, being those worlds at which the sentence is true. The relation < associates with each world w E W a binary notion of relative normality between propositions; we write X <w Y to assert informally that, according to world w, proposition Y is more normal than X. That is, given a partition {X, Y} of a context XU Y, the relation X < Y asserts that Y is more normal (unexceptional, etc.) than X. We assume that< is a strict partial ordering on its last two arguments, that is for w E W, <w is asymmetric and transitive. As well, we assume that the incoherent proposition is maximally abnormal:

Truth of a formula at a world in a model is as for propositional logic, with an addition for---+:

"Y is more normal than X" by X < Y rather than by Y < X .

Definition 4.1

1. f=~ p for p E P iff w E P(p) .

1. F=~ · a. iff f!=~ a..

A formula a. is valid, written f= a., just if it is true at every world in every model. We identify the proposition expressed by a sentence a. with the set of worlds in which a. is true, denoted ll a. IIM, that is,

Thus a. ___, (3 is true just if the proposition expressed by a. A (3 is more normal than that expressed by a.A· (J. a. is necessarily true, Da., is defined as ·a. ___, a. .

Consider the logic closed under classical propositional logic along with the following rules of inference and axioms: RCEA/LLE: From f- a. := a.' infer f- (a. ___, (3) := (a.' ___, (3 ) RCECA:

RI/SupraCI: From f- a. ::::> (3 infer f- a. ___, (3

We call the smallest logic based on the above axiomatisation C . Theoremhood of a formula a. is denoted, as usual, by f- a.. This system is quite weak; however in the full paper we con­ sider the even weaker logic c- consisting of propositional logic and RCEA, RCECA, and Rl. RCEA asserts that con­ ditionals with the same consequent and equivalent (in propo­ sitional logic) antecedents are equivalent. RCECA asserts the same thing with respect to consequents, but is somewhat more general, in that the consequents need be equivalent just in the "context" given by the antecedent. Rl asserts that if (3 is logically implied by a., then it is also normally implied. WeakCEM gives a weak version of the excluded middle for a weak conditional; in the semantics this is reflected by asym­ metry of < . Similarly Trans reflects transitivity of< in the semantics. We obtain the following basic results:

Theorem 4.1

As well, we obtain:

Theorem 4.2 a. is valid in the class of comparative condi­ tional models ifff- a. in C.

For those familiar with conditional logic, the formulas RCM, RT, ASC, CC, and CA (and their nonmonotonic con­ sequence operator counterparts: Right Weakening, Cut, Cau­ tious Monotonity, And, and Or) are not valid in C . Nonethe­ less, despite its (monotonic) inferential weakness, the logic already allows a rich set of nonmonotonic inferences, as cov­ ered in the next section. However, before proceeding we first consider various extensions to the logic.

4.2 Extensions to the Logic

In the logic C most properties of the relation <w stem from its being a strict partial order (viz. asymmetric and transitive). We also look at strengthening <w by considering properties that seem reasonable for a notion of normality. Consider the following:

For CD, if X is less normal than Y, then a stronger propo­ sition than X (viz. X \ Z) is also less normal than Y. CU is a dual : if X is less normal than Y, then a weaker propo­ sition than Y (viz. Y U Z) is also more normal than X . UD combines these conditions, and WDjU is a weak version of disjoint unions, described below. Interestingly, the first two of these conditions have appeared in the belief revision lit­ erature. Our relation < is what [Alchourr6n and Makinson, 1985] call a (transitive) hierarchy; while < with CD and CU is a regular hierarchy. Their interpretation of < echoes ours for X < Y, that "X is less secure or reliable or plausible ... than Y" [Gardenfors and Rott, 1995, p. 75].

Consider next the following rules and formulas :

Space considerations preclude a full discussion of these con­ ditions. WeakRCM is a weaker version of both the rule RCM and the formula ASC in conditional logic. CM ("Conditionalisation" in nonmonotonic consequence rela­ tions) gives a conditional version of one half of the deduc­ tion theorem. Combining WeakRCM and CM yields the rule RCM, allowing weakening of the consequent of a con­ ditional. D supplies a certain "reasoning by cases" for the conditional.

We obtain the following correspondence between semantic conditions and the axiomatisation:

Theorem 4.3 C + CD (CV, UD, WDjU) is complete with respect to the class of comparative conditional models closed under WeakRCM (CM, RCM, D).

We could go on and add other conditions in the semantics. Again space considerations dictate against a lengthy discus­ sion, but two conditions are worth noting here:

Connectivity: For X, Y <::;; W, either Y <w X or X <w Y .

Disjoint union has appeared frequently in the literature, for example [Savage, 1972; Fine, 1973; Dubois eta/., 1994]. The addition of disjoint union requires that the notion of a model be altered slightly (from a relation < to :S); the resultant se­ mantic framework would correspond to the basic definition of a plausibility structure [Friedman and Halpern, 2001]. The addition of connectivity would make <w a qualitative proba­ bility in the terminology of [Savage, 1972].

5 Nonmonotonic Reasoning

We claimed at the outset that the logic C and its strengthen­ ings would allow a simple approach to nonmonotonic infer­ ence, having just the "right" properties for a rule-based in­ terpretation of a conditional. For the logics, the central idea was that, given a partition {X, Y} of a context X U Y ~ W, the relation X < Y asserts that Y is more normal (unexcep­ tional, etc.) than X . To obtain nonmonotonic inference, we simply assume that this relation holds in any subcontext, that is X n Z < Y n Z wherever "reasonable". More formally, we have the following:

Definition 5.1 Let M = (W, <, P) be a comparative condi­ tional model in C.

Define M * = (W, <*, P), the augmentation of M, by:

In the augmentation of a model, we will have X <~ Y if X <w Y . Otherwise, X <~ Y if there are X', Y' where X' <w Y' for X ~ X' andY~ Y', and there is no X", Y" where X ~ X" ~ X' and Y ~ Y" ~ Y' and Y" <w X" in the original model.

Theorem 5.1 If M = (W, <, P) is a comparative condi­ tional model then so is M* = (W, <*, P).

We define f=* as validity in the class of augmented com­ parative conditional models; that is f=* a iff a is true at every world in every augmented comparative conditional model. Nonmonotonic inference is defined as follows:

We say that f3 is a nonmonotonic inference from a with re­ spect to r, or just f3 is a nonmonotonic inference from a if the set r is clear from the context of discussion.

We illustrate nonmonotonic inference first by a familiar example:

Thus birds fly and have wings, and penguins are (necessarily) birds that do not fly. We obtain the following:

We also obtain b 1\ x 1\ y 1\ z r-- w for x E { T , g, ·g} , y E {T,p, ·p} , z E {T, J, ·!}. Thus green (g) birds have wings, as do non-green flying penguins. As well p r-- w, and so pen­ guins inherit the property of having wings by virtue of neces­ sarily being birds. Note that if we replaced (7) by p --+ b, we would no longer obtain p r-- w; however we would obtain the weaker b 1\ p r-- w. We justify this by noting that a normality conditional a --+ f3 does not imply a strict specificity relation between a and f3 whereas D (a ::) {3 ) does.

The next example further illustrates reasoning in the pres­ ence of exceptions.

So Quakers are pacifists while Republicans are not, and Quakers are generous. We obtain q 1\ ·r r-- p and q 1\ r r-- g. Thus in the last case, while Quakers that are Republican are, informally, exceptional Quakers, they are nonetheless still generous by default.

Concerning our original motivating examples, in (I) we do not obtain the undesirable inference ·o r-- ·a, and in (2) we do not obtain f r-- ·u. Last, we note that while we obtain full incorporation of irrelevant properties, we do not obtain full default transitivity. Thus

does not yield a r-- c (nor, incidentally, do we obtain ·b r-- ·a). However we do get a 1\ b r-- c. If we replaced a --+ b with D (a ::) b) we would get a r-- c. If we replaced b--+ c with D(b ::) c) we would again get a r-- c, inC (in fact we could derive a --+ c in those logics containing RCM, as given in Theorem 4.3).

6 Discussion

We have argued that there are two interpretations of a default conditional: as a weak (typically material) implication, or as something akin to a rule of inference. The former interpreta­ tion is explicit in, for example, circumscriptive abnormality theories, and implicit in an approach such as conditional en­ tailment. It is clear that there are many, and varied, applica­ tions in which the first interpretation is appropriate. However we have also noted that there are various reasons to suppose that this is not the only such interpretation: First, work such as [Poole, 1991] and [Neufeld, 1989] can be viewed as ar­ guing against principles of the "core" logic underlying this first interpretation (the former arguing against the principle CC/And and the latter against CAlOr). Second, there are ex­ amples of inferences in approaches such as rational closure or in conditional entailment that are either too weak or too strong. Last, there are emerging areas (such as causal reason­ ing) in which a "weak material implication" interpretation is not appropriate. While this distinction has been recognized previously, what is new here is the development of a fam­ ily of logics, with a novel semantic theory and proof theory, along with a specification of nonmonotonic inference, for the "rule-based" interpretation.

All of the logics presented here are quite weak, at least compared to the "conservative core" or, equivalently, the system P of [Kraus eta!., 1990]. We argue however that such lack of inferential capability is characteristic of a "rule­ based" interpretation of a conditional. Moreover it proves to be the case that nonmonotonic reasoning is defined very eas­ ily in these logics, and allows a rich set of inferences concern­ ing the incorporation of irrelevant properties and of property inheritance.

An open question concerns how informal, commonsense defaults should be classified -whether as a defeasible classi­ cal conditional or as a rule. Certainly past work has favoured the "defeasible classical conditional" interpretation. How­ ever, a case can be made that many examples formerly in­ terpreted as belonging to the first category are better inter­ preted as belonging to the "rule" category. Consider Lewis' approach to counterfactuals [Lewis, 1973] in which the fol­ lowing example, concerning a past party, is given: "If John had gone it would have been a good party" and "If John and Mary had gone it would have not been a good party". From this we deduce that "if John had gone, Mary would not have gone". This, to most readers, is a strange result: John's going and Mary's going are (presumably) independent events. Ar­ guably this result ought not to obtain, and so perhaps counter­ factuals, as previously modelled by Lewis' sphere semantics, may be better interpreted via the "rule" interpretation.

Acknowledgements

I thank the reviewers for their useful suggestions. This work was supported by a Natural Sciences and Engineering Coun­ cil of Canada Discovery Grant.