A Circumscriptive Theorem Prover: Preliminary Report

AAAI 1988

TL;DR

This paper presents a novel approach to building a theorem prover for circumscription, a form of nonmonotonic reasoning, by leveraging assumption-based truth maintenance systems (ATMS). The authors demonstrate how ATMS can be used to efficiently compute minimal models, which are central to circumscription, and present a working implementation that handles first-order logic.

What Problem Does This Paper Address?

Nonmonotonic reasoning is crucial for AI systems that need to reason with incomplete information and default assumptions. Circumscription, a prominent formalism for nonmonotonic reasoning, allows us to infer conclusions based on the assumption that "what is not explicitly stated is false." However, efficiently determining whether a conclusion follows from a circumscribed theory has been a significant challenge. Existing methods for computing circumscriptive conclusions have often been unsatisfactory, lacking effective algorithms. This paper aims to bridge this gap by developing an algorithmic approach to circumscription.

Methods

The core of the paper's contribution lies in connecting circumscription with the concept of minimal models and then using assumption-based truth maintenance systems (ATMS) to compute these minimal models.

  • Minimal Models and Confirmation: The authors reframe circumscription in terms of "minimal models." A conclusion is valid under circumscription if it holds in all "minimal" models of the theory. They introduce the concept of "confirmation" where a sentence q is confirmed by a sentence p if p is a disjunction of elements from a specific set D (representing defaults), TU{p} is satisfiable, and TU{p} entails q. A key result states that q holds in all D-maximal models of T if and only if there's a p that confirms q and p is "unconfirmed."
  • ATMS for Minimal Models: The paper argues that assumption-based truth maintenance systems (ATMS) are well-suited for this task. ATMS are designed to track dependencies and justifications for beliefs, and they can determine the "environments" (sets of assumptions) under which a proposition holds. The authors show that the minimal environments computed by an ATMS correspond to the "weakest" confirming sentences needed for circumscription.
  • Backward-Chaining ATMS: To implement this, they develop a backward-chaining ATMS. This is a departure from existing ATMS work which often used forward-chaining. They also extend the ATMS to handle first-order logic, addressing issues like quantification and variable binding. The implementation uses a "bilattice" structure to represent ATMS environments.

Datasets

Not discussed in the paper. The paper uses canonical examples from the literature for demonstration:

  • The "birds flying" example.
  • A disjunctive example from McCarthy.
  • The "Yale shooting problem."

Key Insights and Ideas

  • Bridging ATMS and Circumscription: The paper establishes a strong theoretical link between the minimal model semantics of circumscription and the functionality of ATMS in finding minimal justifications. This provides a concrete algorithmic path to solving circumscription problems.
  • Confirmation as a Core Concept: The introduction of "confirmation" provides a more tractable way to reason about minimal models than directly manipulating model sets.
  • Backward-Chaining ATMS for Efficiency: Developing a backward-chaining ATMS is crucial for theorem proving, as it allows for goal-directed reasoning, which is more efficient than forward-chaining for answering specific queries.
  • First-Order ATMS for Practicality: Handling first-order logic is essential for real-world applications, and the paper outlines how to extend ATMS to this more expressive language.

Key Results

The paper presents a working implementation of a circumscriptive theorem prover. The key qualitative result is that the system correctly handles several challenging nonmonotonic reasoning examples, including:

  • Birds Flying: Correctly identifies Tweety as flying and Fred (an ostrich) as not flying.
  • Disjunctive Example: Correctly infers that either 'a' is a block or 'b' is a block, but not both.
  • Yale Shooting Problem: Correctly concludes that Fred is not alive after waiting and firing the gun, resolving the temporal projection paradox by considering default assumptions about abnormality.

The authors also note that the computational procedure is "reasonably efficient," citing the Yale shooting problem being solved in approximately one second on a Symbolics 3600.

Limitations and Future Work

  • Assumptions on Theory Structure: The authors acknowledge that their approach, particularly the handling of quantification in first-order logic, relies on certain assumptions about the structure of the input theory. They note that generalizing this to handle all first-order theories might be difficult.
  • Wider Circumstances: While Proposition 2.1 is presented under specific assumptions about the theory T (e.g., domain closure, uniqueness of names), the authors suggest that the validity of the proposition and their implementation might extend to "somewhat wider circumstances," which is an area of ongoing investigation.
  • Generalization of ATMS: The paper mentions that the ATMS construction might need further generalization to handle all first-order theories, indicating potential areas for future research.

Summary updated

BibTeX
@inproceedings{1988circumscriptive,
  title = {{A Circumscriptive Theorem Prover: Preliminary Report}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure