A Technique for Establishing Completeness Results in Theorem Proving with Equality

Gerald E. PetersonAAAI 1980

Abstract

In automated theorem proving (ATP), the inclusion of equality has historically presented a significant challenge, often forcing a trade-off between theoretical completeness and computational efficiency. This paper introduces a formal proof technique utilizing generalized semantic trees to demonstrate the completeness of theorem-proving systems that incorporate equality. By bridging the gap between broad resolution/paramodulation methods and the efficient but narrow Knuth-Bendix procedure, the author provides a framework for developing theorem provers that are both mathematically robust and practically viable.

Introduction

Handling the equality relation ($=$) in first-order logic is a cornerstone of automated reasoning, yet it is notoriously difficult to implement efficiently. By the late 1960s, the development of paramodulation—a rule allowing for the substitution of equal terms—provided a path to completeness. When combined with resolution, paramodulation is guaranteed to find a proof if one exists. However, this completeness came at a high cost: the search space often exploded into a "mountain of irrelevant clauses," rendering the systems impractical for complex problems.

Conversely, the Knuth-Bendix procedure (1970) offered high efficiency through simplification and subsumption (the removal of redundant information). However, Knuth-Bendix was limited to "equality units" and could not handle the complex structures required for full first-order logic, such as field theory or non-equational axioms. This paper addresses the fundamental challenge: proving that a system remains complete even when efficiency-boosting techniques like simplification and subsumption are integrated.

Methodology: Generalized Semantic Trees

The author’s primary contribution is a technique based on Generalized Semantic Trees, which provides a structured way to analyze the search space of a theorem prover.

  1. E-Interpretations: Traditional semantic trees represent possible interpretations of logical statements. To accommodate equality, the author modifies these into "E-interpretations." This involves defining a partial order on atoms based on the concept of reduction, where an equation $s=t$ is treated as a directional rule to transform a complex term $s$ into a simpler term $t$.
  2. Failure Node Taxonomy: The technique classifies points where a proof attempt fails into two distinct categories:
  3. R (Resolution) failure nodes: Standard logical contradictions.
  4. P (Paramodulation) failure nodes: Contradictions arising specifically from equality substitutions.
  5. Tree Shrinking: The core of the completeness proof demonstrates that by applying specific inference rules (resolution or paramodulation), the system can always generate a new clause that makes the semantic tree "smaller." Through mathematical induction, the author shows that the tree must eventually shrink to a single node, representing the discovery of the empty clause—the formal proof of the theorem.

Key Theoretical Insights

Directionality and Reduction

A central insight of the paper is the application of term-rewriting logic to full first-order logic. By ordering terms so that substitutions always move from "complex" to "simple," the author adapts the efficiency of the Knuth-Bendix procedure to a much broader logical context.

The Lifting Lemma

The paper highlights a technical necessity in the "lifting" process—moving from specific ground instances to general logical variables. The author demonstrates that lifting for paramodulation is only reliable if the substitutions used are "irreducible." This constraint is vital for preventing the theorem prover from entering infinite loops during the search process.

Elimination of Reflexive Axioms

Previously, it was believed that a set of "functionally reflexive axioms" was necessary to ensure completeness in equality proofs. Peterson proves that these tedious axioms are not required, significantly simplifying the requirements for building an automated prover.

Results and Implications

The paper defines a comprehensive system consisting of resolution, paramodulation, factoring, equality reversal, simplification, and subsumption removal. The primary result is a formal proof that this specific combination of rules is complete for first-order logic with equality.

Furthermore, the author establishes specific restrictions that maintain this completeness while maximizing speed:

  • Prioritization: Simplification and subsumption are given priority to prune the search space early.
  • Restricted Paramodulation: The system prohibits paramodulation into variables, a move that prevents the massive, useless branching that plagued earlier ATP attempts.

Conclusion

While the paper is primarily theoretical and lacks empirical benchmarking—a common trait for the era—it provides the mathematical foundation necessary for the next generation of theorem provers. By formalizing how simplification and subsumption interact with completeness, the author moved ATP away from exhaustive, inefficient searches and toward the more directed, reduction-based strategies that characterize modern automated reasoning tools. The work identifies a path toward systems that are not only theoretically guaranteed to find proofs but are also efficient enough to handle real-world mathematical problems.

Summary updated

BibTeX
@inproceedings{peterson1980technique,
  author = {Gerald E. Peterson},
  title = {{A Technique for Establishing Completeness Results in Theorem Proving with Equality}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure