In the early 1990s, the field of Artificial Intelligence faced a conceptual "identity crisis" regarding the representation of vagueness and doubt. Didier Dubois and Henri Prade’s 1994 paper, originally presented at the AAAI proceedings, serves as a rigorous mathematical defense of fuzzy logic against contemporary critics. More importantly, it provides a definitive proof that a "perfect" (fully compositional) calculus for uncertainty is a mathematical impossibility.
The Distinction: Partial Truth vs. Uncertainty
The core of the paper lies in distinguishing between two often-conflated concepts: partial truth and uncertainty.
- Partial Truth (Fuzzy Logic): This describes the degree to which a proposition is true. For example, if a man is 180cm tall, the statement "He is tall" might have a truth value of 0.7. This is a matter of definition and linguistic vagueness.
- Uncertainty (Possibility/Probability Theory): This describes our state of knowledge about a binary (True/False) proposition. If we are told there is a 0.5 probability that a man is tall, we do not know his height; we only know the likelihood of the binary state.
The authors illustrate this with their famous Bottle Analogy. A bottle that is "half-full" represents a partial truth (a degree of 0.5). However, a bottle that has a 0.5 probability of being full is entirely different; in the latter case, the bottle is either completely full or completely empty, but our knowledge is incomplete. Conflating these two leads to significant errors in logical reasoning.
The Compositionality Trap
In AI, "compositionality" is the property where the value of a complex expression (e.g., $A \land B$) can be calculated solely from the values of its components ($A$ and $B$). This is computationally attractive because it allows for "plug-and-play" arithmetic in expert systems, avoiding the need to track complex dependencies.
Fuzzy logic is compositional: the truth of "tall AND heavy" is a direct function of the truth of "tall" and the truth of "heavy." However, Dubois and Prade prove that uncertainty is inherently non-compositional. If $P(A) = 0.5$, we cannot determine $P(A \land \neg A)$ without knowing the relationship between $A$ and its negation. In a compositional system, $P(A \land \neg A)$ would be forced to equal $P(A \land B)$ where $P(B)=0.5$, which is logically absurd for uncertainty measures like probability.
The Impossibility Theorem
Using formal logical analysis and the framework of Possibility Theory, the authors demonstrate that on a standard Boolean algebra, one cannot construct a function mapping uncertainty to the unit interval $[0, 1]$ that is fully compositional for all logical connectives (AND, OR, NOT) without the system collapsing into a triviality.
They analyze proposed "likelihood logics" that attempt to maintain compositionality and show they can only represent a maximum of four levels of certainty (True, Likely, Unlikely, False). This makes such systems too crude for sophisticated AI applications that require a continuous scale of belief.
Refuting the "Collapse" of Fuzzy Logic
The paper specifically addresses a 1993 critique by Charles Elkan, who claimed fuzzy logic was mathematically "trivial" because it supposedly collapsed into standard two-valued logic under certain conditions. Dubois and Prade demonstrate that Elkan’s proof was a consequence of a category error: he applied Boolean equivalences (like the law of excluded middle) to fuzzy logic—a system that specifically rejects those equivalences to accommodate the "gray areas" of partial truth.
Conclusion
Dubois and Prade conclude that the future of AI reasoning requires a clear separation of concerns. Fuzzy sets should be used to model vague linguistic concepts (linguistic variables), while possibility theory or probability should be used to model the uncertainty of the knowledge itself. By proving the impossibility of a fully compositional uncertainty calculus, the authors established the mathematical boundaries for how AI must handle incomplete information and vague definitions in a computationally efficient yet logically sound framework.
Summary updated