The Management of Heuristic Search in Boolean Experiments with Rue Resolution

Vincent J. DigricoliIJCAI 1985

Introduction

In the field of automated theorem proving, the treatment of equality has long been a significant bottleneck. Traditional provers typically handle equality by incorporating explicit axioms—reflexivity, symmetry, transitivity, and substitution. While logically sound, this approach often leads to a combinatorial explosion, as the prover explores a vast search space of irrelevant deductions. This paper presents a specialized inference method known as RUE (Resolution by Unification and Equality) resolution, which incorporates equality axioms directly into the resolution process. By utilizing a suite of powerful heuristics to prune the search space, the authors demonstrate that complex Boolean algebra theorems, such as the associativity of OR, can be proven in under 30 seconds—a task that frequently challenges human mathematicians.

The RUE Resolution Mechanism

The core of this approach is RUE Resolution and the Negative Reflexive Function (NRF) rule. Unlike standard resolution, which requires a perfect match (unification) to resolve two literals, RUE allows literals to resolve even if they do not match perfectly. Instead of failing, the process generates a "disagreement set" of inequalities. These inequalities represent the differences between the terms that must subsequently be proven false to complete the resolution.

Figure 1: Illustration of disagreement sets in RUE resolution where terms do not perfectly unify.

By embedding equality into the resolution rule itself, the length of the resulting proofs is drastically reduced. For instance, a proof that might require over 40 steps using standard axioms can be condensed into 18 steps using RUE.

Heuristic Search Management

To make RUE resolution practically viable for difficult proofs, the author introduces six management heuristics designed to navigate the "needle in a haystack" problem of logical deduction:

  1. Heuristic Ordering by Degree of Unification: A scoring system (0–100) weights how "close" two terms are to matching. The prover prioritizes paths with higher scores, using partial matching as a compass for the search.
  2. Irreducible Literal Pruning: The system identifies inequalities that can never be resolved—such as attempting to prove two distinct Skolem constants are equal—and aborts those search paths immediately.
  3. Heuristic Substitution Selection: This strategy chooses which variables to unify first to maximize the simplification of the resulting formula.
  4. Complexity Bounds: Hard limits are placed on argument nesting, character length, and the number of variables to prevent the generation of overly complex or "monstrous" formulas.
  5. Redundancy Removal: Identical or subsumed logical clauses are deleted to maintain a lean search space.
  6. Axiom Frequency Bounds: The system limits how many times a specific axiom can be used in a single proof path to prevent infinite loops.

Experimental Evaluation

The primary benchmark for this system was the proof of the associativity of OR in Boolean algebra: $$x \lor (y \lor z) = (x \lor y) \lor z$$

To evaluate the prover's efficiency, the authors compared its performance against human benchmarks. Three university students, described as "mathematically astute," required 3, 6, and 9 hours respectively to prove associativity manually. In contrast, the RUE prover, aided by its heuristic suite, found an 18-step proof in just 22.4 seconds on an IBM 370/3081.

Figure 2: A segment of the automated proof trace for Boolean associativity showing substitutions and rule applications.

The search involved 7,572 unifications. Without the management heuristics, a standard breadth-first search would have faced an expansion factor of approximately 16 at every level, making the proof computationally impossible within a reasonable timeframe.

Conclusion and Future Work

The results achieved with RUE resolution represent a significant advancement in automated theorem proving for Boolean algebra. The "Degree of Unification" score effectively acts as a fitness function, transforming a binary match/no-match process into a guided search. However, some limitations remain. The most powerful heuristics are specific to RUE resolution and are not easily portable to other systems. Furthermore, the prover in these experiments was assisted by intermediate lemmas; proving associativity "from scratch" remains a formidable challenge for future research. Nonetheless, the ability to reduce proof length and search time so dramatically highlights the power of implicit equality handling and robust heuristic management.

Summary updated

BibTeX
@inproceedings{digricoli1985management,
  author = {Vincent J. Digricoli},
  title = {{The Management of Heuristic Search in Boolean Experiments with Rue Resolution}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1985},
}
Figure