A Comparative Study of Ranking Formulas Based on Consistency

1 Introduction

Representing preferences and reasoning about them have been extensively studied in Artificial Intelligence (AI) and notably in knowledge representation and reasoning, where a set of information is equipped with a partial or total preordering [Domshlak et al., 2011]. Nevertheless, classical logics begin under the assumption that all formulas are regarded equally important, and there is no preference between them. However, in many real-world situations, it is desirable to express preferences among information, especially when one data source is more reliable than another. To cope with such applications, a number of works were introduced to incorporate explicit orderings over formulas [Dubois and Prade, 1988; Delgrande and Schaub, 2000; Delgrande et al., 2004]. However, in many applications we may lack information about the data sources and/or their reliability or other explicit information in view of which formulas may be ranked according to plausibility, probability, etc.

In particular, in case a given knowledge base K is inconsistent one may still be interested in ranking formulas for several purposes. When trying to restore consistency in an informed way, one may proceed by trying to falsify specific (conflicting) information in K. We may think of a scientist facing an inconsistent data set. Dissatisfied with the inconsistency, she may want to conduct new experiments in the hope of falsifying some data and thereby restoring consistency. But where to begin? Some formulas in K may be more conflicting than others and it may make sense to target them first when searching for defeaters. On the other hand, one may be in a situation where one has to practically rely on K, in which case one is interested in identifying formulas which are involved in less conflicts (ideally none). A ranking rank : K → N on formulas in K may help in identifying the relevant information for both scenarios. But what does it mean for a formula to be more conflicting than others?

There are many ways of making this precise, many of which will be explored in this paper. Let us present two in order to familiarize the reader with some basic underlying ideas. One way is to make use of minimal conflicts (or minimal inconsistent sets), which are inconsistent subsets of K whose strict subsets are consistent. The dual notion is the one of a maxicon set (or maximal consistent subset) of K, i.e., a subset of K that is ⊆-maximal with the property of being a consistent subset of K.

Example 1. For instance, where K1 = {p, q, ¬(p ∧ q), ¬p, u}, the minimal conflicts are {p, ¬p} and {p, q, ¬(p ∧ q)}, while the maxicon sets are {p, q, u}, {p, ¬(p∧q), u} and {q, ¬(p ∧ q), ¬p, u}.

Approach 1. A formula present in more minimal conflicts is more conflicting than others and therefore it might be advisable to try to falsify it first, absent other information. The number of conflicts in which a formula is contained may be considered its rank. In this case:

If we engage in defeater search, we may want to start with searching for defeaters for p since it is the most conflicting formula (having the highest rank). If we have to rely on parts of the knowledge base, it may be best to stick to the least conflicting formulas with the lowest ranks, in this case u.

There is a richness of choices of formal explications of the idea of how conflicting a formula is. Moreover, different choices give rise to different outcomes. We motivate an alternative approach by means of another example.

Example 2. Consider K2 = {p, ¬(p∧q), q∧s, q∧¬s, q∧p}. We have the minimal conflicts {p, q ∧ s, ¬(p ∧ q)}, {p, q ∧ ¬s, ¬(p ∧ q)}, {p ∧ q, ¬(p ∧ q)} and {q ∧ s, q ∧ ¬s}. So, p has the rank 2, while p ∧ q has the rank 1.

This may seem counter-intuitive, given that a logically stronger formula is strictly ranked better than a weaker formula. It seems committing to p should be considered maximally as risky as committing to p ∧ q and it would seem strange to claim that p is more conflicting than the logically stronger p ∧ q. Let us therefore consider another idea.

Approach 2. Instead of counting the minimal conflicts a formula is part of, one could count the number of maxicon sets in which it is contained. The most unproblematic formulas, classical theorems, will be contained in every maxicon set. A formula contained in minimal conflicts will not be present in some. One could define the rank of a formula in K as the difference between the number of maxicon sets of K and the number of maxicon sets in which it is contained.

Example 3 (Ex.2 cont.). The maxicon set of K2 are {p, ¬(p∧ q)}, {p, q ∧ s, q ∧ p}, {p, q ∧ ¬s, q ∧ p}, {q ∧ s, ¬(q ∧ p)} and {q ∧¬s, ¬(p ∧ q)}. We have, for instance, that p receives the rank 2 and p ∧ q receives the rank 3.

Other approaches. As the reader will have noticed, many variations of the above presented ideas are possible. One of many ways to measure the inconsistency of a set of formulas is by counting the number of conflict sets. E.g., the inconsistency of K1 above is 2, the one of K2 is 4. The marginal distribution a formula α makes to the inconsistency of K can be measured by looking at the difference between the inconsistency of K and K\{α}. This difference may be considered the rank of α according to this alternative approach. As the reader can easily verify, in our Example 1 this results in:

Similarly, one could use other known inconsistency measures from the literature to determine the marginal contribution α makes to the inconsistency of K (e.g., [Ribeiro and Thimm, 2021; Thimm, 2016]). Finally, one may use other approaches to rank formulas, for instance, based on notions from game theory such as the Shapley value [Hunter and Konieczny, 2010], etc.

In this paper, we will comparatively study different options, identifying cases where the induced ranking coincide or differ. Additionally, one may have certain basic expectations concerning such rankings. E.g., formulas not involved in minimal conflicts should always receive rank 0, the rank of formulas should be robust under the addition of non-conflicting formulas to the knowledge base, etc. We will propose and study such postulates. By means of the postulate-based and comparative study, this paper provides a first systematic study of different approaches to ranking formulas based on consistency considerations. In the literature, various proposals have been made for the formula clustering problem. Basically, the goal is to organize the formulas into several groups and to compare them as a set (e.g., minimal conflicts, maxicon sets, etc.). A little further afield, in [Rescher and Manor, 1970, p. 186] we find the clustering of knowledge bases into innocent bystanders (non-members of minimal conflicts) and culprits (members of minimal conflicts). There has been a research effort to comparing maxicon sets in description logics [Bienvenu et al., 2014], existential rules [Yun et al., 2018], propositional logic [Konieczny et al., 2019], and databases setting [Kimelfeld et al., 2020]. More recently, in [Yun et al., 2018], the authors used inconsistency measures to rank and filter maxicon sets in existential rules knowledge bases.

Moreover, in [Ribeiro, 2022], the authors consider a preference relation on the subsets of a knowledge base given a formula α. However, such global evaluation could be not sufficient enough for real-world applications. A more focused comparison of the formulas individually might provide a clear picture on the plausibility of information as discussed previously. Contrastingly, there is few work on the formula ranking problem which is concerned with ordering a set of formulas, e.g., from the most to the least plausible ones. In the context of the situation calculus, [Klassen et al., 2018] have studied the incorporation of plausibility levels into the iterated belief change. Further, [Amgoud and Ben-Naim, 2015] used logical argumentation to rank conclusions based on the ranking of their target arguments. In [Ribeiro and Thimm, 2021], the authors have shown how culpability measures can induce a ranking among agent's beliefs. Then, a consolidation function is defined by removing preferably beliefs with high culpability values. Despite the existence of the abovecited works that can serve to rank formulas in knowledge bases, there exists no framework to formally compare the behaviour of these methods for ordering formulas in knowledge bases. In contrast with extant work that rely on prioritised logics, the key feature of our study is that it solely requires the inherent structure of the base to express a ranking reflecting a plausibility order on the formulas. This makes our approach widely applicable to various knowledge systems without the need of any external preference information.

2 General Setting

We assume an arbitrary finite set of propositional variables V. We use the set V with the usual classical connectives (¬, ∨, ∧, →) as well as the two constants ⊤ (true) and ⊥ (false) to build in the usual way the propositional language L(V). Well-formed formulas from L(V) are denoted by Greek letters α, β, γ, etc. We also denote by ⊢ the classical consequence relation. Two formulas α, β ∈ L(V) are called equivalent, denoted as usual by α ≡ β, if {α} ⊢ β and {β} ⊢ α. A knowledge base is a finite set of propositional formulas. We write KV to denote the set of all knowledge bases build over V. From now on, we let S# denote the cardinality of any set of sets S. Given K ∈ KV, we denote by Atoms(K) ⊆ V the set of all atoms occurring in K. Let Atoms(K) = {p1, . . . , pn} and let {q1, . . . , qn} ⊆ V be atoms not occurring in Atoms(K). We use K[q1, . . . , qn] to denote the syntactic substitution of each occurrence p1≤i≤n by q1≤i≤n in K. Also, K is said to be inconsistent if there exists a formula α such that K ⊢ α and K ⊢ ¬α. In the following, we use the notation K⊕α [resp. K⊖α] for K∪ {α} [resp. K \ {α}]. A Boolean interpretation w is defined as a total function from V to {0, 1}. By W we denote the set of all Boolean interpretations. An interpretation w ∈ W is a model of a formula α ∈ L(V) iff α is true w.r.t. w in the classical truth functional way. We recall some concepts which have widespread roles for reasoning under inconsistency in AI.

Definition 1. Given K ∈ KV , then, a subset M ⊆ K is a:

minimal inconsistent set of K iff M is inconsistent and ∀α ∈ M, M ⊖ α is consistent.

maximal consistent set of K iff M is consistent and ∀α ∈ K \ M, M ⊕ α is inconsistent. 1

minimal correction set of K iff K \ M is consistent, and ∀α ∈ M, K \ M ⊕ α is inconsistent.

For ease of notation, MI(K), MS(K) and MC(K) stand for the three notions, respectively. We define MS(α, K) = {M ∈ MS(K) | α ∈ M}, and MI(α,K) = {M ∈ MI(K) | α ∈ M}. Abusing notation, we define the minimal correction sets for a set of minimal inconsistent sets S ⊆ MI(K) as MC(S) = min⊆{M ⊆ K | ∀M ′ ∈ S,M ∩M ′ ̸= ∅}. A formula not involved in any MI of K is called a free formula. We use Free(K) to denote the set of free formulas in K, i.e., Free(K) = K \ ⋃ MI(K) = ⋂ MS(K). The formulas in K that are inconsistent are called self contradictory formulas and denoted as ⊥(K) = {α ∈ K | α ⊢ ⊥}. Let us also define Prob(K) to be the set of problematic formulas that are involved in at least a conflict, i.e., Prob(K) = ⋃ MI(K).

Definition 2. The following consequence relations are typically defined on the basis of MS(K) for a given K ∈ KV:

• K |∼∀ α iff for all M ∈ MS(K), M ⊢ α.
• K |∼∃ α iff for some M ∈ MS(K), M ⊢ α.

Let U(K) denote the set of universal conclusions of K, i.e., U(K) = {α | K |∼∀ α}. We say that α is nonmonotonically consistent with K if K |̸∼∃ ¬α. We write ⊤(K) for the set of all nonmonotonically consistent formulas with K.

3 Formula Ranking Framework

Our aim is to express preferences as ordinal rankings over a finite set of information by only using the inherent structure of the knowledge base. Such a ranking reflects the plausibility of each formula in the context of the information in the knowledge base. While we limit ourselves to propositional logic, the formula ranking semantics presented in this paper do not commit to any particular language (given decidability).

Definition 3. Given K ∈ KV, a ranking on K is a binary relation ⪰ over the elements of K such that ⪰ is total, reflexive and transitive. A formula ranking semantics σ is a mapping σ : KV → 2K×K which maps each knowledge base K to a ranking ⪰σK on K. α ⪰σK β means that α is at least as plausible as β by the semantics σ. If α ⪰σK β and β ⪰σK α, α and β are equally plausible and we write α ≃σK β, and if α ⪰σK β and β ̸⪰σK α, α is strictly more plausible than β and we write α ≻σK β.

Since our knowledge bases are finite, each ranking induces a unique (inversely) order-preserving surjective function to an initial sequence of natural numbers {0, . . . , n}, allowing to assign numerical ranks to formulas.

Given two formula ranking semantics σ1 and σ2 over K = {α1, . . . , αn}, the well-known Kendall-tau distance [Kendall, 1938] computes how many pairs of formulas over which σ1 and σ2 disagree, i.e., ∆(σ1, σ2,K) = |{(αi, αj) s.t. αi ≻σ1 K αj , αj ≻σ2 K αi, 1 ≤ i < j ≤ n}|. This distance can be [0,1]- normalized as: dτ(σ1, σ2,K) = 2×∆(σ1,σ2,K) n×(n-1) . Given the above, we are now ready to define the rank-(in)compatibility for formula ranking semantics.

1 Minimal inconsistent sets resp. maximal consistent sets are also known as minimal conflicts resp. maxicon sets.

Definition 4. Given two formula ranking semantics σ1 and σ2, we say that σ1 and σ2 are rank-compatible iff for all K ∈ KV , dτ (σ1, σ2, K) = 0; otherwise, σ1 and σ2 are rankincompatible.

Basically, if dτ(σ1, σ2,K) = 1, the two rankings obtained by the semantics σ1 and σ2 are in completely reversed order over K. Note that the concept of (in)-compatibility is of interest, since as we will see in the rest of the paper various criteria induce different rankings over the formulas of K. This is also the case for social rankings when using for instance the Shapley value or Banzhaf index [Doignon et al., 2022].

4 Postulates for Formula Ranking Semantics

We start our approach by providing some desirable requirements that allow to understand and compare the behaviour of our different formula ranking semantics. In all the properties listed below it is silently quantified over all K ∈ KV. We partition these postulates into five classes.

4.1 Syntax-based Postulates

The two following properties state that the names of the variables in K are not important for the comparison result.

Syntax Independence (SI). for every set {q1, . . . , qn} ⊆ V s.t. Atoms(K) ∩ {q1, . . . , qn} = ∅, ∀α, β ∈ K, we have α ⪰σK β iff α[q1, . . . , qn] ⪰σK[q1,...,qn] β[q1, . . . , qn].

Non-Interference (NI). Let γ be a formula which shares no atoms with K. Then, ∀α, β ∈ K, α ⪰σK β iff α ⪰σK⊕γ β.

4.2 Conflict-based Postulates

The second class of criteria concerns the robustness of rankings under the inconsistency in K.

In consistent bases, all formulas are ranked equally:

Non-Discrimination (ND). If Prob(K) = ∅, then ∀α, β ∈ K, α ≃σK β.

Inconsistent formulas are strictly worse than consistent ones:

Self Contradictory Formula (SF). ∀α ∈ K s.t. α ̸∈ ⊥(K), if β ∈ ⊥(K), then α ≻σK β.

Given an inconsistent K, a formula α ∈ K is centrally conflicting in K if after its removal K is consistent. A centrally conflicting formula should always be ranked (strictly) lower than one that is not centrally conflicting:

Central Conflict (CC). ∀α, β ∈ K, if K ⊖ α ⊬ ⊥ and K ⊖ β ⊢ ⊥, α ≺σK β.

Given α is at least as good as β, adding a formula with which α does not conflict preserves the relative ranking between α and β:

Decomposability (DE). ∀α, β ∈ K, α ⪰σK β and MI(α, K) = MI(α, K ⊕ γ) implies α ⪰σK⊕γ β.

4.3 Inference-based Postulates

Herein, we make four properties that express the behavior of rankings under logical relations between formulas of K.

Equivalent formulas shall be ranked equally:

Logical Equivalence (LE). ∀α, β ∈ K, if α ≡ β, then α ≃σK β.

Logically weaker formulas are as least as strong as logically stronger ones:

Weakening (WE). ∀α, β ∈ K, if α ⊢ β, β ⪰σK α.

Adding a logically stronger formula should not weaken the plausibility of a given formula:

Left Dominance (LD). For all α, β ∈ K, and for all γ, if γ ⊢ α and α ⪰σK β, then α ⪰σK⊕γ β.

Adding a logically weaker formula should not strengthen the plausibility of some formula:

Right Dominance (RD). ∀α, β ∈ K, and for all γ, if β ⊢ γ s.t. β ̸∈ ⊥(K), and α ⪰σK β, then α ⪰σK⊕γ β.

4.4 Freeness-based Postulates

The following properties express the role of free-conflict formulas on the robustness of rankings.

All free formulas are equally plausible:

Free Equivalence (FE). ∀α, β ∈ Free(K), α ≃σK β. Universal formulas are equally plausible:

Universal Equivalence (UE). ∀α, β ∈ U(K), α ≃σK⊕α⊕β β.

Free formulas are strictly better than those involved in conflicts: 2

Free Discernment (FD). If α ∈ Free(K), then ∀β ∈ Prob(K), α ≻σK β.

4.5 Update-based Postulates

These criteria concern the robustness of rankings under the addition/contraction of formulas. Obviously, the expansion of K by tautological formulas (which are free) should not impact the ranking, but what about other types of formulas (free, nonmonotonically consistent or universal ones)?

The first two postulates concern the update of knowledge bases with innocent bystanders.

Dynamic Freeness 1 (DF1). ∀α, β ∈ K, if α ⪰σK β then α ⪰σK⊕γ β, where γ ∈ Free(K ⊕ γ).

Dynamic Freeness 2 (DF2). ∀γ ∈ Free(K), ∀α, β ∈ K⊖ γ, if α ⪰σK β then α ⪰σK⊖γ β.

We can require similar dynamic properties for universal and nonmonotonically consistent consequences of K.

Dynamic Universality 1 (DU1). ∀γ ∈ U(K), ∀α, β ∈ K, if α ⪰σK β then α ⪰σK⊕γ β.

Dynamic Universality 2 (DU2). ∀γ ∈ U(K), ∀α, β ∈ K⊖ γ, if α ⪰σK β then α ⪰σK⊖γ β.

Dynamic Consistency 1 (DC1). ∀γ ∈ ⊤(K), ∀α, β ∈ K, if α ⪰σK β then α ⪰σK⊕γ β.

2 We omit some obvious variants of the given criteria for reasons of space (such as Universal Discernment, etc.).

Dynamic Consistency 2 (DC2). ∀γ ∈ ⊤(K), ∀α, β ∈ K⊖ γ, if α ⪰σK β then α ⪰σK⊖γ β.

To sum up, the above properties put upon formula ranking semantics are generally independent, except the following special cases where some of them follow from others.

Proposition 1. The following properties hold:

1. σ satisfies DF1 (resp. DF2) iff it satisfies DC1 (resp. DC2).
2. if σ satisfies DC1 (resp. DC2), then it satisfies DU1 (resp. DU2).
3. σ satisfies UE iff it satisfies FE.
4. if σ satisfies FE, then it satisfies ND.
5. if σ satisfies DE, then it satisfies LD.
6. if σ satisfies WE, then it satisfies LE.

5 Formula Ranking Semantics

This section presents different ways of ranking formulas in knowledge bases according to their plausibility. We also investigate the (in)-compatibility of the different formula ranking semantics. We will see that these ranking semantics could place the formulas in different orders.

5.1 Culpability-based Ranking Semantics

The key idea behind inconsistency measures is to quantize the amount of conflict in knowledge bases, and therefore they represent a good candidate for ranking information.

To put it simply, an inconsistency measure is a function I : KV,K → R≥0 that assigns a non-negative real value to K where I(K) = 0, if Prob(K) = ∅. Such value presents the intensity of conflict in the base K (see e.g., [Jabbour et al., 2014; Jabbour et al., 2016; Jabbour et al., 2017; Ammoura et al., 2017; Thimm and Wallner, 2019; Bona et al., 2019]). On the other hand, culpability measures, as defined in [Hunter and Konieczny, 2010; Ribeiro and Thimm, 2021], seek to evaluate the responsibility of a formula to render a base inconsistent. More precisely, a culpability measure is a function C on K×KV that associates a real value to each formula α ∈ K such that if Prob(K) = ∅, then C(α, K) = 0, ∀α ∈ K; and if α ∈ Prob(K), then C(α,K) > 0. Now, we present the first formula ranking semantics that makes use of culpability measures as follows:

Definition 5. Given a culpability measure C, a culpabilitybased ranking semantics associates to any K ∈ KV a ranking ⪰CK such that ∀α, β ∈ K, α ⪰CK β iff C(α, K) ≤ C(β, K).

Roughly speaking, the culpability-based ranking semantics ranks the formulas by decreasing score. Concretely, the lower the culpability value, the higher the plausibility of a formula, with the free formulas all being ranked equally at the top.

For illustration, let us now consider a particular culpability measure called the Shapley inconsistency value [Hunter and Konieczny, 2010], which uses the Shapley value to evaluate the contribution a formula makes to the inconsistency of the knowledge base. This measure is defined as follows:

Definition 6. Let K ∈ KV s.t. |K| = n, α ∈ K and I be an inconsistency measure s.t. I(K) = MI(K)#. Then, the Shapley inconsistency value (SIV) w.r.t. I is defined as:

That is, the SIV value is higher the more a formula is involved in conflicts of K. We make the choice in this paper to focus on the SIV value since it possesses the desirable postulates any rational measure should satisfy [Hunter and Konieczny, 2010]. It has been shown in [Hunter and Konieczny, 2008] that SIK(α) = ∑M∈MI(α,K) 1 |M| . In this way, the SIV value induces a preference ordering, which we call Shapley-based ranking, where ∀α, β ∈ K, α ⪰SIV K β iff SIK(α) ≤ SIK(β).

Example 4. Consider the knowledge base K = {p, ¬p, q, ¬(p ∧ q), r, ¬p ∧ r, s ∧ ¬s}. We have MI(K) = {{p, ¬p}, {p, q, ¬(p ∧ q)}, {p, ¬p ∧ r}, {s ∧ ¬s}}. Then, SIK(p) = 4 3 , SIK(¬p) = SIK(¬p ∧ r) = 12 , SIK(r) = 0, SIK(¬(p ∧ q)) = SIK(q) = 13 , and SIK(s ∧ ¬s) = 1. Hence, r ≻SIV K ¬(p ∧ q) ≃SIV K q ≻SIV K ¬p ≃SIV K ¬p ∧ r ≻SIV K s ∧ ¬s ≻SIV K p. This shows that Shapley ranking semantics can lead to counter-intuitive results, here a violation of SF.

5.2 Clustering-based Ranking Semantics

In this subsection, we turn to a more elaborate family of rankings semantics based on formula clustering. Central to the topic of reasoning with inconsistency are the crucial notions of minimal inconsistent and maximal consistent sets, which are used to cluster formulas from two complementary perspectives into several groups. In what follows, we use these two concepts as our primary criterion for defining rankings on the formulas.

MI-based ranking semantics. Given a knowledge base K, one might stratify the formulas of K based upon the minimal inconsistent sets. So, the plausibility rank of a formula can be measured by the conflicts in which the formula is involved.

Definition 7. Given K ∈ KV and α, β ∈ K, the MI-based ranking semantics associates to K a ranking ⪰MI such that ∀α, β ∈ K, α ⪰MI K β iff β ∈ ⊥(K), or MI(α,K)# ≤ MI(β,K)#, otherwise.

In words, the less conflicts in which a formula is contained, the less problematic it is, and thus the more plausible, with the self contradictory formulas all being ranked equally lower than any other formula. The rationale here is that to achieve consistency, one has to delete at least one formula from every MI, thus by removing a formula which is in more conflicts, one resolves more "rapidly" the inconsistencies. It is worth highlighting here that the MI-based ranking semantics can be obtained by taking the MIV# culpability measure [Hunter and Konieczny, 2008], defined as MIV#(α) = MI(α, K)#. However, this result remains valid only if ⊥(K) = ∅.

Despite that the Shapley-based ranking is MI-dependent, the next result shows that the MI- and the Shapley-based ranking semantics give different orderings on the formulas.

Theorem 2. The MI-based ranking semantics and the Shapley-based ranking semantics are rank-incompatible.

Now, we define a variant of MI-based semantics which will show to have some more intuitive properties. Before introducing it, let us first define an enriched notion of minimal inconsistent sets of α as follows: MI+(α,K) = {M ∈ MI(K) | ∃β ∈ M : α ⊢ β}. Intuitively, MI+(α,K) contains the set of conflicts the formula α participates in, both directly and indirectly (in the sense that a logically weaker formula participates). This gives rise to a new plausibility ordering among formulas as stated by Definition 8.

Definition 8. Given K ∈ KV and α, β ∈ K, the enriched MI-based ranking semantics associates to K a ranking ⪰MI+ such that ∀α, β ∈ K, α ⪰MI+ K β iff MI+(α,K)# ≤ MI+(β, K)#.

Example 6 (Ex. 2 cont.). Based on the set K1 = {p, ¬(p ∧ q), q ∧ s, q ∧ ¬s, p ∧ q}, we have seen that WE is violated by MI. Where α = p ∧ q and β = p, recall that MI(p, K)# = 2 = ({{p, ¬(p∧q), q∧s}, {p, ¬(p∧q), q∧¬s}})# > MI(p∧ q, K)# = 1 = ({{p∧q, ¬(p∧q)}})#. The situation changes when we move to MI+. We now have: MI+(p,K)# = ({{p, ¬(p ∧ q), q ∧ s}, {p, ¬(p ∧ q), q ∧ ¬s}})# = 2 < 3 = MI+(p ∧ q, K)# = ({{p ∧ q, ¬(p ∧ q)}} ∪ MI+(p, K))#.

Theorem 3. The MI-based ranking semantics and the MI+- based ranking semantics are rank-incompatible.

MS-based ranking semantics. The well-known inference relations (see Def. 2) are based on the notion of maximal consistent sets. These sets induced a natural way to rank formulas. Namely, given K ∈ KV, the formulas can been stratified into priority levels based on their belonging to MS(K).

Definition 9. Given K ∈ KV and α, β ∈ K, the MS-based ranking semantics associates to K a ranking ⪰MS such that ∀α, β ∈ K, α ⪰MS K β iff MS(α,K)# ≥MS(β,K)#.

The intuition underlying this ranking is: the more maximal consistent sets of K contain a formula, the more plausible is the formula.

Example 7 (Ex. 4 cont.). We have MS(K) = {{p, q, r}, {p, ¬(p ∧ q), r}, {¬p, q, ¬(p ∧ q), r, ¬p ∧ r}}. Then, r ≻MS K p ≃MS K q ≃MS K ¬(p ∧ q) ≻MS K ¬p ≃MS K ¬p ∧ r ≻MS K s ∧¬s.

At a first glance, one might think that the notions of minimal inconsistent sets and maximal consistent sets lead to the same formula ranking. However, it turns out that the MSand MI-based ranking semantics are different (as has been observed in the introduction).

Theorem 4. The MS-based ranking semantics and the MIbased ranking semantics are rank-incompatible.

5.3 Update-based Ranking Semantics

This subsection examines other forms of formula rankings based on the update of knowledge bases. Let us state the idea precisely: instead of focusing on the set of maximal consistent sets or minimal inconsistent sets in which the formula appears, we can build a ranking dynamically by evaluating the impact of contracting a formula from the knowledge base. In essence, this novel ranking semantics will be investigated for the cases of minimal inconsistent, maximal consistent sets and the set of problematic formulas.

Ranking-based onMI-revision. This ranking semantics is based on the number of minimal inconsistent sets of K that would be eliminated if a formula α was removed from K.

Definition 10. Given K ∈ KV and α, β ∈ K, the revision MI-based ranking semantics (in short, MIR-based ranking semantics) associates to K a ranking ⪰MIR such that ∀α, β ∈ K, α ⪰MIR K β iff MI(K⊖α)# ≥MI(K⊖β)#.

According to this semantics, a formula whose removal "destroys" less minimal inconsistent sets is selected as a more plausible formula (for instance, the removal of a free formula leaves the minimal inconsistent sets intact whence it should be considered most plausible). Just like the other rankings, this ranking can be expressed equivalently by a numerical ranking. Since this may be less obvious, we show how.

Interestingly, it can be shown that the ranking obtained under the MI-based ranking semantics coincides with the one based on revision MI-based semantics.

Theorem 6. For knowledge bases K for which ⊥(K) = ∅, the MI-based ranking semantics and the MIR-based ranking semantics are rank-compatible.

Ranking-based on MS-revision. Now, we define the rank of a formula α as the number of maximal consistent sets of K that would be eliminated if α was removed from K. Hence, we might prefer a formula that destroys more maximal consistent sets.

Definition 11. Given K ∈ KV and α, β ∈ K, the revision MS-based ranking semantics (in short, MSR-based ranking semantics) associates to K a ranking ⪰MSR such that ∀α, β ∈ K, α ⪰MSR K β iff β ∈ ⊥(K), or MS(K ⊖ α)# ≥ MS(K⊖β)#, otherwise.

The MSR-based preference relation can be expressed by a numerical ranking. Let rankK(α) = MS(K)# -MS(K ⊖ α)# if α /∈ ⊥(K), and rankK(α) = ∞ else. Then,

Theorem 8. The MS-based ranking semantics and the MSRbased ranking semantics are rank-incompatible.

Example 8 (Ex. 4 cont.). For the knowledge base K, we have MS(K ⊖ p) = {{¬p, q, ¬(p ∧ q), r, ¬p ∧ r}}, MS(K ⊖ ¬p) = {{p, q, r}, {q, r, ¬(p ∧ q), ¬p ∧ r}, {p, r, ¬(p ∧ q)}}, MS(K ⊖ q) = {{p, ¬(p ∧ q), r}, {¬p, ¬(p ∧ q), r, ¬p ∧ r}}, MS(K ⊖ r) = {{p, q}, {p, ¬(p ∧ q)}, {¬p, q, ¬(p ∧ q), ¬p ∧ r}}, MS(K⊖¬(p∧q)) = {{p, q, r}, {¬p, q, r, ¬p∧r}}, and MS(K⊖¬p ∧ r) = {{p, q, r}, {¬p, q, ¬(p ∧ q), r}, {p, ¬(p ∧ q), r}}. Then, r ≃MSR K ¬p ≃MSR K ¬p ∧ r ≻MSR K q ≃MSR K ¬(p ∧ q) ≻MSR K p ≻MSR K s ∧ ¬s which is different from the MS-based ranking.

Maybe surprisingly, the MSR-based semantics is rankincompatible with the one based on MI-based semantics, as well as with the MS-based semantics.

Theorem 9. The MSR-based ranking semantics and the MI-based (resp. the MS-based) ranking semantics are rankincompatible.

Ranking-based on problematic formulas revision. This semantics compares information by counting the number of problematic formulas after removing the formula α from the knowledge base. More formally,

Definition 12. Given K ∈ KV and α, β ∈ K, the problematic-based ranking semantics (in short, Probbased semantics) associates to K a ranking ⪰Prob such that ∀α, β ∈ K, α ⪰Prob K β iff |Prob(K⊖α)| ≥ |Prob(K⊖β)|.

Intuitively, a formula is more plausible if its removal affects slightly the other formulas status in K.

Theorem 10. The MI-based ranking semantics and the Probbased (resp. the MS-based) ranking semantics are rankincompatible.

5.4 Distance-based Ranking Semantics

Up to this point, we have defined formula ranking semantics that are all syntax-dependent. To discriminate among formulas, this section is intended to introduce another criterion to grade formulas according to their plausibility. More precisely, this new criterion could be expressed via the closeness of a formula to the consistency, namely the maximal consistent sets, or the free set of K.

Consistency-based distance. This semantics is based on minimizing the distance to the maximal consistent sets of the knowledge base. More precisely, a formula α is more plausible in K if it is not far away from maximal consistent sets of K. Before we introduce our consistency-based ranking semantics, we shall consider the distance between two interpretations d : W × W → N, satisfying the usual properties (i) for all w1,w2 ∈ W, d(w1,w2) = d(w2,w1), and (ii) d(w1, w2) = 0 iff w1 = w2. Numerous notions, already studied in logic and AI, can be used to define the distance between interpretations. A commonly used distance that we consider here is the hamming distance [Dalal, 1988] where the function dH(w1,w2) returns n if w1 and w2 differ on n atoms. Clearly, the function dH(w1,w2) induces a hamming distance for each pair of formulas such as dH(α, β) = ∞ if α ∈ ⊥(K) or β ∈ ⊥(K), dH(α, β) = min w1|=α,w2|=β dH (w1, w2),

otherwise. Now, the hamming distance between a formula and a consistent set of formulas K can be formulated as: dH(α,K) = dH(α, ∧β∈K β). Thereafter, our intent is to determine a plausibility order on the formulas where the most plausible formulas are those that are as close as possible to the maximal consistent sets of K. Towards this end, the formulas will be ranked by increasing order of their distance to MS(K). Let us start by associating with each formula α ∈ K a distance vector VMS(α,K) = (dH(α,M1), . . . , dH(α,Mn)) with MS(K) = {M1, . . . ,Mn}. Note that this vector is sorted in nondecreasing order. By doing this, a way to rankorder formulas is by simply comparing their distance vectors.

