Minimal Belief and Negation as Failure: A Feasible Approach

Antje Beringer, Torsten SchaubAAAI 1993

Introduction: The Gap Between Theory and Computation

In the field of Artificial Intelligence, reasoning about nonmonotonicity—where new information can invalidate previous conclusions—is a fundamental challenge. Vladimir Lifschitz’s logic of "Minimal Belief and Negation as Failure" (MBNF) emerged as a powerful theoretical framework for this purpose. MBNF is uniquely expressive, capable of distinguishing between what is objectively true in a domain and what an agent or database believes to be true. However, despite its semantic elegance, MBNF remained a purely mathematical construct for years, lacking a practical proof theory or an automated engine to compute answers to epistemic queries.

This paper bridges the gap between high-level epistemic logic and practical automated theorem proving. The authors introduce FONF (First Order logic with Negation as Failure), a feasible subsystem of MBNF, and provide the first concrete automated proof theory to support it.

FONF: A Feasible Subsystem

To make MBNF computable, the authors identify a subset of the logic that retains significant expressive power while remaining computationally tractable. The transition from the full MBNF to the FONF system involves a specific translation technique: the introduction of a "world variable" appended to every predicate and function symbol.

This technique allows the system to simulate "possible worlds"—a core concept in modal logic—within a standard first-order logic framework. By parameterizing predicates with these variables, the logic can formally represent different states of knowledge without the overhead of a full modal semantics. This translation ensures that proving a statement within the simplified FONF system is equivalent to proving it within the broader MBNF framework, provided the queries fall within the feasible subset.

The Extended Connection Calculus

The core technical contribution of the paper is the development of an Extended Connection Calculus designed for FONF. The connection method is a well-established technique in automated reasoning that proves theorems by identifying paths through matrices of literals.

To handle the unique requirements of epistemic logic, the authors introduced two new structures:

  1. NM-matrices: These allow the system to represent nonmonotonicity directly within the proof structure.
  2. Adjunct Matrices: These facilitate a recursive approach to "Negation as Failure" (NAF).

In this system, if the engine needs to prove a negative literal (e.g., not P), it initiates a recursive sub-proof to determine if P can be established. If the sub-proof fails to find a connection for P, the original not P is considered true. This recursive mechanism allows the system to handle complex queries about ignorance and belief that standard theorem provers cannot.

Practical Implementation and the Determinate Restriction

Efficiency is a primary concern in automated reasoning. To avoid the "multiple model" problem—where a set of rules might lead to several conflicting but valid interpretations—the authors focus on determinate databases and queries. This restriction prevents circular definitions, such as "I believe A if I don't believe B, and I believe B if I don't believe A."

By focusing on this determinate subset, the authors achieved a remarkably lightweight implementation. They demonstrated that their entire proof engine could be implemented in just five lines of Prolog code. This highlights a key insight of the paper: complex epistemic reasoning does not necessarily require heavy-duty software architectures if the underlying logic is elegantly designed and properly restricted.

Results and Comparative Expressivity

The authors validate their approach through several key findings:

  • Soundness and Completeness: They provide formal proofs that their translation from MBNF to FONF is truth-preserving for the identified subset.
  • Superior Expressivity: FONF is shown to be more powerful than standard Prolog, as it can handle disjunctions and existential quantifiers that are typically outside the scope of standard logic programming. It also outperforms previous competing approaches to epistemic query answering in terms of the range of queries it can resolve.
  • Practical Utility: The system can handle nuanced distinctions, such as the difference between "Is it true that Anne does not teach biology?" (a statement about reality) and "Is it known that Anne does not teach biology?" (a statement about the database's knowledge).

Limitations and Future Work

While the paper marks a significant step forward, certain limitations remain. The current system cannot handle non-determinate (circular) rules, which, while rare in many practical applications, are theoretically interesting. Additionally, the system currently lacks the ability for "quantifying-in," meaning variables cannot occur free inside the scope of a negation operator.

Future research may explore implementing FONF using alternative deduction methods, such as resolution, to compare efficiency against the connection calculus in large-scale industrial databases. Nevertheless, by providing the first concrete algorithm for MBNF, this work moves epistemic logic from theoretical curiosity into the realm of functional AI tools.

Summary updated

BibTeX
@inproceedings{beringer1993minimal,
  author = {Antje Beringer and Torsten Schaub},
  title = {{Minimal Belief and Negation as Failure: A Feasible Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure