Complete Inference Rules for the Cancellation Laws

Jieh Hsiang, Michaël Rusinowitch, Kô Sakai

Abstract

This paper introduces a set of complete inference rules designed to handle algebraic cancellation laws directly within automated theorem provers. By embedding these laws into the logic engine, the authors eliminate the need for inefficient axioms, significantly reducing redundant computations and improving proof search efficiency in mathematical domains like ring and group theory.

Introduction

In automated theorem proving, managing equality and algebraic properties such as the cancellation law (e.g., if $ac = bc$, then $a = b$) is a major challenge. Standard provers typically treat these laws as standard axioms, which often leads to an explosion of redundant intermediate steps (resolvents), severely hindering the search for a proof. Previous attempts to address this were often incomplete or heuristic-based. This work provides a theoretically complete set of inference rules that can entirely replace the cancellation axiom, streamlining the proving process.

Proposed Inference Rules

The authors propose specialized inference rules for three variations of cancellation: basic right cancellation, cancellation with identity, and cancellation except for the null element. The core technical innovation is the integration of these rules with Ground-Linear Simplification Orderings, allowing the prover to focus only on the most complex parts of a statement.

Basic Right Cancellation

The rule C1 handles the standard case where terms are cancelled from the right. This rule, along with its multi-premise variant C2, allows for more direct logical inferences without the overhead of the original axiom.

Inference rules C1 and C2 for right cancellation.

Cancellation with Identity

In structures with an identity element $e$ (e.g., $x + 0 = x$), the rule CI1 handles cases where $f(y, x) = x$ implies $y = e$. This specialized rule is crucial for efficiently handling algebraic structures like groups.

Inference rule CI1 for cancellation with identity.

Evaluation and Results

The proposed rules were evaluated using abstract algebraic structures and benchmark problems from ring theory. A prototype implementation demonstrated significant efficiency gains. For instance, in generating a "canonical set" for group theory, the new rules required only 14 critical pairs, compared to 17 using standard methods like the Knuth-Bendix algorithm. Furthermore, the technique enables the elimination of functional reflexive axioms, which frequently cause infinite loops in reasoning systems.

Key Insights and Conclusion

The most significant insight is that specialized rules can completely eliminate the need for the cancellation axiom in the input set. By "hard-coding" these mathematical properties into the logic engine and using simplification orderings to prune the search tree, the authors provide a leaner and faster approach to automated reasoning. While this work focuses on right-cancellation, future research will explore the complexities of simultaneous left and right cancellation and the integration of these rules with other techniques like negative paramodulation.

Summary updated

BibTeX
@inproceedings{hsiang1987complete,
  author = {Jieh Hsiang and Michaël Rusinowitch and Kô Sakai},
  title = {{Complete Inference Rules for the Cancellation Laws}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure