Structuring Computer Generated Proofs

Christoph Lingenfelder

Abstract

Automated Deduction Systems (ADS) excel at verifying complex mathematical theorems but often produce output that is incomprehensible to human mathematicians. This paper presents a methodology for transforming dense, flat machine-generated proofs into structured, hierarchical natural deduction formats. By leveraging the topological properties of proof graphs, the system identifies logical subgoals and reusable lemmata, bridging the gap between raw machine verification and human-readable mathematical communication.

Introduction

The primary barrier to the widespread adoption of automated provers is their "PR problem": machine-generated proofs are typically massive sequences of logical steps lacking the "big ideas" and hierarchical structure that humans use to navigate a proof. While previous research could translate these into natural deduction, the results were often longer and more confusing than the originals. The challenge lies in structuring the logic so that essential ideas are highlighted and trivial steps are sidelined.

Methodology: Topology as Logic

The core innovation of this work is a multi-step pipeline that transforms an abstract refutation graph into a structured natural deduction proof.

Topological Analysis

The algorithm uses the "shape" of the proof graph to infer logical structure. It searches for separating links—edges that, if removed, split the graph into distinct components representing natural subgoals. Furthermore, it identifies isomorphic subgraphs, which are identical structures appearing multiple times. Instead of repeating the logic, the system extracts these as single, citable lemmata.

Graph Δ illustrating the topological structure of a proof, where nodes represent logical literals and links represent dependencies.

Generalized Natural Deduction Proofs (GNDPs)

The paper introduces GNDPs as an intermediate state. These allow for "external lines"—steps known to be true via the refutation graph but not yet fully expanded into the formal natural deduction calculus. This allows the system to maintain a high-level view before final linearization.

Linearization and Simplification

Once the hierarchy is established, the proof lines are arranged in a dependency graph to be "flattened" into a readable sequence. To avoid information overload, the author applies heuristics to identify "trivial" steps. Drawing on Martin Davis’s definition of "obvious" inferences, the system prunes steps that do not significantly contribute to a human reader's understanding.

Key Results and Insights

The primary result is the shift from viewing a proof as a mere list of facts to viewing it as a structured argument. The system can automatically identify subgoals and extract lemmata, producing a proof that follows a human-like style, moving from assumptions to intermediate conclusions and finally to the theorem.

A structured natural deduction proof generated from the graph, showing numbered lines, hypotheses (Hyp), and logical derivations.

Limitations and Future Work

While successful, the current simplification process is heuristic. Future research aims to develop sophisticated "user models" to tailor the level of detail to the reader's expertise (e.g., providing more detail for a student than for a professor). Additionally, the final leap from structured formal logic to natural language prose (English or German) remains a major research hurdle.

Finally, finding isomorphic subgraphs in very large proofs is computationally expensive, presenting a classic graph theory challenge that may limit the speed of transformation for extremely complex theorems.

Summary updated

BibTeX
@inproceedings{lingenfelder1989structuring,
  author = {Christoph Lingenfelder},
  title = {{Structuring Computer Generated Proofs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}
Figure