# conditional_inference_under_disjunctive_rationality__97e755b5.pdf

Conditional Inference under Disjunctive Rationality

Richard Booth1 Ivan Varzinczak2,3,4

1 Cardiff University, United Kingdom 2 CRIL, Univ. Artois & CNRS, France 3 CAIR, Computer Science Division, Stellenbosch University, South Africa 4 ISTI-CNR, Italy

boothr2@cardiff.ac.uk, varzinczak@cril.fr

The question of conditional inference, i.e., of which conditional sentences of the form if α then, normally, β should follow from a set KB of such sentences, has been one of the classic questions of AI, with several well-known solutions proposed. Perhaps the most notable is the rational closure construction of Lehmann and Magidor, under which the set of inferred conditionals forms a rational consequence relation, i.e., satisfies all the rules of preferential reasoning, plus Rational Monotonicity. However, this last named rule is not universally accepted, and other researchers have advocated working within the larger class of disjunctive consequence relations, which satisfy the weaker requirement of Disjunctive Rationality. While there are convincing arguments that the rational closure forms the simplest rational consequence relation extending a given set of conditionals, the question of what is the simplest disjunctive consequence relation has not been explored. In this paper, we propose a solution to this question and explore some of its properties.

Introduction The question of conditional inference, i.e., of which conditionals of the form if α then, normally, β should follow from a set KB of such sentences, has been one of the classic questions of AI, with several well-known solutions proposed (Goldszmidt, Morris, and Pearl 1993; Lehmann 1995; Lehmann and Magidor 1992; Pearl 1990; Weydert 2003). Since the work of Lehmann and colleagues in the early 90s, the so-called preferential approach to defeasible reasoning has established itself as one of the most elegant frameworks within which to answer this question. Central to the preferential approach is the notion of rational closure of a conditional knowledge base, under which the set of inferred conditionals forms a rational consequence relation, i.e., satisfies all the rules of preferential reasoning, plus Rational Monotonicity. One of the reasons for accepting rational closure is the fact it delivers a venturous notion of entailment that is conservative enough. Given that, rationality has for long been accepted as the core baseline for any appropriate form of non-monotonic entailment. Very few have stood against this position, including Makinson (1994), who considered Rational Monotonic-

Copyright c 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

ity too strong and has briefly advocated the weaker rule of Disjunctive Rationality instead, which says that if one may draw a conclusion from a disjunction of premises, then one should be able to draw this conclusion from at least one of these premises taken alone. This rule is implied by Rational Monotonicity and may still be desirable in cases where the latter does not hold. Quite surprisingly, the debate did not catch on, and, for lack of rivals of the same stature, rational closure has since reigned alone as a role model in non-monotonic inference. That used to be the case until Rott (2014) reignited interest in Disjunctive Rationality by considering interval models in connection with belief contraction. Inspired by that, here we revisit disjunctive consequence relations and introduce a suitable notion of disjunctive rational closure of a conditional knowledge base. We start by giving a summary of the formal background and of the rational closure construction. Then, in the following section, we make a case for weakening the rationality requirement and propose a semantics with an accompanying representation result for a weaker form of rationality enforcing the rule of Disjunctive Rationality. After this we investigate a notion of closure of (or entailment from) a conditional knowledge base under Disjunctive Rationality. Our analysis is in terms of a set of postulates, all reasonable at first glance, that one can expect a suitable notion of closure to satisfy. Following that we propose a specific construction for the Disjunctive Rational Closure of a conditional knowledge base and assess its suitability in the light of the postulates put forward in the previous section. We conclude with some remarks on future directions of investigation.

Formal Preliminaries Let P be a finite set of propositional atoms. We use p, q, . . . as meta-variables for atoms. Propositional sentences are denoted by α, β, . . ., and are recursively defined as usual: α ::= | | P | α | α α | α α | α α | α α. We use L to denote the set of all propositional sentences. With U def= {0, 1}P, we denote the set of all propositional valuations, where 1 represents truth and 0 falsity. We use v, u, . . ., possibly with primes, to denote valuations. We shall sometimes represent valuations as sequences of atoms (e.g., p) and barred atoms (e.g., p), where the presence of an atom indicates that the atom is true (has the value 1) in the valuation, while the presence of a barred atom indicates

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

that the atom is false (has the value 0) in the valuation. Thus, for the logic generated from P = {b, f, p}, where the atoms stand for, respectively, being a bird , being a flying creature , and being a penguin , the valuation in which b is true, f is false, and p is true is represented as b fp. Satisfaction of a sentence α L by a valuation v U is defined in the usual way and is denoted by v α. The set of models of a sentence α is defined as JαK def= {v U | v α}. This notion is extended to a set of sentences X in the usual way: JXK def= T α XJαK. We say a set of sentences X (classically) entails α L, denoted X |= α, if JXK JαK.

KLM-Style Rational Defeasible Consequence Several approaches to non-monotonic reasoning have been proposed in the literature over the past 40 years. The preferential approach, initially put forward by Shoham (1988) and subsequently developed by Kraus, Lehmann, and Magidor (1990) in much depth (the reason why it became known as the KLM-approach), has established itself as one of the main references in the area. This stems from at least three of its features: (i) its intuitive semantics and elegant prooftheoretic characterisation; (ii) its generality w.r.t. alternative approaches to non-monotonic reasoning such as circumscription (Mc Carthy 1980), default logic (Reiter 1980), and many others, and (iii) its formal links with AGM-style belief revision (Gärdenfors and Makinson 1994). The fruitfulness of the preferential approach is also witnessed by the great deal of recent work extending it to languages that are more expressive than that of propositional logic such as those of description logics (Bonatti 2019; Britz, Meyer, and Varzinczak 2011; Giordano et al. 2007). A defeasible consequence relation | is a binary relation on L. We say | is preferential (Kraus, Lehmann, and Magidor 1990) if it satisfies the rules:

(Ref) α | α (LLE) |= α β, α | γ

(And) α | β, α | γ

α | β γ (Or) α | γ, β | γ

(RW) α | β, |= β γ

α | γ (CM) α | β, α | γ

If, in addition to the preferential rules, the defeasible consequence relation | also satisfies the following Rational Monotonicity rule (Lehmann and Magidor 1992), it is said to be a rational consequence relation:

(RM) α | β, α | γ

Rational consequence relations can be given an intuitive semantics in terms of ranked interpretations.

Definition 1 A ranked interpretation R is a function from U to N { } satisfying the following convexity property: for every i N, if R(u) = i, then, for every j s.t. 0 j < i, there is a u U for which R(u ) = j.

Given R, we call R(v) the rank of v w.r.t. R. The intuition is that valuations with a lower rank are deemed more

normal (or typical) than those with a higher rank, while those with an infinite rank are regarded as so atypical as to be forbidden . Given a ranked interpretation R, we therefore partition the set U into the set of plausible valuations (those with finite rank), and that of implausible ones (with rank ). Figure 1 depicts an example of a ranked interpretation for P = {b, f, p}. (Plausible valuations are associated with the colour blue, whereas the implausible ones with red.)

bf p bf p b f p b fp bfp

Figure 1: A ranked interpretation for P = {b, f, p}.

Given R and α L, with JαKR we denote the set of plausible valuations satisfying α in R. With R(α) def= min{R(v) | v JαKR} we denote the rank of α in R. By convention, if JαKR = , we let R(α) = . Defeasible consequence of the form α | β is then given a semantics in terms of ranked interpretations in the following way: We say α | β is satisfied in R (denoted R α | β) if R(α) < R(α β). (Here we adopt Jaeger s (1996) convention that < always holds.) Equivalently, α | β iff β holds in all the most normal α-valuations. If R α | β, we say R is a ranked model of α | β. In the example in Figure 1, we have R b | f, R (p b) | , R p | f, R f | b, and R p b | b. That this semantic characterisation of rational defeasible consequence is appropriate is a consequence of a representation result linking the seven rationality rules above to precisely the class of ranked interpretations (Lehmann and Magidor 1992; Gärdenfors and Makinson 1994).

Rational Closure

One can also view defeasible consequence as formalising some form of (defeasible) conditional and bring it down to the level of statements. Such was the stance adopted by Lehmann and Magidor (1992). A conditional knowledge base KB is a finite set of statements of the form α | β, with α, β L. In knowledge bases, we shall abbreviate α | with α. As an example, let KB = {b | f, p b, p | f}. Given a conditional knowledge base KB, a ranked model of KB is a ranked interpretation satisfying all statements in KB. The ranked interpretation in Figure 1 is a ranked model of the above KB. An important reasoning task in this setting is that of determining which conditionals follow from a conditional knowledge base. Of course, even when interpreted as a conditional in (and under) a given knowledge base KB, | is expected to adhere to the KLM rules. To be more precise, we can take the defeasible conditionals in KB as the core elements of a defeasible consequence

relation | KB. By closing the latter under the preferential rules (in the sense of exhaustively applying them), we get a preferential extension of | KB. Since there can be more than one such extension, the most cautious approach consists in taking their intersection. The resulting set, which also happens to be closed under the preferential rules, is the preferential closure of | KB, which we denote by | KB P C. When interpreted again as a conditional knowledge base, the preferential closure of | KB contains all the conditionals entailed by KB. The same process and definitions carry over when one requires the defeasible consequence relations also to be closed under the rule RM, in which case we talk of rational extensions of | KB. Nevertheless, as pointed out by Lehmann and Magidor (1992, Section 4.2), the intersection of all such rational extensions is not, in general, a rational consequence relation: it coincides with preferential closure and therefore may fail RM. Among other things, this means that the corresponding entailment relation, which is called rank entailment and defined as KB |=R α | β if every ranked model of KB also satisfies α | β, is monotonic and therefore it falls short of being a suitable form of entailment in a defeasible reasoning setting. As a result, several alternative notions of entailment from conditional knowledge bases have been explored in the literature on non-monotonic reasoning (Booth et al. 2019; Casini, Meyer, and Varzinczak 2019; Giordano et al. 2012; Lehmann 1995; Weydert 2003), with rational closure (Lehmann and Magidor 1992) commonly acknowledged as the gold standard in the matter. Rational closure (RC) is a form of inferential closure extending the notion of rank entailment above. It formalises the principle of presumption of typicality (Lehmann 1995, p. 63), which, informally, specifies that a situation (in our case, a valuation) should be assumed to be as typical as possible (w.r.t. background information in a knowledge base). Assume a partial order KB on all ranked models of a knowledge base KB, defined as follows: R1 KB R2, if, for every v U, R1(v) R2(v). Giordano et al. (2015) showed that there is a unique KB-minimal element. The rational closure of KB is defined in terms of this minimum ranked model of KB.

Definition 2 Let KB be a conditional knowledge base, and let RKB RC be the minimum element of KB on ranked models of KB. The rational closure of KB is the defeasible consequence relation | KB RC def= {α | β | RKB RC α | β}.

As an example, Figure 1 shows the minimum ranked model of KB = {b | f, p b, p | f} w.r.t. KB. Hence we have that f | b is in the rational closure of KB. Rational closure is commonly viewed as the basic (although not the only acceptable) form of non-monotonic entailment, on which other, more venturous forms of entailment can be and have been constructed (Booth et al. 2019; Casini et al. 2014; Casini, Meyer, and Varzinczak 2019; Kern-Isberner 2001; Lehmann 1995).

Disjunctive Rationality and Intervals One may argue there are cases where Rational Monotonicity is too strong a rule to enforce and for which a weaker defeasible consequence relation would suffice (Giordano et al.

2010; Makinson 1994). Nevertheless, doing away with rationality, i.e., sticking to the preferential rules only, is not particularly appropriate in a defeasible-reasoning context. Indeed, as widely known in the literature, preferential systems induce entailment relations that are monotonic (Lehmann and Magidor 1992). In that respect, here we are interested in defeasible consequence relations (or conditionals) that do not necessarily satisfy RM while still encapsulating some form of rationality. A case in point is that of the Disjunctive Rationality (DR) rule (Kraus, Lehmann, and Magidor 1990):

(DR) α β | γ α | γ or β | γ Intuitively, DR says that if one may draw a conclusion from a disjunction of premises, then one should be able to draw this conclusion from at least one of these premises taken alone. Kraus, Lehmann, and Magidor (1990) offered the following example to illustrate the plausibility of DR: If we do not hold that if Peter comes to the party, it will be great and do not hold that if Cathy comes to the party, it will be great, how could we hold that if at least one of Peter or Cathy comes, the party will be great? A preferential consequence relation is called disjunctive if it also satisfies DR. As it turns out, every rational consequence relation is also disjunctive, but not the other way round (Lehmann and Magidor 1992). Therefore, DR is a weaker form of rationality, as its name suggests. Given that, Disjunctive Rationality is indeed a suitable candidate for the type of investigation we have in mind. A semantic characterisation of disjunctive consequence relations was given by Freund (1993) based on a filtering condition on the underlying ordering. Here, we provide an alternative semantics in terms of interval-based interpretations. (We conjecture Freund s semantic constructions and ours can be shown to be equivalent in the finite case.) Definition 3 An interval-based interpretation is a pair I def= L , U , where L and U are functions from U to N { } s.t. for all u U, (i) L (u) U (u); (ii) if L (u) = i or U (u) = i, then for every 0 j < i, there is u s.t. either L (u ) = j or U (u ) = j, and (iii) L (u) = iff U (u) = . Given I = L , U and u U, L (u) is the lower rank of u in I , and U (u) is the upper rank of u in I . Hence, the pair (L (u), U (u)) is the interval of u in I . We say u is more preferred than v in I , denoted u v, if U (u) < L (v). The order on U defined above via an interval-based interpretation forms an interval order over the set of valuations of finite lower/upper rank, i.e., it is a strict partial order that additionally satisfies the interval condition: if u v and u v , then either u v or u v. Furthermore, every interval order over any subset of U can be defined from an interval-based interpretation in this way. See the work of Fishburn (1985) for more details, and also that of Rott (2014), who more recently explored interval orders in the context of belief contraction. Figure 2 illustrates an example of an interval-based interpretation for P = {b, f, p}. Whenever the intervals associated to valuations u and v overlap, the intuition is that both valuations are incomparable in I ; otherwise the leftmost interval is seen as more preferred than the rightmost one.

bf p bf p b f p b fp bfp

Figure 2: An interval-based interpretation for P = {b, f, p}.

The notions of plausible and implausible valuations carry over to interval-based interpretations, only now the plausible valuations are the ones with finite lower ranks (and hence also finite upper ranks, by part (iii) of the previous definition). With L (α) def= min{L (v) | v JαKI } and U (α) def= min{U (v) | v JαKI } we denote, respectively, the lower and the upper rank of α in I . By convention, if JαKI = , we let L (α) = U (α) = . We say α | β is satisfied in I (denoted I α | β) if U (α) < L (α β). (Recall the convention that < .) As an example, in the interval-based interpretation of Figure 2, we have I b | f, I p | f, and I f | p (contrary to the ranked interpretation R in Figure 1, which endorses the latter). In the tradition of the KLM approach to defeasible reasoning, we define the defeasible consequence relation induced by an interval-based interpretation: | I def= {α | β | I α | β}. We can now state a KLM-style representation result establishing that our interval-based semantics is suitable for characterising the class of disjunctive defeasible consequence relations, which is a variant of Freund s result:

Theorem 1 A defeasible consequence relation | is disjunctive if and only if there is I such that | = | I .

Towards Disjunctive Rational Closure

Given a conditional knowledge base KB, the obvious definition of closure under Disjunctive Rationality consists in taking the intersection of all disjunctive extensions of | KB (cf. the earlier subsection Rational closure ). Let us call it the disjunctive closure of | KB, with interval-based entailment, defined as KB |=I α | β if every interval-based model of KB also satisfies α | β, being its semantic counterpart. The following result shows that the notion of disjunctive closure is stillborn, i.e., it does not even satisfy DR.

Proposition 1 Given KB, (i) the disjunctive closure of KB coincides with its preferential closure | KB P C. (ii) There exists KB such that | KB P C does not satisfy DR.

This result suggests the quest for a suitable definition of entailment under DR should follow the footprints in the road which led to the definition of rational closure. Such is our contention here, and our research question is now: Is there a single best disjunctive relation extending the one induced by a given conditional knowledge base KB?

Let us denote by | KB the special defeasible consequence relation that we are looking for. Next, we consider some desirable properties for the mapping from KB to | KB , and consider some simple examples in order to build intuitions. In the following section, we will offer a concrete construction: the Disjunctive Rational Closure of KB.

Basic Postulates

Starting with our most basic requirements, we put forward the following two postulates:

Inclusion If α | β KB, then α | KB β.

D-Rationality | KB is a disjunctive consequence relation.

Another reasonable property to require is for two equivalent knowledge bases to yield exactly the same set of inferences. This prompts the question of what it means to say that two conditional knowledge bases are equivalent. One strong notion of equivalence can be defined as follows.

Definition 4 For α, β, γ, δ L, α | β is equivalent to γ | δ if |= (α γ) (β δ). KB and KB are equivalent (KB KB ), if there is a bijection f : KB KB s.t. each α | β KB is equivalent to f(α | β).

We can then express a weak form of syntax independence:

Equivalence If KB1 KB2, then | KB1 =| KB2 .

Weaker notions of equivalence between knowledge bases are possible (see, e.g., (Beierle, Eichhorn, and Kern-Isberner 2017)), leading to stronger forms of syntax independence. Finally, the last of our basic postulates requires rational closure to be the upper bound on how venturous our consequence relation should be.

Infra-Rationality | KB | KB RC.

Minimality Postulates

Echoing a fundamental principle of reasoning in general and of non-monotonic reasoning in particular is a property requiring | KB to contain only conditionals whose inferences can be justified on the basis of KB. The first idea to achieve this would be to set | KB to be a set-theoretically minimal disjunctive consequence relation that extends KB.

Example 1 Suppose the only knowledge we have is a single conditional saying birds normally fly , i.e., KB = {b | f}. Assuming just two variables, we have a unique -minimal disjunctive consequence relation extending KB, which is given by the interval-based interpretation I in Figure 3. Indeed, the conditional b | f is saying precisely that bf b f, but is telling us nothing with regard to the relative typicality of the other two possible valuations, so any pair of valuations other than this one is incomparable. For this reason, we do not have f | I b here. Note the rational closure in this example does endorse this latter conclusion, thus providing evidence that the rational closure arguably gives some unwarranted conclusions.

The next example shows there might be more than one - minimal extension of a KB-induced consequence relation.

Figure 3: Interval-based model of KB = {b | f}.

Example 2 Assume a COVID-19 inspired scenario with only two propositions, m and s, standing for, respectively, you wear a mask and you observe social distancing . Let KB = {m | s, m | s}. There are two -minimal disjunctive consequence relations extending | KB, corresponding to the two interval-based interpretations I1 and I2 (from left to right) in Figure 4. The first conditional is saying ms m s, while the second is saying ms m s. According to the interval condition (see the paragraph following Definition 3), we must then have either ms m s or ms m s. The choice of which gives rise to I1 and I2, respectively.

m s ms ms m s

m s ms ms m s

m s ms ms m s

Figure 4: Left and center: Interval-based models of the two -minimal extensions of | KB, for KB = {m | s, m | s}. Right: Interval-based model of the union of the two - minimal extensions of | KB.

In the light of Example 2, a question that arises is what to do when one has more than a single -minimal extension of | KB. Proposition 1 already tells us we cannot, in general, take their intersection. However we might still expect the following postulates as reasonable.