Definition 13. Given K ∈ KV s.t. MS(K) = {M1, . . . ,Mn}, and α, β ∈ K, the consistency-based ranking semantics associates to K a ranking ⪰d such that α ⪰dK β iff VMS(α, K) ≥d VMS(β, K) where ≥d is an order relation over vectors.

The consistency-based ranking semantics is general enough to consider various instantiations of the order relation ≥d over vectors. Obvious choices for this vector ranking ≥ include the min: in such case, the induced ranking ⪰min K is dichotomous, that is, formulas can be split into two main groups: consistent formulas in an inconsistent base seen as equally plausible, followed by self contradictory formulas judged as the worst plausible ones; the avg: this allows for computing the average up the distance vectors. Notice that the induced ordering ⪰avg K allows for compensation between distances. The third relation is the lexicographic order lex defined as follows: VMS(α,K) ≥lex VMS(β,K) iff VMS(α,K) = VMS(β,K), or there exists k ≤ n s.t. V kMS (α,K) < V kMS (β,K) and V iMS (α,K) = V iMS (β,K) for each i < k where V iMS (α, K) is the i-th value in VMS.

Theorem 12. The Consistency-based semantics w.r.t. ≥lex (in short, Conslex-based) and the MSR-based ranking semantics are rank-incompatible.

Freeness-based distance. The last formula ranking semantics follows the intuition that the more close a formula is to the free ones, the more plausible is, since the free formulas are the most plausible formulas in the knowledge base.

Definition 14. Given K ∈ KV and α, β ∈ K, the freenessbased ranking semantics associates to K a ranking ⪰Free such that ∀α, β ∈ K, α ⪰Free K β iff min{|M|,M ∈ MC(MI(α, K)) \ {α}} ≤ min{|M|, M ∈ MC(MI(β, K)) \ {β}}.

Intuitively, this ranking semantics encodes the fact that the distance of α to the free set of K is the minimum set of formulas that need to be removed in order to make α free in K.

Theorem 13. The Conslex-based ranking semantics and the freeness-based ranking semantics are rank-incompatible.

6 Discussion

Table 1 summarizes the satisfaction of the postulates (Section 4) by the different formula ranking semantics.

A number of observations can be made regarding the rank(in)compatibility between rankings and the results reported in Table 1. First of all, the formula ranking semantics studied in this paper are mostly rank-incompatible. For many pairs of ranking (in)compatibilities are by no means obvious: e.g., although MIR and MI are compatible (when ⊥(K) = ∅), the same does not hold for MSR and MS (resp. and MI). What the many incompatibilities show is that the different approaches to consistency measurement indeed make a difference in the ranking of information, despite their underlying similarities, and that this difference can be evaluated by means of a postulate-based analysis. Despite their rankincompatibility, all the formula ranking semantics rank free formulas at the top. In addition, if the knowledge base is consistent, all formulas are equally plausible according to the different ranking semantics investigated in this paper. However, we remark that there is no consensus regarding self contradictory formulas as some rankings semantics may rank these formulas not as the least plausible ones, e.g., MI- or Shapley-based semantics. This seems clearly a shortcoming which is captured by the fact that the SF property holds only for MI+-, MS- and Conslex-based semantics. Further, Table 1 shows that syntax-, freeness-, and update-based postulates are shared by the different formula ranking semantics. This seems intuitive since these properties seem natural candidates for minimal requirements on rankings. We also note that the LD postulate is satisfied by all ranking semantics except for the Prob-based semantics. More interestingly, as one can see, some other properties demarcate specific rankings. To be precise, the CC and DE postulates are satisfied only by Shapley, MI- and MIR-based semantics, except for DE which also holds for freeness-based ranking. These two postulates allow to distinguish between MI- and MSR-based rankings. Moreover, the very basic WE property is satisfied only by the MI+, MS and Conslex rankings. Lastly, Table 1 shows that the MI+ and MS-based ranking semantics strictly dominate all the other rankings by satisfying all the considered postulates except for CC and DE.

7 Summary and FutureWork

In this paper, a framework for ranking semantics in propositional logic was presented, where formulas are ranked based on consistency by using solely the inherent structure of the knowledge base. A broad family of properties is also investigated, some of them are satisfied by all ranking semantics, while others (e.g. CC, WE, DE) better discriminate between some rankings. We have also shown that almost ranking semantics are pairwise incompatible. In future work we will consider other semantics, such as argumentationbased rankings [Amgoud and Ben-Naim, 2015], rankingsbased on multi-valued logics and rankings-based on MC sets [Mu, 2015]. This paper provides a first step to possible future characterization results concerning sets of criteria.

Acknowledgments

This work was funded, in part, by the Agence Nationale de la Recherche ANR under grant EXPIDA: ANR-22-CE23-0017.