# simple_conditionals_with_constrained_right_weakening__3f8031cb.pdf

Simple Conditionals with Constrained Right Weakening

Giovanni Casini1 , Thomas Meyer2 and Ivan Varzinczak3

1CSC, University of Luxembourg, Luxembourg 2CAIR, University of Cape Town, South Africa 3CRIL, Universit e d Artois & CNRS, France giovanni.casini@uni.lu, tmeyer@cs.uct.ac.za, varzinczak@cril.fr

In this paper we introduce and investigate a very basic semantics for conditionals that can be used to define a broad class of conditional reasoning systems. We show that it encompasses the most popular kinds of conditional reasoning developed in logic-based KR. It turns out that the semantics we propose is appropriate for a structural analysis of those conditionals that do not satisfy the property of Right Weakening. We show that it can be used for the further development of an analysis of the notion of relevance in conditional reasoning.

1 Introduction The structure if C, then D is omnipresent in communication and cognition. It is generally considered as one of the building blocks of reasoning and its formalisation in logics. An if-then connection can be of many different types: For every triple of natural numbers x, y, z, if x > y and y > z, then x > z , Birds usually fly , If you have had alcohol, you should not drive , If you throw a stone against that window, then you will break it , If you go out in this weather, you will probably get a cold , If I were you, I wouldn t do that . From these examples it is clear that a conditional connection between propositions can be associated with different modalities. This includes necessity, presumption, deontic, causal, probabilistic, and counterfactual. In this paper we investigate a semantic characterisation of a basic and general class of conditionals. For such a class to be viewed as sufficiently general, it needs to include the existing popular classes of conditionals that have been proposed. We use choice functions ranging over possible worlds, a very general formal tool that has been used for characterising conditional reasoning [Rott, 2001]. It turns out that the framework we propose is also appropriate for modelling some constraints related to the problem of relevance. More specifically, it provides the basis for a structural analysis of conditionals that do not satisfy the property of Right Weakening. The basic idea of a conditional is very simple: C D is read as if the condition C holds, then the effect D holds with a certain modality . An important question in the area of Knowledge Representation (and the related field of Philosophical Logic) is the study of appropriate formalisations of

the different kinds of modality necessary for the characterisation of important reasoning behaviours. In order to model conditional reasoning, there is usually a focus on two main aspects that need to be formalised:

1. The existence (or non-existence) of a connection between a specific type of condition and a specific type of effect (both represented by propositions).

2. The modality of such a connection (necessity, presumption, probability, preference, .. . ).

But there is also a third aspect that is frequently neglected in this context:

3. The relevance of such a connection.

The importance of relevance in conditional reasoning has not gone unnoticed [Delgrande, 2011]. However what relevance means in the context of conditional reasoning remains vague. Before proceeding with the technical aspects of our contribution, we first provide an intuitive sense of our use of the term relevance in the present context. Most of the formalisations of conditional reasoning have been built using a possible-worlds semantics, referring more or less directly to classical modal operators. This approach has made it possible to define logical systems accounting for various kinds of non-classical reasoning in surprisingly efficient ways. On the other hand, relying on possible worlds, and consequently on closed logical theories, enforces some properties (e.g. logical omniscience) that can be in conflict with some modelling goals. One limit is that the possibleworlds approach to the formalisation of conditionals ( if a condition C holds, then an effect D holds with a certain modality ) tries to account for the degree of (epistemic or factual) necessity which is associated with the truth of D given the truth of C, but it does not account for whether the truth of D given the truth of C has any relevance for the kind of reasoning we are considering. Examples from deontic or causal reasoning can illustrate the point.

If you are involved in a car accident, you should remain on the spot is an acceptable norm, but If you are involved in a car accident, you should remain on the spot or paint yourself in blue is not as acceptable.

If you turn the wheel of a moving car, the car will move in a circle is meaningful, while If you turn the wheel

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

of a moving car, the car will move is not really that meaningful.

If you throw a stone against the window, it will break is meaningful, but If you throw a stone against the window, it will break or Ann will drink tea is not.

For all these examples, if we use a possible-worlds semantics to model the conditionals, the truth of the first conditional implies the truth of the second one (see the following section). But, even though this can be reasonable from a purely truththeoretical point of view, if we want to determine what our obligations are in case of car accidents, or what the effects of turning the car wheel are, or those of throwing a stone, the second conditional in each example has to be considered irrelevant, if not misleading. The semantics we propose still uses possible worlds, but allows us to define reasoning patterns that do not enforce the kind of problematic derivations indicated above. The paper is organised as follows. In Section 2 we investigate the problem more formally and propose a first semantic construction. Section 3 shows how to take back popular properties of conditional reasoning, while Section 4 introduces an even more basic form of conditional reasoning. In Section 5 we investigate different forms of closures of conditional bases. Related Work and Conclusions follow.

2 The Formal Framework We use a simple conditional language, containing only conditionals of the form C D without the possibility of nesting the conditionals or combining them via propositional operators. This is in line with the so-called KLM approach [Kraus et al., 1990] or the I/O logics [Makinson and van der Torre, 2000]. This choice of language provides for a framework that combines simplicity and generality, and allows for extending the work presented here to richer conditional languages. We use a finitely generated propositional language L, with the operators , , , , , having their usual meaning. Capital letters C, D, . . . will be used to refer to the propositions. Cn indicates classical propositional consequence, with being the corresponding consequence relation. W will be used to denote the set of valuations (possible worlds) generated by L, while [C]W is the set of valuations in W satisfying a formula C (we omit the subscript whenever the context allows for it). ˆV indicates a (canonical) formula characterising a set of valuations V . W.l.o.g., W could be a subset of the propositional valuations generated by L, and Cn and the supraclassical monotonic consequence operation and relation generated by W. Our language will be L , the conditional language built on top of L: L def {C D | C, D L}. As indicated in Section 1 we define a possible-worlds semantics, using choice functions as the constructions within the framework. The essential information conveyed by a conditional If C, then D is if the condition C holds, then the effect D holds (with a certain modality) . Hence, the basic construction of a conditional system will simply associate to each condition the set of its effects. Definition 1. An effect function is a function

f+ : 2W 2(2W).

A standard conditional interpretation is a pair

I = (W, f+). I +-satisfies a conditional C D (I + C D) if there is a V f+([C]) s.t. V [D].

This function associates with each condition (a propositional theory, that is, a set of valuations) a set of effects (a set of propositional theories, that is, a set of sets of valuations). For example, a set of conditionals {C D, C E, F G} would be +-satisfied by an interpretation I = (W, f+) s.t. f+([C]) = {[D], [E]}, f+([F]) = {[G]} and f+([H]) = for every H s.t. (H C) (H F). This brings us to our first representation result. It is easy to prove that the class of the standard conditional interpretations can be used to characterise the set of conditionals closed under two basic structural properties, Left Logical Equivalence and Right Weakening:

C D, C E D E (LLE); C D, D E C E (RW)

Theorem 1. A set of conditionals C is closed under (LLE) and (RW) iff there is a standard interpretation I = (W, f+) s.t. C = {C D | I + C D}.

Proof. We omit the proof from right to left. From left to right: let C be a set of conditionals closed under (LLE) and (RW). We need to define an interpretation I = (W, f+) s.t. I + C D iff C D C. Let AC def {C | there is a D s.t. C D C} (the set of all conditions appearing in C) and EC(C) def {D | C D C} (the effects of a condition C according to C). For every propositional formula C do the following: If C / AC , set f+(C) = . If C AC, then set the functions as follows: Let be the partial order on L determined by logical strength, that is, C D iff C D, while MC def max> (EC(C)) (the set of the logically strongest formulas in EC(C)). Set f+([C]) = {[D] | D MC}. Next easy steps: prove that for every conditional E F, I E F iff E F can be derived from (LLE) and (RW) from some C D s.t. C AC and D MC. Then prove that the same holds for all the E F C.

