Multi-Valued Logics

Matthew L. GinsbergAAAI 1986

Abstract

This paper introduces bilattices as a unifying mathematical foundation for diverse non-monotonic reasoning systems in AI, such as default logic and truth maintenance systems. By representing truth values along two independent axes—truth and knowledge—the framework provides a consistent formal language for handling defaults and contradictions.

Introduction

In the mid-1980s, AI research faced a significant challenge in formalizing "non-monotonic" reasoning. Unlike classical logic, where proven facts remain true indefinitely, real-world intelligence requires the ability to retract assumptions as new information arrives. For instance, assuming a bird can fly until learning it is a penguin necessitates a logic that can handle "default" conclusions and subsequent revisions.

While solutions like Reiter’s Default Logic and Doyle’s Truth Maintenance Systems (TMS) existed, they were often viewed as ad-hoc tools. Matthew L. Ginsberg’s 1986 paper addresses this by proposing bilattices—mathematical structures that track both the degree of truth and the degree of certainty, offering a single language to describe these disparate systems.

The Bilattice Framework

The core innovation is the departure from binary "true/false" values. Ginsberg suggests arranging truth values along two distinct partial orders:

  1. The Truth Axis ($\le_t$): Ranges from "false" ($f$) to "true" ($t$).
  2. The Knowledge Axis ($\le_k$): Ranges from "unknown" ($u$) to "contradictory" ($\perp$).

This two-dimensional space allows for intermediate values, such as "default true" ($dt$) or "default false" ($df$). Logical operators like AND, OR, and NOT are redefined as operations within this bilattice. Inference is viewed as the process of moving "up" the knowledge axis as information is gained.

A seven-valued bilattice structure incorporating default values, showing the relationship between unknown, default, and certain truth values.

As shown in the figure above, the structure provides a formal way to represent states of partial knowledge. A statement can be "true by default" (positioned between unknown and true) or "contradictory" (representing conflicting evidence for both truth and falsehood).

Key Insights and Ideas

The most significant contribution is the explicit separation of truth from certainty. This allows an AI to distinguish between a lack of information ("unknown") and conflicting information ("contradictory").

Ginsberg demonstrates that logical inference corresponds to finding the greatest lower bound in the knowledge axis. This perspective unifies various AI techniques; for example, Reiter’s Default Logic can be mapped onto a 7-valued bilattice, while TMS can be viewed as a bilattice where truth values represent sets of justifications.

Truth value assignments for the "Tweety" bird example, illustrating how different mappings handle default reasoning.

The Tweety example (shown in the table above) illustrates how the framework handles conflicting defaults. By assigning values like $dt$ (default true) and $df$ (default false), the system can maintain consistency even when faced with the "penguin" exception to the "birds fly" rule.

Key Results

The paper provides several formal proofs to validate the framework:

  • Theorem 4.1: Establishes that logical entailment ($p \vdash q$) is equivalent to a specific ordering within the bilattice structure.
  • Mapping Default Logic: Successfully represents the complex "extensions" of Reiter's logic within a 7-valued bilattice.
  • Mapping TMS: Shows that Truth Maintenance Systems are specific instances of bilattices where values are contexts or justifications.

Conclusion and Future Work

Ginsberg’s bilattice framework offers an elegant unification of non-monotonic reasoning. However, the author notes that the computational efficiency of a general-purpose inference engine based on this theory remains to be fully explored. While the paper focuses on symbolic logic, future work was suggested to integrate other methods like probabilistic reasoning and circumscription. At the time of publication, implementation of these ideas was underway at Stanford.

Summary updated

BibTeX
@inproceedings{ginsberg1986multi,
  author = {Matthew L. Ginsberg},
  title = {{Multi-Valued Logics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure