Formulas Free From Inconsistency: An Atom-Centric Characterization in Priest's Minimally Inconsistent LP (Extended Abstract)

1 Introduction

It has been increasingly recognized that measuring inconsistency for knowledge bases is a good starting point for facilitating the process of inconsistency handling in a wide variety of applications [Mu et al., 2013a; Mu et al., 2013b; Hunter and Konieczny, 2010; Hunter, 2006; McAreavey et al., 2011; Picado-Mui˜no, 2011; Liu and Mu, 2017]. Here a knowledge base refers to a finite set of propositional formulas. Without loss of generality, we assume that an inconsistency measure is a function from the set of all knowledge bases to [0,+∞) such that the higher the value assigned to a knowledge base, the more inconsistent that knowledge base is.

A growing number of inconsistency measures have been proposed so far. A more detailed survey of inconsistency measures has been given by Thimm [Thimm, 2018]. Although each of these measures was proven to exhibit some good behaviours tailed to some certain (often restricted) perspectives, it has been reported that different inconsistency measures may bring different (possibly incompatible) characterizations of inconsistent knowledge bases [Grant and Hunter, 2011]. Such a dilemma makes properties for characterizing desirable inconsistency measures more necessary.

* This paper is an extended abstract of an article in Journal of Artificial Intelligence Research[Mu, 2019].

The set of basic properties presented by Hunter and Konieczny [Hunter and Konieczny, 2006; Hunter and Konieczny, 2008] provides a good starting point for characterizing inconsistency measures. A number of variants of this set have been proposed by adapting or revising some ones of this set [Mu et al., 2011; Jabbour et al., 2014; Jabbour et al., 2016; Besnard, 2014; Besnard, 2017]. The property of Free Formula Independence, one of Hunter and Konieczny's basic properties, aims to capture an intuition that formulas independent of inconsistency have no impact on the assessment of inconsistency in a knowledge base. Here free formulas of a knowledge base refer to ones that are not involved in any minimal inconsistent subset (an inconsistent subset without a proper inconsistent subset) of the knowledge base. Then Free Formula Independence grasps the intuition well in the context of inconsistency characterized by minimal inconsistent subsets.

Characterizing inconsistency in terms of minimal inconsistent subsets provides a syntactic perspective to analyse the inconsistency in a knowledge base. Besides this, atoms assigned to non-classical truth values by some paraconsistent models such as Belnap's four-valued semantics [Belnap, 1977; Arieli and Avron, 1998] and Priest's LPm semantics [Priest, 1991] have been also used to characterize inconsistency [Hunter and Konieczny, 2010; Ma et al., 2011]. However, the independence of free formulas from minimal inconsistent subsets cannot ensure that the property of Free Formula Independence is also appropriate for characterizing atom-centric inconsistency measures stemming from the inconsistency characterization based on paraconsistent models [Hunter and Konieczny, 2010]. Here atom-centric inconsistency measures refer to ones that take into account the proportion of the language involved in inconsistency [Hunter and Konieczny, 2010]. Then the property of Free Formula Independence has been weakened to characterize such situations by replacing free formulas with safe formulas [Thimm, 2009; Hunter and Konieczny, 2010].

On the other hand, it has been argued that the notion of safe formula cannot cover the tautology, which is free from inconsistency in intuition [Besnard, 2017]. Then an alternative set of Hunter and Konieczny's properties has been presented by Besnard, in which two postulates Tautology Independence and Conjunct Independence together entail that adding a formula safely consistent for a knowledge base to that base has no impact on the inconsistency assessment of that base [Besnard, 2017]. However, if we consider only the formulas built upon atoms involved in a knowledge base, then such a safely consistent formula for that base must be a tautology, as shown in [Mu, 2019]. This implies that the term of safely consistent formula is not general enough to cover formulas free from inconsistency characterization.

In this paper, we propose an atom-centric characterization of formulas that are independent of inconsistency in Priest's minimally inconsistent LP (Logic of Paradox) LPm [Priest, 1991], which is one of the simple paraconsistent logics often used to exemplify the inconsistency characterization in terms of paraconsistent semantics [Konieczny et al., 2003; Hunter and Konieczny, 2010]. Inspired by the invariance of minimal inconsistent subsets, we propose a new counterpart of the notion of free formula in LPm, which can cover the tautology, the safe formula and the safely consistent formula. But it cannot rule out some formulas not really free fromminimal inconsistent subsets. That is, such a semantic characterization of independence may lead to some undesired result in syntactic aspect. Then we enhance the counterpart and propose a notion of Bi-free formula, which is used to capture formulas that are independent of both syntactic and atomcentric inconsistency characterizations in the framework of Priest's minimally inconsistent LP. Moreover, we show that our counterparts are more general than the other alternatives of free formulas. Finally, the corresponding counterparts of the property of Free Formula Independence are also given.

The rest of this paper is organized as follows. In Section 2, we introduce some necessary notions about inconsistency characterization and alternatives of the property of Free Formula Independence. In Section 3, we propose the notion of B-atom-free formula, which is a counterpart of free formula in Priest's minimally inconsistent LP LPm. In Section 4, we propose the notion of Bi-free formula, which is appropriate for characterizing formulas free from both syntactic and semantic inconsistency characterizations in the framework of Priest's LPm. Finally, we conclude this paper in Section 5.

2 Preliminaries

Let P be a finite set of propositional atoms and L a propositional language built from P and two propositional constants ⊤ (true) and ⊥ (false) under connectives {¬, ∧, ∨}. We use a, b, c, · · · to denote propositional atoms, and α, β, γ, · · · to denote propositional formulas. In addition, we use α ≡ ⊤ to denote that α is a tautology.

A knowledge base K is a finite set of propositional formulas. We use At(K) to denote the set of atoms appearing in formulas of K.

We use K ⊢ ⊥ (resp. K ̸⊢ ⊥) to denote that a knowledge base K is inconsistent (resp. consistent). We useMI(K) to denote the set of all the minimal inconsistent subsets of K. A formula in K is called a free formula if this formula does not belong to any minimal inconsistent subset of K. We use FF(K) to denote the set of free formulas of K.

The LPm model [Priest, 1991] of knowledge bases is given in the framework of Priest's Logic of Paradox (Priest's LP for short) [Priest, 1979], which provides three-valued models for knowledge bases by expanding the classical truth values {T, F} to the set {T, F, {T, F}}, in which the third truth value {T, F} (abbreviated as B ) is considered intuitively as both true and false [Priest, 1991]. Here we use the following concepts about the LPm model used in [Hunter and Konieczny, 2010]. An interpretation ω for LPm models maps each atom to one of the three truth values T, F, B such that

• ω(⊤) = T, ω(⊥) = F,
• ω(¬α) = B iff ω(α) = B, ω(¬α) = T iff ω(α) = F,
• ω(α∧ β) =min≤t{ω(α), ω(β)},
• ω(α∨ β) =max≤t{ω(α), ω(β)},

where F <t B <t T. Then the set of models of a formula α is defined as ModLP(α) = {ω|ω(α) ∈ {T, B}}. Further, the set of models of a knowledge base K is defined as

Let ω be a model of K, then we use ω!(K) to denote the set of propositional variables of K assigned to B by ω. Based on ω!(K), we call a model ω of K a minimal (inconsistent) model of K if there is no ω′ ∈ ModLP(K) such that ω′ !(K) ⊂ ω!(K). We use MinModLP(K) to denote the set of minimal models of K. Essentially, each ω ∈ MinModLP(K) is one of the "most classical" models of K, and ω!(K) describes a minimal set of atoms that have to be assigned to B by ω. We call the elements of ω!(K) the B-atoms of ω w.r.t. K if ω is a minimal model of K. From now on, we use B(ω) to denote the set of B-atoms of the minimal model ω.

