Minimal inconsistent sets have played an important role in the analysis and general handling of inconsistency in logical knowledge bases. We introduce a semantical counterpart of this notion we call minimal inconsistent signature, which is a minimal set of propositions such that projecting the knowledge base onto it still preserves the inconsistency. We analyse minimal inconsistent signatures and the corresponding dual notion of maximal consistent signatures in depth and show, among others, that the hitting set duality applies for them as well. We apply our new notions to the field of inconsistency measurement and derive a series of new inconsistency measures, which we analyse in terms of postulate satisfaction and general behaviour. Finally, we analyse the computational complexity of various problems within this new context.
Reasoning with inconsistent information is a central issue for approaches to knowledge representation
and reasoning [
In this work, we define and analyse a new approach to analyse inconsistency, but defined in terms of
signatures rather than subsets of the knowledge base. More precisely, we define a minimal inconsistent
subsignature as a minimal set of propositions, such that forgetting1 [
To summarise, the contributions of this paper are as follows: 1. We revisit the notion of forgetting parts of the signature of a knowledge base for the purpose of defining a semantical counterpart to minimal inconsistent subsets and make some new observations (Section 3). 2. We define minimal inconsistent and maximal consistent subsignatures and analyse their properties; in particular, we show that these structures also obey the hitting set duality (Section 4). 3. We define and analyse new inconsistency measures based on minimal inconsistent subsignatures and maximal consistent subsignatures (Section 5). 4. We analyse the computational complexity of various decision problems related to minimal inconsistent subsignatures (Section 6).
We will discuss necessary preliminaries in Section 2, discuss related work in Section 7, and conclude with a discussion in Section 8.
Proofs of technical results can be found in an extended version of this paper [
Let At be some fixed propositional signature, i. e., a (possibly infinite) set of propositions, and let ℒ(At) be the corresponding propositional language constructed using the standard connectives ∧ (conjunction), ∨ (disjunction), → (implication), and ¬ (negation). Let furthermore ⊤, ⊥∈ At be special propositions denoting tautology and contradiction, respectively.
Definition 1. A knowledge base is a finite set of formulas ⊆ ℒ (At). Let K be the set of all knowledge bases.
If Φ is a formula or a set of formulas we write At(Φ) to denote the set of propositions appearing in Φ . For a set Φ = {1, . . . , } let ⋀︀ Φ = 1 ∧ . . . ∧ and ¬Φ = {¬ | ∈ Φ }.
Semantics to a propositional language are given by interpretations where an interpretation on At is a function : At → {true, false}. Let Ω( At) denote the set of all interpretations for At (with the convention that (⊤) = true and (⊥) = false). An interpretation satisfies (or is a model of) a proposition ∈ At, denoted by |= , if and only if () = true. The satisfaction relation |= is extended to formulas in the usual way. For Φ ⊆ ℒ (At) we also define |= Φ if and only if |= for every ∈ Φ .
In the following, let Φ , Φ 1, Φ 2 be formulas or sets of formulas. Define the set of models Mod(Φ) = { ∈ Ω( At) | |= Φ }. We write Φ 1 |= Φ 2 if Mod(Φ 1) ⊆ Mod(Φ 2). Φ 1, Φ 2 are equivalent, denoted by Φ 1 ≡ Φ 2, if and only if Mod(Φ 1) = Mod(Φ 2). If Mod(Φ) = ∅ we also write Φ |=⊥ and say that Φ is inconsistent (or unsatisfiable ).
Definition 2. Let be a knowledge base.
a) ′ |=⊥ and b) for all ′′ with ′′ ⊊ ′, ′′ ̸|=⊥. 2. ′ ⊆ is called a maximal consistent subset of if a) ′ ̸|=⊥ and b) for all ′′ with ′ ⊊ ′′ ⊆ , ′′ |=⊥.
Let MIS() and MCS() denote the set of all minimal inconsistent subsets of and the set of all maximal consistent subsets of , respectively.
Let furthermore FREE() = ∖ ⋃︀ MIS() denote the set of free formulas of , i. e., those formulas
of that are not members of any minimal inconsistent subset of . Moreover, a formula is safe
for a knowledge base if ̸|=⊥ and At( ) ∩ At( ∖ { }) = ∅. Let SAFE() denote the set of safe
formulas of and note that SAFE() ⊆ FREE() [
A forgetting operator is an operator that removes a given set of propositions from a signature of the
knowledge base. Its initial motivation [
Definition 3. For a formula and some ∈ At() define the elimination of from , denoted as ÷ , to be the formula ÷ = [ → ⊤] ∨ [ → ⊥].
In other words, eliminating from is equivalent to replacing with ⊤ or ⊥. A nice property of
variable elimination is that inferences on the remaining part of the signature are retained [
Example 1. Let = ( ∧ ) ∨ ( ∧ ¬). Forgetting from gives us
÷ = (⊤ ∧ ) ∨ ( ∧ ¬) ∨ (⊥ ∧ ) ∨ ( ∧ ¬) ≡ ∨ ( ∧ ¬) Note that, e. g., |= ∨ and ÷ |= ∨ .
Observe that variable elimination preserves inconsistency, i. e., if a formula is inconsistent then forgetting any proposition cannot restore consistency. For this to see, first observe that the order in which propositions are eliminated does not matter, so let ÷ for a set ⊆ At() denote the application of variable elimination in any order.
Proposition 1. ̸|=⊥ if and only if ÷ At() ≡ ⊤ .
Our aim in the rest of this section is to devise a forgetting operation based on variable elimination that is able to restore consistency, i. e., by removing “conflicting” parts of the signature of the formula or knowledge base, we wish to end up with a consistent outcome. Note that restoring consistency will retract a lot of inferences, which is then not aligned with the initial motivation for forgetting from above. We illustrate our aim with a simple example.
Example 2. Consider the formula given by = ∧ ¬ ∧ . Clearly |=⊥. Intuitively, the proposition (and the modelled information about it) is responsible for the inconsistency. We therefore expect that forgetting leaves us with a formula ′ = , from which we can still derive meaningful information about . Note, however, that ÷ ≡ ⊥ .
In order to define a forgetting operation with the above behaviour, we have to operate on the level of proposition occurrences rather than proposition. Since we do not wish to retain inferences by forgetting but only to remove propositions (and the information modelled for them), we allow proposition occurrences to be replaced by ⊤ or ⊥ individually. For that, let [
→ 1′/ 2′/ . . . / ′] denote the propositional formula that is obtained from by replacing the first occurrence of in by 1′, the second occurrence of in by 2′, and so on (the operation is undefined if the number of occurrences of in is not equal to ).
Example 3. For the formula = ∧ ( ∨ ) ∧ ¬ we have [ → ⊤/ ⊥ / ⊥] = ⊤ ∧ (∨ ⊥) ∧ ¬ ⊥≡ .
The above operation allows us to define a new variant of variable elimination as follows. Let # denote the number of occurrences of ∈ At() in .
Definition 4. For a formula and some ∈ At() define ⊟ =
⋁︁ 1,...,#∈{⊤,⊥}
[ → 1/ . . . /#]
The operator ⊟ allows the replacement of each occurrence of with ⊤ or ⊥ such that contradictions within a formula can be resolved. Let us consider again Example 2.
Example 4. Consider again
= ∧ ¬ ∧ Here we have as desired.
⊟ = (⊤ ∧ ⊤ ∧ ) ∨ (⊤ ∧ ⊥ ∧ ) ∨ (⊥ ∧ ⊤ ∧ ) ∨ (⊥ ∧ ⊥ ∧ ) ≡ ⊤ ∧ ⊤ ∧ ≡
Before we continue with an analysis of ⊟ let us first give some intuitions and a simple syntactic characterisation of what ⊟ does to a formula. It may not be apparent from the definition above, but what ⊟ basically does is the following: it replaces every disjunction within that contains or ¬ by ⊤ and removes all occurrences of and ¬ from conjunctions. Recall that a formula is in negation normal form (NNF) if negations only appear right in front of propositions. For formulas in NNF we can characterise ⊟ as follows.
Proposition 2. For a formula in NNF and some ∈ At() define ⊟ ̂ inductively on the structure of via ⊟ ̂ = ⎨⎧ ⊤ if = or = ¬
⊟ ̂ ∨ ′ ⊟ ̂ if = ∨ ′ ⎩ ⊟ ̂ ∧ ′ ⊟ ̂ if = ∧ ′ If ∈/ At() we define ⊟ ̂ = . Then
⊟ ̂ ≡ ⊟
Since 1 ∨ . . . ∨ ∨ ⊤ ≡ ⊤ and 1 ∧ . . . ∧ ∧ ⊤ ≡ 1 ∧ . . . ∧ for all 1, . . . , , it should be clear that forgetting from a formula in NNF means that we replace every disjunction within that contains or ¬ by ⊤ and remove all occurrences of and ¬ from conjunctions, as stated above.
Note that every formula can be translated into NNF with only a linear increase in size and that this translation yields an equivalent formula. Most of our examples are using formulas in NNF, so the above characterisation can be applied.
If multiple propositions are forgotten with ⊟ , it should be obvious that the order does not matter. So for a set = {1, . . . , } ⊆ At() let
⊟ = (. . . (( ⊟ 1) ⊟ 2) . . .) ⊟ with an arbitrary order among the propositions in . Furthermore, for a knowledge base and ⊆ At() we write
⊟ = { ⊟ ∩ At() | ∈ } Example 5. Consider 1 = {, ¬ ∧ }, we get
1′ = 1 ⊟ = {⊤∨ ⊥, (¬⊤ ∧ ) ∨ (¬ ⊥ ∧)} ≡ { } Consider a syntactic variant of 1, namely 2 = { ∧ ¬, }, we get
2′ = 2 ⊟ = {(⊤ ∧ ¬⊤) ∨ (⊥ ∧¬ ⊥) ∨ (⊤ ∧ ¬ ⊥) ∨ (⊥ ∧¬⊤), } ≡ { } So this example shows that ⊟ is (to some extent) not syntax-sensitive, even in the presence of inconsistency. We come back to this aspect later (in particular, see Proposition 10).
From the examples so far it should be clear that inferences are not necessarily retained (even on the remaining signature). In particular, in Example 4 we have |= ¬ (in fact entails everything), but ⊟ ̸|= ¬. In fact, we obtain the following observation.
Proposition 3. Let be a formula such that |=⊥. Then there is ⊆ At() such that ⊟ ̸|=⊥.
The above observation shows that, from the perspective of inconsistency-tolerant reasoning, ⊟ is a sensible choice for a forgetting operation, since it allows the restoration of consistency in any case. Moreover, ⊟ does also not introduce inconsistencies.
Proposition 4. Let be a knowledge base and ⊆ At(). If is consistent then ⊟ is consistent and |= ⊟ .
Our forgetting operator ⊟ allows us to project the signature of a knowledge base to a subset of its signature. We define this concept in a general manner as follows. 2|{} ≡ { }.
Definition 5. For a knowledge base and ⊆ At(), the projection of onto , denoted |, is defined as | = ⊟ (At() ∖ ).
Example 6. We consider again 1 = {, ¬ ∧ } and 2 = { ∧ ¬, }. We get 1|{} ≡ { } and
The notion of projection allows us to define analogues to the concepts of minimally inconsistent subsets and maximally consistent subsets of a knowledge base (see again Definition 2), based on a more semantical perspective. In general, we say that a set ⊆ At() is a consistent subsignature of if | is consistent, otherwise it is called an inconsistent subsignature.
Definition 6. Let be a knowledge base.
a) | |=⊥ and b) for all ′ with ′ ⊊ , |′ ̸|=⊥. 2. ⊆ At() is called a maximal consistent subsignature of if a) | ̸|=⊥ and b) for all ′ with ⊊ ′ ⊆ At(), |′ |=⊥.
Let MISig() and MCSig() denote the set of all minimal inconsistent subsignatures and the set of all maximal consistent subsignatures, respectively.
We furthermore say that a proposition ∈ At() is a free proposition in if ∈/ for all ∈ MISig().
Example 7. We consider again the knowledge base 1 = {, ¬ ∧ }. Here we have For 2 = { ∧ ¬, } we get likewise
MISig(1) = {{}} MISig(2) = {{}}
MCSig(1) = {{}} MCSig(2) = {{}} Example 8. Consider
1. is consistent if MISig() = ∅ if MCSig() = {At()}. 2. MCSig() ̸= ∅.
Observe that item 2 above includes the case where the only consistent signature is empty, so we may have MCSig() = {∅}.
A particular property of the set of all minimal inconsistent subsets MIS() is its monotony wrt. expansions of . More precisely, if ⊆ ′ then MIS() ⊆ MIS(′). For the corresponding semantical counterpart MISig(), this is not generally true.
Example 9. Consider 4 = { ∨ , ¬ ∧ ¬}. Here we have MISig(4) = {{, }}. However, adding the formula gives us MISig(4 ∪ {}) = {{}} and therefore MISig(4) ̸⊆ MISig(4 ∪ {}).
But MISig() behaves monotonically when it comes to expansions of the signature. Proposition 6. Let be a knowledge base and ⊆ At(). Then MISig( ⊟ ) ⊆ MISig().
Another particularly interesting property of the sets of minimal inconsistent subsets and the set of
maximal consistent subsets of a knowledge base is the hitting set duality [
Definition 7. A hitting set of a set of sets = {1, . . . , } is a set ⊆ 1 ∪ . . . ∪ such that ∩ ̸= ∅ for all = 1, . . . , . A hitting set is minimal if there is no other hitting set ′ with ′ ⊊ .
The hitting set duality for MIS() and MCS() says that is a minimal hitting set of MIS() if
∖ ∈ MCS() [
A corollary of the above result is that free propositions can also be characterised as those propositions that appear in all maximal consistent subsignatures (as it is the case with free formulas and maximal consistent subsets).
Corollary 1. Let a knowledge base. A proposition ∈ At() is a free proposition in if ∈ for all ∈ MCSig().
We continue with a more detailed analysis and comparison of the behaviours of minimal inconsistent subsets and signatures. As for the former, removing free propositions from a signature does not influence the structure of the minimal inconsistent subsignatures, as the following proposition shows. Proposition 7. Let be a knowledge base and ∈ At() a free proposition of . Then MISig() = MISig( ⊟ ).
Minimal inconsistent subsignatures are not only robust against the removal of free propositions from the signature (as the above proposition showed) but also against the removal of free formulas from the knowledge base (as the next proposition shows).
Proposition 8. Let be a knowledge base and a free formula of . Then MISig() = MISig( ∖{ }).
The previous two propositions show that our notion of a minimal inconsistent subsignature is quite suitable for capturing the essence of the reasons why a knowledge base is inconsistent, since removal of “independent” syntactic (i. e., formulas) or semantic (i. e., propositions) information does not influence it. On the other hand, the next proposition shows that removing semantic information that is involved in inconsistency indeed has an influence.
Proposition 9. Let be a knowledge base and ∈ At() not a free proposition of . Then MISig( ⊟ ) ⊊ MISig().
Note that the syntactic counterpart of the previous observation, i. e., that the removal of non-free syntactic information changes the structure of minimal inconsistent subsignatures, does not hold in general.
Example 10. Consider 5 = {, ¬, ∧ ¬} with MISig(5) = {{}}. Note that ∧ ¬ is obviously not a free formula of 5, but MISig(5 ∖ { ∧ ¬}) = {{}} = MISig(5).
However, the notion of minimal inconsistent subsignature still behaves as expected in the previous example. The formula ∧ ¬ actually describes redundant semantical information and its removal does not impact which parts of the signature are responsible for producing the inconsistency. As a matter of fact, the set of minimal inconsistent subsignatures is, to some extent, robust against syntactic variations, even in the presence of inconsistency.
Proposition 10. Let be a knowledge base and , { ∧ }). formulas. Then MISig( ∪ {, }) = MISig( ∪ Definition 8. consistent.
The observation made in the previous proposition is quite remarkable. It says that in terms of
analysing inconsistency through the signature, it does not matter whether a knowledge base is defined
as a set of formulas or a single conjunction of these formulas. While this is obvious when reasoning
with consistent knowledge bases, the case of inconsistency usually requires a distinction between
using the logical conjunction and the “comma” operator, see [
We now consider the application of our framework of minimal inconsistent subsignatures and maximal
consistent subsignatures for inconsistency measurement. In general, an inconsistency measure [
An inconsistency measure is any function : 2ℒ(At) → R≥ 0 with () = 0 if is Many existing inconsistency measures are based on minimal inconsistent and maximal consistent subsets of , see [16] for a survey. We here consider the measures MI and MI-C, defined via MI-C() = MI() = |MIS()|
∑︁ for any knowledge base , both introduced by Hunter and Konieczny [17], as well as the measures MC and P, defined via
P() = | MC() = |MCS()| + |SC()| − 1
⋃︁ both by Grant and Hunter [18], where SC() = { ∈ | |=⊥} is the set of self-contradicting formulas of .
We can use minimal inconsistent and maximal consistent subsignatures in a similar manner as minimal inconsistent and maximal consistent subsets are being used in the above measures. Definition 9. Let be a knowledge base. Define functions MISig, MISig-C, MCSig and PSig via MISig() = |MISig()| MISig-C() = ∑︁
1 ∈MISig() | | MCSig() = |MCSig()| + |SCSig()| − 1 PSig() = ⃒⃒⃒⃒ ⋃︁ ⃒⃒⃒⃒
⃒⃒ ∈MISig() ⃒⃒
SCSig() = { ∈ At() | |{}|=⊥} with and
is the set of self-contradicting propositions.
In other words, MISig returns the number of minimal inconsistent subsignatures as a measure of inconsistency. MISig-C is a refinement of this idea and weighs each minimal inconsistent subsignature by its inverse size (with the intuition that larger minimal inconsistent subsignatures constitute a less obvious reason for inconsistency than smaller subsignatures). MCSig uses maximal consistent subsignatures instead of minimal inconsistent subsignatures. The intuition is that the more maximal consistent subsignatures there are, the more possible ways to resolve the inconsistency exist, and, therefore, the larger the inconsistency. We include the set of self-contradicting propositions here in order to ensure that the value 0 is only attained for consistent knowledge bases (if, e. g., we have MISig() = {{}} then there is also just one maximal consistent subsignature and without adding |SCSig()| the inconsistency value would be 0). Finally, the measure PSig takes the number of propositions appearing in at least one minimal inconsistent subsignature as a measure of inconsistency.
Example 11. We consider again 3 from Example 8 with
3 = { ∧ ∧ , ¬ ∨ ¬, ∧ ¬, ( ∨ ¬) ∧ }
We can first observe that all new measures are indeed inconsistency measures (Definition 8), i. e., they return the value 0 in the case of consistency (and only in this case).
MISig MISig-C MCSig PSig
MO ✗ ✗ ✗ ✗
IN ✓ ✓ ✓ ✓
DO ✗ ✗ ✗ ✗
SI PY ✓ ✗ ✓ ✗ ✓ ✗ ✓ ✗
AI SM ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
PI PP ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
Proposition 11. The functions MISig, MISig-C, MCSig and PSig are inconsistency measures.
Inconsistency measures are usually evaluated wrt. rationality postulates [16]. Due to space limitations, we do not consider all postulates from [16], but focus on the most prominent ones. Let be any function : 2ℒ(At) → R≥ 0.
Monotony (MO) If ⊆ ′ then () ≤ (′).
Free-formula Independence (IN) If ∈ FREE() then () = ( ∖ { }).
Safe-formula Independence (SI) If is safe for then () = ( ∖ { }).
Dominance (DO) If /∈ , ̸|=⊥ and |= then ( ∪ { }) ≥ ( ∪ { }). Penalty (PY) If /∈ FREE() then () > ( ∖ { }).
MO states that adding formulas cannot decrease the degree of inconsistency. IN and SI state that removing free (resp. safe) formulas does not change the degree of inconsistency. DO requires that replacing formulas with semantically stronger information cannot decrease the degree of inconsistency. PY is the complement of IN and states that removing non-free formulas decreases the degree of inconsistency. We will consider one further postulate from [19] that is concerned with syntax irrelevance and is rarely satisfied by existing inconsistency measures [16].
}) = ( ∪ { ∧ }).
As we will see below, our measures (naturally) do not comply with the postulates MO, DO, and PY, since these are particularly concerned with the role of formulas in inconsistency. Due to Proposition 10 (which also directly leads all our measures to satisfy AI) all our measures are insensitive to the exact structure of the formulas. However, the introduction of minimal inconsistent subsignatures brings us into the position to introduce semantical counterparts of these postulates, which are particularly well suited to describe our new measures: Signature-monotony (SM) For ⊆ At() it is ( ⊟ ) ≤ ().
Free-proposition independence (PI) If is a free proposition in , then () = ( ⊟ ). Proposition-penalty (PP) If ∈ At() is not a free proposition in , then () > ( ⊟ ). In other words, SM states that forgetting parts of the signature of a knowledge base cannot increase the degree of inconsistency. PI states that removing free propositions cannot change the degree of inconsistency. Conversely, PP states that removing non-free propositions decreases the degree of inconsistency.
Naturally, our new measures satisfy the newly introduced postulates. In summary, we can make the following statement on the compliance of our new measures with all the considered postulates. Theorem 2. The compliance of the measures MISig, MISig-C, MCSig and PSig to the rationality postulates is as shown in Table 1.
As it can be seen from Table 1, all our new measures behave similarly with respect to the considered postulates. However, in the next section we will see that they behave diferently in terms of complexity.
We assume familiarity with the standard complexity classes P, NP and coNP, see [20] for an introduction. We also require knowledge of the complexity class DP, which is defined as DP = {1 ∩ 2 | 1 ∈ NP, 2 ∈ coNP}. In other words, DP is the class of problems that are the intersection of a problem in NP and a problem in coNP. We also use complexity classes of the polynomial hierarchy that can be defined (using oracle machines) via Σ 1P = NP, Π 1P = coNP, and Σ P = NPΣ P− 1 Π P = coNPΣ P− 1 for all > 1, where denotes the class of decision problems solvable in class with access to an oracle that can solve problems that are complete for . In analogy to DP, we define DP2 via DP2 = {1 ∩ 2 | 1 ∈ Σ 2P, 2 ∈ Π 2P}. We also consider classes of the counting polynomial hierarchy [21]. In particular, the class CNP is the class of counting decision problems where the corresponding decision problem is in NP. More precisely, let (, ) be a predicate, where it can be decided in nondeterministic polynomial time if (, ) is true. Given and a natural number ∈ N, the decision problem of deciding whether there are at least instances of , such that (, ) is true, is then in CNP (the class C=NP is defined analogously by replacing “at least” with “exactly”). Similarly, the class # · coNP is a counting complexity class [22] that contains problems that upon input return the number of instances such that (, ) is true, which itself is a problem in coNP. Finally, FP is the class of functional problems that can be computed in deterministic polynomial time.
Complexity results regarding some basic decision problems are as follows.
1. Deciding whether is a consistent subsignature of is NP-complete. 2. Deciding whether is a minimal inconsistent subsignature of is DP-complete. 3. Deciding whether is a maximal consistent subsignature of is DP-complete.
We consider now problems related to our new inconsistency measures from Section 5. As in [23], we consider the following problems (for a given inconsistency measure ): Due to Theorem 3, decision problems related to (in-)consistency of signatures have the same complexity as the corresponding problems on formulas (e. g., deciding whether a set of formulas is consistent is NP-complete as is the problem of deciding whether a set of propositions is a consistent subsignature). The observations made in [23] about the above problems for the corresponding measures defined on the formula level then also extend to our new measures quite easily. More precisely, we get the following characterisations regarding computational complexity.
Theorem 4. The computational complexity of the problems Exact , Upper , Lower , Value wrt. the measures MISig, MISig-C, MCSig, and PSig is as shown in Table 2.
Our approach has some connections to previous works, in particular inconsistency-tolerant reasoning with paraconsistent logics, which we will discuss in Section 7.1. Further related work will be discussed in Section 7.2. except statements with an additional “-c” (which are completeness statements) or “-h” (which are hardness 7.1. Relationships with paraconsistent reasoning We briefly recall Priest’s 3-valued logic for paraconsistent reasoning [ 24]. A three-valued interpretation on At is a function : At → {, , } where the values and correspond to the classical true and false, respectively. The additional truth value stands for both and is meant to represent a conflicting truth value for a proposition. The function is extended to arbitrary formulas as shown in Table 3. An interpretation satisfies a formula (or is a 3-valued model of that formula), denoted by | =3 =3 for a knowledge base accordingly. Let Mod3() if either ( ) = or ( ) = . Define | denote the set of all 3-valued models of . Note that the interpretation 0 defined via 0() = for all ∈ At is a model of every formula, so it makes sense to consider minimal models wrt. the usage of the paraconsistent truth value . A model of a knowledge base is a minimal model of if it is a model and there is no other model ′ of with ( ′)− 1() ⊊ ( )− 1(). Let MinMod3() denote the set of minimal models of . properties of this inference relation and a refined version of it see [25].
We can define an inference relation on
MinMod3() by considering all minimal models. More formally, define |∼ 3 via |∼ 3 if | =3 for all
∈ MinMod3() For an in-depth discussion of the
For a three-valued interpretation define its two-valued projection : − 1({, }) → {true, false} via () = true if () = and () = false if () = , for all ∈ − 1({, }). In other words, is a two-valued interpretation that is only defined on those propositions, where gives a classical truth value, and the truth value assigned by agrees with . We can capture the relationship between three-valued models and inconsistent signatures as follows. formula .
Proposition 12. Let be a three-valued interpretation. Then |=3 if |= ( ⊟ − 1()) for every
So a three-valued interpretation is a model of , if and only if the classical part of is a model of the formula obtained by forgetting those propositions assigned to .
Proposition 13. Let be a knowledge base.
1. If ∈ MinMod3() then − 1() ∈ MISig(). 2. If ∈ MISig() then there is ∈ MinMod3() with − 1() = .
In other words, is a minimal inconsistent subsignature if and only if there is a minimal 3-valued
model that assigns to exactly those propositions in . Note that while works such as [25] analyse the
inferential capabilities of (refined versions of) |∼ 3, the properties of minimal inconsistent subsignatures
have (in the form as we did in the preceding section) not been analysed in that line of research before.
7.2. Further related work
Lang and Marquis [
Brewka et. al [27] consider a generalisation of the concept of inconsistency called strong inconsistency. A subset ⊆ of formulas of a knowledge base , is strongly inconsistent if every ′ with ⊆ ′ ⊆ is inconsistent. In classical propositional logic, a set is strongly inconsistent if and only if it is inconsistent, but the two concepts difer when considering non-monotonic formalisms, such as answer set programming (ASP) [28, 29]. Strong inconsistency and minimal inconsistent subsignatures are, in general, two orthogonal concepts that address diferent aspects of inconsistency handling. However, it is conceivable to combine both of them in non-monotonic formalisms such as ASP, and obtain minimal strongly inconsistent subsignatures. For that, we basically have to substitute requirements pertaining to inconsistency by strong inconsistency (such as in Definition 6). This would open up applications of our inconsistency measures in those formalisms as well, see also [30, 31].
We considered an approach to analyse inconsistency in a knowledge base through forgetting parts of the signature such that the remaining knowledge base is consistent. In particular, we considered the notions of minimal inconsistent and maximal consistent subsignatures as counterparts to minimal inconsistent and maximal consistent subsets. Structurally, minimal inconsistent and maximal consistent subsignatures behave similarly as their subset-based counterparts, in particular, we showed that the hitting set duality is also satisfied by those notions. We analysed the application of these notions to the field of inconsistency measurement and devised several novel and interesting new inconsistency measures. Finally, we studied several problems in this context wrt. their computational complexity.
A possible venue for future work is to develop signature-based variants of inconsistency-tolerant
reasoning methods based on maximal consistent subsets such as the one by Rescher and Manor [
The research reported here was partially supported by the Deutsche Forschungsgemeinschaft (project “Explainable Belief Merging”, grant 465447331).
[16] M. Thimm, On the evaluation of inconsistency measures, in: J. Grant, M. V. Martinez (Eds.),
Measuring Inconsistency in Information, volume 73 of Studies in Logic, College Publications, 2018. [17] A. Hunter, S. Konieczny, Measuring inconsistency through minimal inconsistent sets, in: G. Brewka, J. Lang (Eds.), Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR’2008), AAAI Press, Menlo Park, California, Sydney, Australia, 2008, pp. 358–366. [18] J. Grant, A. Hunter, Measuring consistency gain and information loss in stepwise inconsistency resolution, in: W. Liu (Ed.), Proceedings of the 11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2011), number 6717 in Lecture Notes in Artificial Intelligence, Springer-Verlag, 2011, pp. 362–373. [19] P. Besnard, Revisiting postulates for inconsistency measures, in: Proceedings of the 14th European
Conference on Logics in Artificial Intelligence (JELIA’14), 2014, pp. 383–396. [20] C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994. [21] K. W. Wagner, The complexity of combinatorial problems with succinct input representation, Acta
Informatica 23 (1986) 325–356. [22] L. A. Hemaspaandra, H. Vollmer, The satanic notations: counting classes beyond #P and other definitional adventures, SIGACT News 26 (1995) 2–13. URL: https://doi.org/10.1145/203610.203611. doi:10.1145/203610.203611. [23] M. Thimm, J. P. Wallner, On the complexity of inconsistency measurement, Artificial Intelligence 275 (2019) 411–456. [24] G. Priest, Logic of Paradox, Journal of Philosophical Logic 8 (1979) 219–241. [25] S. Coste-Marquis, P. Marquis, Recovering consistency by forgetting inconsistency, in: S. Hölldobler, C. Lutz, H. Wansing (Eds.), Logics in Artificial Intelligence, 11th European Conference, JELIA 2008, Dresden, Germany, September 28 - October 1, 2008. Proceedings, volume 5293 of Lecture Notes in Computer Science, Springer, 2008, pp. 113–125. [26] P. Besnard, Forgetting-based inconsistency measure, in: Proceedings of the 10th International
Conference on Scalable Uncertainty Management (SUM’16), 2016, pp. 331–337. [27] G. Brewka, M. Thimm, M. Ulbricht, Strong inconsistency, Artificial Intelligence 267 (2019) 78–117. [28] M. Gelfond, V. Lifschitz, Classical negation in logic programs and disjunctive databases, New
Generation Computing 9 (1991) 365–385. [29] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub, Answer Set Solving in Practice, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, 2012. [30] M. Ulbricht, M. Thimm, G. Brewka, Measuring inconsistency in answer set programs, in: Proceedings of the 15th European Conference on Logics in Artificial Intelligence (JELIA’16), 2016, pp. 577–583. [31] M. Ulbricht, M. Thimm, G. Brewka, Handling and measuring inconsistency in non-monotonic logics, Artificial Intelligence 286 (2020) 103344. [32] G. Brewka, Preferred subtheories: An extended logical framework for default reasoning, in: N. S.
Sridharan (Ed.), Proceedings of the 11th International Joint Conference on Artificial Intelligence.
Detroit, MI, USA, August 1989, Morgan Kaufmann, 1989, pp. 1043–1048. [33] L. Zhou, H. Huang, G. Qi, Y. Ma, Z. Huang, Y. Qu, Measuring inconsistency in dl-lite ontologies, in: Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology - Volume 01, WI-IAT ’09, IEEE Computer Society, Washington, DC, USA, 2009, pp. 349–356. [34] J. Grant, F. Parisi, On measuring inconsistency in graph databases with regular path constraints,
Artificial Intelligence 335 (2024) 104197. [35] F. Parisi, J. Grant, On measuring inconsistency in definite and indefinite databases with denial constraints, Artificial Intelligence 318 (2023) 103884.