Strong Inconsistency in Nonmonotonic Reasoning

Gerhard Brewka, Matthias Thimm, Markus UlbrichtIJCAI 2017 · DOI

TL;DR

This paper introduces "strong inconsistency" as a more robust notion for nonmonotonic reasoning, extending classical logic's concept of minimal inconsistent subsets. This new concept allows for a generalized duality between inconsistent and consistent subsets, crucial for applications like knowledge base repair and inconsistency measurement in complex AI systems.

What Problem Does This Paper Address?

In classical logic, understanding inconsistencies in a knowledge base is often done by identifying "minimal inconsistent subsets" (MIS). These are the smallest sets of statements that contradict each other. This concept is powerful because it directly informs how to "repair" a knowledge base by removing these minimal sets, or how to measure its overall inconsistency. However, this classical notion breaks down in nonmonotonic reasoning systems (like default logic or answer set programming). In these systems, adding new information can sometimes resolve inconsistencies, meaning a knowledge base can be consistent overall, yet still contain subsets that would be inconsistent if considered in isolation. This makes the classical MIS concept insufficient for tasks like diagnosing errors or quantifying inconsistency in these more expressive AI formalisms.

Methods

The core of the paper is the introduction of strong inconsistency. A subset $H$ of a knowledge base $K$ is strongly $K$-inconsistent if all of its supersets within $K$ are inconsistent. This is a stronger condition than classical inconsistency. The authors then define minimal strongly $K$-inconsistent subsets (MSIS) as the smallest such strongly inconsistent subsets.

A key theoretical contribution is the Generalised MinHS duality theorem. This theorem shows that for any knowledge base $K$, there's a direct correspondence between minimal hitting sets of MSIS and maximal $K$-consistent subsets of $K$. This mirrors a known duality in classical logic but is now extended to nonmonotonic settings. The paper also introduces concepts like "neutral" and "consistency restoring" formulas, analogous to "free" formulas in classical logic, but adapted for the nonmonotonic context.

For computational aspects, the paper analyzes the complexity of checking for strong inconsistency and minimal strong inconsistency, relating it to the satisfiability problem (SAT) of the underlying logic. They also propose a generic algorithm for computing strongly inconsistent subsets, which works by iteratively checking supersets.

Datasets

Not discussed in the paper. The paper focuses on abstract logical frameworks and uses examples from logic programming and quantified Boolean formulas rather than specific datasets.

Key Insights and Ideas

  • Strong Inconsistency is the Key: The paper argues that "strong inconsistency" is the natural generalization of classical inconsistency for nonmonotonic logics, enabling a unified treatment.
  • Restoring Classical Duality: The most significant insight is that the powerful duality between minimal inconsistent sets and maximal consistent sets, lost in nonmonotonic reasoning, is recovered by using minimal strongly inconsistent subsets. This is crucial for repair and diagnosis.
  • Nonmonotonicity's Impact on Inconsistency: The paper highlights that in nonmonotonic systems, inconsistency isn't as straightforward as in classical logic. A consistent knowledge base can still contain "classically" inconsistent subsets, and adding information can resolve inconsistencies in ways not seen in monotonic systems.
  • Complexity Trade-offs: While strong inconsistency is more complex to check than classical inconsistency (often involving checking supersets), the paper shows that the computational complexity doesn't always increase drastically, and in some cases, it aligns with existing complexity classes.

Key Results

  • Generalised MinHS Duality: For any knowledge base $K$, a set $H$ is a minimal hitting set of the minimal strongly inconsistent subsets of $K$ if and only if $K \setminus H$ is a maximal $K$-consistent subset.
  • Complexity Bounds: The paper establishes complexity bounds for checking strong and minimal strong inconsistency, relating them to the satisfiability problem of the underlying logic. For example, if SAT is $\Sigma_m^p$, strong inconsistency is $\Pi_m^p$.
  • Generic Algorithm: A sound and complete algorithm for computing strongly inconsistent subsets is provided, with a runtime dependent on the logic's consistency checking complexity.
  • Applications: The paper demonstrates how strong inconsistency is directly applicable to knowledge base repair and inconsistency measurement, providing a unified framework for both monotonic and nonmonotonic logics.

Limitations and Future Work

  • Abstract Framework: While the abstract framework is powerful, the paper acknowledges that specific algorithms and complexity analyses for particular nonmonotonic logics (like logic programming or argumentation frameworks) are needed.
  • Computational Efficiency: The generic algorithm for computing strongly inconsistent subsets has a potentially high runtime ($O(2^n \cdot n \cdot f(n))$). Future work will focus on developing more direct and efficient algorithms for specific logics.
  • Diagnosis Generalization: The paper suggests that strong inconsistency can generalize model-based diagnosis to more expressive logics, but a detailed analysis is left for future work.
  • Inconsistency Measures: While a generalized measure (Incmsi) is proposed, further investigation into other inconsistency measures and their properties in the nonmonotonic setting is suggested.
  • Equivalence vs. Strong Equivalence: The paper notes that while strong equivalence is crucial for nonmonotonic reasoning, classical equivalence doesn't preserve the properties related to strong inconsistency.

Summary updated

BibTeX
@inproceedings{brewka2017strong,
  author = {Gerhard Brewka and Matthias Thimm and Markus Ulbricht},
  title = {{Strong Inconsistency in Nonmonotonic Reasoning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/125},
}
Figure