Neil V. Murray and Erik Rosenthal present Path Resolution, a hybrid inference rule for automated theorem proving that bridges the gap between traditional resolution and Prawitz analysis. By representing logical formulas as "semantic graphs," the authors provide a framework that operates on formulas in Negation Normal Form (NNF), avoiding the computational overhead and literal duplication often associated with converting formulas to Conjunctive Normal Form (CNF).
The Problem: CNF and Search Space Explosion
In automated deduction, researchers have historically faced a trade-off between Prawitz analysis and resolution. Prawitz analysis searches for contradictions without inferring new formulas, avoiding redundant data but failing to store intermediate progress. Resolution stores progress by generating resolvents but frequently leads to an exponential explosion of the search space.
Furthermore, most systems rely on Conjunctive Normal Form (CNF). Converting complex formulas into CNF can cause a massive increase in the number of literals, making the subsequent search for a proof significantly harder. Murray and Rosenthal aim to retain the strengths of both methods while working on the more flexible Negation Normal Form (NNF).
Semantic Graphs and NNF
The authors build their system on the foundation of semantic graphs. Instead of sets of clauses, formulas are represented as graphs where nodes (literals) are connected by c-arcs (conjunctions) and d-arcs (disjunctions). This allows the structure of the original formula to be preserved both visually and computationally.
By working directly on NNF, the authors avoid the "literal explosion" inherent in normalization. The meaning of a formula is defined through its paths: a formula is satisfiable if there is a "c-path" (a path of conjunctions) where all literals can be true simultaneously. A contradiction exists if every c-path contains a complementary pair of literals, known as a link.
The Path Resolution Inference Rule
Path resolution is the core inference rule of this framework. It identifies "chains"—sets of complementary literal pairs (links) within the graph. If a subgraph is "spanned" by a chain (meaning every path through it contains a link), it represents a contradiction. Path resolution allows the prover to analyze a subgraph and generate a "path resolvent" relative to the rest of the graph.
This rule acts as a "super-rule," generalizing hyper-resolution, clash-resolution, and NC-resolution into a single framework. It effectively allows Prawitz-style analysis to be performed incrementally, saving partial contradictions as the search progresses.
Link Deletion and Efficiency
The paper also introduces Link Deletion strategies. Links represent potential resolution steps; deleting a link after it has been "activated" (used in an inference) is a powerful way to prune the search space. The authors formally prove that path resolution is sound and identify specific classes of resolution chains where links can be deleted without losing the "spanning property" required to find a proof.
In a standard benchmark case study from Chang and Lee (1973), path resolution required only 2 steps to reach a contradiction, whereas a standard binary resolution refutation for the same problem required 8 steps.
Conclusion
While path resolution reduces the number of inference steps and avoids CNF overhead, the authors acknowledge that finding the appropriate resolution chain within a complex graph remains a difficult search problem. Future work is needed to evaluate the implementation's performance on massive, real-world logic problems compared to modern SAT/SMT solvers and to provide full completeness proofs for all deletion strategies.
Summary updated