Consolution and its Relation with Resolution

Elmar Eder

Introduction

Automated Theorem Proving (ATP) has traditionally been divided between two major paradigms: Resolution and the Connection Method. Resolution, the industry standard, is prized for its ability to derive and reuse lemmata (new clauses). However, this process often destroys the original formula's structure, making it difficult to use structural cues to guide the search. Conversely, the Connection Method maintains structural integrity by checking paths through the original formula but lacks a mechanism for lemma reuse, often leading to "proof explosion."

Elmar Eder's "Consolution" framework proposes a hybrid approach. It aims to retain the structural awareness of connection calculi while incorporating the lemma-reusing power of resolution.

The Consolution Framework

Consolution operates on a "matrix," which is a set of clauses. In this context, a formula is valid if every path through the matrix contains complementary literals (e.g., $P$ and $\neg P$).

The Consolvent Inference Rule

The primary innovation is the consolution inference rule. Unlike resolution, which combines clauses to produce a new clause, consolution takes two sets of partial paths (premises) and produces a "consolvent"—a new set of paths.

A consolution derivation showing the combination of path sets.

To manage the potentially massive search space, consolution employs two simplification techniques:

  1. Elimination: Removing paths that are already proven to be complementary.
  2. Shortening: Replacing a path with a subset of itself. This allows a single partial path to represent multiple potential full paths, significantly compressing the search space.

Resolution as a Special Case

A key theoretical contribution of Eder’s work is the demonstration that Resolution is a restricted form of Consolution. Specifically, if a strategy is applied where every path is shortened to a length of 1, the Consolution calculus becomes functionally identical to Resolution.

A standard resolution derivation for comparison.

By allowing paths of arbitrary lengths, Consolution provides a more general framework. While Resolution is "stuck" at length 1, Consolution can adapt its path lengths to balance between structural guidance and lemma reuse.

Soundness, Completeness, and Simulation

Eder provides rigorous proofs for the soundness and completeness of the consolution calculus. A critical result is Theorem 6.1, which proves that Consolution can simulate any Resolution refutation step-by-step. This confirms that Consolution is at least as powerful as Resolution while offering greater flexibility.

The transition from propositional logic to first-order logic is handled through standard lifting techniques, utilizing unification and most general unifiers (MGUs) to manage variables.

Conclusion and Future Directions

Consolution serves as a formal bridge between two historically separate ATP philosophies. By providing a systematic way to traverse paths while "saving work" via lemmata, it opens new avenues for theorem prover design.

However, challenges remain. While the calculus is well-defined, the optimal strategy—the heuristics for choosing which paths to combine or shorten—is still an open research question. Future work may also involve integrating advanced techniques like Prawitz' matrix reduction to further enhance efficiency.

Summary updated

BibTeX
@inproceedings{eder1991consolution,
  author = {Elmar Eder},
  title = {{Consolution and its Relation with Resolution}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}
Figure