This paper introduces four novel inconsistency-tolerant inference relations for knowledge bases. These relations are based on the minimal hitting sets of a knowledge base, which are sets of interpretations that contains a model of every formula in the knowledge base. We prove several useful properties of hitting sets and the inference relations based on them. The full landscape of the relationships between the four novel inference relations and the two inferences based on maximal consistent subsets by Rescher and Manor is given. We show that all of the considered inference relations are non-monotonic and satisfy several System P properties. Finally, we show that the respective complexity of inference is at most in the second level of the polynomial hierarchy.
Reasoning from knowledge bases is a central topic in
knowledge representation and reasoning (KRR) [
A powerful approach to inconsistency-tolerant reasoning
is due to Rescher and Manor [
In this paper, we introduce an approach to
inconsistencytolerant inference relations that employ the minimal hitting
sets of a knowledge base. Hitting sets of a knowledge base K
were defined by Thimm [
0009-0007-4797-8726 (Y. Hatab); 0000-0002-1551-7016 (K. Sauerwald); 0000-0002-8157-1053 (M. Thimm) © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). of subset relation). We identify and prove several useful properties of hitting sets, which were not known before.
The main observation of this paper is that one can define
inference of a formula φ from a knowledge base K based on
whether models of φ appear in hitting sets of K under certain
conditions. We define four inference relations |∼ ns, |∼ nc, |∼ ps
and |∼ pc. The most sceptical inference relation |∼ ns states
that K entails φ if all interpretations in all minimal hitting
sets of K are models of φ . The most credulous inference
relation |∼ pc states that φ follows from K, if there is at least
some model of φ in some minimal hitting set of K. According
to |∼ nc-inference, φ follows from K if all minimal hitting
sets contain at least some model of φ , and, likewise, in |∼
pcinference, φ follows from K if all interpretations in some
minimal hitting set are models of φ . We show that |∼ ns and
|u∼nndceirncfeornesniscteenreclya.tiAonlls icnofeinrecnidcee wreiltahticolnasss|i∼canls,e|n∼tancil,m|∼enpst
and |∼ pc are pairwise distinct and are different from those
based on maximal consistent subsets by Rescher and Manor
[
In summary, the main contributions of this paper are: • Definition of inconsistency tolerant inference relations in four degrees of skeptability, that are based on minimal hitting sets. • Proof of the relationship among these four inference relations and to other inference relations. • Several properties of hitting sets and of inference relations based on hitting sets. • An axiomatic evaluation of all four inference relations. • Non-trivial bounds for the complexity of the inference problem for all four inference relations.
In the next section, we provide the necessary background and consider the notion of hitting sets. In Section 3, we prove several novel properties for hitting sets. Then, in Section 4, we define four inference relations based on hitting sets. In Section 5, we determine and prove the exact relationship among hitting set-based inference relations and other inference relations. We show that classical and non-monotonic reasoning properties are satisfied or violated by our inference relations in Section 6. In Section 7, we consider the complexity of the inference problem for hitting set-based inference relations and show residence in the second level of the polynomial hierarchy. Finally, in Section 8, we consider some future work.
In this section, we give the necessary background information on logic, inference relations, and maximal consistent subsets.
Let At be some fixed propositional signature, i. e., a finite set of propositional variables (also called atoms), and let L (At) be the corresponding propositional language constructed using the connectives ∧ (conjunction), ∨ (disjunction), → (implication), ↔ (bi-implication) and ¬ (negation). We use the symbol ⊤ to express a tautology and ⊥ to represent falsity.
If Φ is a formula or a set of formulas we write At(Φ) to denote the set of propositions appearing in Φ. For a set Φ = {φ1, . . . , φn} let ⋀︁ Φ = φ1 ∧ . . . ∧ φn and ¬Φ = {¬φ | φ ∈ Φ}. Moreover, we use overlining to denote the complement of a formula, i. e., for every formula φ , if φ = ¬ψ then φ = ψ and otherwise φ = ¬φ .
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) an atom a ∈ At, denoted by ω |= a, if and only if ω(a) = true. The satisfaction relation |= is extended to formulas, such that, for some subset of the language Φ ⊆ L (At) we define ω |= Φ if and only if ω |= φ for every φ ∈ Φ. As an abbreviation we sometimes identify an interpretation ω with its complete conjunction, i. e., if a1, . . . an ∈ At are exactly those propositional variables that are assigned true by ω and an+1, . . . , am ∈ At are exactly those variables that are assigned false by ω we identify ω by a1 . . . anan+1 . . . am (or any permutation of this). For example, the interpretation ω1 on {a, b, c} with ω(a) = ω(c) = true and ω(b) = false is abbreviated by abc.
In the following, let Φ, Φ1, Φ2 be sets of formulas. Deifne the set of models Mod(Φ) = {ω ∈ Ω(At) | ω |= Φ}. We write Φ1 |= Φ2 if Mod(Φ1) ⊆ Mod(Φ2). We say that Φ1, Φ2 are equivalent, denoted by Φ1 ≡ Φ2, if Mod(Φ1) = Mod(Φ2). If Mod(Φ) = 0/ we also write Φ |=⊥ and say that Φ is inconsistent.
In this work, we are only considering knowledge bases that are non-empty and do not contain formulas that contradict themselves.
Definition 1. A knowledge base K is a finite set of formulas K ⊆ L (At), where: K ̸= 0/ and, every formula φ ∈ K is consistent. Let K be the set of all knowledge bases.
Note that every formula in the knowledge base K is
consistent. However, the knowledge base itself can be inconsistent.
For example K = {p, q, ¬p ∨ ¬q}.
2.2. On Inference from Inconsistency
In this subsection, we consider inferences from inconsistent
knowledge that are based on maximally consistent subsets.
Definition 2 ([
We demonstrate Definition 2 in the following example. Example 1. We consider the knowledge base K = {p, q, r ∧ ¬p}. First, observe that K is inconsistent. One can see easily that MCS(K) = {{p, q}, {q, r ∧ ¬p}} are the maximally consistent subsets of K.
By employing Definition 2, one can formally define the
approach by Rescher and Manor to inconsistent-tolerant
reasoning [
Definition 3 ([
• A formula φ is said to be an inevitable consequence of K, shortly K |∼ imc φ , if M |= φ for all M ∈ MCS(K). • A formula φ is said to be an weak consequence of K, shortly K |∼ wmc φ , if M |= φ for some M ∈ MCS(K).
A basic observation is that |∼ imc and |∼ wmc are distinct relations.
Proposition 4 ([
Consider the knowledge base K1 = {p, q, s, s → t, ¬t}. Obviously, K1 is inconsistent, as there is an apparent inconsistency in the subset {s, s → t, ¬t} of K. However, there are some formulas that do not contribute to an inconsistency, namely, p and q. Such formulas (or any deductible formula of them) can be inferred by the inevitable consequence relation (|∼ imc). Moreover, one can infer the formulas contributing to inconsistency like s, s → t, or ¬t, using the weak consequence inference relation (|∼ wmc). However, knowledge bases like K1 = {p ∧ q, ¬p}, one cannot infer q using |∼ imc even though the atom itself is not contributing the inconsistency.
A hitting set H ⊆ Ω(At) for a knowledge base K ensures that
every formula φ ∈ K is satisfied by at least one interpretation.
Definition 5 ([
Hitting sets have been used in [
Definition 6 ([
Ihs(K) = min{ |H| | H is a hitting set of K } − 1
Note that Ihs is well-defined, since we assume that every formula of a knowledge is (in itself) consistent, see item 3 of Proposition 7 below.
In this section, we will discover several properties of hitting sets. These properties will turn out very useful for the proofs we conduct later in this paper. We start by considering an example that demonstrates the notion of hitting sets and the hitting-set inconsistency measure. Example 2. Consider the knowledge base K3 = {p, ¬p ∧ r, q} Possible minimal hitting sets are: H1 = {pqr, p¯qr}, H2 = {pqr, p¯q¯r}, H3 = {pqr¯, p¯qr} , H4 = {pqr¯, p¯q¯r}, H5 = {pq¯r¯, p¯qr} and H6 = {pq¯r, p¯qr} Making H (K1) = {H1, H2, H3, H4, H5, H6}. Note that H7 = { pq¯r, p¯qr, p¯q¯r } is a hitting set of K3, but H7 is not a minimal hitting set of K. This is because minimality is defined in terms of cardinality, and thus we have H7 ∈/ H (K). Let us label the interpretations for later reference as follows: ω1 = pqr, ω2 = pqr¯, ω3 = pq¯r , ω4 = pq¯r¯, ω5 = p¯qr, ω6 = p¯q¯r. Applying the hitting-set inconsistency measure will result in Ihs(K3) = 2.
Note that a set of formulas S contain an inconsistent
formula exactly when there is no hitting set for S [
Proposition 7. The following statements hold for each knowledge base K.
1. K is consistent iff |H| = 1 for some H ∈ H (K). 2. H (K) is non-empty. 3. Each H ∈ H (K) is non-empty.
4. |H| = |H′| for all H, H′ ∈ H (K).
Proof. We consider each of the statements independently. 1. We show statement 1 by showing each direction independently. “⇒” if K is consistent, let ω be a model of K. Then H = {ω} is a (minimal) hitting set with |H| = 1. “⇐” Let |H| = 1 for some H ∈ H (K), so H = {ω}.
Then ω |= φ for all φ ∈ K and we have that ω is a model of K. Therefore K is consistent. 2. Recall that every formula in K is consistent. Thus, for each formula φ in K there is an interpretation ωφ such that ωφ |= φ . It is easy to see that {ωφ | φ ∈ K} is a hitting set of K. Because we are in a finite setting, the existence of a hitting set implies the existence of a minimal hitting set. Hence, H (K) is a non-empty set. 3. Because K is non-empty, i.e., there is at least one formula φ ∈ K. Since every hitting set H ∈ H (K) contains a model of φ , H is non-empty. 4. For some knowledge base K, and by definition of H , each member of H (K) is minimal in the sense of cardinality. Consequently, there is no hitting set H′ of K where H′ is of smaller size than any member of H (K).
The following notion of a consistent partitioning was given
by Thimm [
Definition 8 ([
Hitting sets can be conceptualized in terms of consistent partitions. 1–10 Proposition 9. For every minimal hitting set of size n there is a minimal consistent partitioning of size n. And vice versa. Proof. We show each direction independently. “⇒” We prove this by contradiction. For a knowledge base K, assume there exist a a minimal hitting set H ∈ H (K) of size n, and there does not exist a minimal consistent partitioning of the same size n. Given that H is a hitting set of K then for each interpretation ω ∈ H satisfies a set of formulas Γ ⊆ K, and if we have n number of interpretations we will have n number of subsets of K, these subsets must be consistent, because there exist exactly one interpretation that satisfies it. Let Φ be the set that contains all Γ′s of K. Thus, Φ is a consistent partitioning of K. Following our assumptions that means that that Φ is not minimal, so there must be a smaller set that is a consistent partitioning. However, having such a set would result in having a hitting set H′ where |H| = x, such that, each Γ ∈ Φ is satisifiable by one interpretation since they are consistent, and x < n. Which means that, H′ is a hitting set of K, which would violate our assumption that H is a minimal hitting set of K. Hence, for every minimal hitting set of size n there is a minimal consistent partitioning of size n. “⇐” This is shown by construction for some knowledge base K and a consistent partitioning Φ = {K1, . . . , Kn}. One would construct for each Ki ∈ Φ one interpretation that models such a set. Which would create a set H that is a hitting set of K. Furthermore, H is minimal because assuming H′ exists and it is smaller than H. That would result in a smaller consistent partitioning of the same size according the earlier point. Which is a contradiction, therefore, H′ can’t exist, and H is a minimal hitting set.
The next example demonstrates the relationship between hitting sets and consistent partitions.
Example 3. We consider the knowledge base K2 = {p, q, s, s → t, ¬t}. One can easily see that K2 is inconsistent and that Φ = {{p, q, s → t}, {s, ¬t}} is a minimal consistent partitioning of K2. The set H = {pqst, pqst} is minimal hitting set of K. Clearly, every interpretation in H is a model of exactly one of the elements in Φ.
We consider now some basic observations on the dynamics of hitting sets when a formula is added to a knowledge base K. The first proposition shows that adding a formula will only increase the number of elements in a minimal hitting set.
Proposition 10. Let K be a knowledge base and φ a consistent formula. For each H ∈ H (K) and for each H′ ∈ H (K ∪ {φ }) holds |H| ≤ | H′|.
Proof. Towards a contradiction assume the contrary. Let H, H′ be minimal hitting sets (of K and K ∪ {φ }) such that |H′| < |H|. Clearly, because H′ is a hitting set of K ∪ {φ }, it is also a hitting set of K. Thus, |H′| < |H| contradicts the minimality of H.
A direct consequence of Proposition 10 is that Ihs(K) ≤
Ihs(K ∪ {φ }) holds for every knowledge base K and very
formula φ [
The following property guarantees that when extending K to K ∪ {φ }, there is always one minimal hitting set of K ∪ {φ } that is an extension of a minimal hitting set of K. Proposition 11. Let K be a knowledge base and φ a consistent formula. There is a minimal hitting set H ∈ H (K) and a minimal hitting set H′ ∈ H (K ∪ {φ }) such that H ⊆ H′. Proof. First, recall that due to Proposition 7, every knowledge base has at least one hitting set. Let H0′ ∈ H (K ∪ {φ }) be a minimal hitting set of K ∪ {φ }. Clearly, H0′ is also hitting set of K. Let H0 ⊆ H0′ be a ⊆ -minimal subset of H0′ that is still a hitting set of K. If H0 is a minimal hitting set of K, we are done. We consider the case of H0 is not a minimal hitting of K. This means that there is a minimal hitting set H of K with |H| < |H0|. As H is a hitting set of K, for each formula ψ ∈ K there is a model ωψ of ψ with ωψ ∈ H. Because φ is consistent, there is also a model ωφ for φ . Now let H′ = H ∪ {ωφ }, which is clearly a hitting set of K ∪ {φ }, because H′ contains a model of every formula of K ∪ {φ }. In summary, we have |H| < |H0| ≤ | H0′ | and thus, we have that |H| + 1 = |H′| ≤ | H0| ≤ | H0′ | holds. From this last observation and because H0′ is a minimal hitting set of K ∪ {φ }, we obtain that H′ is a minimal hitting set of K ∪ {φ } by employing Corollary 4.
A very basic observation that complements Proposition 11 is that if a minimal hitting set H of a knowledge base K contains a model of φ , then H is also a minimal hitting set of K ∪ {φ }.
Proposition 12. Let K be a knowledge base and φ a consistent formula. If a minimal hitting set H ∈ H (K) contains a model of φ , then H (K ∪ {φ }) ⊆ H (K) and H ∈ H (K ∪ {φ }).
Proof. First, recall that due to Proposition 7, every knowledge base has at least one hitting set. Let Hφ ∈ H (K) be a minimal hitting set of K that contains a model of φ . Clearly, Hφ is then also a hitting set of K ∪ {φ } and furthermore, due to Proposition 10, also minimal. Thus, we obtain that Hφ ∈ H (K ∪ {φ }). For the second part of the statement, let H′ ∈ H (K ∪ {φ }) be a hitting set of K ∪ {φ } such that H′ ∈/ H (K). Clearly, H′ has to be also a hitting set of K, because H′ contains a model of every formula in K. Moreover, because of Corollary 4, we obtain H′ is also a minimal hitting set of K.
Finally, we observe that there might be minimal hitting sets of K and of K ∪ {φ } that are completely unrelated to all minimal hitting sets of the respective other knowledge base. Proposition 13. There are knowledge bases K and consistent formulas φ witnessing the following statements: 1. There is a minimal hitting set H ∈ H (K) such that for all minimal hitting sets H′ ∈ H (K ∪ {φ }) holds H ̸⊆ H′. 2. There is a minimal hitting set H′ ∈ H (K ∪ {φ }) such that for all minimal hitting sets H ∈ H (K) holds H ̸⊆ H′. Proof. For Statement 1, let K = {p, ¬p ∧ r, q} be the knowledge base from Example 2 and let φ = ¬p ∧ ¬q ∧ r. Observe that H = {pq¯ r, p¯qr¯} is a minimal hitting set of K, but no superset of H is a minimal hitting set of K ∪ {φ }.
For Statement 2, let K = {p ∧ r, p ∧ q} and let φ = p ∧ q ∧ ¬r. Note that H′ = {pq¯ r, pqr¯} is a minimal hitting set of K ∪ {φ }. We have that H = {pqr} is the one and only minimal hitting set of K, which not a subset of H′. 1–10 Formula p ∨ r ¬p q ∧ r ¬q p ∧ r
K3 |∼ ns ✓ ✗ ✗ ✗ ✗
K3 |∼ nc ✓ ✓ ✗ ✗ ✗
K3 |∼ ps ✓ ✗ ✓ ✗ ✗
K3 |∼ pc ✓ ✓ ✓ ✓ ✗ 4. Inference Based on Hitting Sets By leveraging hitting sets we can define several inference relations based on different criteria of model satisfaction. These inference relations help determine the logical consequences of a knowledge base under various conditions of certainty and possibility.
We will consider multiple inference relations, written |∼ with superscripts, that are relations of type P(K) × L (At). For such a relation |∼ , we ease notation and write φ |∼ ψ for {φ } |∼ ψ. Given knowledge bases K, K′, we are lifting |∼ by saying that K′ follows from K′ w.r.t. |∼ , written K |∼ K′, if for all φ ∈ K′ holds K |∼ φ .
Define inference relations |∼ ns, |∼ nc, |∼ ps and K |∼ ns φ K |∼ nc φ K |∼ ps φ K |∼ pc φ if ∀H ∈ H (K) : ∀ω ∈ H : ω |= φ if ∀H ∈ H (K) : ∃ω ∈ H : ω |= φ if ∃H ∈ H (K) : ∀ω ∈ H : ω |= φ if ∃H ∈ H (K) : ∃ω ∈ H : ω |= φ for every knowledge base K and formula φ .
If K |∼ ns φ holds, we say that φ is a necessary skeptical inference of K. If K |∼ nc φ holds, we say that φ is a necessary credulous inference of K. If K |∼ ps φ holds, we say that φ is a possible skeptical inference of K. If K |∼ pc φ holds, we say that φ is a possible credulous inference of K.
The following example considers the four inference relations |∼ ns, |∼ nc, |∼ ps and |∼ pc.
Example 4. We consider again K3 = {p, ¬p ∧ r, q} from Example 2, and the formulas p ∨ r , ¬p, q ∧ r, ¬q and p ∧ r. One can observe the following: 1. K3 |∼ ns p ∨ r, since all interpretation in each minimal hitting set in H (K3) satisfy p ∨ r 2. K3 |∼ nc ¬p, since in every minimal hitting set in
H (K3) there is an ω that models ¬p. 3. K3 |∼ ps q ∧ r, since both interpretations of H1 model q ∧ r. 4. K3 |∼ pc ¬q, since there exist an interpretation in a hitting set that model ¬q, like ω6. 5. K3 ̸|∼ ns ¬p, because there is some interpretation (like ω2 ) that does not model ¬p 6. K3 ̸|∼ nc q ∧ r, because there is some hitting set H4 where all interpretations does not model q ∧ r 7. K3 ̸|∼ ps ¬p because for every minimal hitting set there will always be some interpretation that satisfies p since it exists as formula in the knowledge base. 8. K3 ̸|∼ pc p ∧ r since no interpretation satisfies p ∧ r Figure 1 summarizes the entailment of |∼ ns, |∼ nc, |∼ ps, |∼ pc.
The following lemma highlights the logical dualities between possible and necessary inference. Lemma 15. Let K be a knowledge base and φ a formula. Then • K |∼ ps φ iff K ̸|∼ nc ¬φ .
• K |∼ pc φ iff K ̸|∼ ns ¬φ .
Proof. We start by showing the first statement. The following sequence of equivalences yields the statement.
K |∼ ps φ ⇔ ∃H ∈ H (K) : ∀ω ∈ H : ω |= φ ⇔ ¬¬∃H ∈ H (K) : ∀ω ∈ H : ω |= φ ⇔ ¬∀H ∈ H (K) : ∃ω ∈ H : ω ̸|= φ ⇔ ¬∀H ∈ H (K) : ∃ω ∈ H : ω |= ¬φ ⇔ K ̸|∼ nc ¬φ and similarly for item 2 as follows,
K |∼ pc φ ⇔ ∃H ∈ H (K) : ∃ω ∈ H : ω |= φ ⇔ ¬¬∃H ∈ H (K) : ∃ω ∈ H : ω |= φ ⇔ ¬∀H ∈ H (K) : ∀ω ∈ H : ω ̸|= φ ⇔ ¬∀H ∈ H (K) : ∀ω ∈ H : ω |= ¬φ ⇔ K ̸|∼ ns ¬φ
Intuitively, |∼ ns is the strictest inference of all four and |f∼oupcr. iTshteheinmfeoresntcpeerrmelaistsioivne|∼ innfcearenndc|e∼ preslaarteiosno mame wonhgatailnl the middle, yet incomparable. In the following theorem we formally confirm our intuition of these inference relations. More precisely, we fully clarify the relationship among the four inference relations |∼ ns, |∼ nc, |∼ ps and |∼ pc. We consider this as one of the main contributions of this paper. Theorem 16. The relationships among |∼ ns, |∼ |∼ pc hold: nc, |∼ ps, and 1. |∼ ns ⊊ |∼ nc 2. |∼ ns ⊊ |∼ ps 3. |∼ nc ⊊ |∼ pc 4. |∼ ps ⊊ |∼ pc 5. |∼ ps ⊈ |∼ nc 6. |∼ nc ⊈ |∼ ps Proof. For any two arbitrary inference relations |∼ x, |∼ y, to prove that |∼ x⊊ |∼ y it is enough to show that for every pair (K, φ ) ∈|∼ x there exist the same pair (K, φ ) ∈|∼ y. We start by showing set inclusion.
1. We show |∼ ns ⊊ |∼ nc. For some set K and formula φ .
If K |∼ ns φ then that means that every interpretation ω in every hitting set H ∈ H (K) also models φ . Then it must be the case that for every hitting set H ∈ H (K), there exists some interpretation ω |= φ .
Then (K, φ ) ∈|∼ nc. 2. We show |∼ ns ⊊ |∼ ps. For some set K and formula φ . if K |∼ ns φ then that means that every interpretation ω in every hitting set H ∈ H (K) also models φ . Then, it must be the case that all interpretations of some hitting set H ∈ H (K) where ω |= φ . Then (K, φ ) ∈|∼ ps. 3. We show |∼ nc ⊊ |∼ pc. For some set K and formula φ . if K |∼ nc φ then that means that for every hitting set H ∈ H (K) there exist some interpretation ω that models φ . Then it must be the case that there exist some interpretations ω of some hitting set H ∈ H (K) where ω |= φ . Then (K, φ ) ∈|∼ pc. 1–10 4. We show |∼ ps ⊊ |∼ pc. For some set K and formula φ . if K |∼ ps φ then that means that there exist some hitting set H ∈ H (K) such that every interpretation ω ∈ H, ω |= φ . Then it must be the case that there exist some interpretations ω of some hitting set H ∈ H (K) where ω |= φ . Then (K, φ ) ∈|∼ pc.
Note that Example 4 witnesses that all set inclusions in Statements 1. to 4. are strict. Moreover, Example 4 witnesses Statements 5 and 6.
Theorem 16 establishes that |∼ ns is the most “strict" of the four inference relations we proposed; and that |∼ pc is the least “strict" inference relation. Meaning anything entailed by |∼ ns is also entailed by |∼ nc and |∼ ps. On the other spectrum, |∼ nc and |∼ ps are subsumed by |∼ pc. Shaping a lattice where |∼ ns and |∼ pc are acting as upper and lower bounds. 5. On Relationships to other
Inference Relations In this section we study the relationship of our newly discovered inference relations |∼ ns, |∼ nc, |∼ ps, and |∼ pc to classical propositional logic, and inference relations based on maximally consistent subsets. Furthermore, we discuss how the inference relations interact within consistency.
We start by considering |∼ imc and |∼ wmc from Rescher and
Manor [
Proposition 17. Let K be a knowledge base. Then ∀M ∈ MCS(K) : ∃H ∈ H (K) : ∃ω ∈ H : ω |= M Proof. We prove this by contradiction. Given a knowledge base K, say that for some maximally consistent subset M ∈ MCS(K), there does not exist an interpretation ω in any hitting set of K that satisfies M. By the definition of hitting sets in Section 2 Definition 5, each hitting set must satisfy each formula in the knowledge base, so each interpretation satisfies some formulas in the knowledge base. Therefore, there exist an interpretation ω ∈ H where H ∈ H (K) such that, ω |= Φ and Φ ⊆ M. Since M is consistent, then there must exist an interpretation ω′ that satisfies M. However, if we replace ω in H with ω′, that would result in a set H′ that is the same size as H, i.e, minimal, and is more general in the sense that it satisefis everything that H satisfies plus previously unsatisfied elements of M. Consequently H′ is a minimal hitting set of K, leading to a contradiction to our assumption.
In other words, for every maximally consistent subset M of a knowledge base K, there exists at least one interpretation ω in a minimal hitting set of K that satisfies M. |∼ imc |∼ wmc ⊊ |∼ pc
Example 5. We consider again the knowledge base K = {p, q, r ∧ ¬p} from Example 1. Recall that the maximal consistent subsets are MCS(K) = {{p, q}, {q, r ∧ ¬p}}. One can see easily that K |∼ imc q holds and that K ̸|∼ ns q holds. This is because there is a minimal hitting set H = { p¯q¯r, pqr} which contains a countermodel of q. Furthermore, it is the case that K |∼ pc r and K ̸|∼ wmc r hold. This shows that |∼ ns ⊊ |∼ imc and |∼ wmc ⊊ |∼ pc holds.
The following observation is a consequence of Proposition 17 and Example 5.
Theorem 18. It holds: 1. |∼ ns ⊊ |∼ imc 2. |∼ wmc ⊊ |∼ pc Proof. Example 5 provides proof for the strictness of the inference relations. We show the inclusions given in Statement 1 and Statement 2.
Statement 1 follows from Proposition 17. Since all maximally consistent subsets are satisfied by some interpretation in a hitting set. Then assuming the antecedent results in having all interpretations of every hitting set satisfying φ . Which shows that all maximally consistent subsets satisfy φ . Then we obtain that K |∼ imc φ holds.
For Statement 2 observe that all maximally consistent subsets are satisfied by an interpretation in a minimal hitting set. Meaning that, when assuming the antecedent K |∼ wmc φ , indicates there is some maximally consistent subset that satisfies φ . Hence, there is some interpretation in some minimal hitting set that satisfy φ . Consequently, we have that K |∼ pc φ holds.
Proposition 18 confirm our intuition about the upper and lower bounds induced by inference relations |∼ ns and |∼ pc.
We have provided a full landscape of all these
relationships that points out that all these six inference operations
are distinct approaches for inconsistent-tolerant reasoning.
Figure 2 summarizes the results on the relationships among
|a∼nnds,T|∼henocr,e|∼mp1s,8|.∼ Rpecc, a|∼llimthc,ataintdw|∼aswmschogwivnenthiant T|∼himecor⊊e m|∼ 1wm6c
holds [
Given the consistency of a knowledge base, several results can be obtained. Specifically, consistency allows us to demonstrate that certain inference relations align perfectly with classical entailment. For instance, when the knowledge base is consistent, both the necessary skeptical inference and the necessary credulous inference coincide with classical entailment, ensuring that our reasoning framework maintains logical soundness.
Proposition 19. Let K be a consistent knowledge base and φ a formula. Then, K |∼ ns φ iff K |∼ nc φ iff K |= φ . Proof. We first begin by proving that necessary skeptical (|∼ ns) and necessary credulous (|∼ nc) are equivalent if the knowledge base is consistent.
If K |∼ ns φ then K |∼ nc φ since the universal quantifier ∀ encompasses the case of the existential quantifier ∃ (due to Proposition 7).
If K |∼ nc φ then K |∼ ns φ . If K |∼ nc φ and K is consistent, then by Proposition 7, there is always one element in each hitting set. i.e. in the case of consistency for all H ∈ H (K) holds |H| = 1. Thus, there exist some ω ∈ H encompasses the only element in H.
Next, we prove that K |∼ ns φ iff K |= φ . “⇒” if K |∼ ns φ then K |= φ . Assuming that the antecedent is true; then because K is consistent we obtain that each H ∈ H (K) is a singleton set due to Proposition 7 Clearly, because we have K |∼ ns φ , for each H = {ω} with H ∈ H (K), we have ω |= φ . Which satisfies the definition of classical entailment. “⇐” if K |= φ , then K |∼ ns φ . Assuming that the antecedent is true, every model of K is a model of φ . Moreoever, because K is consistent, there exist an interpretation that satisfies every formula in K. Hence, for each ω ∈ Mod(K), {ω} is a minimal hitting set. due to Definition 5 of minimal hitting sets. Therefore, K |∼ ns φ .
When knowledge bases are consistent, we can also prove that possible skeptical and possible credulous inferences yield non-trivial outcomes, providing meaningful insights into the semantics of the knowledge base.
Proposition 20. Let K be a consistent knowledge base and φ a formula. Then: K |∼ ps φ iff K |∼ pc φ iff K ∪ {φ } ̸|=⊥ Proof. First part is similarly proven like Proposition 19, possible skeptical (|∼ ps) and possible credulous (|∼ pc) are equivalent if the knowledge base is consistent. If K |∼ ps φ then K |∼ pc φ since the universal quantifier ∀ encompasses the the case of existential quantifier ∃
If K |∼ pc φ then K |∼ ps φ . Since K is consistent, then by Proposition 7, there is always one element in each hitting set. i.e. in the case of consistency for all H ∈ H (K) holds |H| = 1. Thus, there exist some ω ∈ H encompasses the only element in H. Establishing the same result for all ω ∈ H.
Second part is to prove that K |∼ pc φ iff K ∪ {φ } ̸|=⊥. “⇒” If K |∼ pc φ then K ∪ {φ } ̸|=⊥, assuming the antecedent is true, then there exist an interpretation ω that satisfies K such that ω |= K. Then by definition of classical logic satisfiability, there exist an interpretation that satisfies {φ } ∪ K then {φ } ∪ K ̸|= ⊥. “⇒” If K ∪ {φ } ̸|=⊥ then K |∼ pc φ . when the antecedent is true, we have that K ∪ {φ } is consistent. Thus, there is an interpretation ω such that ω |= K and ω |= φ holds. Since hitting sets are minimal, there is a H ∈ H that contains ω and thus, K |∼ pc φ holds. 6. Evaluation Regarding Properties Classical logics, e. g., propositional logic or first-order logic, fall into the class of Tarskian logics. Those logics are characterized by having the property that logical entailment is a closure operator. We take inspiration from Tarskian logics and consider the following closure-like properties: If φ ∈ K, then K |∼ φ .
If K |∼ K′ and K′ |∼ φ , then K |∼ φ .
(Extensivity) (Idempotency) If ψ is consistent and K |∼ φ , then K ∪ {ψ} |∼ φ . (Consistent Monotonicity) The properties (Extensivity) and (Idempotency) are the same as for closure operators. (Consistent Monotonicity) is similar to monotonicity, but respects that knowledge bases do not contain inconsistent formulas. The following proposition shows that none of the inference relations considered are monotonic logics, and most of them violate all properties of a Tarskian logic.
Theorem 21. In general, the following statements hold: • |∼ nc and |∼ pc satisfy (Extensivity). • |∼ ns and |∼ ps violate (Extensivity). • |∼ ns, |∼ nc, |∼ ps and |∼ pc violate (Idempotency) and (Consistent Monotonicity).
Proof. We start by proving that |∼ nc and |∼ pc satisfy (Extensivity). |∼ nc. Assume that φ ∈ K holds. For each hitting set H ∈ H (K), there is an interpretation ωφ ∈ H such that ωφ |= φ . Hence, we have K |∼ nc φ . |∼ pc. Assume that φ ∈ K holds. Note that due to Proposition 7, there is at least one minimal hitting set in H (K) . Moreover, for each hitting set H ∈ H (K), there is an interpretation ωφ ∈ H such that ωφ |= φ .
Hence, we have K |∼ ps φ .
Next, we show that |∼ ns and |∼ ps violate (Extensivity). |∼ ns. Consider the knowledge base K = {a, ¬a} over the signature Σ = { }
a . A minimal hitting set of K is H = {a, a¯ }. Hence, we have that a ∈ K holds, yet we have that K ̸|∼ ns a holds. Clearly, this is a violation of (Extensivity). |∼ ps. Consider the knowledge base K = {a, ¬a} over the signature Σ = {a}. The only minimal hitting set of K is H = {a, a¯}. Hence, we have that a ∈ K holds, yet we have that K ̸|∼ ps a holds. Clearly, this is a violation of (Extensivity).
In the following, we show that |∼ ns, |∼ nc, |∼ ps and |∼ pc violate (Idempotency). Let K = {p ∧ q, p ∧ ¬q}, let K′ = {p ↔ q, ¬q}, and let φ = ¬p ∧ ¬q. We obtain the following sets of minimal hitting sets:
H (K) = {H} with H = {pq, pq¯ } 1–10 H (K′) = {H′} with H′ = { p¯q¯} Note that we have Mod(φ ) = { p¯q¯} and thus, we have K′ |∼ φ andInKt h̸|∼e φfolfloorwailnl g|∼∈, {w|∼e shnos,w|∼ tnhca,t|∼ |∼psn,s|∼, |∼pcn}c., |∼ ps and |∼ pc violate (Consistent Monotonicity). |∼ ns, |∼ nc and |∼ ps. The proof holds for all |∼ ∈ {|∼ ns, |∼ nc, |∼ ps}. Let K = {p ∧ r, p ∧ q}, let φ = p ∧ q ∧ r let ψ = p ∧ q ∧ ¬r. We obtain the following sets of minimal hitting sets:
H (K) = {H0} H (K ∪ {ψ}) = {H1, H2} with H0 = {pqr} with H1 = {pqr, pqr¯}
H2 = {pq¯ r, pqr¯}
Hence, we have K |∼ nc φ and K ∪ {ψ} ̸|∼ nc φ . |∼ pc. Let K = {p, ¬p ∧ r, q}, let ψ = ¬p ∧ ¬q ∧ r and let φ = ¬p ∧ q ∧ ¬r. Observe that H = {pq¯r, p¯qr¯} is a minimal hitting set of K, and thus, we have K |∼ pc φ . The minimal hitting sets of K ∪ {ψ} are: H (K ∪ {ψ}) = {H1, H2} with H1 = {pqr, p¯q¯r}
H2 = {pqr¯, p¯q¯r} Consequently, we have K ∪ {ψ} ̸|∼ pc φ , which contradicts (Consistent Monotonicity).
The following properties are similar to those of System P
[
If φ is consistent, then φ |∼ φ .
If φ |= ψ and K |∼ φ , then K |∼ ψ.
(Consistent Reflexivity)
(Right Weakening)
If K, K′ are consistent, K ≡ K′ and K |∼ φ , then K′ |∼ φ .
(Consistent LLE)
If ψ is consistent, K ∪ {ψ} |∼ φ and K |∼ ψ, then K |∼ φ .
(Consistent Cut)
If ψ is consistent, K |∼ ψ and K |∼ φ , then K ∪ {ψ} |∼ φ .
(Consistent CM)
If φ , ψ are consistent, φ |∼ χ and ψ |∼ χ, then φ ∨ ψ |∼ χ.
(Consistent Or)
Note that in the area of non-monotonic logic, System P is
known as the conservative core, as it captures preferential
entailment [
The following proposition attests that the inference relations considered in this paper satisfy (almost) all of the our adaption of the System P properties.
Theorem 22. In general, the following statements hold • |∼ ns, |∼ nc, |∼ ps and |∼ pc satisfy (Consistent Reflexivity) , (Right Weakening), (Consistent LLE), (Consistent Cut) and (Consistent Or). • |∼ ns and |∼ nc satisfy (Consistent CM). • |∼ ps and |∼ pc violate (Consistent CM). ∼ Pprocosfa.tiWsfye (sCtaorntsbisytensthRowefleinxgivitthya)t . |∼Fonsr, |∼ |∼ nnsca,n|∼d p|∼s nacnsdat|isfaction of (Consistent Reflexivity) follows from Proposition 19 and satisfaction of (Consistent Reflexivity) by classical propositional logic. For |∼ ps and |∼ pc satisfaction of (Consistent Reflexivity) follows from Proposition 20 directly.
Next, we show that |∼ ns, |∼ nc, |∼ ps and |∼ pc satisfy (Right Weakening). Note that we have that φ |= ψ holds if Mod(φ ) ⊆ Mod(ψ) holds. From this, and the definition oKf |W∼|∼eψns,fs|o∼hronawcl,l |∼|∼ ∈thpsa{t|∼an d|∼n|n∼ss,,p|∼c,n|∼cw,n|e∼c,opsb,|∼t|∼aippnsc }th.aantdK ||∼∼ pφc i msaptilsiefys (Consistent LLE). For |∼ ns and |∼ nc satisfaction of (Consistent LLE) follows from Proposition 19 and satisfaction of (Consistent LLE) by classical propositional logic. For |c∼∈on{s|∼istenpts,K|∼ , pwce} hoabvseertvheatthKat|∼ duφe htoolPdrsowpohseintieovner1K9, ∪fo{rφe}acihs consistent. This is a purely semantical definition, and hence, we obtain easily that (Consistent LLE) is satisfied for |∼ .
We show that |∼ ns, |∼ nc, |∼ ps and |∼ pc satisfy (Consistent Cut). |∼ ns andA|∼ssnucm.eLthetat|∼ K o|∼neαoafn|d∼ Kns ∪or{ α|∼ }n c|∼ inns βthehoflodlsl.oFwrionmg.
K |∼ α, we obtain that every minimal hitting set H ∈ H (K) contain a model of α. Note that due to Proposition 7, H (K) is not empty, hence, such an H is also guaranteed to exist. Then, by employing Proposition 12, we obtain from the observations above that each minimal hitting set H of K is also a minimal hitting set of K ∪ {α}, which implies that H (K) = H (K ∪ {α}) holds. Consequently, we have that K ∪ {α} |∼ β implies that K |∼ β holds. |∼ ps and|∼ |∼psp.c.ThIne tphreoofoflfloowr i|∼ngpcwies waniallloggivuee,thbeutpHroβofisfoar minimal hitting set that contains a model of β .
Form K |∼ ps α, we obtain that there is minimal hitting set H ∈ H (K) of K that contains only models of α. Note that due to Proposition 7, we obtain that H a non-empty set. Consequently, H contains at least one model of α. Moreover, from K ∪ {α} |∼ ps β , we obtain that there is a minimal hitting set Hβ ∈ H (K ∪ {α}) contains only models of β . By employing Proposition 12 and our observations from above, we obtain H (K ∪ {α}) ⊆ H (K). Consequently, Hβ is also a hitting set of K. Consequently, we obtain that K |∼ ps β holds.
We show that |∼ ns, |∼ nc, |∼ ps (Consistent Or). and |∼ pc satisfy |∼ ns and( C|∼ onncs.isLteentt O|∼r) eisitshaetrisfiebdeb y|∼ ennstaoilrm|e∼nntc. |=Noofteclathssaitcal propositional logic. Consequently, due to Proposition 19, (Consistent Or) is also satisfied by |∼ ns. |∼ ps and{ φ|∼ }pc|∼. pLs eχt |∼anedit{hψer}b|∼e p|∼s pχs ohro l|∼d.pcB.yAsesmumpleoytihnagt Proposition 20, our assumptions are equivalent to stating that {φ , χ} is consistent and, respectively, that {ψ, χ} is consistent. This implies also that t{iφon∨2ψ0,aχga}ini,sthceonlastitsetrenyti.eldBsy{φem∨pψlo}y|i∼ngps Pχr.oposiExtensivity
Idempotency Consistent Monotonicity
Next, we show that |∼ ns and |∼ nc satisfy (Consistent CM). Let |∼ be one of |∼ ns or |∼ nc. Assume that K |∼ α and K |∼ β holds. From K |∼ α, we obtain that every minimal hitting set H ∈ H (K) contain a model of α and a model of β . Note that due to Proposition 7, H (K) is not empty, hence, such an H is also guaranteed to exist. By employing Proposition 12, we obtain from the observations above that each minimal hitting set H of K is also a minimal hitting set of K ∪ {α}. Our observations imply that H (K) = H (K ∪ {α}) holds. CoAnsseqlausetnstltye,pwoef htahvise tphraotoKf, ∪w{eαs}h o|∼wβthhaotld|∼s.ps and |∼ pc violate (Consistent CM). We give the proof for the violation of (Consistent CM) by |∼ ps. The proof for |∼ ps is the same, but with β = p ∧ q ∧ ¬r. Let K = {p ∧ q ∧ r, p ∧ (q ↔ ¬r)}, let α = ¬q ∧ r and let β = p ∧ q. The minimal hitting sets of K, respectively K ∪ {α}, are:
H (K) = {H1, H2}
with H1 = {pqr, pqr¯} H (K ∪ {α}) = {H2} H2 = {pqr, pq¯r} Tcohnetna,inwsenhoamveotdhealtsKof|∼βp.sTαhuasn,dwKe o|∼bptasiβn thhoaltdKs.∪H{oαw}ev̸|∼erp,sHβ2 holds; which witnesses a violation of (Consistent CM).
We have seen that |∼ ns, |∼ nc, |∼ ps, and |∼ pc are all nonmonotonic logics that satisfy most of the (consistent versions) of the System P properties. Figure 3 summarizes the results of the axiomatic study presented here. 7. Computational complexity Understanding the computational complexity of the proposed inference operators is crucial for assessing their practical applicability. By analyzing the decision problems associated with each inference operator, we can determine how feasible it is to implement these operators in realworld reasoning systems. This analysis reveals the complexity classes of these inference operators, particularly in deriving logical consequences under inconsistency, thereby evaluating the efficiency and scalability of the proposed methods. We consider the following decision problem for |∈∼ {|∼ ns, |∼ nc, |∼ ps, |∼ pc}: |∼ -INFERENCE: Input Knowledge base K, formula φ Output YES iff K |∼ φ , otherwise NO
First, we analyze the complexity of hitting sets, which are the building blocks of our inference relations. In the following lemma, we show the computational complexity of deciding whether a set is a hitting set. Lemma 23. Let K be a knowledge base and H ⊆ Ω(At). Deciding whether H is a hitting set of K can be solved in polynomial time.
Proof. Verifying whether for an interpretation ω and a formula φ , we have ω |= φ , can be solved in polynomial time. We therefore check for all φ ∈ K and all ω ∈ H, whether ω |= φ . If we find for each φ ∈ K a positive answer, H is a hitting set.
Lemma 24. Let K be a knowledge base and H ⊆ Ω(At). Deciding whether H is a minimal hitting set of K is coNPcomplete.
Proof. For coNP membership consider the complementary problem of deciding whether H is not a minimal hitting set. This is either because H is not a hitting set or it is not minimal. The first case can be solved in (deterministic) polynomial time due to Lemma 23. For the latter case, this can be solved by guessing a set H′ ⊆ Ω(At) with |H′| < |H| and verifying that H′ is a hitting set, cf. Lemma 23. The problem of deciding whether H is not a minimal hitting set can therefore be solved in NP. It follows that deciding whether H is a minimal hitting set of K is in coNP.
For coNP-hardness, we provide a reduction from the coNPcomplete problem of deciding whether a given propositional formula φ is undecidable. On input φ we construct an instance (Kφ , Hφ ) for our problem via (let x ∈/ At(φ ) be a fresh atom)
Kφ = {x, ¬x ∨ φ }
Hφ = {ω1, ω2} where ω1, ω2 : At(φ ) ∪ {x} → {true, false} are defined via ω1(x) = true ω2(x) = false ω1(a) = true for all a ∈ At(φ ) ω1(a) = true for all a ∈ At(φ ) Observe that (Kφ , Hφ ) can be constructed in polynomial time wrt. φ . We claim that φ is unsatisfiable if and only if Hφ is a minimal hitting set of Kφ .
• “⇒”: Assume that φ is unsatisfiable, i. e., there is no ω with ω |= φ . Observe first that Hφ is a hitting set of Kφ since we have ω1 |= x and ω2 |= ¬x ∨ φ . Assume there is a hitting set H′ with |H′| < |Hφ | = 2, so H′{ω}. Then ω |= x and ω |= ¬x ∨ φ . It follows that ω |= φ , contradicting the assumption that φ is unsatisfiable. It follows that Hφ is a minimal hitting set. • “⇐”: We show the contraposition, i. e., if φ is satisfiable then Hφ is not a minimal hitting set. So assume that φ is satisfiable and let ω |= φ . We extend ω to an interpretation over At(φ ) ∪ {x} via ω(x) = true. Then observe that ω |= Kφ and therefore {ω} is a minimal hitting set with 1 = |{ω}| < |Hφ | = 2. So Hφ is not a minimal hitting set.
Theorem 25. |∼ ps-INFERENCE and |∼ pc-INFERENCE are both in ΣP.
2 Proof. For Σ2P = NPNP membership, consider the following algorithm. On input K and φ , guess a set H ⊆ Ω(At) (with maximally |K| elements) and verify using the NP-oracle (=coNP-oracle) that H is a minimal hitting set, see Lemma 24. Then, in deterministic polynomial time, check ω |= φ for all ω ∈ H (note that there are at most |K| many elements in 1–10 H). If all (resp. at least one) check is positive, the answer to |∼ ps-INFERENCE (resp. |∼ pc-INFERENCE) is positive as well. It should be clear that this algorithms runs in Σ2P and correctly solves the given problem.
Theorem 26. |∼ ns-INFERENCE and |∼ nc-INFERENCE are both in ΠP.
2 Proof. For Π2P = coNPNP membership, we consider the corresponding complementary problems, i. e., given K and φ decide whether K ̸|∼ ns φ and K ̸|∼ nc φ , respectively. Then, the statement of this theorem follows directly from Theorem 25 and Lemma 15.
The next proposition shows that all inferences considered here are NP-hard.
Proposition 27. |∼ ns-INFERENCE, |∼ nc-INFERENCE, |∼ psINFERENCE and |∼ pc-INFERENCE are NP-hard.
Proof. In the following, let |∼ be one of the inference relations of |∼ ns, |∼ nc, |∼ ps, or |∼ pc. Let φ a formula in KNF, i.e., φ consists of clauses C1, . . . ,Cn and let K = {φC1 , . . . , φCn }, whereby φCi = ⋁︁l∈Ci l denotes the disjunction of all literals for a clause Ci. Note that an interpretation ω is a model of φ if and only if ω is a model of all formulas in K.
We show that φ is satisfiable if and only if K |∼ φ . “⇒” If φ is satisfiable, then we have that K is satisfiable.
Hence, due to Proposition 7, we have that every minimal hitting set of K has exactly one element. Moreover, the one and only interpretation in every minimal hitting set from H (K) is a model of every formula in K and, hence, also a model of φ . So, regardless of which of the inference relations from above we consider, we have K |∼ φ (c.f. Definition 14). “⇐” If φ is not satisfiable, then we have that K is unsatisfiable. Towards a contradiction, we assume that K |∼ φ holds. Due to Proposition 7, this means that regardless which of the inference relations from above we consider, there is at least one minimal hitting set H ∈ H (K) of K that contains a model ω of φ . Now, recall that ω is consequently also a model of all formulas in K. From the latter and because H is minimal, we obtain that H has to be a singleton set, i.e., H = {ω}. However, because φ is not satisfiable, we have that every minimal hitting set of K contains at least two elements due to Proposition 7. Leading to the desired contradiction.
We highly suspect that |∼ ps-INFERENCE and |∼ pcINFERENCE are also Σ2P-hard and |∼ ns-INFERENCE and |∼ ncINFERENCE are also Π2P-hard. However, a proof as, so far, eluded us. 8. Summary and Future work In this paper, we defined novel inference relations. A specific feature of these inference relation is that they allow paraconsistent reasoning. We established the relationship among these inference relations and also among inference relations based on maximal consistent subsets. Our findings concluded that inference relations derived from hitting sets not only align with classical entailment when the knowledge base is consistent but also provide a nuanced approach to handling inconsistencies. Moreover, we showed how two of the proposed inference relations, namely necessary skeptical inference and possible credulous inference, form a lattice to all other inference relations, including ones not introduced in this work.
Finally, we showed that the implications of our work are significant for developing more reliable AI systems capable of reasoning under uncertainty, by proving it’s reasoning capabilities in nonmonotonic reasoning. By leveraging hitting sets, one can achieve a more comprehensive understanding of inconsistent knowledge bases, by facilitating improved decision-making processes in uncertain and complex environments.
While our study has laid a solid foundation, there are
several avenues for future research. One apparent result to be
explored is the hardness of these inference relations.
Moreover, extending our framework to other types of logical
systems and exploring its applicability in different domains
could provide valuable insights. For instance, investigating
the interplay between hitting sets and many-valued logics,
like priest’s three-valued logic [