Path Dissolution: A Strongly Complete Rule of Inference

Neil V. Murray, Erik RosenthalAAAI 1987

Abstract

This paper introduces path dissolution, a novel inference rule for automated theorem proving that operates on formulas in Negation Normal Form (NNF). Unlike traditional resolution-based methods, path dissolution is "strongly complete," guaranteeing that any sequence of inference steps will eventually lead to a conclusion. By representing formulas as semantic graphs and systematically eliminating contradictory paths, the method ensures termination and facilitates model finding.

Introduction

In the 1980s, automated theorem proving was dominated by resolution, which requires formulas to be converted into Conjunctive Normal Form (CNF). This conversion often leads to a combinatorial explosion in formula size and obscures the structural intuition of the original logic. Murray and Rosenthal (1987) sought a more flexible approach that could operate on Negation Normal Form (NNF) while providing a mathematical guarantee of convergence—a property known as "strong completeness."

The Problem with Resolution

Resolution-based methods are often hindered by the requirement for CNF. Furthermore, while "connection-graph resolution" was once thought to be strongly complete, counterexamples proved otherwise. A strongly complete rule ensures that if a formula is contradictory, any sequence of inference steps will eventually prove it, preventing the system from getting "stuck" in infinite loops of redundant inferences.

Methods: Semantic Graphs and Dissolution

The authors represent logical formulas as Semantic Graphs. In these structures, nodes represent literals, while horizontal and vertical connections (c-arcs and d-arcs) represent conjunctions and disjunctions, respectively.

Basic semantic graph transformations illustrating the representation of logical dependencies.

The core mechanism is the c-path: a set of nodes representing a conjunction of literals that, if all true, would satisfy the formula. The Dissolution Step involves:

  1. Identifying a Link: Finding a pair of complementary literals (e.g., $A$ and $\neg A$) on the same c-path.
  2. Calculating the Dissolvent: Creating a new graph that excludes all c-paths passing through that link. Since a path containing a contradiction cannot be satisfied, its removal preserves the formula's meaning.
  3. Path Reduction: Each step strictly reduces the total number of c-paths, guaranteeing termination.

Key Insights

  • Guaranteed Termination: By focusing on path reduction rather than clause generation, dissolution avoids the infinite search spaces common in resolution.
  • Model Characterization: Applying dissolution until no links remain results in a "linkless" graph. The remaining paths explicitly characterize all possible interpretations that satisfy the formula, making it a powerful tool for model finding.
  • Beyond CNF: Operating on NNF allows the rule to maintain the natural structure of logical formulas, avoiding the overhead of CNF conversion.

Key Results

The authors provide a formal proof of convergence for ground formulas. They demonstrate the algorithm's efficacy using complex examples, such as a 12-path unsatisfiable graph.

A complex 12-path unsatisfiable graph undergoing dissolution. Labeled links (e.g., '2') indicate the sequence of reduction steps.

By systematically dissolving labeled links, the graph eventually collapses into an empty state, proving contradiction. For satisfiable formulas, the process reduces the graph to a form that lists all satisfying truth assignments.

Limitations and Future Work

The primary limitation acknowledged is the application to First-Order Logic. Unlike resolution, which "lifts" to variables very cleanly via Robinson’s Unification Theorem, dissolution requires more complex bookkeeping. The authors describe their first-order techniques as "primitive" and suggest that more research is needed to make the rule as efficient as resolution for complex predicate calculus.

Additionally, while the rule is strongly complete, the paper does not provide a detailed analysis of the computational complexity or the search space involved in choosing which links to dissolve first to reach a conclusion most efficiently.

Summary updated

BibTeX
@inproceedings{murray1987path,
  author = {Neil V. Murray and Erik Rosenthal},
  title = {{Path Dissolution: A Strongly Complete Rule of Inference}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure