The Automatic Acquisition of Proof Methods

Kurt AmmonAAAI 1988

Introduction

Automated Theorem Proving (ATP) typically involves searching through a massive space of possible logical deductions. While machines are proficient at exhaustive search, they often lack the high-level strategies or "intuition" that human mathematicians use to navigate complex theories. The SHUNYATA program addresses this gap by automatically acquiring general proof strategies from just a few examples, moving away from hard-coded heuristics toward a system that learns how to prove new theorems by "studying" existing ones.

Methodology: The SHUNYATA Program

SHUNYATA uses a multi-stage iterative procedure to acquire proof methods, transforming specific logical steps into general operators:

  1. Elementary Analysis: The system examines a proof step-by-step. It uses a base of "metatheorems" (knowledge about functions, domains, and ranges) to identify constraints that characterize why a specific step works.
  2. Simplification: It temporarily removes constraints to see if the proof step can still be generated. If it can, the constraint is deemed "unessential" and discarded, leading to a more general operator.
  3. Unification and Division: The system attempts to merge new operators with existing ones (unification). If they are too different to merge, it creates a new "division" in the proof method.
  4. Genetic Construction: The process is "genetic" in that it builds increasingly powerful partial methods from scratch. Each successful method forms the foundation for the next, more complex one.
An example of a proof trace analyzed by SHUNYATA, showing the sequence of equations, the axioms applied, and the variable substitutions used.

Knowledge Base and Axioms

In the context of symbolic AI, the system relies on a predefined set of axioms and elementary functions. These form the building blocks for all deductions. For example, in algebraic theories, the system utilizes a standard set of identities to perform its analysis.

The set of 17 axioms used by the system to perform logical deductions and analyze proof steps in the provided examples.

Key Results and Insights

SHUNYATA was tested on several benchmarks, most notably SAM’s Lemma in Modular Lattice Theory. While a brute-force approach generated 86,000 proof steps, SHUNYATA’s refined method reduced this to just 111 steps, with the core proof consisting of only 8 steps. This generation took approximately 75 minutes on 1988-era hardware.

Key insights from the project include:

  • Learning from a Single Proof: Unlike modern deep learning, SHUNYATA can extract a general method from a single, well-chosen example.
  • The Power of Redundancy: Simplification often revealed that many constraints thought to be essential were actually redundant, leading to more robust methods.
  • Readability: By using acquired methods, SHUNYATA produces proofs that mirror human-like steps, making them much easier for mathematicians to verify compared to traditional ATP outputs.

Limitations and Future Work

While the final proofs are concise, the acquisition phase remains computationally expensive. Additionally, the system is dependent on its initial knowledge base; it cannot "invent" new elementary functions if they are missing. Future directions include applying these techniques to automatically analyze mathematics textbooks, potentially allowing a machine to learn an entire field of study by reading standard educational materials.

Summary updated

BibTeX
@inproceedings{ammon1988automatic,
  author = {Kurt Ammon},
  title = {{The Automatic Acquisition of Proof Methods}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure