TL;DR
This paper introduces the first experimental results for RUE (Resolution by Unification and Equality), a method that bakes the axioms of equality directly into the inference rules of automated theorem provers. By using "disagreement sets" to handle mismatched terms, RUE significantly reduces the search space, outperforming traditional methods by orders of magnitude in the number of unifications required for Boolean algebra proofs.
What Problem Does This Paper Address?
In the world of automated deduction, handling the concept of equality (e.g., if $a=b$ and $b=c$, then $a=c$) is a notorious bottleneck. Traditional resolution-based provers treat equality axioms—like reflexivity, symmetry, and transitivity—as just another set of clauses in the input.
This approach often leads to a "combinatorial explosion," where the prover spends vast amounts of time deriving trivial variations of existing facts. The authors address this by asking: What if the logic engine itself understood equality, rather than just reading it from a list of rules?
Methods
The author proposes a system called RUE resolution, which replaces standard binary resolution. Its core innovation lies in two specific areas:
- Implicit Equality Axioms: Instead of including explicit axioms for equality in the problem description, RUE incorporates them into two new inference rules: RUE and NRF (Negative Reflection).
- Disagreement Sets: When the prover tries to unify two terms that don't match (e.g., $f(a, g(b))$ and $f(a', g(b'))$), it doesn't simply fail. Instead, it generates a "disagreement set"—a list of the specific sub-terms that differ (in this case, $\{a, a'\}$ and $\{b, b'\}$). The prover then attempts to prove that these differences are equal to zero (or null) to bridge the gap.
This allows the prover to decompose complex structural differences into simpler sub-problems, effectively performing a "top-down" analysis of why two terms don't match.
Datasets
The paper evaluates the RUE prover using a set of benchmark problems in Boolean Algebra, originally proposed by McCharen, Overbeek, and Wos (MOW).
- Axioms: 8 standard Boolean axioms (identity, distributive laws, etc.).
- Theorems: 13 theorems (T1 through T13) of increasing complexity, ranging from simple identity proofs ($0=1$ is false) to more difficult deductions like De Morgan’s Laws.
The performance of the RUE prover (written in PL/I on a CDC 6600) is compared directly against the MOW prover (written in Assembly on an IBM 370/195).
Key Insights and Ideas
- Structural Decomposition: The "aha moment" of RUE is treating a mismatch not as a failure, but as a roadmap. By identifying exactly where two functional terms diverge, the prover can focus its search on proving those specific sub-terms are equal.
- Unification as the True Metric: Because the two systems compared were running on different hardware and programmed in different languages, the author argues that the total number of unifications is a more honest measure of algorithmic efficiency than raw CPU time.
- Proof Brevity: RUE proofs are significantly shorter. Because the equality logic is "under the hood," the resulting proof steps are more direct and human-readable compared to the verbose chains of transitivity found in traditional proofs.
Key Results
The results for simpler theorems (T1-T7) were dramatic:
- Search Space Reduction: For Theorem 1 ($0=1$), RUE required only 77 unifications, while the MOW system required 26,702.
- Consistency: Across the first seven theorems, RUE consistently used a fraction of the unifications required by the MOW prover.
- Proof Length: RUE proofs were roughly half the length of MOW proofs (when MOW's explicit equality steps are accounted for).
Limitations and Future Work
Despite the early successes, the paper hits a wall with more complex problems:
- The Associativity Wall: RUE struggled with Theorem 8 (associativity) and beyond. The author notes that these results were "In Progress" because the system required better heuristic pruning—the ability to intelligently discard unpromising search paths.
- Hardware/Language Gap: The author acknowledges that their PL/I implementation on a slower CDC 6600 was at a disadvantage compared to MOW’s highly optimized Assembly code on a faster IBM machine, making time-based comparisons difficult.
- Hybrid Potential: The paper suggests that RUE shouldn't necessarily stand alone; future work could involve combining it with other techniques like demodulation (rewriting terms to a simpler form) or paramodulation to handle the most complex proofs.
Summary updated