A Theorem-Prover for a Decidable Subset of Default Logic

Philippe Besnard, Rene Quiniou, Patrice QuintonAAAI 1983

Introduction

In the field of Artificial Intelligence, classical logic has long been criticized for its monotonicity—the property that adding new information never invalidates existing conclusions. Human common-sense reasoning, however, is inherently non-monotonic; we frequently make assumptions (e.g., "birds fly") that we retract upon learning specific exceptions (e.g., "this bird is a penguin").

Raymond Reiter’s Default Logic (1980) provided a formal framework for this type of reasoning, but it introduced significant computational challenges. Determining whether a conclusion holds in Default Logic requires checking for consistency, a task that is generally undecidable in first-order logic. This paper addresses this bottleneck by identifying a "sweet spot": a subset of logic powerful enough for practical knowledge representation but restricted enough to guarantee that a theorem-prover will always terminate with a correct answer.

Defining the Decidable Subset: Predefinite Variable Clauses

To achieve decidability, the authors restrict the language of the knowledge base to "predefinite variable clauses." This restriction involves two primary constraints:

  1. No Function Symbols: The logic cannot contain function symbols, though constants are permitted.
  2. Variable Constraints: Any variable appearing in a positive literal must also appear in at least one negative literal within the same clause.

These constraints are common in deductive database contexts. By limiting the language in this way, the authors ensure that the search space for proofs remains finite, preventing the infinite derivations that typically lead to undecidability in first-order theorem proving.

The Saturation Algorithm and Knowledge Compilation

The core of the proposed system is a resolution-based technique called saturation. This process systematically generates all possible inferences from a set of clauses until no new information can be derived. If the saturation process produces an "empty clause" (a logical contradiction), the set is proven to be inconsistent.

To optimize the prover, the authors introduce the concept of Saturation by Sets. Rather than re-running the entire inference process for every individual query, the system "saturates" the base theory with the available defaults upfront. This effectively "compiles" the default theory into its various possible extensions (sets of consistent conclusions). Once these extensions are compiled, the system can reuse them to answer multiple queries efficiently, treating the complex interaction between rules and defaults as a pre-computed state.

Theoretical Guarantees

The paper provides two foundational proofs for this approach:

  • Completeness (Theorem 6): The authors prove that if a formula has a valid proof within the default theory, their algorithm is guaranteed to find it.
  • Termination (Theorem 7): Unlike general-purpose first-order provers, this algorithm is guaranteed to stop. The restrictions on variable clauses ensure that the saturation process cannot continue indefinitely.

By combining these properties, the authors successfully define a decidable fragment of Default Logic, turning consistency checking from a heuristic-based "best effort" into a rigorous, terminating algorithm.

Limitations and Future Work

While the system offers a robust solution for decidable non-monotonic reasoning, it involves certain trade-offs. The reliance on predefinite variable clauses means the system cannot handle complex nested functions, making it more suitable for sophisticated database logic than for general mathematical theorem proving.

Furthermore, the current model is optimized for static axioms. While it handles new queries and default updates efficiently through its compilation approach, any change to the core, non-default facts requires the entire saturation process to be restarted. At the time of publication, the authors were moving toward a practical implementation in PROLOG, positioning this work as a theoretical blueprint for the next generation of common-sense reasoning engines.

Summary updated

BibTeX
@inproceedings{besnard1983theorem,
  author = {Philippe Besnard and Rene Quiniou and Patrice Quinton},
  title = {{A Theorem-Prover for a Decidable Subset of Default Logic}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}
Figure