Abstract
Minimal inconsistent subsets of knowledge bases
play an important role in classical logics, most notably for repair 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
the same role as minimal inconsistent subsets in
classical reasoning. In particular, we show that the
well-known classical duality between hitting sets
of minimal inconsistent subsets and maximal consistent subsets generalises 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
repair and inconsistency measurement