Abstract
In classical logic, the principle of explosion ensures that a single contradiction renders a knowledge base trivial. To maintain utility, one must localize and resolve these inconsistencies. Traditionally, researchers have relied on Minimal Inconsistent Sets (MIS) to identify the "culprits" of a contradiction. However, MIS often fail to capture the full scope of a conflict—a phenomenon the authors describe as "iceberg inconsistencies." This paper, presented at AAAI-25, establishes a formal framework of 14 desirable properties for germane conflicts and introduces Substitution Conflicts, a novel definition that leverages variable substitution to identify hidden contradictions. We demonstrate that while no definition can satisfy all desirable properties simultaneously, Substitution Conflicts provide a robust and economically viable method for inconsistency localization.
Introduction: The Challenge of Localisation
When a knowledge base contains contradictory facts, the primary goal is to identify which specific formulas are responsible. In classical logic, the "principle of explosion" means that any statement can be derived from a contradiction, making the entire system useless unless the error is localized.
The standard tool for this task is the Minimal Inconsistent Set (MIS)—the smallest subset of formulas that remains contradictory. While mathematically elegant, MIS are often insufficient for practical repair. They tend to be "too small," focusing only on the immediate point of friction while ignoring related formulas that are fundamentally part of the same conflict.
The "Iceberg" Problem
The authors argue that many inconsistencies are like icebergs: the MIS is merely the visible tip. Consider a scenario involving a robbery investigation:
- A salesperson claims: "I did not open the safe AND the thieves were unarmed."
- A security chief claims: "The thieves were armed."
The MIS identifies only the dispute regarding the weapons. However, the salesperson’s claim about the safe is inextricably linked to their testimony. If the contradiction is "repaired" by accepting the security chief's statement, the salesperson's entire testimony is called into question. Traditional MIS would ignore the "safe" component, potentially leading to incomplete repairs. The challenge lies in defining "germane" conflicts—subsets that are truly relevant to the inconsistency without including the entire database.
A Property-Based Framework
To evaluate what makes a conflict "germane," the authors propose 14 formal properties, categorized into three groups:
- Core Properties: Including Inconsistency (the set must be contradictory) and Inclusion (every inconsistency must contain at least one germane conflict).
- Semantic Properties: Including Syntax-Robustness, which requires that a conflict remains unchanged if a formula is replaced by a logically equivalent one.
- Atom-related Properties: Including Substitution-Robustness, which posits that if a set is a conflict, it should remain one if its variables or atoms are consistently swapped.
Substitution Conflicts
The paper introduces Substitution Conflicts as a solution to the limitations of MIS. A set of formulas is defined as a Substitution Conflict if there exists a substitution (a mapping of atoms to other formulas) that transforms a known minimal conflict into that set.
This approach asks a fundamental question: "Could this set of formulas be viewed as a specific instance of a more general, structural contradiction?" By focusing on the internal structure of formulas rather than just their immediate truth values, Substitution Conflicts can detect problematic formulas that MIS overlook.
Theoretical Insights: The "No Free Lunch" Theorem
A central contribution of the paper is Theorem 1, an impossibility result. The authors prove that no definition of a conflict can simultaneously satisfy four specific properties:
- Inconsistency
- Inclusion
- Tautology-Freeness
- Substitution-Robustness
This "No Free Lunch" theorem implies that any robust system for localizing inconsistency must make trade-offs. The authors argue that for effective knowledge base repair, we should prioritize Substitution-Robustness over Minimality. While this may result in larger conflict sets, it ensures that the "iceberg" beneath the surface is properly identified.
Results and Complexity
The authors evaluate Substitution Conflicts against existing methods (such as $\star$-conflicts) and find that they satisfy a broader range of core properties, including Safe-Set-Freeness. They further prove that Substitution Conflicts represent the "most economical" way to satisfy both inconsistency and substitution robustness.
From a computational standpoint, detecting a substitution conflict is situated in $\Sigma^p_2$ of the polynomial hierarchy. While this indicates high complexity, it is comparable to other sophisticated inconsistency-tracking techniques in the field.
Limitations and Future Work
The primary trade-off for the robustness of Substitution Conflicts is a loss of Syntax-Robustness. Because the definition relies on the structural form of formulas to allow for substitutions, rewriting a formula into a logically equivalent but structurally different form may cause it to lose its status as a substitution conflict. Additionally, the definition may occasionally include tautologies if they are necessary to complete a substituted structure.
Future research may look toward 3-valued logics (True, False, or Inconsistent) to refine these definitions and potentially mitigate the semantic limitations identified in this study.
Conclusion
By moving beyond the narrow focus of minimality, "Germane Conflicts" provides a more comprehensive framework for understanding how contradictions manifest in knowledge bases. The introduction of Substitution Conflicts offers a theoretically grounded method for capturing the full scope of an inconsistency, providing a more reliable foundation for automated reasoning and system repair.
Summary updated