Theorem Proving Under Uncertainty - A Possibility Theory-based Approach

Didier Dubois, Jérôme Lang, Henri Prade

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.

Resolution trees showing the derivation of contradictions with associated necessity degrees.

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.

Equivalence between a resolution graph and a search tree for finding optimal proofs.

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 min operator 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

BibTeX
@inproceedings{dubois1987theorem,
  author = {Didier Dubois and Jérôme Lang and Henri Prade},
  title = {{Theorem Proving Under Uncertainty - A Possibility Theory-based Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure