Interpolative Reasoning with Default Rules

1 Introduction

We consider the problem of reasoning about what is true in a particular situation (or for a particular object), given a generic set of rules describing some domain of interest. One wellknown problem with using classical logic for this task is that many rules have exceptions, e.g. birds generally fly but penguins are birds which do not fly. If we only know that Tweety is a bird, but not whether or not it is a penguin, it is reasonable to assume that Tweety is a typical bird which therefore can fly. We write α|∼β to denote the default rule 'if α then generally β'. A variety of approaches have been proposed to reason about such default rules, most of which are based on the idea of defining a preference order over possible worlds and insisting that β is true in the most preferred (i.e. the

Henri Prade

Universit´e Paul Sabatier, CNRS IRIT, Toulouse, France prade@irit.fr

most normal) of the worlds in which α is true [Pearl, 1988; Kraus et al., 1990; Pearl, 1990; Geffner and Pearl, 1992; Benferhat et al., 1998]. A remarkable observation is that despite the different intuitions underlying various systems, there are particular defaults that are entailed by a given set of defaults D = {α1|∼β1, ..., αn|∼βn} in the vast majority of approaches. These defaults are captured by the axioms of System P [Kraus et al., 1990]:

(RE) α|∼α

(LLE) If α ≡ α′ and α|∼β then α′ |∼β

(RW) If β |= β′ and α|∼β then α|∼β′

(OR) If α|∼γ and β|∼γ then α∨ β|∼γ

(CM) If α|∼β and α|∼γ then α∧ β|∼γ

(CUT) If α∧ β|∼γ and α|∼β then α|∼γ

where α ≡ α′ and β |= β′ refer to equivalence and entailment from classical logic.

Example 1. Let D contain the following defaults, encoding that adults normally pay taxes, but undergraduate and PhD students are adults who do not normally pay taxes:

undergraduate|∼adult phd|∼adult

undergraduate|∼¬paysTaxes phd|∼¬paysTaxes

adult|∼paysTaxes

From (CM) we derive adult ∧ undergraduate|∼¬paysTaxes, which means that when we only know that a given person is an adult and undergraduate, we will assume that he or she does not pay taxes.

This example also illustrates a second problem, which existing approaches to default reasoning do not alleviate: while the set of defaults specifies that undergraduate and PhD students do not pay taxes, there is no knowledge about master's students. Intuitively, since master's students are conceptually somewhat between undergraduates and PhD students, we would expect that they do not pay taxes either. This idea that intermediate situations should have intermediate consequences is called interpolation and has also received considerable attention in the literature [K´oczy and Hirota, 1993; Dubois et al., 1997; Schockaert and Prade, 2011; Perfilieva et al., 2012]. Interpolation is a convenient way of implementing similarity-based reasoning: the commonsense reasoning pattern whereby in absence of explicit information, humans tend to make conclusions based on what is true for similar situations [Collins and Michalski, 1989]. It is difficult, however, to quantify similarity degrees in a principled way, and to determine how similar two situations should be before we can assume with reasonable certainty that they have the same properties. Interpolation, on the other hand, only relies on a qualitative notion of betweenness, where information about betweenness can be provided by experts or induced from data.

The idea of interpolating default rules, however, has to the best of our knowledge not yet been considered. One problem in combining both forms of commonsense reasoning is the different nature of existing semantics: while default reasoning is based on ranking possible worlds, interpolation relies on identifying conceptual relationships between natural language labels. In this paper, we propose the notion of conceptual structures as a unifying semantics for default reasoning and interpolation. Essentially, conceptual structures are qualitative abstractions of conceptual spaces [G¨ardenfors, 2000], the latter being geometric models for the meaning of natural language labels based on prototype theory. Conceptual structures are introduced in more detail in Section 2. Section 3 then explains how we can see defaults and betweenness information as constraints on conceptual structures, and proposes an axiomatization for sound and complete reasoning about such constraints. This axiomatization generalizes System P, and in particular, inherits its cautious nature. In Section 4 we explore how our inference relation could be further refined, by considering two extensions of System P: rational closure [Lehmann and Magidor, 1992] and conditional entailment [Geffner and Pearl, 1992].

2 Conceptual structures

Closely related to prototype theory, G¨ardenfors' theory of conceptual spaces is a model for categorization [G¨ardenfors, 2000] in which natural categories are represented as convex regions in some multi-dimensional feature space whose dimensions correspond to cognitively primitive features. Each category is represented as the set of instances (i.e. points) which are closer to the prototypes of that category than they are to the prototypes of contrast categories. The notion of betweenness, which underpins interpolation, can then be related to the geometric relationship of category representations in a conceptual space. This situation is illustrated in Figure 1, which shows the conceptual space representations of a number of the categories a1, ..., a6 (defining a partition of the conceptual space) and the categories b1, b2, b3 (defining another partition). We could consider, for instance, that a4 is completely between a1 and a5 (because a4 is included in the convex hull of a1 ∪ a5) and partially between a1 and a3 (because a4 overlaps with the convex hull of a1 ∪ a3).

Intuitively, a default α|∼β is valid if the most typical instances of α are also instances of β. In prototype theory, objects are considered typical instances of a category when they are close to its prototypes. This notion of typicality as geometric centrality, however, is not compatible with the axioms of System P. For instance, Figure 2 shows a situation in which the most central elements of a are in b and in c, whereas the most central elements of a ∧ b are outside c, thus violating (CM). However, there is considerable evidence that the perceived typicality of objects, by a given individual, does not only depend on their closeness to prototypes but also on the frequency with which they have encountered particular exemplars [Nosofsky, 1988]. Figure 1 shows the exemplars that have been encountered by a given individual; most exemplars of a3 and a4 have been instances of b1 and most exemplars of a6 have been instances of b2. We will consider that typical instances of a category are those objects that are similar to a large number of observed exemplars of that category. More precisely, typicality will reflect the order of magnitude of the density of exemplars. This view is compatible with the axioms of System P. In the scenario from Figure 1 it will lead us to accept the defaults a3|∼b1, a4|∼b1 and a6|∼b2.

The semantic structures that we will use to formalise interpolative reasoning about defaults can be seen as qualitative abstractions of a conceptual space and the associated density of observed exemplars in different regions of that space. We consider the propositional language built from the atoms in A and the connectives ∧, ∨, ¬ and → in the usual way. For a propositional formula α we let JαK ⊆ 2A denote the set of models of that formula.

Formally, we define a conceptual structure as a tuple (Ω, B, B, π), where Ω ⊆ 2A is a set of interpretations. Intuitively ω ∈ Ω if the region corresponding to the formula ∧ω|=a a is non-empty, i.e. the set Ω captures the part-whole relations that are satisfied in a given conceptual space. For example, identifying interpretations with the set of atoms they make true, in the case of Figure 1 we would have

The ternary relations B, B ⊆ 2Ω × Ω × 2Ω capture the betweenness information from a conceptual space. In particular, (X, ω, Y ) ∈ B means that reg(ω) is entirely between reg(X) and reg(Y ), where we write reg(ω) for the nonempty and convex region corresponding to ω and reg(X) = ⋃ω′∈X reg(ω′ ) for a set of interpretations X. Similarly, (X, ω, Y ) ∈ B means that reg(ω) is partially between reg(X) and reg(Y ). In the scenario of Figure 1, we would have, among others:

We will furthermore require that conceptual structures satisfy the following properties. First, if ω is entirely between X and Y , then it should also be partially between X and Y :

Betweenness is monotonic w.r.t. set inclusion:

Betweenness is symmetric:

A non-empty region cannot be between an empty region and another region:

Every region is between itself and any other non-empty region

The following postulate asserts that partial betweenness is sufficient for a triple to be in B:

The last postulate expresses that atomic propositions correspond to convex regions:

We will call a conceptual structure admissible iff it satisfies (1)-(9). If we see conceptual structures as qualitative descriptions of conceptual spaces, it seems natural to require them to be admissible. However, note that (1)-(9) are not sufficient to guarantee that a conceptual structure can be realized in a Euclidean space. For example, it can be shown that in any Euclidean space Rn , a ⊆ CH(b ∪ c) and d ⊆ CH(a ∪ b) entails d ⊆ CH(b ∪ c) where a, b, c and d are compact subsets of Rn and CH denotes the convex hull operator. However, as not every conceptual space is Euclidean [G¨ardenfors, 2000] it seems more appropriate to limit the postulates to a more conservative set.

Finally, the last argument π of a conceptual structure is a possibility distribution over Ω, i.e. a mapping from Ω to [0, 1]. Intuitively, the values π(ω) reflect how dense the occurrence of exemplars in reg(ω) is. Without loss of generality we can assume that π(ω) ∈ {λ0, ..., λk} for some 0 < λ0 < λ1 < ... < λk = 1. The distribution induces a partition Ω0∪...∪Ωk of the set Ω, where Ωi = {ω | π(ω) = λi}. The elements of Ωk correspond to those areas of a conceptual space where most exemplars are found. Note in particular that we require π(ω) > 0 for every ω ∈ Ω (i.e. non-dogmatism). In the case of Figure 1, for instance, we may have (k = 1)

with Ω0 containing the remaining elements from Ω. We can interpret the values λi as reflecting the order of magnitude of the probability of encountering an exemplar with the properties made true by ω. We refer to [Benferhat et al., 1999] for an interpretation of possibility distributions in terms of bigstepped probabilities, in a non-monotonic reasoning setting.

3 Preferential reasoning

3.1 Semantics

To formalize interpolative reasoning with default rules, we will interpret default rules and betweenness information as constraints on conceptual structures, and thus indirectly as constraints on conceptual spaces. Given a conceptual structure C = (Ω, B, B, π) and X ⊆ Ω, we write coreπ(X) for the most typical interpretations among X, i.e.

When clear from the context, we will omit the subscript π. We say that C satisfies the default rule α|∼β if

Note that, as a matter of convention, C can only satisfy α|∼β if Ω ̸|= ¬α, i.e. if core(JαK) ̸= ∅. In this way, our interpretation of defaults coincides with the view from [Benferhat et al., 1997] that α|∼β iff Π(α ∧ β) > Π(α ∧ ¬β).

We will use two types of betweenness rules. First, we will write α ⇝ α1 ⋊⋉α2 to denote that all typical instances of α are conceptually between typical instances of α1 and typical instances of α2. We say that C satisfies α ⇝ α1 ⋊⋉α2 if

We may consider for example that a typical master's student is conceptually between a typical undergraduate student and a typical PhD student: master ⇝ undergraduate ⋊⋉phd (but not, perhaps, students on an MBA).

Second, we write β1 ⋊⋉ β1 → β to express that only instances of β can be (partially or completely) between β1 and β2; C satisfies β1 ⋊⋉β1 → β if

For instance italy ⋊⋉ spain → mediterranean expresses the belief that only Mediterranean countries can be conceptually between Italy and Spain.

Finally, in addition to default rules and betweenness information, we will also consider strict rules. We interpret α → β, for α and β propositional expressions, as the constraint that α ∧ ¬β corresponds to an empty region, i.e. C satisfies α → β if

Let D be a set of default rules, S a set of strict rules, and B a set of betweenness constraints of the form α ⇝ α1 ⋊⋉α2 or β1 ⋊⋉β1 → β. We say that 〈D, S, B〉 preferentially entails the default α|∼β, written 〈D, S,B〉 |=P (α|∼β), if α|∼β is satisfied by any admissible conceptual structure that satisfies the defaults in D, the strict rules in S and the betweenness information in B.

Note that the proposed framework essentially corresponds to a form of qualitative reasoning about conceptual spaces, taking into account part-whole relations (using strict rules), typicality and betweenness. As such, it is orthogonal to the proposal from [G¨ardenfors and Williams, 2001] to use qualitative spatial reasoning to reason about categories in conceptual spaces with vague boundaries. Indeed, the notion of conceptual structures could be generalized by associating with each natural language category a nested set of regions. This would, however, require us to formalize the interaction between typicality and categorical membership degrees, which is perhaps not yet sufficiently well understood. Another related approach is [Alenda and Olivetti, 2012], which proposes a preferential semantics for a logic in which relative distance between concepts can be expressed. This approach is somewhat dual to what we propose: instead of proposing geometric semantic structures in which both defaults and spatial relationships can be expressed, [Alenda and Olivetti, 2012] represents spatial relationships using preferential structures.

3.2 Axiomatization

To capture preferential entailment with betweenness information, we need the axioms of System P as well as a new axiom allowing us to conclude α|∼β from α1|∼β1, α2|∼β2, α ⇝ α1 ⋊⋉α2 and β1 ⋊⋉β2 → β. As the following example illustrates, however, this is not sufficient for complete reasoning about conceptual structures.

Example 2. Let S = ∅, D = {x|∼β1, α2|∼β2, α3|∼β3} and let B contain the following betweenness information:

Every conceptual structure satisfying x|∼β1 will satisfy x ∧ y|∼β1 or x ∧ ¬y|∼β1. However, from x ∧ y|∼β1, α2|∼β2, δ ⇝ (x ∧ y) ⋊⋉ α2 and β1 ⋊⋉ β2 → µ we can derive δ|∼µ using the proposed interpolation principle. If x ∧ ¬y|∼β1 holds, together with α3|∼β3, δ ⇝ (x ∧ ¬y) ⋊⋉α3 and β1 ⋊⋉ β3 → µ, we can again derive δ|∼µ. It follows that δ|∼µ will hold in every conceptual structure satisfying 〈D, S,B〉, yet we cannot derive this using the aforementioned axioms.

To address this issue, we need to consider propositional combinations of default rules in the language. Formally, we consider the language L defined as follows: every default α|∼β (with α and β propositional formulas over the set of atoms A) is in L; every betweenness rule of the form α ⇝ α1 ⋊⋉α2 or β1 ⋊⋉β2 → β is in L; every propositional formula is in L; if ψ and φ are in L then also ψ ∨ φ, ψ ∧ φ, ψ → φ and ¬ψ are in the L. We can now formulate the axioms of System P (only considering defaults with a consistent antecedent) and the interpolation principle (I) as implications in L

(RE) α|∼α provided that S ∪ {α} is consistent

• (OR) (α|∼γ) ∧ (β|∼γ) → (α∨ β|∼γ)

We also need to add the following axioms:

(PROP) The axioms from propositional logic at the metalevel

It can be verified that any conceptual structure satisfying α|∼γ but not α|∼¬β indeed satisfies α ∧ β|∼γ. This corresponds to the property of rational monotonicity as an axiom. However, this should not be confused with how rational monotonicity is considered in relation to the rational closure of SystemP [Lehmann andMagidor, 1992]. In particular, it is well known that when α|∼γ is in the rational closure of a set of defaults but α|∼¬β is not, then α∧β|∼γ will also be in the rational closure. In the axiom (RM) considered above, however, ¬(α|∼¬β) does not refer to the fact that α|∼¬β cannot be inferred, but to the fact that the negation of α|∼¬β can be derived. Axiom (INC) is used to make inconsistencies among defaults explicit at the meta-level.

Finally, we consider the following axioms about betweenness:

(BetRE1) α ⇝ α⋊⋉β provided that S ∪ {β} is consistent

(BetRE2) a⋊⋉a → a for an atom a

As will become clear below, these axioms form the counterpart of conditions (1)-(9) and would need to be extended if particular classes of conceptual spaces were considered (e.g. Euclidean spaces). Note that (BetRE2) only holds for atoms, and not for arbitrary propositional formulas.

We say that B is consistent with S if for every rule α ⇝ α1 ⋊⋉α2 it holds that S ∪ {α}, S ∪ {α1} and S ∪ {α2} are consistent, and for every rule β1 ⋊⋉β2 → β, S ∪ {β}, S ∪ {β1} and S ∪ {β2} are consistent. Similarly, we say that D is consistent with S if S ∪ {α} is consistent for each default α|∼β in D.

Proposition 1. Let S be a set of strict rules, D a set of defaults consistent with S, and B a set of betweenness rules consistent with S. The following statements are equivalent:

1. 〈D, S,B〉 |=P µ|∼γ
2. µ|∼γ can be derived fromD∪S∪B using axioms (RE), (LLE), (RW), (OR), (CM), (CUT), (I), (PROP), (RM), (INC), (BetRE1), (BetRE2), (BetSYM1), (BetSYM2), (BetOR), (BetLE1), (BetLE2) and modus ponens.

Proof. The soundness of the axioms w.r.t. the proposed semantics is clear. Here we show that the axioms are also complete. By (PROP), D ∪ S ∪ B is equivalent to a formula of the form

where each δij is a propositional formula, a default rule or a betweenness rule. Now consider one of the disjuncts

Let R be the set of defaults appearing as conjuncts in (11). Without loss of generality, we can assume that, up to logical equivalence, all default rules that can be derived from (11) are contained in R. We can moreover assume that R is consistent, as otherwise we could use (INC) to derive ⊥ and eliminate the disjunct (11) from (10). If this means that there are no disjuncts left in (10), we can derive ⊥ and using (PROP) also µ|∼γ.

It follows from (RM) that we can assume R to be rationally closed without loss of generality, and in particular that there exists a possibility distribution π over the set of models of S such that α|∼β ∈ R iff Π(α ∧ β) > Π(α ∧ ¬β). This follows from the characterization of the rational closure from [Benferhat et al., 1997].

Now assume that R contains no default rule of the form µ|∼γ. We show that π can be extended to a conceptual structure C = (Ω, B, B, π) satisfying δ1 1 ∧ ... ∧ δ1n1 and thus 〈D, S,B〉, but not µ|∼γ. It is clear by construction that C does not satisfy µ|∼γ as otherwise this default rule would appear in R. We choose Ω as the set of models of S. Furthermore, (X, ω, Y ) ∈ B iff there is a rule α ⇝ α1 ⋊⋉α2 that can be derived from B such that

Finally, (X, ω, Y ) ∈ B unless X = ∅, Y = ∅, or there is a betweenness rule β1 ⋊⋉β2 → β that can be derived from B such that

We need to show that C satisfies the conditions (1)-(9). It is straightforward to see why (2), (3), (4), (5), (6), (7) and (9) are satisfied.

Now consider (1). Assume that (X, ω, Y ) ∈ B \ B. Note that this means that X ̸= ∅ and Y ̸= ∅ as the consistency of B w.r.t. S ensures that no triples of the form (∅, ω, Y ) or (X, ω, ∅) are in B. This means there exist formulas α, α1, α2, β, β1, β2 such that α ⇝ α1 ⋊⋉ α2 ∈ B, β1 ⋊⋉β2 → β ∈ B, core(Jα1K) ⊆ X ⊆ Jβ1K, core(Jα2K) ⊆ Y ⊆ Jβ2K, ω ∈ core(JαK)\JβK. From core(Jα1K) ⊆ Jβ1K and core(Jα2K) ⊆ Jβ2K, given that π is the exact semantic counterpart of R (as R is equal to its rational closure), it holds that α1|∼β1 and α2|∼β2 are contained in R. Together with

α ⇝ α1 ⋊⋉α2 ∈ B and β1 ⋊⋉β2 → β ∈ B , we find using (I) that α|∼β can be derived from (11). In other words, we have core(JαK) ⊆ JβK which is in confict with our assumption that ω ∈ core(JαK) \ JβK.

Finally, we consider (8). It is clear by construction that when (X, ω,Z) ∈ B or (Y, ω,Z) ∈ B then also (X ∪ Y, ω,Z) ∈ B. Conversely, assume that X, Y and Z are maximal sets for which (X, ω,Z) /∈ B and (Y, ω,Z) /∈ B. Note that this implies X ̸= ∅, Y ̸= ∅ and Z ̸= ∅. From (X, ω, Z) /∈ B there must be a betweenness rule β1 ⋊⋉β2 → β that can be derived from B such that X ⊆ Jβ1K, Z ⊆ Jβ2K but ω /∈ JβK. Due to the assumption on the maximality of X and Z we can moreover assume that X = Jβ1K and Z = Jβ2K. From (Y, ω,Z) /∈ B we similarly find that there must be a betweenness rule γ1 ⋊⋉ γ2 → γ that can be derived from B such that Y = Jγ1K and Z = Jγ2K but ω /∈ JγK. From Jβ2K = Z = Jγ2K and (BetLE2) we find that β1 ⋊⋉ β2 → β and γ1 ⋊⋉ β2 → γ can be derived, and because (BetOR) also (β1 ∨ γ1) ⋊⋉β2 → (β ∨ γ). We have that X ∪ Y ⊆ Jβ1 ∨ γ2K, Z ⊆ Jβ2K and ω /∈ Jβ ∨ γK, from which we obtain (X ∪ Y, ω, Z) /∈ B.

4 Discussion

The inference system introduced in the previous section coincides with System P when no betweenness information is present. As such it inherits the disadvantages of System P and in particular its cautious nature. For example, from bird|∼fly we cannot derive bird ∧ red|∼fly, despite that there is nothing to suggest that being red would prevent a bird from flying. To cope with this problem, a number of solutions have been proposed.

One of the best known solutions is the rational closure [Lehmann and Magidor, 1992], which is equivalent to System Z [Pearl, 1990]. Semantically, the rational closure can be characterized as follows. Let Ω10 ∪ ... ∪Ω1k be the partition of Ω induced by a possibility distribution π1 and let Ω20 ∪...∪Ω2k be the partition induced by π2 . We say that π1 is less specific than π2 iff for each i, Ω1i ∪ ... ∪ Ω1k ⊇ Ω2i ∪ ... ∪ Ω2k , i.e. if π1 considers more interpretations typical (or normal) than π2 . Given a set of defaults D there is a unique least specific possibility distribution π that satisfies D [Benferhat et al., 1997]. The default rules in the rational closure of D are exactly the default rules that are satisfied by π. In the presence of betweenness information, there may be several different possibility distributions that are minimally specific, as illustrated by the next two examples.

Example 3. Let S = ∅ and let D = {α1|∼β1, α2|∼β2, α3|∼β3}; B contains the following betweenness information:

The rules α1 ∧ x ∧ y|∼β1 and α3 ∧ u ∧ v|∼β3 are (classically) in the rational closure of D. If we accept these default rules to be valid, then interpolation would allow us to derive α1 ∧ x|∼¬β1 and α3 ∧ u|∼¬β3, which suggests that α1∧x∧y|∼β1 and α3∧u∧v|∼β3 should not be in the rational closure. As a result, some sort of non-deterministic choice is needed to obtain a 'stable' generalization of the rational closure. Accordingly, there are three compatible possibility distributions π1, π2 and π3 which are minimally specific, where:

• π1 satisfies α1 ∧ x ∧ y|∼β1 and α3 ∧ u|∼¬β3
• π2 satisfies α3 ∧ u ∧ v|∼β3 and α1 ∧ x|∼¬β1
• π3 satisfies ¬(α1 ∧ x ∧ y|∼β1) and ¬(α3 ∧ u ∧ v|∼β3)

A natural result would be to accept only the default rules that are valid for each of these minimally specific models, e.g. we would derive α ∧ u|∼β1 but not α ∧ x|∼β1 or α ∧ x|∼¬β1.

Example 4. Let D be as in the previous example, but let B now contain the following rules:

where we assume that x1, x2, y1 and y2 do not occur in any of the rules fromD. Again there are three minimally specific possibility distributions, and in only one of these the default rules x1|∼y1 and x2|∼y2 are valid. However, in this example there is nothing to suggest that being x ∧ y is exceptional for α1 so α1 ∧x∧y|∼β1, and analogously α3 ∧x∧y|∼β3 should be in the rational closure, which means that also x1|∼y1 and x2|∼y2 should intuitively be in the rational closure. In contrast to the previous example, only considering those defaults that are valid in each of the minimally specific possibility distributions appears to be too cautious.

Given these difficulties in generalizing rational closure, we instead take inspiration from the notion of conditional entailment [Geffner and Pearl, 1992] to introduce a technique for refining the inference system from the previous section. Let us define the set A of potential antecedents as follows:

For each α in A we consider a fresh atom δα, intuitively corresponding to the assumption that we are in a normal situation for α. Let us write ∆ = {δα | α ∈ A}. We now rewrite the knowledge base 〈D, S,B〉 to a knowledge base 〈S∗ ,B∗ 〉 as follows:

• add each strict rule from S to S∗ ; for each default α|∼β in D, add α ∧ δα to S∗ ;
• for each betweenness rule of the form β1 ⋊⋉β2 → β in B, add β1 ⋊⋉β2 → β and β2 ⋊⋉β1 → β to B∗ ; for each atom a ∈ A, add a ⋊⋉a → a to B∗ .
• for each betweenness rule of the form α ⇝ α1 ⋊⋉α2 in B, add (α ∧ δα) → (α1 ∧ δα1 ) ⋊⋉(α2 ∧ δα1 ) to B∗ .

A propositional interpretation ω is a model of 〈S∗ , B∗ 〉 iff

• ω is a model of S∗
• For every (α ∧ δα) → (α1 ∧ δα1 ) ⋊⋉ (α2 ∧ δα1 ) and β1 ⋊⋉β2 → β in B∗ such that ω |= ¬(α1 ∧δα1 )∨β1 and ω |= ¬(α2 ∧δα2 )∨β2, it holds that ω |= ¬(α∧δα)∨β.

Similar to the construction in the proof of Proposition 1, when Ω is a set of models of S∗ we can find relations B and B such that the conceptual structure C = (Ω, B, B, π) satisfies S∗ ∪ B∗ (for an arbitrary possibility distribution π).

We say that 〈S∗ ,B∗ 〉 |= α for α a propositional formula if every model of 〈S∗ ,B∗ 〉 is also a model of α. An irreflexive and transitive relation < on ∆ is an admissible priority relation if for every α ∈ A and every ∆0 ⊆ ∆ such that 〈S∗ ∪ ∆0 ∪ {α},B∗ 〉 |= ¬δα there is a δ ∈ ∆0 such that δ < δα. An admissible priority relation < induces a priority relation ≼ on models of 〈S∗ ,B∗ 〉 |=, where ω ≼ ω′ iff for every δ ∈ ∆ such that ω ̸|= δ and ω′ |= δ there exists a δ′ ∈ ∆ such that δ < δ′ , ω |= δ′ and ω′ ̸|= δ′ .

Finally, we say that α|∼β is conditionally entailed by 〈S∗ ,B∗ 〉 iff for every admissible priority relation < on ∆, it holds that β is satisfied in every model of 〈S∗ ∪ {α},B∗ 〉 which is minimal under the corresponding priority relation ≼.

Example 5. Consider the scenario from Example 3. The set S∗ contains

The set B∗ contains among others the rules β1 ⋊⋉β2 → ¬β3 and β3 ⋊⋉β2 → ¬β1 from B, and

It can be verified that in any model of 〈S∗ ∪ {α1 ∧ x ∧ y ∧ δ(α1∧x∧y)},B∗ 〉, one of the variables δα1 , δ(α1∧x), δα3 , δ(α3∧u) has to be false, hence in any admissible order one of these should have lower priority than δ(α1∧x∧y). Similarly, we find that one of these four variables should have a lower priority than δ(α1∧x∧y), that one of δα1 , δα3 should have a lower priority than δ(α1∧x), and that one of δα1 , δα3 should have a lower priority than δ(α3∧u). We can then show that (among others) α1|∼β1, α1 ∧ u|∼β1 and α1 ∧ u ∧ v|∼β1 can be conditionally entailed, but not α1 ∧x|∼β1 or α1 ∧x|∼¬β1, which is in accordance to the defaults that are valid for every minimally specific possibility distribution in Example 3.

For the scenario from Example 4, it can be verified that x1|∼y1 and x2|∼y2 can both be conditionally entailed, as we would intuitively expect, which corresponds to the defaults that are valid for one particular minimally specific possibility distribution.

The previous example suggests that conditional entailment does not suffer from the same problems as rational closure in an interpolation setting, although further work is needed to analyze its properties.

5 Conclusions

We have proposed an inference system in which interpolative reasoning can be applied to default rules. At the semantic level, both defaults and betweenness information are treated as constraints on conceptual structures. At the syntactic level, we have shown how the axioms of System P can be extended with an axiom encoding the interpolation principle, although we need a language in which propositional combinations of default rules can be expressed to allow for complete reasoning. We have then shown how the resulting form of preferential reasoning can be refined by generalizing the notion of conditional entailment.