Vacuity If | KB P C is disjunctive, then | KB = | KB P C.

Preferential Extension | KB P C | KB .

(Note, given Proposition 1, the postulate above follows from Inclusion and D-Rationality.)

Representation Independence What should the answer be in Example 2? Intuitively, faced with the choice of which of the pairs ms m s or ms m s to include, and in the absence of any reason to prefer either one, it seems the right thing to do is to include both, and thereby let the interval-based interpretation depicted in Figure 4 (right) yield the output. Notice that this will be the same as the rational closure in this case. We can express the desired symmetry requirement in a syntactic form, using the notion of symbol translations (Marquis and Schwind 2014). A symbol translation (on P) is a function σ : P L. It can be extended to a function on L by setting, for each sentence α, σ(α) to be the sentence obtained from α by replacing each atom p

occurring in α by its image σ(p) throughout. Similarly, given KB and σ( ), we denote by σ(KB) the knowledge base obtained by replacing each conditional α | β in KB by σ(α) | σ(β). A specific family of symbol translations are the negation-swapping ones, i.e., when σ(p) {p, p}, for all p P. We propose the following postulate:

Negated Rep. Independence For any negation-swapping symbol translation σ( ), α | KB β iff σ(α) | σ(KB) σ(β).

Example 3 Going back to Example 2, when modelling the scenario, instead of using propositional atom m to denote you wear a mask we could equally well have used it to denote you do not wear a mask . Then the statement if you wear a mask then, normally, you do social distancing would be modelled by m | s, etc. This boils down to taking a negation-swapping symbol translation such that σ(m) = m and σ(s) = s. Then σ(KB) = { m | s, m | s}, and if we inferred, say, m s | s from KB then we would expect to infer m s | s from σ(KB).

We note that Weydert (2003) and Jaeger (1996) also consider representation independence in the context of conditional inference, but in slightly different frameworks.

Cumulativity Postulates The idea behind a notion of Cumulativity in our setting is that adding a conditional to the knowledge base that was already inferred should not change anything in terms of its consequences. We can split this into two halves .

Cautious Monotonicity If α | KB β and KB = KB {α | β}, then | KB | KB .

Cut If α | KB β and KB = KB {α | β}, then | KB | KB .

We conclude this section with an impossibility result concerning a subset of the postulates we have mentioned so far.

Theorem 2 There is no method satisfying all of Inclusion, D-Rationality, Equivalence, Vacuity, Cautious Monotonicity and Negated Representation Independence.

Proof: Assume, for contradiction, that satisfies all the listed properties. Suppose P = {m, s} and let KB be the knowledge base from Example 2, i.e., {m | s, m | s}. By Inclusion, m | KB s and m | KB s. By D-Rationality, we know | KB satisfies the Or rule, so, from these two, we get m m | KB s which, in turn, yields (m s) ( m s) | KB s, by LLE. Applying DR to this means we have:

(m s) | KB s or ( m s) | KB s (1)

Now, let σ( ) be the negation-swapping symbol translation mentioned in Example 3, i.e., σ(m) = m, σ(s) = s, so σ(KB) = { m | s, m | s}. Then, by Negated Representation Independence, we have (m s) | KB s iff ( m s) | σ(KB) s. But clearly we have KB σ(KB), so, by Equivalence, we obtain from this:

(m s) | KB s iff ( m s) | KB s (2)

Putting (1) and (2) together gives us both (m s) | KB s and ( m s) | KB s. Now, let KB = KB {(m s) |

s}. By Cautious Monotonicity, | KB | KB . In particular, ( m s) | KB s. It can be checked that the preferential closure of KB is itself a disjunctive consequence relation. In fact, it corresponds to the interval-based interpretation on the left of Figure 4. Hence, by Vacuity, this particular intervalbased interpretation corresponds also to | KB . But, we can see from the figure ( m s) | KB s contradiction. Theorem 2 is both surprising and disappointing, since all the properties mentioned seem to be intuitive and desirable. What can we do in the face of this result? Our strategy will be to construct a method that can satisfy as many of these properties as possible. We now provide our candidate for such a method - the disjunctive rational closure.

A Construction for Disjunctive Rational Closure In order to satisfy D-Rationality, we can focus on constructing a special interval-based interpretation from KB and then take all conditionals holding in this interpretation as the consequences of KB. In this section, we give our construction of the interpretation I KB DC that gives us the disjunctive rational closure of a conditional knowledge base. To specify I KB DC, we will construct the pair L KB DC, U KB DC of functions specifying the lower and upper ranks for each valuation. Since we aim to satisfy Infra-Rationality, our construction method takes the rational closure RKB RC of KB as a point of departure. Starting with the lower ranks, we simply set, for all v U: L KB DC(v) def= RKB RC(v). That is, the lower ranks are given by the rational closure. For the upper ranks U KB DC , if we happen to have L KB DC(v) = RKB RC(v) = , then, to conform with the definition of interval-based interpretation, it is clear that we must set U KB DC (v) = also. If L KB DC(v) = , then the construction of U KB DC (v) becomes a little more involved. We require first the following definition.