The property of Free Formula Independence, one of Hunter and Konieczny's basic properties for characterizing desirable inconsistency measures, is to capture the intuition that formulas free from inconsistency of a knowledge base have no impact on the evaluation of the inconsistency of that base. Let I be an inconsistency measure for knowledge bases, then Free Formula Independence can be given as follows:

It has been reported that not all the free formulas are free from the inconsistency in other contexts of inconsistency characterization [Hunter and Konieczny, 2010]. Then a weaker alternative of Free Formula Independence, called Safe Formula Independence, has been proposed to accommodate such cases [Hunter and Konieczny, 2010]:

• Safe Formula Independence: If α is a safe formula of K ∪ {α}, then I(K ∪ {α}) = I(K).

Here a formula α ∈ K is called a safe formula if α ̸⊢ ⊥ and At({α}) ∩ At(K \ {α}) = ∅ [Hunter and Konieczny, 2010; Thimm, 2017]. A safe formula is a special kind of free formula.

However, Besnard has argued that the term safe formula cannot cover tautologies, and then this weaker version does not entail the following property of Tautology Independence [Besnard, 2017], which is a straightforward consequence of Free Formula Independence:

• Tautology Independence: If α ≡ ⊤, then I(K∪{α}) = I(K).

Then the property of Free Formula Independence is replaced by Tautology Independence, together with the following property of Conjunct Independence [Besnard, 2017]:

• Conjunct Independence: If α∧β ̸∈ K, β ̸∈ K, and α is safely consistent for K ∪ {β}, then I(K ∪ {α ∧ β}) = I(K ∪ {β}).

Moreover, it has been shown that Tautology Independence and Conjunct Independence together entails that I(K ∪ {α}) = I(K) if α is safely consistent for K [Besnard, 2017].

Here a formula α is safely consistent for K (a safely consistent formula of K ∪ {α} for short in this paper) if there exists a substitution σ such that σα is a tautology and σa = a for all a ∈ At(K), but either σb = b or σb = ⊥ or σb = ⊤ for all b ∈ At({α}) \ At(K) [Besnard, 2017]. It has been shown that the term safely consistent formula can cover safe formulas, that is, if α is a safe formula for K∪{α}, then α is safely consistent for K [Besnard, 2017].

3 The B-Atom-Free Formula

The safely consistent formula is more general than the safe formula. It covers the tautology as well. However, as shown in [Mu, 2019], if a safely consistent formula of a knowledge base has no atom different from ones of other formulas, then it must be a tautology. This implies that the notion of safely consistent formula is not general enough to capture the formula free from inconsistency in Priest's LPm.

In this section, we focus on characterizing formulas free from inconsistency in the framework of Priest's LPm. We start with the following characterization of the role of free formulas in terms of invariance of minimal inconsistent subsets. Let K be a knowledge base and α ∈ K. Then

• α ∈ FF(K) if and only if MI(K) =MI(K \ {α}).

This characterization inspires us to characterize the formulas free from inconsistency in the framework of Priest's LPm using the invariance of inconsistency characterization. Intuitively, for each minimal model of K, the B-atoms B(ω) of ω w.r.t. K are exactly ones that have to be considered contradictory when we give a definitely true or false value to other atoms. We use BA(K) to denote the set of all Batoms of minimal models of K, i.e., BA(K) = {B(ω)|ω ∈ MinModLP(K)}. Then BA(K) can be considered as a characterization of inconsistency in K from an atom-centric perspective.

To capture the invariance of inconsistency characterization in the framework of Priest's LPm, we give the following counterpart of the notion of free formula.

Definition 1. Let K be a knowledge base and α ∈ K. Then we call α a B-atom-free formula of K if BA(K) = BA(K \ {α}).

Essentially, the independence of the B-atom-free formula of inconsistency characterization stems from the invariance of the set of B-atoms in Priest's LPm. In this sense, the notion of B-atom-free formula captures the underlying idea of free formula.

The following proposition shows that the notion of Batom-free formula can cover the tautology, the safe formula, and safely consistent formulas.

Proposition 1. Let K be a knowledge base and α ∈ K.

1. If α ≡ ⊤, then α is a B-atom-free formula of K.
2. If α is a safe formula, then α is a B-atom-free formula of K.
3. If α is safely consistent for K\{α}, then α is a B-atomfree formula of K.

The complete proofs of this and subsequent propositions can be found in [Mu, 2019].

On the other hand, the term of B-atom-free formula strictly covers the safely consistent formula. To illustrate this, Consider K1 = {a, ¬a ∧ b, b ∧ c}. Note that b ∧ c is the unique B-atom-free formula of K1. However, b ∧ c is neither a safe formula of K1 nor a safely consistent formula of K1.

Now we are ready to replace the property of Free Formula Independence with the following property:

• B-atom-free Formula Independence: If α is a B-atomfree formula of K, then I(K \ {α}) = I(K).

Then we can get the following results from Proposition 1:

• Assuming B-atom-free Formula Independence entails Tautology Independence and Safe Formula Independence.
• Assuming B-atom-free Formula Independence entails that I(K ∪ {α}) = I(K) if α is safely consistent for K.
• Assuming B-atom-free Formula Independence and I(K ∪ {α, β}) = I(K ∪ {α ∧ β}) entail Conjunct Independence.

However, ω is a model of K ∪ {α, β} if and only if ω is a model of K∪{α∧β}. This implies that for any inconsistency measure I based on LPm models, it holds that I(K ∪ {α ∧ β}) = I(K ∪ {α, β}).

4 Bi-Free Formulas

The invariance of inconsistency characterization in terms of minimal models cannot ensure that a B-atom-free formula must be a free formula. To illustrate this, consider K2 = {a, ¬a, ¬a ∨ b, ¬b}. Both ¬a ∨ b and ¬b are B-atom-free formulas of K2. But, neither ¬a ∨ b nor ¬b is a free formula of K2.

On the other hand, not all the free formulas of a knowledge base are really independent of B-atoms in the framework of Priest's LPm. To illustrate this, consider K3 = {a ∧ ¬a ∧ b, ¬b}. Note that ¬b is a unique free formula of K3, but ¬b is not a B-atom-free formula of K3. We also need to exclude such a type of free formulas from free formulas.

However, we can characterize the free formulas that are not really independent of inconsistency characterization by the notion of false B-independent formula.

Definition 2. Let K be a knowledge base and α a free formula of K. We call α a false B-independent formula of K if ∃S ⊂ K s.t. S ⊢ ⊥ and BA(S) ̸= BA(S ∪ {α}).

We propose a notion of Bi-free formula to describe formulas that are free from inconsistency characterization in both syntax and paraconsistent semantics.

Definition 3. Let K be a knowledge base and α ∈ K. Then we call α a Bi-free formula of K if for all S ⊆ K s.t. α ∈ S, it holds that BA(S) = BA(S \ {α}).

Note that for any M ∈ MI(K), BA(M) ̸= BA(M \ {α}) = ∅ for all α ∈ M. Then all the Bi-free formulas are free formulas. However, the following proposition shows that the notion of Bi-free formula can exclude the false Bindependent formula.

Proposition 2. Let K be a knowledge base and α a Bi-free formula of K. Then α is not a false B-independent formula of K.

Interestingly, we show that if α is a Bi-free formula, then α is a both B-atom-free and free formula.

Proposition 3. Let K be a knowledge base and α ∈ K. If α is a Bi-free formula of K, then BA(K) = BA(K \ {α}) and MI(K) = MI(K \ {α}).

Moreover, we have a more interesting characterization of Bi-free formulas in the case that for any false B-independent formula α of K, it holds that BA(K) ̸= BA(K \ {α}).

Proposition 4. Let K be a knowledge base such that BA(K) ̸= BA(K \ {β}) for any false B-independent formula β. Then α ∈ K is a Bi-free formula of K if and only if BA(K) = BA(K \ {α}) and MI(K) = MI(K \ {α}).

