Introduction
In human mathematics, the intuition that "this theorem can be proved similarly to the previous one" is a powerful tool for discovery. However, formalizing this analogical reasoning for computers is notoriously difficult. Most automated theorem provers treat every new problem as a blank slate, failing to leverage the structural "wisdom" contained in existing proofs. This paper addresses this gap by introducing a formal method for automating proof analogy. By representing proofs as terms—following the "propositions as types" paradigm—and utilizing second-order pattern matching, the authors demonstrate how a computer can transform an existing proof into a valid proof for a similar, more complex theorem.
Methodology
The authors' approach is built upon two primary pillars:
- Propositions as Types (Curry-Howard Isomorphism): Mathematical propositions are treated as types, and their proofs as terms (specifically lambda-terms). If a term can be "type-checked" against a proposition, the proof is considered valid. This framework turns proof manipulation into a program transformation problem.
- Second-Order Pattern Matching: Unlike standard first-order matching, which only replaces variables with constants or terms, second-order matching allows variables to represent functions or sequences of inference rules. This is crucial for capturing structural changes in a proof, such as repeating a sequence of logic or applying rules in new contexts.
As shown in the workflow above, a user provides a known proof (proof1) and a transformation rule (a schema consisting of pattern1 -> pattern2). The system uses Huet’s second-order pattern matching algorithm to find all possible ways pattern1 matches proof1, producing a set of "unifiers" (substitutions). These unifiers are then applied to pattern2 to generate candidate proof terms for the new theorem. Finally, a type-checker filters these candidates to identify valid proofs.
Evaluation
The method was evaluated using a running example based on Gentzen’s LK system, a formal logic system.
The authors tested the system by transforming a source theorem involving disjunctions and existential quantifiers into increasingly complex versions. These target theorems required structural adaptations, such as adding a "thinning" step or an additional hypothesis. Implemented in Common-Lisp, the system successfully discovered the correct proof terms. In one complex test, the matching process generated 148 unifiers, and the type-checker successfully identified the valid proof for the new theorem.
Key Insights and Limitations
A central insight of this work is that useful analogies in logic are fundamentally syntactic. By focusing on the structure of the proof term rather than the semantic meaning of symbols, the system can capture the "pattern of reasoning." The power of second-order matching allows the system to abstract away specific sub-derivations and move them to new contexts.
However, several challenges remain. Currently, the user must manually define the transformation rules. Furthermore, second-order matching is computationally expensive and can lead to a combinatorial explosion of potential proofs. The authors suggest that integrating types directly into the matching process could drastically reduce the number of useless unifiers and improve efficiency. Future research will focus on the automatic construction of these transformation rules, moving closer to a system that can truly "learn" from its previous successes.
Summary updated