Definition 5 Given a ranked interpretation R and a conditional α | β such that R α | β, we say a valuation v verifies α | β in R if v α and R(v) = R(α).

Now, assuming L KB DC(v) = , our construction of U KB DC (v) splits into two cases, according to whether v verifies any of the conditionals from KB in RKB RC or not.

Case 1: v does not verify any of the conditionals in KB in RKB RC. In this case, we set: U KB DC (v) def= max{RKB RC(u) | RKB RC(u) = }.

Case 2: v verifies at least one conditional from KB in RKB RC. In this case, the idea is to extend the upper rank of v as much as possible while still ensuring the constraints represented by KB are respected in the resulting I KB DC. If v verifies α | β in RKB RC, then this is achieved by setting U KB DC (v) = RKB RC(α β) 1; or, if R(α β) = , then again just set U KB DC (v) = max{RKB RC(u) | RKB RC(u) = }, as in Case 1. We introduce now the following notation. Given sentences α, β:

t KB RC(α, β) def= RKB RC(α β) 1, if RKB RC(α β) = max{RKB RC(u) | RKB RC(u) = }, otherwise.

But we need to take care of the situation in which v possibly verifies more than one conditional from KB in RKB RC. In order to ensure that all conditionals in KB will still be satisfied, we need to take:

U KB DC (v) def= min{t KB RC(α, β) | (α | β) KB and

v verifies α | β in RKB RC}

So, summarising the two cases, we arrive at our final definition of U KB DC :

U KB DC (v) def=

min{t KB RC(α, β) | α | β KB and

v verifies α | β in RKB RC}, if v verifies at least one conditional from KB in RKB RC

max{RKB RC(u) | RKB RC(u) = }, otherwise.

Note that if v verifies α | β KB in RKB RC, then RKB RC(v) = RKB RC(α) RKB RC(α β) 1 = t KB RC(α, β). Thus, in both cases above, we have L KB DC(v) U KB DC (v) and so the pair L KB DC and U KB DC form a legitimate intervalbased interpretation. We thus arrive at our final definition of the disjunctive rational closure of a conditional knowledge base. Definition 6 Let I KB DC def= L KB DC, U KB DC be the intervalbased interpretation specified by L KB DC and U KB DC as above. The disjunctive rational closure (hereafter DRC) of KB is the defeasible consequence relation | KB DC def= {α | β | I KB DC α | β}. Let us revisit the examples we have seen throughout the paper, to see what DRC gives. Example 4 Going back to Example 1, with KB = {b | f}, the rational closure yields RKB RC(bf) = RKB RC( bf) = RKB RC( b f) = 0 and RKB RC(b f) = 1. Since L KB DC = RKB RC, this gives us the lower ranks for each valuation in I KB DC. Turning to the upper ranks, the only valuation that verifies the single conditional b | f in KB is bf, thus U KB DC (bf) = t KB RC(b, f) = RKB RC(b f) 1 = 1 1 = 0, meaning that the interval assigned to bf is (0, 0). The other three valuations all get assigned the same upper rank, which is just the maximum finite rank occurring in RKB RC, which is 1. Thus the interval assigned to b f is (1, 1), while both the valuations in J b K are assigned (0, 1). So I KB DC outputs exactly the same interval-based interpretation depicted in Figure 3 which, recall, gives the unique -minimal disjunctive consequence relation extending KB in this case. Example 5 Returning to Example 2, with KB = {m | s, m | s}, the rational closure yields RKB RC(ms) = RKB RC( ms) = 0 and RKB RC(m s) = RKB RC( m s) = 1, which gives us the lower ranks. The valuation ms verifies only m | s, and so U KB DC (ms) = t KB RC(m, s) = RKB RC(m s) 1 = 1 1 = 0. Similarly, the valuation ms verifies only m | s and so, by analogous reasoning, U KB DC ( ms) = t KB RC( m, s) = 0. So both valuations are assigned the interval (0, 0) by I KB DC. The other two valuations, which verify neither conditional in KB, are assigned (1, 1). In this case, I KB DC returns just the rational closure of KB, as pictured in Figure 4 (right).

In both examples above, DRC returns the right answers.

Example 6 Consider KB = {b | f, p b, p | f}. As previously mentioned, the rational closure RKB RC for this KB is depicted in Figure 1. Since both of the valuations in Jp b K (in red at the top of the picture) are deemed implausible (i.e., have rank ), they are both assigned interval ( , ). Focusing then on just the plausible valuations, the only valuation verifying b | f in RKB RC is bf p (which verifies no other conditional in KB), so U KB DC (bf p) = RKB RC(b f) 1 = 1 1 = 0. The only valuation verifying p | f is b fp, so U KB DC (b fp) = RKB RC(p f) 1 = 2 1 = 1. All other plausible valuations get assigned as their upper rank the maximum finite rank, which is 2. The resulting I KB DC is the interval-based interpretation depicted in Figure 2.