This class of conditionals is quite broad, and imposes a minimal number of constraints. It represents the idea that a conditional simply associates a condition with a set of effects, and we check what holds in the valuations satisfying such effects. By using this as a starting point, and then adding constraints to the choice functions, we get semantic characterisations of many interesting classes of conditionals that have been studied in the literature (see Section 3). But (RW) holds even in this broad, basic, class of conditionals. The counter-intuitive nature of the conditionals in the examples in Section 1 are due precisely to the validity of (RW). The statement remain on the spot or paint yourself in blue is a logical consequence of remain on the spot . Similarly, moving is a consequence of moving in circle , while the window will break or Ann will drink a tea is a consequence of the window will break . The satisfaction of (RW) is directly connected to the use of a possible-worlds framework.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

Because of this, some researchers advocating for alternative kinds of semantics have suggested that the possible-worlds approach is inherently problematic since it contains the assumption that all conditionals bear a truth value [Parent and van der Torre, 2014, p.1]. On the other hand, the core idea underlying the possible-worlds approach (modelling our reasoning referring to what holds in specific sets of conceivable situations) has some important advantages: it appears intuitive, it is general and powerful, and it is a well-developed field of investigation that offers to the user a full set of axiom schemas that can be modified and extended easily. That is, it provides simple and useful investigative tools. So, should we abandon the possible-worlds paradigm when it comes to conditional reasoning? Our response to this question is that the better course of action is to investigate ways of fitting very basic forms of conditional reasoning, possibly not satisfying (RW), into the formal possible-worlds framework. Interestingly enough, constraining (RW) is analogous to the placing of constraints on the property of Monotonicity. In both cases we are dealing with constraints on the transitivity of the if-then connections:

C D, D E C E (Mon); C D, D E C E (RW)

When constraining (Mon), we deal with conditional transitivity on the condition (on the left). In contrast, when constraining (RW) we deal with conditional transitivity on the effect (on the right). In non-monotonic reasoning the most interesting systems do not aim at arbitrarily invalidating Monotonicity. Instead, a rational agent should reason assuming that Monotonicity holds, and only the explicit knowledge that some situation is exceptional should prevent it from reasoning monotonically. For example, if I know that birds typically fly I conclude that robins, seagulls, and eagles fly, since I am not informed of anything to the contrary. Moreover, only the explicit knowledge that penguins do not fly prevents me from reasoning monotonically about the flying abilities of this subclass of birds [Lehmann and Magidor, 1992; Lehmann, 1995; Pearl, 1990]. The same principle can be applied to Right Weakening. (RW) is a natural reasoning pattern, and an agent should persistently apply it unless it is explicitly aware of the fact that the derived conditional would be not relevant. In order to model irrelevance we introduce a second function.

Definition 2. A relevance function is a function

f : 2W 2(2W). A conditional interpretation is a triple

I = (W, f+, f ). I -satisfies a conditional C D (I C D) if

there is a V f+(C) s.t. V [D]W;

for every V f (C), V [D]W.

The relevance function f associates with a condition C a set of formulas that is considered to be irrelevant w.r.t. C. Informally, this new notion expresses the intuition that we apply (RW) if we are not explicitly aware that it is irrelevant. For example, if f+([C]) = {[D]} and f ([C]) = {[(D E F)]}, then the interpretation -satisfies C D, C (D E), and C (D F), but not C (D E F) or C

Figure 1: A conditional interpretation I = (W, f+, f ) s.t. f+([C]) = {[D]} and f ([C]) = {[(D E F)]}. It -satisfies all the conditionals C H s.t. H is in the grey area on the right.

(D E F G), since (D E F) is an irrelevant formula and (D E F G) is the consequence of an irrelevant formula. As shown in Figure 1, the set of -satisfied conditionals is {C H | H Cn(D) \ Cn(D E F)}. Clearly the satisfaction relation does not satisfy (RW), but the property of Right Logical Equivalence continues to hold, though. C D, D E C E (RLE) Important, (RW) is not abandoned completely: it is replaced with the weaker property of Anti Right Weakening: C D, D E, E F, C E

C F (Anti RW)

or, equivalently: C D, D E, E F, C F

C E (Anti RW ) (Anti RW) states that, once (RW) is blocked for a formula, it is blocked for all the implied formulas. Suppose that If you throw a stone at the window, it will break is satisfied by an interpretation while If you throw a stone at the window, it will break or Ann will drink a tea is not. Then If you throw a stone at the window, it will break or Ann will drink a tea or the sun will rise tomorrow cannot be satisfied either. (Anti RW) implies (RLE): just set F as D in the (Anti RW ) schema. Hence every set of conditionals closed under (Anti RW) is closed also under (RLE). We now obtain our second representation result: using the satisfaction relation , the class of conditional interpretations characterises the class of sets of conditionals closed under (LLE) and (Anti RW).

Theorem 2. A set of conditionals C is closed under (LLE) and (Anti RW) iff there is a conditional interpretation I = (W, f+, f ) s.t. C = {C D | I C D}.

Proof. From right to left, we need to prove that (Anti RW) holds. Assume D E, E F, I C D and I C E. Then there is a V f+([C]) s.t. V [D] [E] [F]. This, together with I C E, implies that there is a V f ([C]) s.t. V [E], that in turn implies V [F]. V [F] and V [F] imply I C F. From left to right: let C be closed under (LLE) and (Anti RW). We define I = (W, f+, f ) as follows. Let AC, EC(C), , and MC be defined as for Theorem 1. For every propositional formula C do the following: If C / AC , let f+([C]) = . If C AC, then set the functions as follows. Let RC = {Cn(D) | D MC} and f+([C]) = {[D] | D MC}

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

(RC is the smallest set of theories containing EC(C)). Let SC = S RC \ EC(C) (SC is the set of all formulas that are satisfied by the theories in f+(C) but are not relevant). Let max (SC) be the set of the strongest logical formulas in SC, and set f (C) = {[D]W | D max (S)}. Next easy step to prove: since C is closed under (Anti RW), I = (W, f+, f ) is a characteristic model of the set of conditionals C.

3 Richer Conditionals

The satisfaction relation over conditional interpretations is general enough to be able to accommodate many wellknown forms of conditional reasoning. In fact, many such forms of conditional reasoning can be characterised by imposing further constraints on the functions f+ and f . Here we examine the introduction of a few important properties. First, in order to characterise the closure under (LLE) and (RW), it is sufficient to set that for every formula C, f ([C]) = (1)

Theorem 3. A set of conditionals C is closed under (LLE) and (RW) iff there is a conditional interpretation I = (W, f+, f ) satisfying Constraint (1) s.t. C = {C D | I C D}.

We omit the proof, since it is immediate to see that there is a full correspondence between the class of conditional interpretations satisfying Constraint (1) and the class of standard interpretations. Hence Theorem 1 applies. Next, the property of Conjunction on the Right, C D, C E C (D E) (And),

can be obtained by imposing that we have at most one theory describing the effects of a condition. That is, for every formula C, #(f+([C])) 1 (2)

Theorem 4. A set of conditionals C is closed under (LLE), (Anti RW) and (And) iff there is a conditional interpretation I = (W, f+, f ) satisfying Constraint (2) s.t. C = {C D | I C D}.

Proof. From right to left. If I C D and I C E, then the only set V f+([C]) is such that V [D], V [E] and there is no theory V f ([C]) s.t. V [D] or V [E]. That implies that V [D] [E] and there is no theory V f ([C]) s.t. V [D] [E], that is, I C (D E). From left to right. Let C be closed under (LLE), (Anti RW) and (And), and let AC, EC(C), and MC be defined as for Theorem 1. Due to (And), for every C AC there is only one formula D in MC (modulo logical equivalence.). Using the same construction used for Theorem 2 we can build the characteristic model.

Next, we observe that for consistency preservation, C C (Cons)

it is sufficient to impose that If [C] = , then / f+([C]). (3)

Continuing, we observe that for Reflexivity (C C) to be satisfied, we simply need to impose that for every C,

there is a V f+([C]) s.t. V [C]; there is no V f ([C]) s.t. V [C]. (4)

And for Monotonicity (Mon) to hold, it is sufficient to impose that for every C, D s.t. C D,

for every V f+([D]) there is a V f+([C]) s.t. V V ;

for every V f ([C]) there is a V f ([D]) s.t. V V. (5)

Theorem 5. A set of conditionals C is closed under (LLE), (Anti RW) and (Mon) iff there is a conditional interpretation I = (W, f+, f ) satisfying Constraint (5) s.t. C = {C D | I C D}.

Proof. From right to left the proof is straightforward. From left to right, let C be closed under (LLE), (Anti RW) and (Mon), and let AC, EC(C), and MC and SC be defined as for Theorems 1 and 2. Let I be defined as in the proof of Theorem 2. I is a characteristic model of C. We need to prove that I satisfies Constraint 5. Let C D. To have (Mon) it is necessary that for every formula E in MD there is a formula F in MC s.t. F E, and this enforces the first part of Constraint (5). For the second part of the constraint, assume it is not satisfied, that is, assume that for some V f (C) there is no V f (D) s.t. V V . According to the construction of I, this implies that there is a formula H in max (SC) that is not implied by any formula I in max (SD) which, in turn, implies that I D H while I C H, contradicting (Mon).

If the properties (And) and (RW) are satisfied, then to add (Mon) we just require that if C D, then V V , with f+(C) = {V } and f+(D) = {V }. Finally, assuming (And) and (RW), the question of how to impose the satisfaction of relevant properties has already been thoroughly investigated by Rott [2001, Chapter 7], and we will investigate in future work how to enforce such properties in our framework.

4 Dropping Anti Right Weakening Is (Anti RW) a reasonable property? It certainly makes sense for some versions of conditional reasoning. A good example is a basic commonsense notion of causality. Given some context, C causes D (C D) iff D would be true in case C were true, but it would not necessarily hold in the absence of C. This could be modelled in the present framework as follows: f+([C]) corresponds to the set of situations associated with the occurrence of C, while f ([C]) corresponds to the set of situations associated with the non-occurrence of C. For example, assume that our background theory contains some basic astronomical notions, such as that we consider it impossible that the sun will not rise tomorrow ( sun tomorrow). Also we know that the passage of the moon in front of the sun will cause an eclipse phenomenon. That is, passage moon eclipse. We can define, for example, a conditional interpretation I = (W, f+, f ) s.t. W [sun tomorrow] (since sun tomorrow), f+([passage moon]) = {V}

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

s.t. V [eclipse] and f ([passage moon]) = {V } s.t. V [ eclipse], with both V and V nonempty. By Definition 2, we have I passage moon eclipse. However, since in every valuation the sun will rise tomorrow (W [sun tomorrow]), we have V, V [sun tomorrow], and consequently V, V [eclipse sun tomorrow]. Given I, despite V [eclipse sun tomorrow], by Definition 2 we have I passage moon eclipse sun tomorrow, because V [eclipse sun tomorrow] too, that is, despite we believe that the passage of the moon in front of the sun causes an eclipse (passage moon eclipse), we do not believe that the passage of the moon in front of the sun causes an eclipse or that the sun will rise tomorrow (passage moon eclipse sun tomorrow). Furthermore, the same will hold for all the formulas implied by (eclipse sun tomorrow). If (eclipse sun tomorrow) holds independently from passage moon, then so does (eclipse sun tomorrow Ann has tea), and passage moon (eclipse sun tomorrow Ann has tea) should not hold. This is exactly what (Anti RW) imposes. On the other hand, (Anti RW) seems to be too strong a constraint in other contexts. To see, consider conditional desires as an example. After her high-school diploma (hsd), Ann would like to get a college degree (cd), that is, hsd cd. To get a college degree it is necessary to go to a college (gc), have enough money (m) to pay the tuition fees, and study hard (sh), that is, cd gc m sh. Ann would like to have money and to go to college (hsd m gc), but she does not like the idea of studying hard, even if associated to having money (hsd m sh). But for sure Ann would like to have money (hsd m). This set of conditionals is not compatible with (Anti RW): if hsd gc is satisfied, but hsd m sh is not (where cd gc m sh), then (Anti RW) imposes that also hsd m cannot be satisfied. (Anti RW) holds because the relation allows for the blocking of the weakening of the formulas associated with the sets of valuations in f+([C]) using the formulas associated with the sets of valuations in f ([C]). However, the same does not hold in the other direction: once a theory is indicated as irrelevant by f ([C]), the definition of does not allow us to conclude that information implied by some theory in f ([C]) is relevant. One way of resolving this issue is to refine the satisfaction mechanism in , allowing for a richer interaction between the theories in f+( ) and the ones in f ( ). In order to do that, we introduce a notion of inferential closeness between formulas based on their logical strength. Given C, D, E, we say that D is inferentially at least as close as E to C (D C E) if E D and D C. For the strict relation, D is said to be inferentially closer than E to C (D >C E) if E D, D E, and D C, that is, to infer C from E it is necessary to pass by the information represented by D. Semantically, D >C E corresponds to saying that [E] [D] [C], as shown in Figure 2. Using the notion of inferential closeness, we refine the interaction between f+( ) and f ( ) by requiring that (RW) on a formula D is blocked only in case for every formula represented in f+([C]) and implying D there is a formula represented in f ([C]) that is inferentially closer to D. That is, if we can derive C D from C E by (RW), such a

Figure 2: Both D and E imply C, but D is inferentially closer to C.

derivation is blocked only in case we know that C F is irrelevant, and F is inferentially closer to D than E.

Definition 3. Let I = (W, f+, f ) be a conditional interpretation. I -satisfies a conditional C D (I C D) if there is a V f+([C]) s.t. V [D]W ; and for every V f ([C]) s.t. V [D]W , ˆV C ˆV (that is, V V ).

Observe that allows to use conditional interpretations to model (and characterise) an elementary form of conditional reasoning. This brings us to our next representation result.

Theorem 6. A set of conditionals C is closed under (LLE) and (RLE) iff there is a conditional interpretation I = (W, f+, f ) s.t. C = {C D | I C D}.

Proof. We only consider from left to right, since the other direction is immediate. Let C be a set of conditionals closed under (LLE) and (RLE). Let AC and EC(C) be defined as for Theorem 1. For every propositional formula C do the following: If C / AC , set f+([C]) = . If C AC, then set the functions as follows: f+(C) = {V | there is a D EC(C) s.t. D ˆV }, and f (C) = {V | there is no D EC(C) s.t. D ˆV }. It is easy to prove that I = (W, f+, f ) is a characteristic model of C.

Observe further that, in order to recover (Anti RW), it is sufficient to impose the condition that for every formula C,

for every V f ([C]) there is no V f+([C]) s.t. V V (6)

Constraint (6) unlocks the next representation result.

Theorem 7. A set of conditionals C is closed under (LLE) and (Anti RW) iff there is a conditional interpretation I = (W, f+, f ) satisfying Constraint (6) s.t. C = {C D | I C D}.

