nanoCoP: Natural Non-clausal Theorem Proving

Jens OttenIJCAI 2017 · DOI

TL;DR

This paper introduces nanoCoP, a novel theorem prover for first-order logic that operates directly on the original formula structure, avoiding the computationally expensive and proof-obscuring translation to clausal form. This "natural" approach leads to shorter proofs and improved performance, demonstrating the viability of non-clausal theorem proving.

What Problem Does This Paper Address?

Automated theorem proving (ATP) aims to automatically determine if a given formula is a logical consequence of a set of axioms. The dominant paradigm in ATP involves translating the input formulas into clausal form (conjunctive or disjunctive normal form) before applying proof search calculi. While this simplifies some aspects of proof search, it introduces significant overhead due to the translation process itself, which can exponentially increase formula size. Furthermore, translating a proof found in clausal form back to a human-readable, non-clausal proof is challenging. Existing non-clausal proof methods, like sequent or tableau calculi, are often less efficient. This paper addresses the need for an ATP system that can perform efficient proof search directly on the original, non-clausal structure of formulas, combining the benefits of natural proof representations with the efficiency of goal-oriented search.

Methods

The core of nanoCoP is a non-clausal connection calculus. This calculus generalizes the well-established clausal connection calculus by working with "non-clausal matrices." These matrices represent formulas as sets of clauses, where each clause can contain literals, sub-matrices, and be recursively defined. The calculus defines rules like "Start," "Axiom," "Decomposition," "Reduction," and "Extension" to manipulate these matrices and find connections (pairs of complementary literals).

Key methodological innovations include:

  • Non-clausal Matrix Representation: Formulas are transformed into a structured matrix representation (Table 1) that preserves their original structure.
  • Connection Calculus Adaptation: The calculus is extended to handle the non-clausal structure, notably by introducing a decomposition rule and modifying the extension rule.
  • Lean Prolog Implementation: The prover is implemented in a remarkably compact Prolog code, leveraging the "lean methodology" pioneered by leanCoP. This involves storing literals in Prolog's database with information about their context (e.g., the largest clause they belong to) to facilitate efficient access.
  • Optimization Techniques: nanoCoP incorporates optimizations like positive start clauses, restricted backtracking, regularity, and lemmata, which are crucial for pruning the search space and achieving completeness.

Datasets

The paper evaluates nanoCoP on:

  • Formula Class Fn: A parameterized class of formulas designed to test the prover's performance on increasingly complex structures.
  • TPTP Library v3.7.0: A standard benchmark collection of first-order logic problems used to assess the prover's overall capability and compare it against other state-of-the-art systems.

Key Insights and Ideas

  • "Natural" Proofs are Efficient: The paper strongly suggests that working with formulas in their original, non-clausal form is not only more intuitive but can also be more efficient than the traditional clausal approach.
  • Clausal Translation is a Bottleneck: The overhead introduced by clausal translation is a significant performance inhibitor, especially for complex formulas where size can explode.
  • Connection Calculus Adaptability: The connection calculus framework is flexible enough to be extended to non-clausal representations, retaining its goal-oriented search efficiency.
  • Compact Implementation is Feasible: The success of nanoCoP demonstrates that powerful ATP systems can be implemented with surprisingly little code, especially when leveraging logic programming paradigms.
  • Proof Length Matters: Shorter proofs are not just aesthetically pleasing; they can be crucial for applications like formal verification where proof complexity directly impacts tractability.

Key Results

  • Performance Improvement: nanoCoP demonstrates solid performance, outperforming both standard and definitional clausal form translations of the leanCoP prover on the TPTP benchmark.
  • Shorter Proofs: Approximately 40-51% of nanoCoP's proofs are shorter than those generated by leanCoP using clausal forms. In some cases, proofs are dramatically shorter (up to 96% shorter).
  • Compactness: The nanoCoP prover is implemented in a very compact Prolog code, highlighting the efficiency of the chosen methodology.
  • TPTP Performance: nanoCoP proves a significant number of problems from the TPTP library, indicating its practical utility.

Limitations and Future Work

  • Limitations: The paper notes that while nanoCoP performs well, the TPTP library contains many problems that are "mostly" in clausal form, which might slightly favor clausal provers. The performance of nanoCoP with restricted backtracking was tested, but a full exploration of its capabilities with various optimization settings might be needed.
  • Future Work:
    • Non-Classical Logics: nanoCoP's non-clausal approach is well-suited for extension to non-classical logics (e.g., intuitionistic, modal logics) where clausal forms are problematic or undesirable.
  • Integration with Other Techniques: Combining nanoCoP with techniques like prefix unification for non-classical logics.
  • Further Optimization: Incorporating strategy scheduling, learning, and variable splitting to enhance performance.
  • Verifiably Correct Software: Leveraging nanoCoP's compact and natural proofs for developing verifiably correct software.

Summary updated

BibTeX
@inproceedings{otten2017nanocop,
  author = {Jens Otten},
  title = {{nanoCoP: Natural Non-clausal Theorem Proving}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/695},
}
Figure