Properties of the Disjunctive Rational Closure We now turn to the question of which of the postulates from the preceding section are satisfied by DRC. To begin with, we obtain all of the basic postulates proposed there.

Proposition 2 DRC satisfies Inclusion, D-Rationality, Equivalence and Infra-Rationality.

We remind the reader that, since Inclusion and DRationality hold, DRC also satisfies Preferential Extension. We can also confirm that DRC conforms with our Representation Independence requirement.

Proposition 3 DRC satisfies Negated Representation Independence.

DRC essentially inherits this property from rational closure, which can also be shown to satisfy it. Although Jaeger (1996) showed that rational closure conforms with his version of Representation Independence, the relationship between his version and ours remains to be explored. Now we look at the Cumulativity properties. It is known from the work by Lehmann and Magidor (1992) that rational closure satisfies both Cautious Monotonicity and Cut, and, in fact, if α | KB RC β and KB = KB {α | β}, then RKB RC = RKB RC . We can show the following for DRC.

Proposition 4 DRC satisfies Cautious Monotonicity, but does not satisfy Cut.

The reason for the failure of Cut is that by adding a new conditional α | β to KB, even when that conditional is already inferred by DRC, we give certain valuations (i.e., those in JαK) opportunity to verify one more conditional from the knowledge base in RKB RC . This leads, potentially, to a corresponding decrease in their upper ranks U KB DC , leading in turn to more inferences being made available. This behaviour reveals that DRC can be termed a base-driven approach, since the conditionals that are included explicitly in the knowledge base have more influence compared to those that are merely derived. However, adding an inferred conditional will never lead to an increase in the upper ranks, which means DRC does satisfy Cautious Monotonicity. As we have seen in our impossibility result (Theorem 2), satisfaction of Cautious Monotonicity, plus that of the other properties proved earlier in this section, comes at the cost of

Vacuity, i.e., even if the preferential closure is a disjunctive relation, the output may sanction extra conclusions.

Proposition 5 DRC does not satisfy Vacuity.

Concluding Remarks In this paper, we have set ourselves the task to revive interest in weaker alternatives to Rational Monotonicity when reasoning with conditional knowledge bases. We have studied the case of Disjunctive Rationality, a property already known by the community from the work of Kraus et al. and Freund in the early 90s, which we have then coupled with a semantics in terms of interval orders borrowed from a more recent work by Rott in belief revision. In our quest for a suitable form of entailment ensuring Disjunctive Rationality, we started by putting forward a set of postulates, all reasonable at first glance, characterising its expected behaviour. As it turns out, not all of them can be satisfied simultaneously, which suggests there might be more than one answer to our research question. We have then provided a construction of the disjunctive rational closure of a conditional knowledge base, which infers a set of conditionals intermediate between the preferential closure and the rational closure. Regarding the computational complexity of our construction, space considerations prevent us from providing the details. Nevertheless, we have checked that our construction method runs in time that grows (singly) exponentially with the size of the input, with rational closure of the knowledge base computed offline. Regarding the properties of DRC, the news is somewhat mixed, with several basic postulates satisfied, as well as Cautious Monotonicity, but with neither Cut nor Vacuity holding in general. Regarding Cut, the reason for its failure seems tied to the fact that DRC places special importance on the conditionals that are explicitly written as part of the knowledge base. In this regard it shares commonalities with other base-driven approaches to defeasible inference such as the lexicographic closure (Lehmann 1995). We conjecture that a weaker version of Cut will still hold for us, according to which the new conditional added α | β is such that α appears as an antecedent of another conditional already in KB. Regarding Vacuity, our impossibility result tells us that its failure is unavoidable given the other, reasonable, behaviour that we have shown DRC to exhibit. Essentially, when trying to devise a method for conditional inference under Disjunctive Rationality, we are faced with a choice between Vacuity and Cautious Monotonicity, with DRC favouring the latter at the expense of the former. It is possible, of course, to tweak the current approach by treating the case when | KB P C happens to be a disjunctive relation separately, outputting the preferential closure in this case, while returning DRC otherwise. However the full ripple effects on the other properties of | KB DC of making this manoeuvre remain to be worked out. As for future work, we plan to investigate suitable definitions of a preference relation on the set of interval-based interpretations. We hope our construction can be shown to be the most preferred extension of the knowledge base according to some intuitively defined preference relation, as has been done in the rational case.

Acknowledgments

This work has been partially supported by the CNRS/Royal Society project Non-Classical Reasoning for Enhanced Ontology-based Semantic Technologies. Thanks to the anonymous reviewers for helpful suggestions. A preliminary version of this work was presented at the 18th Workshop on Non-Monotonic Reasoning (NMR 2020) (Booth and Varzinczak 2020).

References Beierle, C.; Eichhorn, C.; and Kern-Isberner, G. 2017. A transformation system for unique minimal normal forms of conditional knowledge bases. In European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, 236 245. Springer.

Bonatti, P. 2019. Rational closure for all description logics. Artificial Intelligence 274: 197 223.

Booth, R.; Casini, G.; Meyer, T.; and Varzinczak, I. 2019. On Rational Entailment for Propositional Typicality Logic. Artificial Intelligence 277.

Booth, R.; and Varzinczak, I. 2020. Towards Conditional Inference under Disjunctive Rationality. In 18th International Workshop on Nonmonotonic Reasoning (NMR).

Britz, K.; Meyer, T.; and Varzinczak, I. 2011. Semantic Foundation for Preferential Description Logics. In Proc. of the 24th Australasian Joint Conference on Artificial Intelligence, number 7106 in LNAI, 491 500. Springer.

Casini, G.; Meyer, T.; Moodley, K.; and Nortjé, R. 2014. Relevant Closure: A New Form of Defeasible Reasoning for Description Logics. In Proc. of the 14th European Conference on Logics in Artificial Intelligence (JELIA), number 8761 in LNCS, 92 106. Springer.

Casini, G.; Meyer, T.; and Varzinczak, I. 2019. Taking Defeasible Entailment Beyond Rational Closure. In Proc. of the 16th European Conference on Logics in Artificial Intelligence (JELIA), number 11468 in LNCS, 182 197. Springer.

Fishburn, P. 1985. Interval Orders and Interval Graphs: A Study of Partially Ordered Sets. Wiley.

Freund, M. 1993. Injective Models and Disjunctive Relations. Journal of Logic and Computation 3(3): 231 247.

Gärdenfors, P.; and Makinson, D. 1994. Nonmonotonic inference based on expectations. Artificial Intelligence 65(2): 197 245.

Giordano, L.; Gliozzi, V.; Olivetti, N.; and Pozzato, G. 2007. Preferential Description Logics. In Logic for Programming, Artificial Intelligence, and Reasoning (LPAR), number 4790 in LNAI, 257 272. Springer.

Giordano, L.; Gliozzi, V.; Olivetti, N.; and Pozzato, G. 2010. Preferential vs Rational Description Logics: which one for Reasoning About Typicality? In Proc. of the European Conference on Artificial Intelligence (ECAI), 1069 1070.

Giordano, L.; Gliozzi, V.; Olivetti, N.; and Pozzato, G. 2012. A Minimal Model Semantics for Nonmonotonic Reasoning.

In Proc. of the 13th European Conference on Logics in Artificial Intelligence (JELIA), number 7519 in LNCS, 228 241. Springer. Giordano, L.; Gliozzi, V.; Olivetti, N.; and Pozzato, G. 2015. Semantic characterization of rational closure: From propositional logic to description logics. Artificial Intelligence 226: 1 33. Goldszmidt, M.; Morris, P.; and Pearl, J. 1993. A maximum entropy approach to nonmonotonic reasoning. IEEE Transactions on Pattern Analysis and Machine Intelligence 15(3): 220 232. Jaeger, M. 1996. Representation Independence of Nonmonotonic Inference Relations. In Proc. of the 5th International Conference on Principles of Knowledge Representation and Reasoning (KR), 461 472. Morgan Kaufmann Publishers. Kern-Isberner, G. 2001. Conditionals in Nonmonotonic Reasoning and Belief Revision. Springer, Lecture Notes in Artificial Intelligence. Kraus, S.; Lehmann, D.; and Magidor, M. 1990. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence 44: 167 207. Lehmann, D. 1995. Another perspective on default reasoning. Annals of Mathematics and Artificial Intelligence 15(1): 61 82. Lehmann, D.; and Magidor, M. 1992. What does a conditional knowledge base entail? Artificial Intelligence 55: 1 60. Makinson, D. 1994. General patterns in nonmonotonic reasoning. In Gabbay, D.; Hogger, C.; and Robinson, J., eds., Handbook of Logic in Artificial Intelligence and Logic Programming, volume 3, 35 110. Oxford University Press. Marquis, P.; and Schwind, N. 2014. Lost in translation: Language independence in propositional logic application to belief change. Artificial Intelligence 206: 1 24. Mc Carthy, J. 1980. Circumscription, a form of nonmonotonic reasoning. Artificial Intelligence 13(1-2): 27 39. Pearl, J. 1990. System Z: a natural ordering of defaults with tractable applications to nonmonotonic reasoning. In Proc. of the 3rd Conference on Theoretical Aspects of Rationality and Knowledge (TARK). Reiter, R. 1980. A logic for default reasoning. Artificial Intelligence 13(1-2): 81 132. Rott, H. 2014. Four Floors for the Theory of Theory Change: The Case of Imperfect Discrimination. In Proc. of the 14th European Conference on Logics in Artificial Intelligence (JELIA), number 8761 in LNCS, 368 382. Springer. Shoham, Y. 1988. Reasoning about Change: Time and Causation from the Standpoint of Artificial Intelligence. MIT Press. Weydert, E. 2003. System JLZ - rational default reasoning by minimal ranking constructions. Journal of Applied Logic 1(3-4): 273 308.