TL;DR
This paper introduces a novel, calculus-agnostic proof method for possibilistic logic, which handles uncertainty using possibility and necessity measures. This method reduces possibilistic reasoning to classical entailment, making it decidable for fragments of first-order logic where classical entailment is decidable. The authors then apply this to create a robust extension of terminological logics for uncertain knowledge representation.
What Problem Does This Paper Address?
Representing and reasoning with uncertain knowledge is a fundamental challenge in Artificial Intelligence. Possibilistic logic offers a framework for this by assigning possibility and necessity degrees to statements, allowing for nuanced representation of uncertainty. While a resolution-based calculus exists for possibilistic logic, it inherits termination issues from classical resolution, especially when dealing with complex first-order formulas. Furthermore, transforming possibilistic formulas into a suitable format for resolution can be problematic. This paper aims to address these limitations by proposing a new proof method that abstracts away from specific calculi and relies on classical entailment, and by demonstrating its application to terminological logics, a decidable subclass of first-order logic.
Methods
The core of the paper is an alternative proof method for possibilistic logic. Instead of relying on a specific calculus like resolution, this method uses a test for classical entailment as its fundamental operation. The authors show that if classical entailment is decidable for a given fragment of first-order logic, then possibilistic reasoning is also decidable for that fragment. This method is proven to be sound and complete with respect to the semantics of possibilistic logic.
The authors then instantiate this method with terminological logics. Terminological logics are formalisms for knowledge representation that define concepts and relationships between them. By combining possibilistic logic with terminological logics, they create a system that can express uncertain knowledge about concepts and individuals. This extension allows for plausible rules between concepts (e.g., "rich persons are likely to own a Porsche") and uncertain assertions about individuals. The decision procedures for this extended system are derived directly from the general proof method and existing algorithms for terminological logics.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Calculus-Agnostic Proof Method: The most significant insight is the decoupling of possibilistic reasoning from specific proof calculi. By leveraging classical entailment, the method becomes more general and can benefit from decidability results in classical logic.
- Reduction to Classical Entailment: The paper demonstrates a powerful reduction: if you can check classical entailment for a set of formulas, you can also perform possibilistic reasoning. This is a key enabler for decidability.
- Uncertainty in Terminological Logics: Extending terminological logics with possibility and necessity degrees provides a semantically sound and algorithmically viable way to represent uncertain knowledge, going beyond simple probabilistic approaches.
- Handling Inconsistency: The paper delves into the concept of inconsistency in possibilistic knowledge bases and defines an "inconsistency degree," offering a way to quantify how "wrong" a knowledge base is. This is crucial for robust reasoning.
Key Results
- Decidability Theorem: Possibilistic entailment is decidable for fragments of first-order logic where classical entailment is decidable.
- Soundness and Completeness: The proposed alternative proof method is proven to be sound and complete for possibilistic logic.
- Possibilistic Extension of Terminological Logics: The paper presents a formal framework for extending terminological logics with uncertainty, offering both a clear semantics and algorithmic procedures for inference.
- Algorithm Derivation: The proof method automatically yields algorithms for possibilistic entailment when a classical entailment checker is available.
Limitations and Future Work
- Termination of Classical Resolution: While the proposed method abstracts from specific calculi, its decidability ultimately relies on the decidability of the underlying classical entailment test. If the classical entailment test itself doesn't terminate for certain inputs, the possibilistic reasoning might also face issues.
- Nonmonotonic Reasoning: The authors suggest that possibilistic logic provides a good basis for nonmonotonic reasoning, particularly for representing defaults in terminological formalisms. This is identified as an interesting avenue for future research, noting that existing approaches often use propositional logic and may not directly apply to the terminological case.
- Efficiency of Inference: While decidability is established, the efficiency of the derived algorithms for possibilistic terminological logics is not the primary focus, though it's mentioned that further optimizations are possible for restricted terminological systems.
Summary updated