Introduction
Quantifying inconsistency in knowledge bases (KBs) is a fundamental challenge in artificial intelligence. While numerous "syntactic inconsistency measures" have been proposed over decades, the field has lacked a common structural framework to compare their informativeness and underlying logic. This paper introduces a unified framework that represents contradictions as bipartite "inconsistency graphs," establishing a hierarchy of abstraction that clarifies how different measures utilize information.
Methods: The Inconsistency Graph
The core of the proposed framework is the Inconsistency Graph (IG). A knowledge base is represented as a bipartite graph where one set of nodes corresponds to formulas in the KB and the other set represents Minimal Inconsistent Subsets (MISs)—the smallest groups of formulas that trigger a contradiction. An edge exists between a formula and an MIS if the formula is a member of that conflict.
By focusing on the topology of these graphs, the authors define "IG measures" as functions calculated solely from the graph structure, independent of the semantic content of the formulas. This approach shifts the focus from logic to the structural "essence" of contradictions.
Hierarchy of Abstraction
The framework categorizes measures into several abstraction classes based on how much graph information they retain. These classes, such as Conflict-count (CC) and Problematic-count (PC), form a hierarchy of informativeness.
As shown in the hierarchy, moving from an IG-based measure to a simpler class like CC involves intentionally discarding information about which specific formulas cause which conflicts. This formal mapping allows researchers to understand the trade-offs between different measurement approaches.
Key Results and Definitions
The authors successfully mapped ten major existing inconsistency measures into this hierarchy and introduced eight new measures based on graph-theoretic properties. The table below details the definitions for several of these classes.
Beyond classification, the paper presents a Representation Theorem defining the conditions for a valid IG and proves that IG measures are uniquely characterized by the "Independence" property—they are unaffected by "free formulas" that do not participate in contradictions.
Conclusion and Future Work
This framework provides a generative recipe for creating mathematically sound inconsistency measures. However, practical application is currently limited by the computational complexity of identifying all MISs, which is typically NP-hard. Future work will focus on optimizing these calculations for large-scale databases and extending the framework to non-classical logics and semantic measures.
Summary updated