Abstract
This paper introduces a method to transform dense, machine-generated logic proofs into structured, human-readable "Natural Deduction" formats. By treating mathematical equality as a built-in theory and using graph topology to identify logical subgoals, the authors bridge the gap between efficient automated reasoning and intuitive human explanation.
The Explanation Gap in Automated Reasoning
Automated Theorem Provers (ATPs) are incredibly powerful, but they suffer from a significant "explanation gap." Most modern ATPs rely on techniques like resolution and paramodulation. While these are computationally efficient for machines, they produce proofs that are nearly impossible for humans to follow. Instead of a coherent argument, these proofs often manifest as a flat, massive list of technical substitutions and clause manipulations.
The challenge is compounded when equality ($=$) is involved. In standard first-order logic, equality requires specific axioms—such as transitivity, symmetry, and reflexivity—that bloat the proof. While "built-in" equality (paramodulation) simplifies the computer's task, it makes the resulting proof even harder to translate back into Natural Deduction (NK), the hierarchical, step-by-step style of reasoning used by human mathematicians.
Methods: Bridging the Gap
The authors propose a transformation pipeline designed to move from machine-speak to human-speak through four primary stages:
1. Refutation Graphs
Instead of starting with a raw resolution list, the system utilizes a graph-based representation of the proof. In these refutation graphs, nodes represent clauses and links represent logical connections. This format preserves the underlying structure of the argument better than a linear list.
2. Equality Clause Nodes
To handle equality efficiently, the authors introduce specialized nodes that represent paramodulation steps—essentially replacing one term with an equal one. This allows equality to be treated as a "built-in" theory rather than a set of cumbersome axioms, keeping the graph manageable.
3. Topological Structuring
This is the core innovation of the research. The authors analyze the topology (the shape and connectivity) of the refutation graph. By identifying "cuts" or bottlenecks in the graph, the algorithm can automatically decide where to insert a lemma (a mini-proof used as a stepping stone) or where to perform a case analysis.
4. Natural Deduction (NK) Mapping
Finally, the structured graph is mapped to Gerhard Gentzen’s "NK" calculus. This formal system is specifically designed to mirror natural human reasoning, allowing the final output to read like a mathematical argument rather than a computer log.
Key Insights
- Equality as a Specialized Theory: Rather than treating equality as just another predicate, the authors treat it as a specialized theory. This framework is extensible; in the future, other mathematical theories (like groups or fields) could be "built-in" using the same topological transformation logic.
- Geometry Reflects Logic: A major realization of this work is that the logical structure of a proof—its subgoals, lemmata, and branches—is reflected in the physical connectivity of the proof graph. A narrow bridge between two large clusters of nodes is a prime candidate for a lemma.
- Case Analysis for Conditional Equations: Explaining "conditional equations" (e.g., "if $x$ is positive, then $a=b$") is notoriously difficult. The authors demonstrate that these are best handled by forcing a case analysis in the Natural Deduction output, which is far more intuitive for a human reader.
Evaluation and Results
The method was evaluated using Pelletier’s Problems, a classic 1986 benchmark suite of 75 logical puzzles. The authors successfully demonstrated that their system can take a computer-generated proof of a non-trivial equality problem and output a structured narrative.
While the study focuses on qualitative readability rather than raw speed, the results are striking. The transformed proofs read like math textbooks: "Let 1 and 2 be constants... In order to prove P... we consider first the case 3=1... Therefore P3 holds in all cases." This represents a massive improvement over the hundreds of lines of unformatted clauses typically produced by standard resolution provers.
Limitations and Future Work
Despite its success, the method has limitations. It struggles with proofs composed entirely of equality steps, such as complex algebraic identities, where the density of equality nodes can still obscure the overall structure. Additionally, the decision to create a lemma or a case split currently relies on heuristics that may require further fine-tuning. Future work aims to expand this framework to handle other specialized domains like set theory or arithmetic.
Summary updated