Published in 1987, this research represents a foundational step in merging classical logic with fuzzy set theory. It introduces a formal framework for automated reasoning when facts and rules are not 100% certain, extending the classical resolution principle to handle uncertainty through Possibility Theory.
The Challenge of Uncertainty in Logic
Standard logic is inherently rigid: a proposition is either true or false. However, in artificial intelligence and expert systems, we frequently encounter "uncertain" information—statements that are likely true but not guaranteed. While probability theory is the traditional tool for uncertainty, it can be computationally cumbersome for logic because probabilities are additive, causing certainty to "bleed out" quickly over long chains of reasoning.
This paper addresses the need for a logic-friendly way to quantify uncertainty that distinguishes between uncertainty (how sure we are that a fact is true) and fuzziness (how well a specific case fits a vague definition).
Methodology: Possibility Theory and Extended Resolution
The authors build their approach on Possibility Theory, specifically utilizing Necessity Measures ($N$).
Extended Resolution Rule
In classical logic, if you know $P \lor Q$ and $\neg P \lor R$, you can conclude $Q \lor R$. The authors prove that if these premises have necessity degrees $\alpha$ and $\beta$, the conclusion has a necessity degree of at least $\min(\alpha, \beta)$. This "weakest link" principle ensures that a conclusion is only as uncertain as the most uncertain piece of evidence used to reach it.
Refutation and Search Strategy
To prove a statement $P$, the system assumes $\neg P$ is true and searches for a contradiction (the "empty clause"). The "strength" of the contradiction found provides the lower bound of certainty for the original statement. Because multiple proof paths may exist, the authors employ an A* search strategy to find the path that yields the highest possible certainty.
Illustrative Example
As a theoretical work, the paper utilizes a synthetic illustrative example involving a social scenario. It models a set of rules and facts about a meeting, such as:
- "If Robert attends, Mary does [0.8 certainty]"
- "If Beatrice comes, the meeting won't be quiet [0.4 certainty]"
The goal is to prove whether the meeting will be quiet and determine the resulting degree of certainty using the extended resolution framework.
Key Insights and Results
- Mathematical Soundness: The authors formally prove that their extended resolution principle is compatible with the axioms of possibility theory.
- Computational Efficiency: By using the
minoperator and A* search, the authors demonstrate that theorem proving under uncertainty is not significantly more expensive than standard logic. - Resolution of Inconsistency: The system can calculate a "degree of inconsistency" for contradictory knowledge bases, helping to identify unreliable data.
- Necessity vs. Possibility: The framework utilizes the duality between necessity ($N$) and possibility ($\Pi$). If a fact is somewhat certain ($N(p) > 0$), its opposite must be totally impossible ($\Pi(\neg p) = 0$), providing a nuanced way to handle ignorance.
Limitations and Future Work
While the method is sound, the authors noted that full "completeness" (finding every possible true answer) was still under research. Furthermore, while the paper touches on fuzziness, the core logic focuses on the uncertainty of crisp propositions. Integrating truly fuzzy predicates (e.g., "0.7 tall") into this resolution framework remains a direction for future exploration.
Summary updated