The following proposition shows that the notion of Bi-free formula can cover the tautology, the safe formula, and safely consistent formulas.

Proposition 5. Let K be a knowledge base and α ∈ K.

1. If α is a tautology, then α is a Bi-free formula.
2. If α is a safe formula, then α is a Bi-free formula.
3. If α is safely consistent for K \ {α}, then α is a Bi-free formula of K.

On the other hand, the notion of Bi-free formula also strictly covers that of safely consistent formula. To illustrate this, consider K1 = {a, ¬a ∧ b, b ∧ c} again. Then b ∧ c is a unique Bi-free formula of K1. But b ∧ c is not safely consistent for {a, ¬a ∧ b}.

We use BIFF(K), BAFF(K), FBF(K), SCF(K), SF(K), and T (K) to denote the sets of Bi-free formulas, B-atom-free formulas, false B-independent formulas, safely consistent formulas, safe formulas, and tautologies of K, respectively. In summary, we obtain the following results:

1. BIFF(K) ⊆ BAFF(K) ∩ FF(K), in particular, BIFF(K) = BAFF(K) ∩ FF(K) in the case that BA(K) ̸= BA(K \ {β}) for any false B-independent formula β.
2. FBF(K) ⊆ FF(K) \ BAFF(K), in particular, FBF(K) = FF(K) \ BAFF(K) in the case that BA(K) ̸= BA(K \ {β}) for any false B-independent formula β.
3. SCF(K) ⊆ BIFF(K), and it holds that SCF(K) ⊂ BIFF(K) for some K.

Now we provide another alternative of the property of Free Formula Independence, which is appropriate for describing measures from both syntax and paraconsistent semantics.

• Bi-free Formula Independence: If α is a Bi-free formula of K, then I(K \ {α}) = I(K).

Evidently, we can get the following results.

• Assuming Bi-free Formula Independence entails Tautology Independence and Safe Formula Independence.
• Assuming Bi-free Formula Independence entails that I(K ∪ {α}) = I(K) if α is safely consistent for K.
• Assuming Bi-free Formula Independence and I(K ∪ {α, β}) = I(K ∪ {α ∧ β}) entail Conjunct Independence.

Lastly, let us consider the measure ILPm [Hunter and Konieczny, 2010], one of measures often used to exemplify atom-centric inconsistency measuring, which satisfies all the Hunter and Konieczny's properties except Free Formula Independence [Hunter and Konieczny, 2010]. We have shown that ILPm satisfies B-atom-free Formula Independence and Bi-free Formula Independence [Mu, 2019]. In addition, we construct a bi-measure I fB (K) = √(If(K))2 + (ILPm (K))2 to capture the inconsistency from an integrated perspective, where If is a normalized formula-centric measure. Moreover, the inconsistency measure I fB satisfies Bi-free Formula Independence, if If satisfies Free Formula Independence. For example, it has been shown that the formula-centric inconsistency measure Idr [Mu, 2015] satisfies Free Formula Independence [Mu, 2018]. Then we can construct such a bi-measure I dr B (K) = √(1 - e-Idr(K) )2 + (ILPm (K))2 based on Idr(K).

5 Conclusion

Formulas Independent of inconsistency are of interest to analysing and measuring inconsistency. The free formula has been considered as such a kind of formulas. However, not all the free formulas are independent of the inconsistency when the inconsistency is characterized by some paraconsistent models.

In this paper, we have identified formulas independent of inconsistency in the framework of Priest's minimally inconsistent LP LPm. The B-atom-free formula, as a counterpart of free formula, has been proposed based on the invariance of inconsistency characterization. Just as the case of free formula, the B-atom-free formula covers some formulas not independent of inconsistency in syntactic characterization. Then we proposed the notion of Bi-free formula, which exactly covers formulas independent of inconsistency in both formulacentric and atom-centric characterizations. Two corresponding alternatives of the property of Free Formula Independence have been also proposed.

Acknowledgements

This work was partly supported by the National Natural Science Foundation of China under Grant No.61572002 and No.61170300.