Rational Inference Relations from Maximal Consistent Subsets Selection

1 Introduction

A very natural approach to draw plausible conclusions from an inconsistent belief base amounts to taking advantage of the maximal (for set inclusion) consistent subsets of the base (see e.g., [Rescher and Manor, 1970]). Quite surprisingly, very few inference mechanisms exist for defining an inference relation that is based on those subsets. Indeed, to the best of our knowledge, only three mechanisms have been identified so far in the literature (see e.g., [Pinkas and Loui, 1991; Benferhat et al., 1997]:

• skeptical inference, where a formula is a consequence of the base if it is implied by each maximal consistent subset,
• credulous inference, where a formula is a consequence of the base if it is implied by at least one maximal consistent subset,
• argumentative inference, where a formula is a consequence of the base if it is implied by at least one maximal consistent subset and its negation is not.

However, the credulous and the argumentative mechanisms are not satisfactory since they do not induce so-called preferential inference relations, i.e., they miss to satisfy some expected postulates for inference relations [Kraus et al., 1990]. Worse than that, credulous inference does not lead to jointly consistent conclusions since for inconsistent bases, it may be possible to infer credulously both a formula and its negation. Accordingly, the only fully rational choice identified in the literature is skeptical inference: it is the only inference mechanism that leads to preferential inference relations [Kraus et al., 1990]. The basic inference relation based on the skeptical inference mechanism considers every maximal consistent subset of the base. A well-known refinement of this relation consists in focusing on the largest maximal consistent subsets of the base. This relation is known to be rational [Benferhat et al., 1993].

The main question we want to address in this paper is to determine whether other refinements of the basic inference relation satisfying the expected postulates for nonmonotonic inference exist, and if the answer is positive, to characterize some of them. This is important because the inferential power of the inference relation based on all (or only the largest) maximal consistent subsets is sometimes very weak, as illustrated by the following example.

Consider a scenario where a belief base is made by putting together in a common repository some pieces of information, issued from several sources which are equally reliable, and represented by propositional formulae. Suppose also that the origins of the pieces of information (e.g., the sources they come from) are unknown or have been lost. This is a common assumption underlying for instance the AGM setting for belief revision, where it is supposed as well that one cannot trace back the pieces of beliefs [G¨ardenfors, 1988; G¨ardenfors, 1992]. In such a case, one cannot take advantage of them to make a selection of the subsets, as done for instance in belief merging [Konieczny, 2000; Konieczny and P´erez, 2002; Konieczny and P´erez, 2011]. For the sake of illustration, suppose that the (contradictory) pieces of information that were gathered concern an incoming model of car from our favorite brand (those pieces of information have been obtained through different sources, like car magazines, websites, friends, etc.). The first piece of information is that the new car has a 6-cylinder engine: ϕ1 = e6c. The second piece of information is that it has a manual gearbox: ϕ2 = mg. The third one is that it has a turbo (t) and that a car that has a 6-cylinder engine is a not a sport car: ϕ3 = t ∧ (e6c → ¬sc). The fourth one is that the car has a low fuel consumption (lc) and does not have a manual gearbox: ϕ4 = lc ∧ ¬mg. The fifth one is that it is a sport car (sc), that does not have a manual gearbox and that a sport car does not have a low fuel consumption, and that a car with a 6-cylinder engine does not have 4-wheel drive (wd4): ϕ5 = sc ∧ ¬mg ∧ (sc → ¬lc) ∧ (e6c → ¬wd4). The last one is that the car has 4-wheel drive, does not have a manual gearbox, and that cars with 4-wheel drive do not have a low fuel consumption, and that cars with 6-cylinder engine do not need a turbo: ϕ6 = wd4∧¬mg∧(wd4 → ¬lc)∧(e6c → ¬t).

It can be easily checked that K has 5 maximal consistent subsets, namely: K1 = {ϕ1, ϕ6}, K2 = {ϕ1, ϕ5}, K3 = {ϕ1, ϕ2, ϕ3}, K4 = {ϕ1, ϕ3, ϕ4}, K5 = {ϕ3, ϕ5, ϕ6}.

Using skeptical inference from all these maximal consistent subsets, none of the six formulae in K can be derived as a conclusion. This means that whenever the formula ϕi (with i ∈ {1, . . . , 6}), there exists a maximal consistent subset Kj (j ∈ {1, . . . , 5}) of K such that Kj |= ¬ϕi. Similarly, only ϕ3 can be derived from K provided that the largest maximal consistent subsets of K (here, K3, K4, and K5) are considered. As a consequence, only very weak conclusions composed of disjunctions of those formulae can be obtained as consequences. However, all the incoming pieces of information ϕi do not play symmetric role with respect to the maximal consistent subsets Kj . Consider for instance ϕ1 and ϕ2: we have that ϕ1 is a logical consequence of 4 (over 5) maximal consistent subsets of K, while ϕ2 is a logical consequence of only one of them. Since the global inconsistency of a belief base is often due to the presence in it of erroneous pieces of information, it makes sense to take advantage of this discrepancy to consider some pieces of information as more reliable than others because they are more consensual / less conflicting with the other pieces of information which have been reported.

In the following a new family of inference relations from maximal consistent subsets is presented. The key idea underlying them is to select some of the maximal consistent subsets of the base. This allows us to define inference relations with a stronger inferential power than the standard inference relation focusing on the consequences of all maximal consistent subsets. However, making the selection process arbitrary does not guarantee that the resulting inference relation is preferential, which is expected. Some principles are needed. In this direction, we define a general class of monotonic selection relations for comparing maximal consistent subsets. We provide several examples of inference relations from this class. We show that, whenever a monotonic selection relation is used to select the best maximal consistent subsets, the induced inference relation is preferential. Furthermore, it also satisfies rational monotony, i.e., it is a rational inference relation in the sense of [Lehmann and Magidor, 1992]. More than that, we provide a representation theorem showing that the class of rational inference relations of [Lehmann and Magidor, 1992] coincides with the class of skeptical inference relations from selected maximal consistent subsets, where the selection process is achieved using a monotonic selection relation.

2 Preliminaries

Our formal setting is classical propositional logic. Thus we consider a language L defined from a finite set V of propositional variables and the usual connectives. The elements of L are called formulae. An interpretation m is a mapping that assigns a truth value to every variable of V. We denote the set of interpretations of propositional logic by Mod(L). For a formula α and an interpretation m ∈ Mod(L), m is a model of α, denoted m |= α if α is true in m. For a formula α, we denote by Mod(α) the set of its models. We say that a model m is a model of a set of formulae S and write m |= S if for every formula α ∈ S, we have m |= α. For two formulae α, β, we write α |= β if every model of α is a model of β. For a set of formulae S and a formula α, we write S |= α if every model of S is a model of α. Given a set of formulae S, we denote Cn(S) = {α ∈ L | S |= α}, the set of consequences of S. We say that a set S is consistent if and only if it has at least one model. We say that a formula α is consistent if and only if the set {α} is consistent, and that α is a trivial formula if and only if α ≡ ⊤ or α ≡ ⊥.

Definition 1 (Belief base). A belief base is a finite set of formulae.

Standard notions when facing inconsistent belief bases are minimal inconsistent subsets, that encode the sources of conflicts in the base; and maximal consistent subsets, which can be considered as the potential repairs of the inconsistent belief base.

Definition 2 (mc). mc is a mapping defined as follows: for every belief base K, mc(K) is the set of all maximal (for set inclusion) consistent subsets of K:

• K′ ⊆ K
• K′ is consistent
• If K′ ⊂ K′′ ⊆ K, then K′′ is not consistent

Definition 3 (mus). mus is a mapping defined as follows: for every belief base K, mus(K) is the set of all minimal (for set inclusion) inconsistent subsets of K:

• K′ ⊆ K
• K′ is not consistent
• If K′′ ⊂ K′ , then K′′ is consistent

3 Inference from SelectedMaximal Consistent Subsets

Our main objective is to identify selection criteria on maximal consistent subsets, leading to minimize information loss from the belief base while guaranteeing that the induced inference relations are rational ones in the sense of [Lehmann and Magidor, 1992]. One already knows that such criteria exist, since the inference relation based on the largest maximal consistent subsets of K is rational [Benferhat et al., 1993], but we would like to identify other inference schemata and more general conditions on the set of all maximal consistent subsets which are sufficient to ensure that the corresponding inference relations are rational. To this end, we introduce new inference relations based on a selection of the maximal consistent subsets of K maximizing a given scoring function.

We will first define mappings that attach a score to each formula α of K and then aggregate those scores (in the following, we will simply sum up the scores; as will be discussed later, other aggregation functions could be considered alternatively).

Definition 4 (scoring function). A scoring function s associates with a belief base K and a formula α ∈ K a nonnegative real number s(K, α) which is equal to 0 if and only if α is a trivial formula (i.e., such that α ≡ ⊤ or α ≡ ⊥).

Here are some examples of scoring functions. The first one is based on the number of maximal consistent sets a formula belongs to.

Definition 5 (#mc). Let K be a belief base and α ∈ K. We define:

Another interesting example of a scoring function is based on the number of minimal inconsistent sets a formula belongs to. The scale must be reversed here, since this number must be minimized if one wants to give some preference to the less conflicting formulae. The addition of 1 in the second part of the definition is introduced in order to make sure that only trivial formulae can get the score 0.

Definition 6 (#mus). Let K be a belief base and α ∈ K. We define:

We could also use an inconsistency measure in order to attach scores to formulae. Let us consider the measure MIV , introduced by Hunter and Konieczny (2006; 2010), which is based both on the number of minimal inconsistent subsets containing a formula and on their cardinalities. The idea is that belonging to a large inconsistent set puts less blame on a formula than belonging to a small set.

Definition 7 (MIV). Let K be a belief base and α ∈ K. We define:

We can use MIV to define a scoring function miv as follows:

Definition 8 (miv). Let K be a belief base and α ∈ K. We define maxmiv(K) = maxα∈KMIVK(α) and

On this ground, the score of any subset of K can be computed by aggregating (e.g., using sum) the scores of its elements:

Definition 9 (scoresK,sum). Let s be a scoring function. Let K be a belief base, and let Ki ⊆ K. We note scoresK,sum(Ki) = ∑α∈Ki s(K, α).

Especially, we have:

The reader may observe that score#mc K,sum was the scoring function which was informally used in the introduction.

Let us now show how to infer conclusions from a belief base. We first need the following notation that will prove convenient: mc(K, α) = {Ki ⊆ K | Ki ∪ {α} ∈ mc(K ∪ {α})}.

Definition 10 (Inference from subsets with best scores). Let K be a belief base and α and β be two formulae. Let s be a scoring function. We define mcscoresK,sum (K, α) = {Ki ∈ mc(K, α) and there exists no K′i ∈ mc(K, α) such that scoresK,sum(K′i ) > scoresK,sum(Ki)}. We say that α |∼sK,sum β if and only if either α is inconsistent, or for every Ki ∈ mcscoresK,sum (K, α) we have Ki ∪ {α} |= β.

4 Examples

Let us now illustrate the introduced notions by stepping back to sport car example given in the introduction.

Example 1. We have #mc(K, ϕ1) = 4, #mc(K, ϕ2) = 1, #mc(K, ϕ3) = 3, #mc(K, ϕ4) = 1, #mc(K, ϕ5) = 2, #mc(K, ϕ6) = 2, so the score of K1 (resp. K2, K3, K4, K5) w.r.t. score#mc K,sum is equal to 6 (resp. 6, 8, 8, 7). Hence, the best sets are K3 and K4. Therefore, we have that

Hence, we conclude that the car has a 6-cylinder engine, a turbo, and is not a sport car.

We obtain exactly the same result with #mus and miv, so we do not give the details of the computation here. But let us illustrate on the next example that the three inference relations based respectively on the scoring functions #mc, #mus, and miv leads to distinct sets of consequences in the general case.

Example 2. Let K = {ϕ1, ϕ2, ϕ3, ϕ4, ϕ5, ϕ6, ϕ7} with ϕ1 = a ∧ b, ϕ2 = a ∧ (c ∨ d), ϕ3 = a ∧ ¬d, ϕ4 = a ∧ ¬c ∧ e, ϕ5 = ¬a ∧ ¬b, ϕ6 = a ∧ (¬c → ¬e), ϕ7 = a ∧ ¬c ∧ f

K has 9 minimal unsatisfiable subsets: M1 = {ϕ1, ϕ5}, M2 = {ϕ2, ϕ5}, M3 = {ϕ3, ϕ5}, M4 = {ϕ4, ϕ5}, M5 = {ϕ5, ϕ6}, M6 = {ϕ5, ϕ7}, M7 = {ϕ4, ϕ6}, M8 = {ϕ2, ϕ3, ϕ7}, M9 = {ϕ2, ϕ3, ϕ4}.

We have: #mc(K, ϕ1) = 4, #mc(K, ϕ2) = 2, #mc(K, ϕ3) = 3, #mc(K, ϕ4) = 2, #mc(K, ϕ5) = 1, #mc(K, ϕ6) = 2, #mc(K, ϕ7) = 3, so that the score of K1 (resp. K2, K3, K4, K5) w.r.t. score#mc K,sum is equal to 11

(resp. 11, 12, 12, 1). Hence, the best sets are K3 and K4. Therefore, we have that ⊤ |∼#mc K,sum a ∧ b ∧ ¬c ∧ ¬d ∧ f .

Let us count the number of minimal unsatisfiable sets containing a given formula; we have #mus(K, ϕ1) = 6, #mus(K, ϕ2) = 4, #mus(K, ϕ3) = 4, #mus(K, ϕ4) = 4, #mus(K, ϕ5) = 1, #mus(K, ϕ6) = 5, #mus(K, ϕ7) = 5, so the score of K1 (resp. K2, K3, K4, K5) w.r.t. score#mus K,sum is equal to 15 (resp. 19, 19, 20, 1). Hence, the best set is K4. And we have ⊤ |∼#mus K,sum a ∧ b ∧ ¬c ∧ ¬d ∧ ¬e ∧ f . Note that we can also conclude ¬e, which was not the case using #mc.

Let us now show how to compute scores using a Shapley inconsistency value. We have (rounded on two decimals): miv(K, ϕ1) = 3.50, miv(K, ϕ2) = 2.83, miv(K, ϕ3) = 2.83, miv(K, ϕ4) = 3.00, miv(K, ϕ5) = 1.00, miv(K, ϕ6) = 3.00, miv(K, ϕ7) = 3.17, so the score of K1 (resp. K2, K3, K4, K5) w.r.t. score miv K,sum is equal to 12.50 (resp. 12.16, 12.50, 12.50, 1.00). Hence, three sets are selected: K1, K3, K4. So we have ⊤ |∼miv K,sum a ∧ b ∧ ¬c ∧ f . This time, we are neither able to conclude ¬d nor ¬e.

5 Logical Properties

Let us now formally evaluate the introduced methods w.r.t. their logical rationality. There has been much work on the issue of determining the minimum logical properties that any nonmonotonic inference relation should satisfy [Gabbay, 1985; Makinson, 1994; Kraus et al., 1990; Lehmann and Magidor, 1992]. There is now a wide consensus on the fact that the minimal set of expected properties is the one of preferential inference relations [Lehmann and Magidor, 1992] (also called system P), and that an interesting subclass is the one of rational inference relations [Kraus et al., 1990] (also called system R).

Preferential inference relations are characterized by the following postulates:

A rational inference relation is a preferential relation that also satisfies the RM (rational monotony) postulate:

In this section, we show that the three inference relations defined above, as well as many other from the same class that we will formally define soon, satisfy the above postulates.

We start by generalizing the choice of the aggregation function. Previously, we considered sum in order to aggregate the scores of the formulae, but many other aggregation functions can be used instead.

Definition 11 (Aggregation function). ⊕ is an aggregation function if for every positive integer n, for every non-negative real number x1, . . . , xn, ⊕(x1, . . . , xn) is a non-negative real number.

Definition 12 (Properties of aggregation function). An aggregation function ⊕ satisfies:

• Composition if ⊕(x1, . . . , xn) ≤ (y1, . . . , yn) implies ⊕(x1, . . . , xn, z) ≤ (y1, . . . , yn, z)
• Decomposition if ⊕(x1, . . . , xn, z) ≤ (y1, . . . , yn, z) implies ⊕(x1, . . . , xn) ≤ (y1, . . . , yn)
• Symmetry if for every permutation σ, ⊕(x1, . . . , xn) = ⊕(σ(x1, . . . , xn))
• Monotonicity if for every z > 0 we have ⊕(x1, . . . , xn, z) > ⊕(x1, . . . , xn)

Composition, Decomposition and Symmetry were introduced in [Konieczny et al., 2004]. We add here a new property, Monotonicity, and slightly change Composition and Decomposition for dealing with tuples of different sizes.

Observe that sum satisfies the above conditions. Another well-known aggregation function satisfying the previous four properties is lexicographic aggregation [Konieczny et al., 2004; Dubois et al., 1996; Moulin, 1988].

One can then define the score of any subset of the input belief base:

Definition 13 (scoresK,⊕). Let s be a scoring function and ⊕ an aggregation function. Let K be a belief base and Ki ⊆ K with Ki = {α1, . . . , αn}.We define

Based on those scores, one can compare the subsets of the belief base:

Definition 14 (⪰K,⊕). Let s be a scoring function and ⊕ an aggregation function. Let K be a belief base, Ki, Kj ⊆ K. We state that Ki ⪰sK,⊕ Kj if and only if scoresK,⊕(Ki) ≥ scoresK,⊕(Kj ).

We will show that using a scoring function and an aggregation operator satisfying Composition, Decomposition, Symmetry and Monotonicity ensures to get a rational inference relation. However, the result we obtained is in fact much more general: it shows that selectingmaximal consistent subsets of the belief base using a monotonic selection relation is enough for giving rise to a rational inference relation, whatever this selection relation is induced or not from a scoring function. Formally:

Definition 15 (Monotonic selection relation). Given a belief base K, let ⪰K⊆ 2K × 2K be a reflexive, transitive and total relation 1 over the powerset of K. ⪰K is said to be a monotonic selection relation if for every consistent set Ki ⊆ K, for every non-trivial formula α ∈ K \ Ki, Ki ∪ {α} ≻K Ki.

For instance, consider the relation ⪰card that compares the subsets of K based on their cardinality:

Definition 16 (⪰card). For every two subsets Ki, Kj of K, Ki ⪰card Kj if and only if |Ki| ≥ |Kj|.

Clearly enough, ⪰card satisfies the conditions from Definition 15, thus it is a monotonic selection relation.

On this ground, one can define a selection mechanism which consists in keeping only the best sets with respect to a monotonic selection relation:

1 We use the standard notation Ki ≻K Kj for Ki ⪰K Kj and not(Kj ⪰K Ki).

Definition 17 (mc⪰K ). Given a belief base K, a formula α ∈ L, and a monotonic selection selection relation ⪰K, we define mc⪰K (K, α) = {Ki ∈ mc(K, α) | there exists no K′i ∈ mc(K, α) such that K′i ≻K Ki}.

We now show that all the scoring functions studied in this paper induce monotonic selection relations. Formally, we identify sufficient conditions under which a relation comparing the maximal consistent subsets based on a scoring function is a monotonic selection relation.

Proposition 1. Let K be a belief base, ⊕ be an aggregation function satisfying Composition, Decomposition, Symmetry and Monotonicity and let s be any scoring function. ⪰sK,⊕ is a monotonic selection relation.

Proof. Let Ki, Kj ⊆ K. Note that scoresK,⊕(Ki), scoresK,⊕(Kj) are non-negative real numbers. Since Ki ⪰sK,⊕ Kj if and only if scoresK,⊕(Ki) ≥ scoresK,⊕(Kj) we conclude that ⪰sK,⊕ is reflexive, transitive and total.

Let α ∈ K \ Ki be a non-trivial formula. Since ⊕ satisfies monotonicity, Ki ∪ {α} ≻sK,⊕ Ki. Thus, ⪰sK,⊕ satisfies monotonicity.

Let us now generalize Definition 10:

Definition 18 (Inference from best subsets wrt ⪰K). Given a belief base K, two formulae α and β, and a monotonic selection relation ⪰K, we state that α |∼mc⪰K K β if and only if either α is inconsistent, or for every Ki ∈ mc⪰K (K, α) we have Ki ∪ {α} |= β.

We can now present one of the main results of the paper:

Proposition 2. If ⪰K is a monotonic selection relation, then |∼mc⪰K K is rational.

Proof. Ref. If α is inconsistent, then the proof is trivial. So let α be consistent. Then mc(K, α) ̸= ∅. Consequently, mc⪰K (K, α) ̸= ∅. Trivially, for every Ki ∈ mc⪰K (K, α), Ki ∪ α |= α.

LLE. Since α ↔ β, mc(K, α) = mc(K, β). Furthermore, mc⪰K (K, α) = mc⪰K (K, β). We conclude that α |∼mc⪰K K γ implies β |∼mc⪰K K γ.

RW. If γ is inconsistent, then the proof is immediate. Else, let mc⪰K (K, γ) = {K1, . . . , Kn}. From what we supposed, for every Ki we have Ki ∪ {γ} |= α. Since |= α → β we have Ki ∪ {γ} |= β.

Cut. The case when α is inconsistent is trivial. In the rest of the proof we suppose that α is consistent. Since α |∼mc⪰K K β, β is consistent as well. Suppose α ∧ β |∼mc⪰K K γ and α |∼mc⪰K K β. By means of contradiction, suppose α |̸∼mc⪰K K γ. This means that there exists Ki ∈ mc⪰K (K, α) s.t. Ki ∪ {α} ̸|= γ. Observe that Ki ∪ {α} |= β. Note that Ki ∪ {α ∧ β} is consistent and that Ki ∪ {α ∧ β} ̸|= γ. Hence, Ki /∈ mc⪰K (K, α ∧ β). Let us prove that there exists Km ∈ mc⪰K (K, α ∧ β) s.t. Km ≻K K′i . Case 1: Ki ∈ mc(K, α ∧ β). Since Ki /∈ mc⪰K (K, α ∧ β), there

exists Km ∈ mc⪰K (K, α ∧ β) s.t. Km ≻K Ki.

Case 2: Ki /∈ mc(K, α ∧ β). Let Kl ∈ mc(K, α ∧ β) be s.t. Ki ⊆ Kl. Since ⪰K is a monotonic selection relation, Kl ≻K Ki. Let Km ∈ mc⪰K (K, α ∧ β). Then, Km ⪰K Kl. From transitivity of ⪰K, Km ≻K Ki.

In both cases, there exists Km ∈ mc⪰K (K, α ∧ β) s.t. Km ≻K Ki. Observe that Km ∪ {α} is consistent. Let us show that Ki /∈ mc⪰K (K, α).

Case 1: Km ∈ mc(K, α). Then Ki /∈ mc⪰K (K, α).

Case 2: Km /∈ mc(K, α). Let Kn ∈ mc(K, α) be s.t. Km ⊊ Kn. Since ⪰K is a monotonic selection relation, Kn ≻K Km ≻K Ki. In both cases Ki /∈ mc⪰K (K, α). Contradiction. So it must be that Ki ∪ {α} |= γ.

Or. The case when α ∨ β is inconsistent is trivial; in the rest of the proof we suppose that α ∨ β is consistent. Towards a contradiction, let α |∼mc⪰K K γ and β |∼mc⪰K K γ and suppose that α∨ β |̸∼mc K γ. Let Ki ∈ mc⪰K (K, α ∨ β) be such that Ki ∪ {α ∨ β} ̸|= γ. Let m be a model of Ki, i.e. m |= Ki, such that m ̸|= γ. It must be m |= α or m |= β. Without loss of generality, suppose m |= α. Observe that Ki ∪ {α} is consistent.

Let us prove that Ki ∈ mc(K, α) by using reduction ad absurdum. Thus, let us start by supposing that there exists K′i ⊆ K such that K′i ∪ {α} is consistent and Ki ⊊ K′i . Observe that K′i ∪ {α ∨ β} is consistent. Contradiction with Ki ∈ mc(K, α ∨ β). Thus it must be that Ki ∈ mc(K, α).

Let us now show that Ki ∈ mc⪰K (K, α). Again, towards a contradiction, let us suppose that Ki /∈ mc⪰K (K, α). Hence, there exists K′i ∈ mc(K, α) such that K′i ≻K K′i . Observe that K′i ∪ {α ∨ β} is consistent (since K′i ∪ {α} is consistent and α |= α ∨ β). Let us show that there exists Km ∈ mc(K, α ∨ β) s.t. Km ≻ Ki.

Case 1: K′i ∈ mc(K, α ∨ β) is obvious.

Case 2: K′i /∈ mc(K, α∨β). Then, there exists Kn ∈ mc(K, α∨ β) s.t. K′i ⊊ Kn. Since ⪰K is a monotonic selection relation, Kn ≻K K′i ≻K Ki.

In both cases, Ki /∈ mc⪰K (K, α ∨ β). Contradiction; thus it must be Ki ∈ mc(K, α). Observe that m |= Ki and m ̸|= γ. Thus, Ki ̸|= γ. Consequently, α |̸∼mc⪰K K γ. Contradiction. So it must be that α∨ β |∼mc⪰K K γ.

CM. We skip the trivial case when α ∧ β is inconsistent. Suppose α |∼mc⪰K K β and α |∼mc⪰K K γ. Towards a contradiction, suppose there exists Kj ∈ mc⪰K (K, α ∧ β) such that Kj ∪ {α ∧ β} ̸|= γ. Observe that Kj ∪ {α} is consistent and that Kj ∪ {α} ̸|= γ. Thus, Kj /∈ mc⪰K (K, α).

Let us prove that there exists Kl ∈ mc⪰K (K, α) such that Kl ≻K Kj.

Case 1: Kj ∈ mc(K, α). Since Kj /∈ mc⪰K (K, α), there exists Kl ∈ mc⪰K (K, α) such that Kl ≻K Kj.

Case 2: Kj /∈ mc⪰K (K, α). Like in the previous parts of the proof, we show that there exists Kn ∈ mc⪰K (K, α) such that Kn ≻K Kj. So we proved that there exists Kl ∈ mc⪰K (K, α) such that Kl ≻K Kj.

Observe that Kl ∪ {α} |= β, thus Kl ∪ {α ∧ β} is consistent. Let us show that Kl ∈ mc(K, α ∧ β). Towards a contradiction, suppose that there exists Kp ∈ mc(K, α ∧ β) s.t. Kl ⊊ Kp. There must exist δ ∈ Kp \ Kl. Since Kp ∪ {α} is consistent and Kl ⊊ Kp, Kl /∈ mc(K, α), contradiction. So it must be that Kl ∈ mc(K, α ∧ β). This means that Kj /∈ mc⪰K (K, α ∧ β), contradiction. Thus, for every Ks ∈ mc⪰K (K, α ∧ β), Ks ∪ {α∧ β} |= γ. Consequently, it holds that α∧ β |∼mc⪰K K γ.

RM. We skip the trivial case when α ∧ β is inconsistent. Suppose α |∼mc⪰K K γ and α |̸∼mc⪰K K ¬β and let us prove α∧ β |∼mc⪰K K γ. Observe that for every Kl ∈ mc(K, α) we have Kl ∈ mc(K, α ∧ β) if and only if Kl ∪ {α} ̸|= ¬β. Since α |̸∼mc⪰K K ¬β, there exists Ks ∈ mc⪰K (K, α) such that Ks ∪ {α} ̸|= ¬β. Thus, Ks ∈ mc(K, α ∧ β).

Let us show that Ks ∈ mc⪰K (K, α ∧ β). Towards a contradiction, let Kj ∈ mc⪰K (K, α ∧ β) be s.t. Kj ≻K Ks. Observe that Kj ∪ {α} is consistent. Let us prove that there exists Kl ∈ mc(K, α) such that Kl ≻K Ks. If Kj ∈ mc(K, α), the proof is over. Else, let Kn ∈ mc(K, α) be such that Kj ⊊ Kn. Since ⪰K is a monotonic selection relation, Kn ≻K Kj. Thus Kn ≻K Ks. We conclude that Ks /∈ mc⪰K (K, α). Contradiction. So it must be Ks ∈ mc⪰K (K, α ∧ β).

Let us prove that for every Kj ∈ mc(K, α ∧ β), if Kj ̸|= γ then Kj /∈ mc⪰K (K, α∧β). Since α |∼mc⪰K K γ, Kj /∈ mc⪰K (K, α). Since Kj ∪ {α} is consistent and ⪰K is a monotonic selection relation, by using a similar reasoning as before, we obtain that Ks ≻K Kj. Hence, Kj /∈ mc⪰K (K, α ∧ β). This means that α∧ β |∼mc⪰K K γ.

As a corollary, we get that:

Corollary 1. Let K be a belief base, ⊕ an aggregation operator satisfying Composition, Decomposition, Symmetry and Monotonocity and let s be any scoring function. Then |∼mc⪰sK,⊕ K is rational.

6 ACharacterization Result

We have shown that for each belief base K and each monotonic selection relation ⪰K, |∼mc⪰K K is rational. We now show the converse implication, namely, that for each rational relation |∼, there exists a belief base K and a monotonic selection relation ⪰K such that |∼mc⪰K K = |∼. More formally:

Proposition 3. For every rational relation |∼ defined on a logical language L built over a finite set V of propositional variables, there exists a belief base K ⊆ L and a monotonic selection relation ⪰K such that |∼mc⪰K K = |∼.

Proof. Let V = {x1, . . . , xn}. Since |∼ is a rational relation, we know from Theorem 5 by Lehmann and Magidor (1992) that there exists a ranked model W = 〈V, l,≺〉 defining this relation. Let K = {w1, . . . , w2n} be the base composed of all corresponding complete formulae, i.e.,

Let f be a mapping f : K → V such that for every w ∈ K, v = f(w) if and only if v ∈ V is a minimal with respect to ≺ state such that l(v) |= w.

Let us now define the relation ⪰K⊆ 2K × 2K . Let Ki, Kj ⊆ K. If |Ki| > |Kj|, let Ki ≻K Kj. If |Ki| = |Kj| ̸= 1, let Ki ⪰K Kj and Kj ⪰K Ki. If |Ki| = |Kj| = 1, we proceed as follows. Let Ki = {w′ } and Kj = {w′′ }. Let v′ = f(w′ ) and v′′ = f(w′′ ). If v′ ≺ v′′ , let Ki ≻K Kj. If v′′ ≺ v′ , let Kj ≻K Ki. Else, it must be that the two states are equally preferred. Let Ki ⪰K Kj and Kj ⪰K Ki. It is obvious that ⪰K

is a monotonic selection relation. Also α |∼ β if and only if α |∼W β, where |∼W is the relation defined by W [Lehmann and Magidor, 1992]. Also, it is immediate to see that α |∼W β if and only if α |∼mc⪰K K β, which concludes the proof.

Putting the last two results together, we obtain a new representation theorem for rational inference relations:

Theorem 1. A relation |∼ is rational if and only if there exists a belief base K and a monotonic selection relation ⪰K such that |∼mc⪰K K = |∼.

7 Conclusion

In this paper we have pointed out a new family of inference relations from inconsistent belief bases based on the selection of maximal consistent subsets. This selection leads to inference relations with a stronger inferential power than the basic relation based on all maximal consistent subsets. We have provided examples of inference relations from this family which preserve more consequences than the basic relation. The selection process must obey some principles to ensure that it gives rise to an inference relation which is preferential. We have defined a general class of monotonic selection relations for comparing maximal consistent sets that ensures this property. It turns out that this class corresponds precisely to the class of rational inference relations. Thus, we have obtained a new representation theorem for the class of rational inference relations in terms of deduction from (selections of) maximal consistent subsets.

The work presented in this paper is related to a number of approaches where inference is defined from maximal subsets of defaults (see e.g., [Reiter, 1980; Poole, 1988; Makinson, 2005]). Some propositions reported by G¨ardenfors and Makinson (1994) are quite close to results presented in this paper. Indeed, one can find several characterization results for nonmonotonic inference operators based on selection functions over maximal consistent subsets in their paper (see also [Freund, 1998] for related results on the links between extensions and preferential inference). The work by G¨ardenfors and Makinson (1994) nevertheless departs from our own one from several aspects. Thus, while we focus on finite classical propositional logic, G¨ardenfors and Makinson considered more general logical systems. Their representation theorem for rational inference also requires the base to be consistent and deductively closed, while in our approach, the base is finite, so it is not deductively closed, and it can be inconsistent.

A perspective for further research consists in determining the extent to which our results can be lifted from the flat case to the prioritized case. Indeed, though only few inference principles have been defined so far for dealing with inconsistent, flat bases K (as advocated in the introduction), there has been an abundant literature about the design of inference relations from preferred subbases of K, where the preference relation is induced from a plausibility ordering over the formulae in K (see e.g., [Brewka, 1989; Nebel, 1991; Benferhat et al., 1998]). It would be interesting to study how to combine the selection principles at work in such approaches with monotonic selection relations to give rise to new rational inference relations in the prioritized case.