Abstract
Automated theorem proving has historically been divided between efficient resolution-based methods and human-centric natural deduction. This paper proposes a unified framework that leverages the search efficiency of resolution while maintaining the readability of natural deduction. By treating resolution refutations as expansion trees—which function as types for $\lambda$-term proof structures—the authors provide a mechanism to automatically translate machine-generated proofs into intuitive, interactive formats.
Introduction
In the mid-1980s, the field of automated reasoning faced a significant divide. Resolution provers were highly efficient, operating on formulas in normal forms like Conjunctive Normal Form (CNF) to find proofs through refutation. However, these proofs were notoriously difficult for humans to interpret due to abstract operations like Skolemization and the negation of the goal. Conversely, Natural Deduction (ND) provers mirrored human reasoning but suffered from massive search spaces that made full automation difficult. This paper addresses the need for a "smooth integration" between these two paradigms, using resolution for proof discovery and natural deduction for presentation.
Methods
The proposed system treats proofs as first-class citizens, utilizing three technical pillars:
- Proofs as $\lambda$-terms: Adopting the Curry-Howard isomorphism, natural deduction proofs are represented as terms in a typed $\lambda$-calculus. This allows "partial proofs" to be treated as functions awaiting arguments (subproofs).
- Expansion Trees: Serving as the "glue," expansion trees annotate formulas with specific substitution terms discovered during resolution. They capture the essential variable assignments needed to solve a theorem.
- Expansion-Trees-as-Types: The authors extend the notion of formulas-as-types by using expansion trees as types for natural deduction proofs. The tree acts as a blueprint, guiding automated "tactics" to construct the final proof.
Key Insights
Resolution is reframed as a "substitution engine." While natural deduction struggles with quantifier instantiation (e.g., finding specific terms for "there exists $y$"), resolution excels at finding these terms via unification. By separating discovery (Resolution) from presentation (Natural Deduction), the system utilizes the strengths of both.
Results and Implementation
The authors successfully implemented the system using a combination of Common Lisp and Prolog. Key results include:
- Automatic Translation: Resolution refutations are converted into expansion trees, which then generate Gentzen-style sequent calculus (LK) proofs.
- Interactive Flexibility: The $\lambda$-term representation allows users to intervene in the automated process, inspecting or manually completing partial proofs. This combines the best of automated and interactive theorem proving.
Discussion and Future Work
While the system provides a robust bridge, limitations remain. The current focus on LK sequent systems without the "cut" rule can lead to less concise proofs. Furthermore, while the system generates valid proofs, they are not always the most "elegant" or human-like. Future work suggests using "matings" (graph-based logical representations) to improve formula pruning and extending the framework to constructive logic for direct program synthesis.
Summary updated