Strong inconsistency

Minimal inconsistent subsets of knowledge bases play an important role in propositional logic, most notably for diagnosis, axiom pinpointing, and inconsistency measurement. It turns out that for nonmonotonic reasoning a stronger notion is needed. In this paper we develop such a notion, called strong inconsistency. We show that—in an arbitrary logic, monotonic or not—minimal strongly inconsistent subsets play a similar role as minimal inconsistent subsets in propositional logic. In particular, we show that the well-known duality between hitting sets of minimal inconsistent subsets and maximal consistent subsets generalizes to arbitrary logics if the strong notion of inconsistency is used. We investigate the complexity of various related reasoning problems and present a generic algorithm for computing minimal strongly inconsistent subsets of a knowledge base. We also demonstrate the potential of our new notion for applications, focusing on axiom pinpointing and inconsistency measurement.

Authors

• Gerhard Brewka
• Matthias Thimm
• Markus Ulbricht Leipzig University

Keywords

• Nonmonotonic reasoning
• Inconsistency handling
• Minimal inconsistent subsets
• Computational complexity