A Nonclausal Connection-Graph Resolution Theorem-Proving Program

Mark E. StickelAAAI 1982

Mark E. Stickel
Presented at AAAI-82

Abstract

In the early 1980s, automated theorem proving was largely dominated by clausal resolution, a method requiring the conversion of logical statements into a rigid Clause Normal Form (CNF). This paper introduces a novel theorem-proving program that operates on nonclausal formulas using a connection-graph data structure. By reasoning directly on general logical formulas, the system preserves the pragmatic intent of the original statements, reduces redundancy in the search space, and provides a more readable framework for natural language understanding systems.

Introduction

Traditional automated reasoning systems typically rely on converting logical expressions into sets of clauses (disjunctions of literals). While mathematically elegant, this conversion often obscures the underlying structure of the problem and leads to a combinatorial explosion of redundant clauses. Mark E. Stickel’s 1982 paper proposes a departure from this constraint, presenting a system developed for the MICROKLAUS natural language system that utilizes nonclausal resolution and connection graphs to achieve greater efficiency and human-readability.

The Limitations of Clausal Form

The move toward nonclausal logic was motivated by three primary deficiencies in standard clausal resolution:

  1. Loss of Pragmatic Intent: Converting a conditional statement like $P \implies Q$ into the clause $\neg P \lor Q$ strips away the information regarding how the rule should be applied—whether as a forward-chaining rule (if $P$, then $Q$) or a backward-chaining rule (to prove $Q$, try to prove $P$).
  2. Search Space Redundancy: The process of clausification often generates a massive number of clauses to represent a single complex formula, significantly expanding the search space the prover must navigate.
  3. Human Readability: Clause form is notoriously difficult for humans to interpret. For systems intended to interact with natural language, maintaining a logical form that closely mirrors the original input is essential for debugging and user interaction.

Technical Innovations

Nonclausal Resolution

Stickel’s system operates on general quantifier-free formulas rather than clauses. The core mechanism is nonclausal resolution, which identifies an atom occurring with opposite polarity in two formulas. Polarity is determined by the number of negations surrounding an atom: an even number results in positive polarity, while an odd number results in negative polarity.

When two formulas are resolved, the system replaces the complementary atoms with "True" or "False" and simplifies the resulting expression using standard truth-functional identities (e.g., $A \land \text{True} \to A$). This allows the prover to handle complex, nested logical structures without flattening them into CNF.

Connection Graphs

To manage the search for proofs, the program employs a connection graph where:

  • Nodes represent the logical formulas.
  • Links (edges) connect atoms of opposite polarity, representing potential resolution steps.

This structure enables two critical features:

  • Link Inheritance: When a new formula (a resolvent) is generated, it automatically inherits links from its parent formulas. This maintains a continuous map of all possible future inferences.
  • Link Scheduling: Instead of an exhaustive search, the system uses a heuristic-driven scheduler to score and prioritize links. This allows the program to focus on the most promising logical paths first.

Key Insights: Logic as a Network

One of the paper's most compelling insights is the treatment of the connection graph as a form of semantic network. Stickel demonstrates that for certain types of reasoning, such as taxonomic queries (e.g., "Is an elephant an animal?"), the system can find answers simply by traversing the links between assertions in the graph. This "graph searching as planning" approach is computationally cheaper than performing full resolution steps, as it allows the system to verify the existence of a proof path before generating new formulas.

Furthermore, the system introduces procedural control through special connectives ($\to$ and $\leftarrow$), allowing users to specify whether certain implications should be used for forward or backward chaining, thus guiding the deductive process more effectively.

Implementation and Results

The theorem prover was implemented in approximately 4000 lines of INTERLISP. It served as the primary deduction engine for the MICROKLAUS system, processing logical forms generated from English queries by the DIALOGIC system.

Key results from the implementation include:

  • Efficiency: The connection-graph approach successfully restricted the resolution process, avoiding many of the redundant operations that plague standard clausal provers.
  • Integration: The system proved capable of handling real-world natural language tasks of the era, particularly in performing rapid taxonomic inferences within class hierarchies.

Limitations and Future Directions

Despite its successes, Stickel identified several areas for further development. Proving the "completeness" of connection-graph procedures—ensuring the system can find any proof that exists—remains a significant theoretical challenge in nonclausal logic. Additionally, the computational overhead of maintaining inherited links in the graph is substantial. Future work suggested by the author included refining the link scheduler's evaluation functions and fully implementing "factorization" (the merging of identical formula components) to ensure no potential proofs are missed.

Summary updated

BibTeX
@inproceedings{stickel1982nonclausal,
  author = {Mark E. Stickel},
  title = {{A Nonclausal Connection-Graph Resolution Theorem-Proving Program}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1982},
}
Figure