Sacre: A Constraint Satisfaction Problem Based Theorem Prover

AAAI 1999

TL;DR

This paper introduces "Sacre," a novel theorem prover that merges the power of resolution with Constraint Satisfaction Problem (CSP) techniques to tackle first-order logic problems. By reframing logic problems as CSPs, Sacre achieves significant efficiency gains, particularly on problems that challenge traditional theorem provers.

What Problem Does This Paper Address?

Proving theorems in first-order logic, especially when expressed in conjunctive normal form (CNF), is a computationally challenging task. Existing methods generally fall into two categories: consistency searching (syntax-oriented, aiming for contradictions) and satisfiability checking (semantics-oriented, aiming to find models or counterexamples). While these approaches have seen success, there's a continuous need for more efficient and robust methods. The authors identify limitations in existing theorem provers, such as Satchmo's range restriction and potential for irrelevant clause selection, which can lead to search space explosions. They aim to bridge the gap by leveraging the strengths of CSPs, known for their efficiency in solving large combinatorial problems through sophisticated search strategies and heuristics.

Methods

The core innovation of Sacre lies in its hybrid approach, combining resolution with CSP techniques. The paper proposes transforming first-order logic problems in CNF into a specialized type of CSP called a CSPT (Constraint Satisfaction Problem for Terms).

Here's a breakdown of the key methodological aspects:

  • CSPT Formulation: Logic predicates are represented as "-variables" (psi-variables), and their domains are "-domains" (psi-domains). A psi-domain for a predicate p is split into two subdomains: one for terms where p is true and one for terms where p is false. This captures the positive and negative literals of a predicate.
  • Transformation Rules:
    • Each predicate p gives rise to psi-variables Ψp and Ψ¬p.
  • The domains dom(Ψp) and dom(Ψ¬p) are derived from unit clauses of the form p(t) and ¬p(t).
  • Non-unit clauses are transformed into cardinality constraints, specifying the minimum and maximum number of psi-variables that must be true.
  • Extended CSP: Sacre employs an "extended CSP" approach. This means that during the search for a solution, domains can be dynamically extended with new values discovered through constraint satisfaction. This is crucial for handling the potentially infinite Herbrand universe in first-order logic without explicit enumeration.
  • Resolution Procedure: The resolution process in Sacre is described as a forward chaining rule applied to contrapositives, guided by constraint satisfaction. The propagate function is central, determining how satisfying a constraint extends domains and checking for inconsistencies (when a term is found to be both true and false for a predicate).
  • Heuristics and Strategy Tuning: Sacre benefits from a rich set of heuristics, drawing from both theorem proving (e.g., weighting) and CSPs (e.g., forward-checking, min-domain, max-domain). This allows for fine-tuning the search strategy to improve efficiency.

Datasets

The paper evaluates Sacre on problems from the CADE-13 Automated Theorem Proving System competition. These are standard benchmarks for theorem provers. No new datasets were introduced.

Key Insights and Ideas

  • Logic as CSP: The fundamental insight is that first-order logic problems in CNF can be elegantly and effectively represented as CSPs. This reframing opens up a wealth of CSP-specific search strategies and heuristics for theorem proving.
  • Domain Extension for Completeness: The concept of an "extended CSP" is critical. By allowing domains to grow dynamically, Sacre avoids the need to pre-compute the entire Herbrand universe, making it more practical for first-order logic.
  • Efficiency through Pruning: The combination of CSP techniques with resolution allows for significant pruning of the search space. Cardinality constraints and heuristic choices help to quickly identify dead ends and focus the search.
  • Sound but Incomplete: The authors acknowledge that Sacre is incomplete due to its reliance on cardinality constraints acting as a unit-resolution inference rule. However, they argue that this incompleteness can lead to greater efficiency, a trade-off often seen in AI.

Key Results

Sacre demonstrates competitive performance on several CADE-13 problems, often outperforming or matching established theorem provers like Otter and Setheo in terms of speed.

  • Performance on CADE-13: Table 1 shows Sacre solving many problems within a 300-second limit, with some proofs taking less than a second (indicated by 0).
  • Comparison: Sacre shows promising results, particularly on problems where Otter and Setheo also perform well. For instance, on SET083-6, Sacre proves inconsistency in 76 seconds, while Otter takes 1 second and Setheo takes 1 second. On NUM009-1, Sacre proves inconsistency in 8 seconds, while Otter takes 152 seconds and Setheo takes 0 seconds.
  • Limitations: Sacre struggles with certain problems, such as PLA004-1 and PLA011-2, which it cannot solve. This highlights the ongoing challenge of theorem proving and the specific limitations of Sacre's current approach.

Limitations and Future Work

  • Incompleteness: The paper explicitly states that Sacre is incomplete. This stems from the use of cardinality constraints, which, while efficient, do not guarantee finding a proof if one exists. The authors suggest that implementing a case-splitting rule, similar to those in Prolog but adapted for ground terms, could ensure completeness without sacrificing too much efficiency.
  • Heuristic Optimization: The authors note the difficulty in combining various heuristics effectively to maximize search space reduction without hiding solutions. Future work will focus on further experimentation and optimization of these heuristic combinations.
  • Oracle Implementation: The possibility of implementing an "oracle" (similar to Otter's autonomous mode) to automatically determine the best strategies and heuristics for a given problem is a promising avenue for future development.
  • Equality and Paramodulation: Sacre already handles first-order logic with equality and has implemented demodulation. Future versions are planned to integrate paramodulation, further expanding its capabilities.
  • Standard CSPs: For problems with non-recursive clauses and non-extended domains (like Map Coloring), Sacre can be viewed as a standard CSP solver, suggesting potential applications beyond theorem proving.

Summary updated

BibTeX
@inproceedings{1999sacre,
  title = {{Sacre: A Constraint Satisfaction Problem Based Theorem Prover}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure