Consequence-Finding Based on Ordered Linear Resolution

Katsumi InoueIJCAI 1991 · OpenReview

Abstract

Since linear resolution with clause ordering is incomplete for consequence-finding, it has been used mainly for proof-finding. In this paper, we re-evaluate consequence-finding. Firstly, consequence-finding is generalized to the problem in which only interesting clauses having a certain property (called characteristic clauses) should be found. Then, we show how adding a skip rule to ordered linear resolution makes it complete for consequence-finding in this general sense. Compared with set-of-support resolution, the proposed method generates fewer clauses to find such a subset of consequences. In the propositional case, this is an elegant tool for computing the prime implicants/implicates. The importance of the results lies in their applicability to a wide class of AI problems including procedures for nonmonotonic and abductive reasoning and truth maintenance systems.

Introduction

In the field of automated deduction, most systems are optimized for proof-finding (refutation). These systems are "refutation complete," meaning they are guaranteed to find a contradiction (the empty clause) if a set of formulas is inconsistent. However, they are often "deductively incomplete" for consequence-finding: they are not designed to efficiently identify all logical implications of a satisfiable set of facts.

Historically, researchers found that high-performance resolution strategies, such as those utilizing clause ordering, were incomplete for finding consequences. This led to a decline in consequence-finding research during the 1970s. This paper argues that this shift was premature. Modern AI tasks—such as abduction, diagnosis, and belief revision in Truth Maintenance Systems (ATMS)—require finding specific "interesting" consequences rather than just proving contradictions. The challenge lies in performing this search efficiently without generating a massive volume of trivial or redundant formulas.

SOL-Resolution Framework

The author introduces SOL-resolution (Skipping Ordered Linear resolution), a framework that extends standard ordered linear resolution to make it complete for consequence-finding. The method relies on two primary concepts:

  1. Characteristic Clauses: Instead of searching for all possible consequences, the search is restricted to a subset defined by a production field. This field specifies "interesting" literals (e.g., only positive literals or literals involving specific predicates) that the user wishes to find in the resulting clauses.
  2. The Skip Rule: This is the core innovation. In standard resolution, the goal is to eliminate literals. In SOL-resolution, if a literal belongs to the production field, the algorithm can skip it. This effectively moves the literal into the resulting clause rather than resolving it away.
A step-by-step derivation in SOL-resolution illustrating the skip rule and truncation.

As shown in the derivation above, SOL-resolution uses a pair-based notation $\langle C, D \rangle$, where $C$ represents the skipped literals and $D$ represents the literals currently being resolved. The "skip" operation allows the system to preserve relevant information while continuing the linear deduction process.

Key Theoretical Results

The paper provides a formal mathematical foundation for SOL-resolution, highlighted by several key insights:

  • Soundness and Completeness: Theorem 3.2 proves that SOL-resolution is both sound (it only generates true consequences) and complete (it finds a clause that represents every logical consequence within the specified production field).
  • Relevancy-Directed Search: By using a newly added clause as the "top clause" of a linear deduction, the system naturally focuses on consequences relevant to that new information. This is significantly more efficient than older "set-of-support" methods that often explored irrelevant branches of the search space.
  • Unification of AI Tasks: The paper demonstrates that various AI problems—including prime implicant generation, abduction, and circumscription—can be unified as specific instances of finding characteristic clauses via SOL-resolution.

Discussion and Limitations

While SOL-resolution restores completeness and improves efficiency, consequence-finding remains computationally expensive (NP-hard or worse). The paper focuses on the theoretical proof of the method's properties rather than empirical benchmarks. Furthermore, while the author suggests that "best-first search" heuristics could optimize the choice between skipping and resolving, the development of specific heuristic functions remains a subject for future research. Despite these challenges, SOL-resolution provides an elegant and powerful tool for the next generation of AI reasoning systems.

Summary updated

Abstract

Since linear resolution with clause ordering is incomplete for consequence-finding, it has been used mainly for proof-finding. In this paper, we re-evaluate consequence-finding. Firstly, consequence-finding is generalized to the problem in which only interesting clauses having a certain property (called characteristic clauses) should be found. Then, we show how adding a skip rule to ordered linear resolution makes it complete for consequence-finding in this general sense. Compared with set-of-support resolution, the proposed method generates fewer clauses to find such a subset of consequences. In the propositional case, this is an elegant tool for computing the prime implicants/implicates. The importance of the results lies in their applicability to a wide class of AI problems including procedures for nonmonotonic and abductive reasoning and truth maintenance systems.
BibTeX
@inproceedings{inoue1991consequence,
  author = {Katsumi Inoue},
  title = {{Consequence-Finding Based on Ordered Linear Resolution}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
  url = {https://openreview.net/forum?id=H1-9rEGObH},
}
Figure