Proof. From right to left, we need to prove that (Anti RW) holds. Let [D] f+([C]), and [D E] f ([C]); by Constraint (6) for every F, I C (D E F). From left to right, the interpretation defined in the proof of Theorem 2 does the job.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

5 Reasoning with Conditional Bases The next important issue is an investigation of entailment for conditional bases (any finite set B = {C1 D1, . . . , Cn Dn}). Given a conditional base and the representation results we obtained, what forms of entailment are appropriate? In this paper we consider only a classical Tarskian approach to entailment: B | C D if C D is satisfied by every model of B. Let us first check the case of . Definition 4. Let B be a conditional base. B | C D if for every conditional interpretation I, If I E F for every E F B, then I C D. Cn is the corresponding entailment operation:

Cn (B) = {C D | B | C D}. What kind of reasoning is sanctioned by this form of entailment? Lemma 1 shows that the properties we are considering are closed under intersection (proof omitted). Lemma 1. Let C and C be sets of conditionals closed under ( ), with ( ) {(LLE), (RLE), (RW), (Anti RW)}. Also C C is closed under ( ). Cn ( ) does a very simple thing: Cn (B) is the closure of B under (LLE) and (RLE). Theorem 8. Let B be a conditional base and C D be any conditional. C D Cn (B) iff C D can be derived from some E F B using (RLE) and (LLE). Proof. By Lemma 1, Cn (B) is closed under (LLE) and (RLE). We use a procedure analogous to the one used for Theorem 6 to build a model of B: it is sufficient to consider the set AB and the set EB(C) for every C AB, and treat the formulas modulo -equivalence. Such a model is the closure under (LLE) and (RLE) of B, hence it is the smallest model of B (in terms of the set of satisfied conditionals), and characterises Cn (B).

Next we consider what happens if we add (Anti RW). That is, if we refer to the satisfaction relation . Definition 5. Let B be a conditional base. B | C D if for every conditional interpretation I,

If I E F for every E F B, then I C D. Cn is the corresponding entailment operation:

Cn (B) = {C D | B | C D}. Given Lemma 1, Cn (B) must be closed under (LLE) and (Anti RW). (Anti RW ) can be used as a derivation rule. Theorem 9. Let B be a conditional base and C D be any conditional. C D Cn (B) iff C D can be derived from B using (Anti RW ) and (LLE). Proof. By Lemma 1, Cn (B) must be closed under (LLE) and (Anti RW). We build a model I of B using the following procedure: Let AB = {C | C C for some C s.t. C D B for some D} and let EB(C) = {D | C D B}. For every propositional formula C do the following: If C / AC, set f+(C) = . If C AC, then set the functions as follows: Let be defined as in Theorem 1, and let m C = min> (EC(C)). Set f+([C]) = {[D] | EC(C)} and f ([C]) = {[E] | D > E for some D m C}.

We need to prove three more easy things: that I is a model of B closed under (LLE) and (Anti RW); that I is the smallest (w.r.t. the set of satisfied conditionals) such model of B; that I C D iff C D can be derived from B using (LLE) and (Anti RW ).

We shall leave the investigation of more refined, non Tarskian forms of entailment as future work.

6 Related Work and Conclusions There have been many attempts to formalise the notion of relevance, but the version of relevance we consider here is quite different from that usually found in the literature. For example, there is a whole family of Relevant Logics [Restall, 2006], but their investigation of the notion of relevance departs from a more proof-theoretical perspective, aimed at modelling forms of entailment in which the antecedents play an active role in the derivation of the conclusion. In the area of conditional reasoning, Delgrande [2011] has stressed the importance of analysing relevance, and with Pelletier [1998] they investigated the notion of relevance. However, their focus is on the constraints on (Mon), rather than on (RW). Regarding logics that do not satify (RW), an interesting example by Parent and van der Torre [2014] proposes a deontic system satisfying only (RLE), based on the semantics of I/O logics. More in line with our semantic approach is the proposal by Britz et al. [2011], but they weaken (RW) with an approach that is different from the present one, and their system satisfies different properties. In this paper we have presented a possible-worlds semantics that allows us to avoid properties like (RW) or (And), classically associated with the possible-worlds approach. We have introduced (Anti RW), a constrained form of (RW), and we have initiated an investigation into basic forms of entailment in this framework. These are only first steps into this area, though, and much more work still needs to be done. To start off with, it is necessary to consider constrained versions of (RW) other than (Anti RW). It is also necessary to develop the investigation in Section 3 further. That is, to consider the interaction between and with the other structural properties. Similarly, we have only touched the surface when it comes to the investigation into entailment in Section 5. Finally, an interesting option would be the use of negated conditionals into the language, in which we explicitly represent the case where an agent considers some conditionals as not holding. This additional expressivity would allow us to define more interesting constrained versions of (RW). It could also be combined with forms of entailment that use negated conditionals to constrain monotonicity [Booth and Paris, 1998].

Acknowledgments G. Casini and T. Meyer received funding from the EU H2020 programme, Marie Skłodowska-Curie grant No. 690974 (MIREL). T. Meyer has been supported in part by the National Research Foundation of South Africa (grant No. UID 98019). The ideas in this paper have been developed during the Dagstuhl Seminars 19032 and 19072. We thank organisers and participants for the inspiring discussions.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

References [Booth and Paris, 1998] Richard Booth and Jeffrey B. Paris. A note on the rational closure of knowledge bases with both positive and negative knowledge. Journal of Logic, Language and Information, 7(2):165 190, 1998. [Britz et al., 2011] Katarina Britz, Johannes Heidema, and Ivan Varzinczak. Constrained consequence. Logica Universalis, 5(2):327 350, 2011. [Delgrande and Pelletier, 1998] James P. Delgrande and Francis J. Pelletier. A formal analysis of relevance. Erkenntnis, 49(2):137 173, Sep 1998. [Delgrande, 2011] James P. Delgrande. What s in a default? thoughts on the nature and role of defaults in nonmonotonic reasoning. In G. Brewka, V.W. Marek, and M. Truszczynski, editors, Nonmonotonic Reasoning. Essays Celebrating Its 30th Anniversary. College Publications, 2011. [Kraus et al., 1990] Sarit Kraus, Daniel Lehmann, and Menachem Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artif. Intell., 44:167 207, 1990. [Lehmann and Magidor, 1992] Daniel Lehmann and Menachem Magidor. What does a conditional knowledge base entail? Artif. Intell., 55:1 60, 1992. [Lehmann, 1995] Daniel Lehmann. Another perspective on default reasoning. Annals of Mathematics and Artificial Intelligence, 15(1):61 82, 1995. [Makinson and van der Torre, 2000] David Makinson and Leendert van der Torre. Input/output logics. Journal of Philosophical Logic, 29(4):383 408, 2000. [Parent and van der Torre, 2014] Xavier Parent and Leendert van der Torre. Sing and Dance! . In F. Cariani, D. Grossi, J. Meheus, and X. Parent, editors, Deontic Logic and Normative Systems, pages 149 165, Cham, 2014. Springer International Publishing. [Pearl, 1990] Judea Pearl. System Z: a natural ordering of defaults with tractable applications to nonmonotonic reasoning. In Proceedings of the 3rd Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 1990. [Restall, 2006] Greg Restall. Relevant and substructural logics. In D.M. Gabbay and J. Woods, editors, Handbook of the History of Logic, volume 7: Logic and the Modalities in the Twentieth Century, pages 289 398. Elsevier North Holland, 2006. [Rott, 2001] Hans Rott. Change, Choice and Inference: A Study of Belief Revision and Nonmonotonic Reasoning. Oxford University Press, 2001.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)