Reasoning About Inconsistent Formulas

João Marques-Silva, Carlos MencíaIJCAI 2020 · DOI

TL;DR

This paper provides a comprehensive overview of techniques for reasoning about inconsistent logical formulas, focusing on identifying and correcting the sources of inconsistency. It highlights how many algorithms developed for propositional logic can be generalized to more expressive logics like first-order logic, and discusses their application in optimization problems and explainability.

What Problem Does This Paper Address?

In many real-world scenarios, logical systems or knowledge bases can become inconsistent, meaning they contain contradictory information. This inconsistency can arise in various fields, such as debugging software specifications, diagnosing system failures, or even in machine learning model explanations. The challenge lies in understanding why the inconsistency exists and how to resolve it. This paper addresses the problem of analyzing these inconsistent formulas by focusing on two main aspects: identifying the minimal sets of assumptions or clauses responsible for the inconsistency (explanations) and finding minimal sets of clauses to remove or modify to restore consistency (corrections).

Methods

The paper surveys various approaches for analyzing inconsistent formulas, primarily focusing on first-order logic and its fragments. Key concepts introduced and discussed include:

  • Minimal Unsatisfiable Subsets (MUSes): These are the smallest sets of "soft" clauses (those that can be relaxed) that, when combined with the "hard" background knowledge, lead to inconsistency. MUSes serve as explanations for the inconsistency.
  • Minimal Correction Subsets (MCSes): These are the smallest sets of soft clauses that, when removed from the formula, restore consistency. MCSes represent ways to correct the inconsistency.
  • Relationship between MUSes and MCSes: A crucial insight is the duality between MUSes and MCSes, where MCSes are minimal hitting sets of MUSes, and vice-versa.
  • Algorithms for Extraction: The paper details algorithms for finding single MUSes and MCSes. These often involve iterative removal (for MUSes) or addition (for MCSes) of clauses, guided by satisfiability tests (SAT solvers or other oracles). Algorithms like "Deletion-based" and "Clause D" are presented.
  • Generalization to Monotonic Logics: A significant contribution is the demonstration that many algorithms developed for propositional logic can be generalized to more expressive monotonic logics, such as first-order logic fragments. This is achieved by viewing propositional variables as predicate symbols and leveraging existing translations.
  • Enumeration Algorithms: Beyond finding single explanations or corrections, the paper discusses algorithms for enumerating all MUSes and MCSes. This often involves more complex techniques like blocking found solutions to avoid duplicates.
  • Optimization Problems: The paper connects reasoning about inconsistency to optimization problems, particularly Maximum Satisfiability (MaxSAT). It explains how solutions to MaxSAT problems correspond to Maximal Satisfiable Subsets (MSSes), which are complements of MCSes.

Datasets

Not discussed in the paper. The paper focuses on theoretical frameworks and algorithmic approaches rather than empirical evaluation on specific datasets. The running example provided is illustrative rather than a benchmark dataset.

Key Insights and Ideas

  • Generalizability of Algorithms: A core insight is that many techniques for analyzing inconsistent propositional formulas can be effectively generalized to more expressive logics like first-order logic. This significantly broadens the applicability of these methods.
  • Duality of Explanations and Corrections: The strong relationship between MUSes (explanations) and MCSes (corrections) provides a powerful framework for understanding and addressing inconsistency. Finding one can often lead to finding the other.
  • Inconsistency as a Tool: The paper highlights that inconsistency isn't always a problem to be eliminated; it can be a useful concept in itself, particularly in optimization problems like MaxSAT, where finding the "least inconsistent" solution is the goal.
  • MSMP Framework: The Minimal Sets over Monotone Predicates (MSMP) framework offers a unifying perspective for various problems related to finding minimal sets, including MUSes and MCSes, suggesting a path towards more general algorithms.

Key Results

The paper doesn't present quantitative results in terms of specific performance metrics on benchmarks. Instead, its key results are theoretical and conceptual:

  • Overview of State-of-the-Art: It provides a structured overview of existing algorithms and theoretical results for finding and enumerating MUSes and MCSes.
  • Generalization Framework: It establishes that algorithms for propositional logic can be generalized to broader classes of monotonic logics, including fragments of first-order logic.
  • Connections to Optimization: It clarifies the relationship between inconsistency analysis and optimization problems like MaxSAT, showing how solutions to one can be derived from the other.

Limitations and Future Work

  • Decidability: While the paper discusses generalizations to FOL fragments, it notes that the underlying SAT test for these fragments needs to be decidable. The complexity of these decision problems can impact the overall performance.
  • Computational Complexity: The paper acknowledges that computing smallest MUSes (SMUSes) is computationally harder than finding single MUSes, often requiring oracle calls to more complex complexity classes (e.g., $\Sigma_2^P$).
  • Practical Performance: While algorithms are presented, the paper doesn't delve deeply into empirical comparisons of their practical performance on large-scale problems.
  • Non-Monotonic Logics: The paper primarily focuses on monotonic logics, acknowledging that there is also interest in non-monotonic logics for inconsistency analysis, which might require different approaches.
  • Future Work: The authors suggest that the fast pace of improvement in inconsistency analysis algorithms is expected to continue, driven by the many existing applications. Further research into efficient enumeration and generalization to more expressive logics remains an active area.

Summary updated

BibTeX
@inproceedings{marquessilva2020reasoning,
  author = {João Marques-Silva and Carlos Mencía},
  title = {{Reasoning About Inconsistent Formulas}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/682},
}
Figure