Credulous Nonmonotonic Inference

1 Introduction

The approach to nonmonotonic and commonsense rea­ soning based on describing associated inference relations forms one of the most influential and effective tools in studying such a reasoning in AI. A number offundamen­ tal works in this area have reached its first 'saturation' in the so-called KLM theory [Kraus et al., 1990]. In these works a semantic representation of nonmonotonic inference relations was developed based on sets of states ordered by a preference relation: a nonmonotonic infer­ ence rule A f-.- B was assigned a meaning that B should be true in all preferred states satisfying A.

The above notion of nonmonotonic inference was de­ signed to capture a skeptical approach to nonmonotonic reasoning, according to which if there is a number of equally preferred alternatives, we infer only what is com­ mon to all of them. However, works in nonmonotonic reasoning have suggested also an alternative approach, usually called credulous or brave reasoning, according to which each of the preferred alternatives is considered as an admissible solution to the nonmonotonic reason­ ing task. Actually, there are many important reasoning problems in AI and beyond, such as diagnosis, abduction and explanation, that are best seen as involving search for particular preferred solutions. This idea is implicit also in the notion of an extension in default logic [Reiter , 1980] as well as in similar constructs in autoepistemic and modal nonmonotonic logics.

There have been a few attempts in the literature to investigate the properties of credulous inference, mainly with negative conclusions that such an inference does not satisfy practically all 'respectable' rules (see, e.g., [Brass , 1993; Cayrol and Lagasquie-Shiex, 1995]). For example, a distinctive feature of credulous reasoning is that it does not allow to conjoin different conclusions derivable from the same premises (because they might be grounded on different preferred solutions) . In other words, it renders invalid the following well-known rule:

(And) If A f-.- B and A f-.- C, then A f-.- B 1\ C.

In fact, we will establish below that And can be seen as a culprit distinguishing credulous and skeptical non­ monotonic inference. Accordingly, inference relations satisfying this rule will be called skeptical in what fol­ lows .

We suggest below both a formal characterization and semantic interpretation for a number of systems of cred­ ulous nonmonotonic inference based on the notion of an epistemic state. The latter are quite similar to cumu­ lative models of skeptical nonmonotonic inference, de­ scribed in [Kraus et al., 1990], though they will be used in a somewhat different way. Despite this , we will see that skeptical inference is also definable in the frame­ work of epistemic states, and this will give us a good opportunity to compare these two kinds of inference and study their relationship.

We will establish also a close connection between credulous inference relations and ordinary Tarski conse­ quence relations. In fact , we will see that practically all kinds ofnonmonotonic inference relations, both skeptical and credulous, can be described in these terms. Among other things, this will allow us to give a representation of credulous inference in the expectation-based framework suggested in [Giirdenfors and Makinson, 1994].

Below we will follow David Makinson in distinguishing monotonic Tarski consequence relat ions from nonmono­ tonic inference relations. This terminological distinction will be especially suitable in the present context .

2 Preliminaries: supraclassical consequence relations

In what follows we will use ordinary Tarski consequence relations defined in a language containing the classi­ cal connectives { V, 1\, -. , --->}. F will denote the classical entailment with respect to these connectives. Also, A, B, C, ... will denote propositions, while a, b, c, ... fi­ nite sets of propositions.

A Tarski consequence relation f- will be called supra­ classical if it satisfies

( Supraclassicality) If a F A, then a f- A

Thus, a consequence relation is supraclassical if it sub­ sumes classical entailment. Supraclassicality requires all theories of a consequence relation to be deductively closed. It allows for replacement of classically equiva­ lent formulas in premises and conclusions of the rules. In addition, it allows to replace sets of premises by their classical conjunctions: a f- A will be equivalent to 1\ a f- A. This implies, in particular, that any supraclas­ sical consequence relation can be seen also as a certain binary relation among propositions. In fact , such bi­ nary relations are partial orders that will be used below as a 'partial ' generalization of expectation orders from [Giirdenfors and Makinson, 1994], since they have all the properties of the latter except connectivity.

3 Epistemic states

The notion of an epistemic state, defined below, will pro­ vide a uniform semantic framework for representing non­ monotonic inference relations. It is based on a quite com­ mon understanding that nonmonotonic reasoning uses not only known facts, but also defaults or expectations we have about the world. Such defaults are used as auxil­ iary assumptions that allow us to 'jump' to useful conclu­ sions and beliefs that are not logical consequences of the facts alone. Such conclusions are defeasible and can be retracted when further facts become known. This indi­ cates that our epistemic states can be seen as structured entities determined, or generated, by admissible sets of defaults. Furthermore, our defaults and expectations are often conflict with each other, and this may create situ­ at ions in which we have a number of different plausible 'views of the world '. Such situations are actually quite common in nonmonotonic reasoning. In addition, not all defaults or expectations are· equally plausible or accept­ able, and this creates, in turn, priorities and preferences among otherwise admissible combinations of defaults. If we identify each such admissible set of defaults with the (deductively closed) set of its consequences, we will ar­ rive at the following picture:

Definition 3.1. An epistemic state £ is a triple (5,-< , l) , where S is a set of objects called admissible belief states, -< is a preference relation on S, while l is a la­ beling function assigning each admissible state a deduc­ tively closed theory.

Epistemic states turn out to be quite similar to prefer­ ential models of Makinson [Makinson, 1994] and cumu­ lative models from [Kraus et al., 1990]. Indeed, labeling with a deductively closed theory can be equivalently de­ scribed using labeling with a set of worlds, as in [Kraus et al., 1990] (see [Dix and Makinson, 1992] for the rela­ tion between these two kinds of representation). Epis­ temic states in which l is an injective function will be called standard. Clearly, for standard epistemic states, admissible belief states can be safely identified with their associated theories. So, a standard epistemic state can be described as a pair (T, -<), where T is a set of deduc­ tively closed theories and -< is a preference relation on T.

A state s E S will be said to support a proposition A if A E l(s) . A state s will be said to be consistent with A if ·A (/_ l( s). The set of states consistent with A will be denoted by (A).

According to [Kraus et al. , 1990], a subset P of states is called smooth with respect to -< if, for any s E P, either s is -<-minimal in P or there exists t -< s such that t is -<-minimal in P. An epistemic state will be said (negatively) smooth if any set of states (A) is smooth.

Skeptical and credulous validity. The informal un­ derstanding of epistemic states, sketched earlier, gives raise to the notions of skeptical and credulous validity, given below. To begin with, A sceptically entails B if all preferred sets of defaults that are consistent with A, taken together with A itself, logically imply B. This leads to the following definition of skeptical validity that is somewhat different from the standard one, given in [Kraus et al., 1990].

Definition 3.2. A conditional A f-.- B will be said to be sceptically valid in an epistemic state £ if all preferred states in (A) support A ---> B.

Similarly, A credulously entails B if A allows to explain B in the sense that there exists a preferred set of defaults that is consistent with A and, taken together with A, will logically imply B . An inessential modification of this description will give us

Definition 3.3. A conditional A f-.- B will be said to be credulously valid in an epistemic state £ if either (A) is empty or at least one preferred state in (A) supports A---> B .

We will provide below a syntactic characterization for the above two kinds of validity.

4 Basic inference r elation

As we mentioned, credulous nonmonotonic inference in­ validates the basic postulates of skeptical nonmonotonic inference, such as Cut , Cautious Monotony or And. This means that in order to obtain a broader picture of non­ monotonic inference that would encompass both credu­ lous and skeptical kinds, we need to find an alternative ground for classifying inference relations. Below we take as a basis a system suggested in [Benthem, 1984]. The latter will give us a rather rich and neat picture that avoids complications and fancy elaborations created by alternative approaches.

The main idea behind van Benthem's approach is that a conditional can be seen as a special kind of a gen­ eralized quantifier representing a relation between the respective sets of instances or situations supporting its premise and conclusion. In this setting, the nature of a conditional can be described in terms of possible changes made to these sets of situations that still preserve its va­ lidity. Such changes can involve adding new confirming instances, deleting refuting ones, etc. As is shown in [Benthem, 1984], this naturally leads to the set of pos­ tulates, given below.

By a basic inference relation B we will mean a relation on propositions satisfying the following postulates:

(Reflexivity) A f-.- A;

(Left Logical Equivalence) If F= A <--+ B and A f-.- C, then B f-.- C ; '

(Right Weakening) If A f-.-Band B F= C , then A f-.- C;

(Antecedence) If A f-.- B , then A f-.- A 1\ B;

(Deduction) If A 1\ B f-.- C, then A f-.- B -+ C;

(Conjunctive Cautious Monotony) If A f-.- B 1\ C, then A 1\ B f-.- C.

The most salient feature of the above list is that all the above postulates involve no more than one conditional premise. Consequently, the system says nothing about how to combine different conditionals . As a result , a conditional is derivable in B from a set of conditionals only if it is derivable from one of them. The following result gives a direct characterization of this derivability relation. 1

Theorem 4.1. C f-.- D is derivable from A f-.- B in B iff either C F= D , or A 1\ B F= C 1\ D and C 1\ ·D F= A 1\ ·B.

Using the terminology of [Benthem, 1984], the above theorem says that a conditional implies another one if all confirming instances of the former are confirming in­ stances of the latter and all refuting instances of the latter are refuting instances of the former .

As we will see, the system B is sufficiently powerful to capture exactly the one-premise fragment of both credu­ lous and skeptical inference relations , and hence can be seen as their common core.

Regularity. An inference relation will be called reg­ ular if it satisfies t he rules of B and the following rule (where f denotes an arbitrary contradiction):

The conditional A f-.- f says, in effect, that A is seen as impossible with respect to the inference relation , that is, no imaginable situation assumed by f-.- is compatible with A. It is reasonable to conclude then that ·A should hold in all situations, and consequently it can be conjoined to consequences of any proposition.

Duality. It turns out that , for any regular inference relation f-.- we can define a dual inference relation as fol­ lows:

1 Due to space limitations , we omit all proofs.

The above notion of duality can be seen as an ab­ stract form of the relation between ordinary conditionals and their corresponding might-conditionals, well-known in the literature on conditional logic at least since the time of David Lewis.

The following result can be proved by a straightfor­ ward check of the relevant rules. It shows that the set of regular inference relations is closed with respect to taking duals.

Theorem 4.2. If f-.- is a regular inference relation, then f-.- 0 is also a regular inference relation. Moreover, f-.- 0 0 coincides with f-.-.

5 Credulous nonmonotonic inference

In this section we will give a characterization of a basic credulous inference relation.

Definition 5.1. A nonmonotonic inference relation will be called credulous if it is regular and satisfies Rational Monotony:

So, credulous inference is a subsystem of rational in­ ference from [Kraus et al., 1990]. As we will see, the latter can be obtained simply by adding the rule And.

The following theorem shows that the semantic defi­ nition of credulous validity, given earlier , determines a credulous inference relation.

Theorem 5.1. If [ is a smooth epistemic state, then the set of conditionals that are credulously valid in [ forms a credulous inference relation.

In the next section we will show that our postulates provide a complete description of credulous validity.

6 Credulous inference generated by consequence relations

In this section we introduce an alternative representation of credulous inference relations as generated by supra­ classical Tarski consequence relations.

For any supraclassical consequence relation define the following inference relation:

As can be easily seen, A f-.-~ B holds if either no the­ ory of 1-- is consistent with A or A -+ B belongs to at least one maximal theory of 1-- that is consistent with A. Now we may consider the set of theories of 1-- as a standard epistemic state ordered by set inclusion. Then the above description will immediately give us that the above definition provides a description of a credulous in­ ference with respect to this epistemic state. As a result , we obtain the following

Corollary 6.1. If 1-- is a supra classical consequence re­ lation, then f-.-~ is a credulous inference relation.

It turns out that a credulous inference relation deter­ mines, in turn, its generating Tarski consequence relation via the following equivalence:

The following result shows that Tarski consequence relations are strongly equivalent to credulous inference relations.

Theorem 6.2. 1. Iff- is a supraclassical consequence relation, then h- is a credulous inference relation. M arcover, the corresponding consequence relation determined by (CI} coincides with f-.

2. If r- is a credulous inference relation, then f-r- is a supraclassica/ consequence relation. M arcover, the credulous inference relation generated by f-r- via (IC) coincides with r- .

An important consequence of the above result is that any credulous inference relation is generated by an epis­ temic state (corresponding to theories of the associated consequence relation). Therefore, we have the following

Representation Theorem 1. An inference relation r­ is credulous if and only if there exists a smooth epistemic state £ that credulously validates conditionals from r-.

7 Credulous inference based on expectations

There exists a strong connection between the above rep­ resentation of credulous inference in terms of conse­ quence relations and representation of nonmonotonic in­ ference relations based on expectation orders described in [Giirdenfors and Makinson, 1994] .

At the beginning of their paper, Gardenfors and Makinson suggested two general ways of understanding nonmonotonic inference. The first formulation was as follows:

A nonmonotonically entails B iff B follows log­ ically from A together with "as many as possi­ ble" of the set of our expectations as are com­ patible with A.

On the other hand, expectations can be reflected in the form of an ordering between propositions, and then this relation can be used in the nonmonotonic inference as follows:

A nonmonotonically entails B iff B follows log­ ically from A together with all those proposi­ tions that are "sufficiently well expected" in the light of A.

As was rightly noted by the authors, though the two ideas are closely related, the former tends to suggest a multiplicity of possible sets of auxiliary premises, while the second formulation points towards a unique set of such premises. In other words, the first formulation ad­ mits a credulous reading, while the second formulation is primary a skeptical one. Nevertheless, the authors have shown that the two formulations can be 'reconciled' in a single framework. As we will see, however, this possi­ bility depends on a particular structure of expectations chosen that gives rise to rational inference relations; for the latter, credulous validity will actually coincide with the skeptical one.

As we mentioned, a supraclassical consequence rela­ tion (viewed as a binary relation among propositions) is actually a 'partial' generalization of an exrectation or­ der from [Giirdenfors and Makinson, 1994 . Moreover, the above definition (IC) of credulous inference relation generated by a consequence relation can be equivalently expressed as follows:

As was shown in [Gardenfors and Makinson, 1994], Theorem 3.5, the above description is equivalent to the 'standard' definition of expectation inference relations. Thus, our notion can be considered as a generalization of the corresponding interpretation for expectation in­ ference given in [Gardenfors and Makinson, 1994] . In­ formally, it corresponds to the following modification of the second formulation above:

A nonmonotonically entails B if B follows logi­ cally from A together with some consistent set of propositions that are "sufficiently well ex­ pected" in the light of A.

8 Permissive inference

In this section we will describe another interesting kind of brave nonmonotonic inference.

Definition 8.1. An inference relation will be called per­ missive if it satisfies the basic postulates and the Cut rule:

(Cut) If Ar-B and A 1\ B r-c, thenAr- C.

It can be shown that, in the context of B, Cut implies the rule Or:

The following theorem gives a more 'traditional' char­ acterization of permissive inference relations :

Theorem 8.1. Permissive inference relations are com­ pletely characterized by the postulates Reflexivity, Left Logical Equivalence, Right Weakening, Conjunctive Cau­ tious Monotony, Cut and Or.

If we compare the above list of postulates with the characterization of pr~ferential inference, given in [Kraus et a/. , 1990], we can notice that the distinction of per­ missive inference from preferential one amounts simply to replacement of standard Cautious Monotony by Con­ junctive Cautious Monotony. Still, permissive inference is not skeptical, since it does not satisf$ And.

The following result shows that permissive and cred­ ulous inference relations are duals.

Theorem 8.2. r- is a permissive inference relation iff r- 0 is a credulous inference relation.

Using the above duality, we can immediately obtain the following semantic characterization of permissive in­ ference in epistemic states:

Definition 8.2. A conditional A f-.- B will be said to be permissively valid in an epistemic state [ if any preferred state in (A) is consistent with A 1\ B.

So, permissive conditional says informally "A is nor­ mally consistent with B".

Again, the duality of credulous and permissive infer­ ence immediately implies that any supraclassical conse­ quence relation generates a permissive inference relation VIa

and that any permissive inference relation can be pro­ duced in this way from some consequence relation.

X-logics. [Siegel and Forget, 1996) suggested a new de­ scription of nonmonotonic inference relations that they called X-logics. For any set of propositions X, they de­ fined an inference relation f- x as follows:

A detailed study of such inference relations and their use for describing circumscriptions is given in [Moinard and Rolland, 1998). The latter authors have established, in effect, that any X-logic is a permissive inference re­ lation in our sense. Actually, the following result shows that, for finite languages, the two notions turn out to coincide.

Theorem 8.3. Any X-logic is a permissive inference re­ lation. Moreover, for any permissive inference relation f-.- in a finite language there exists a set of propositions X such that f-.- coincides with f-x.

Since any preferential inference relation is permissive, the above result immediately implies that in the finite case any preferential inference relation will also coincide with some X-logic.

9 Preferential and rational inference relations

Preferential inference relation P from [Kraus et al., 1990) can be obtained by adding the rule And to the postulates of B.

It has been shown already in [Adams, 1975) that the condition described in Theorem 4.1 is actually necessary and sufficient for 'one-premise' derivability in preferen­ tial inference relations. Consequently, we immediately obtain that preferential inference is a 'conservative ex­ tension' of the derivability in B:

Theorem 9.1. A conditional C f-.- D is derivable from A f-.- B in P if and only if it is derivable already in B.

The next result shows that our modified definition of skeptical validity is nevertheless adequate for character­ izing preferential inference.

Representation Theorem 2. An inference relation f-.­ is preferential iff there exists a smooth epistemic state [ that sceptically validates conditionals from f---.

As a result, both skeptical and credulous inference ac­ quire a semantic representation in the same framework of epistemic states. We will use this fact in the next section.

Rational inference. Rational inference relations (see [Kraus et a/., 1990)) are preferential inference relations that satisfy also Rational Monotony. So, they are both credulous and skeptical, and hence obliterate, in effect , the distinction between skeptical and credulous infer­ ence. A semantic representation of such inference re­ lations can be obtained by restricting epistemic states to standard states in which the set of admissible theo­ ries is linearly ordered by set inclusion. As can be easily checked, a conditional A f-.- B will be sceptically valid in such a state iff it is credulously valid in it.

10 Interplay

In this section we will invariably use f-.- to denote a skep­ tical (preferential) inference relation, while f:i will denote a credulous inference relation.

Any epistemic state determines both a credulous and skeptical inference relation. Clearly, the two will be re­ lated. Below we will give a number of conditions that relate the two kinds of inference.

To begin with, skeptical consequences of some propo­ sition can always be added to its credulous consequences:

Lemma 10.1. If f:i and f-.- are, respectively, a credulous and skeptical inference relations determined by the same epistemic state, then

If A f-.- B and A f:i C, then A f:i B 1\ C.

Strengthening the Antecedent. There are some useful conditions allowing strengthening the antecedent for skeptical conditionals- a well-known problem for de­ feasible inference. To begin with, we have the following

Lemma 10.2. If f-.- and f:i 0 are, respectively, skeptical and permissive inference relation determined by some epistemic state, then

The above condition is a kind of a 'mixed' Cautious Monotony rule that is valid for any skeptical inference relation. In this rule the 'permissibility claim' A f:i° C serves precisely the same role as irrelevance conditions in [Geffner, 1992).

Unlike credulous inference, skeptical inference rela­ tions do not satisfy, in general, Rational Monotony. Still , the following lemma establish two weaker variants of 'ra­ tional monotony' that hold for skeptical inference rela­ tions and their credulous counterparts:

Lemma 10.3. If f-.- and f:i are, respectively, skeptical and credulous inference relation determined by some epistemic state, then

1. IfA'r--B andAii6--,C, thenAAC'r--B.
2. IfA'r--B andAf,<.---,C, thenA!\C~B.

The last condition above is especially interesting, since it describes a transition from skeptical to credulous in­ ference. The following example of Nixon Diamond illus­ trates the use of these rules.

Example 1 0.1. Let P, Q and R denote, respectively, "Nixon is a pacifist", "Nixon is a quaker" and "Nixon is a republican" . Assume that Q 'r--P and R 'r-- --,p are sceptically acceptable conditionals. Then if Q and R are compatible, that is Q f?<- --,Rand R f?<- --,Q, we can use the above rule to conclude both Q !\ R ~ P and Q !\ R ~ --,p. Thus, in this situation we can credulously infer incom­ patible conclusions.

Credulous rules as defeaters. Credulous inference rules A ~ B can be considered as might-conditionals say­ ing that if A holds then it might be the case that B. Such conditionals play an important role in Nute's de­ feasible logic [Nute, 1990] where they function primarily as def eaters that block applications of skeptical defeasi­ ble rules. This function can be justified via the following condition relating skeptical inference and its counterpart credulous inference:

If A~ --,Band A 17bf , then A f?<- B.

The above condition says that if, given A, it might be the case that --,B , then A should not sceptically entail B. Actually, instead of credulous inference in the above condition, we could as well use permissive inference. So, brave inference rules can indeed function as defeaters of ordinary skeptical rules.

11 Conclusion and perspectives

The main conclusion of this study is that credulous nonmonotonic inference admits a rigorous semantic and syntactic characterization. . Moreover, both credulous and ordinary skeptical inference are representable in the same semantic framework of epistemic states.

As is well-known, common systems of skeptical infer­ ence, namely preferential and rational entailment , are too weak (too skeptical) to account for some natural forms of defeasible inference. In this respect, the most promising perspective suggested by the present study (briefly sketched in the last section) consists in a joint use of skeptical and brave inference rules in order to achieve a more fine-grained representation framework for nonmonotonic inference. As has been shown in the last section, brave inference rules can be used both for de­ riving new plausible skeptical inferences and for defeat­ ing implausible ones. Accordingly, brave conditionals can be used as additional assumptions that allow, e.g., strengthening antecedents of skeptical rules with irrele­ vant propositions or sanction certain instances of tran­ sitive chaining for such rules, etc. In short, brave infer­ ence can facilitate skeptical one in order to achieve an adequate representation of defeasible inference. Further work is needed, however, in order to clarify the perspec­ tives of this approach.