Theorem Proving by Covering Expressions

Lawrence J. Henschen, W. M. EvangelistIJCAI 1977

Abstract

In the early 1970s, automated theorem proving faced a dichotomy between the local, inference-heavy approach of resolution and the global, but computationally explosive, Herbrand methods. This paper introduces "covering expressions"—a compact notation using three symbols (+, -, 0) to represent the set of clauses not subsumed by a given set. By shifting the focus from deducing contradictions to identifying "missing pieces" in the search space, the authors provide a more directed heuristic for proof discovery. We demonstrate the formal properties of these expressions and showcase an interactive system that utilizes them to suggest promising clause replicas.

Introduction: The Search for Global Context

Automated theorem proving in the 1970s was primarily divided into two schools. Resolution-based systems, while popular, often suffered from "low penetrance," generating a vast number of irrelevant inferences for every useful step toward a proof. Because resolution is a local operation, it lacks a global view of the search space. Conversely, Herbrand methods (such as Gilmore’s technique) provided a global perspective but were plagued by "formula explosion," often generating astronomically large Disjunctive Normal Forms (DNFs) before any contradiction testing could begin.

Henschen and Evangelist proposed a middle ground. Their goal was to maintain the global context of Herbrand methods while avoiding the memory overhead of DNFs. They achieved this by introducing a method that uses the results of failed unsatisfiability tests to intelligently guide the search for new clause replicas.

Methodology: The Logic of Covering Expressions

The Ground Case and Product Operation

The core innovation is the Covering Expression. For a set of ground clauses, the search space is represented using terms consisting of three symbols:

  • + or -: Represents a determined literal (positive or negative).
  • 0: Represents a "don't care" state, encompassing both possibilities ($\pm$).

Crucially, a "cover" for a clause $C$ represents the set of all possible clauses that are not subsumed by $C$. To determine if a set of clauses $S$ is unsatisfiable, the algorithm performs a "product" operation—essentially an intersection of these "uncovered" spaces.

Table showing the relationship between clauses, their individual covers, and the resulting cumulative cover.

If the product of all covers becomes empty, the set is proven to be unsatisfiable. If the product is non-empty, the remaining terms provide a precise map of what is missing to complete the proof. This compact notation is significantly more memory-efficient than the massive logical expressions used in earlier Herbrand-style methods.

The General Case: Iterative Refinement

In the general case involving variables, the process becomes iterative. The system calculates a cover for a tentative set of clause replicas. If this set does not yield unsatisfiability, the resulting cover is compared against the original input clauses. This comparison identifies "promising" new replicas or literal matings that could potentially empty the cover, effectively turning the unsatisfiability test into a heuristic for the next generation step.

Key Results: Interactive Proof Discovery

The authors demonstrated their framework through an interactive program. A key feature of this system is the "SGST" (suggest) command. When invoked, the system analyzes the current cover to suggest literals that have "maximal interaction" with the remaining uncovered space.

A trace of an interactive session showing the SGST command and the system's suggestions for adding clauses to the Set of Support (SOS).

As shown in the trace, the system identifies specific literals (like Pcab) and suggests adding them to the set to drive the proof toward completion. This "interspersed" approach—where generation and testing are tightly coupled—allows the system to act as a guided search engine rather than a blind inference generator.

Conclusion and Future Directions

While the paper presents a "work in progress," it establishes a rigorous formal foundation for covering expressions. The primary advantage of this method is its ability to track the "missing pieces" of a proof rather than just the accumulated inferences.

Future work identified by the authors includes:

  1. Heuristic Refinement: Developing more sophisticated criteria for identifying "promising" replicas.
  2. Equality Handling: Integrating techniques like paramodulation to handle equality natively.
  3. Semantic Integration: Allowing users to provide domain-specific knowledge to prune useless suggestions.
  4. Program Verification: Applying the method to find loop invariants, where the "missing piece" logic is particularly applicable.

Summary updated

BibTeX
@inproceedings{henschen1977theorem,
  author = {Lawrence J. Henschen and W. M. Evangelist},
  title = {{Theorem Proving by Covering Expressions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1977},
}
Figure