An Efficient Relevance Criterion for Mechanical Theorem Proving

David A. PlaistedAAAI 1980

Abstract

Automated theorem proving systems often struggle with large knowledge bases, where the search space for proofs expands exponentially with the inclusion of irrelevant facts. This paper, originally presented at AAAI-80, introduces a formal relevance criterion to address this bottleneck. By modeling logical clauses as nodes in a graph and defining relevance through distance-based metrics, the author provides a method to prune knowledge bases in linear time. Crucially, the approach preserves proof completeness, ensuring that a solution remains reachable within the reduced set of facts.

Introduction

In the early development of artificial intelligence, reasoning systems were frequently overwhelmed by "large knowledge bases" containing thousands of facts. While these systems performed adequately on toy problems, they often failed on complex tasks because they could not distinguish between relevant and irrelevant information. For instance, a system attempting to prove a calculus theorem might waste significant resources exploring facts about geography. The challenge was to define a relevance function that is both computationally efficient to calculate and mathematically complete—meaning it does not discard the facts necessary for a proof.

Methodology: Logic as a Graph Problem

Plaisted’s approach transforms the logical problem of deduction into a graph-theoretical problem. The primary structure used is the connection graph, where nodes represent logical clauses. An edge exists between two nodes if their literals can be unified for resolution.

Figure 1: A set of logical clauses $S$ used to demonstrate the relevance algorithm.

Relevance is then defined by the "distance" in this graph from a designated support set (typically the goal and specific premises). A clause is considered relevant if it lies within $n$ steps of the support set. To ensure the system doesn't just find any path but a valid proof path, Plaisted introduces the concept of "full matching," requiring every literal in a clause to have a potential partner for resolution within the selected subset.

The $G_1(S)$ Graph and Linear Complexity

A significant technical hurdle in using connection graphs is their potential size; a standard graph can have $O(m^2)$ edges for $m$ literals, which is prohibitive for large systems. Plaisted proposes a modified graph structure, $G_1(S)$, which introduces intermediate nodes to represent literals.

Figure 2: The $G_1(S)$ graph construction reduces edge complexity by routing connections through intermediate nodes $N_L$.

As shown in Figure 2, instead of connecting every clause $C_j$ containing literal $L$ directly to every clause $D_k$ containing $\bar{L}$, the graph routes these connections through a single intermediate node $N_L$. This reduces the number of edges to $O(m)$, making the relevance calculation linear relative to the size of the knowledge base.

Results and Theoretical Guarantees

The paper proves that for propositional logic, finding the relevant subset $R_n$ takes $O(|T| \cdot ||S||)$ time, where $T$ is the number of support sets and $||S||$ is the total size of the knowledge base. Beyond efficiency, the method is "safe": Theorem 1 establishes that if a proof of length $n$ exists in the original set, a proof of length at most $n$ exists within the pruned subset $R_n$.

Furthermore, the framework allows for the integration of "semantic" support sets. By using human-provided interpretations or associations to guide the initial focus, the machine can mimic human problem-solving strategies, prioritizing facts that are semantically related to the goal.

Conclusion and Limitations

While the propositional case offers linear performance, extending this to first-order logic introduces complexities due to the requirements of unification. Constructing the full connection graph for first-order logic is more expensive ($O(Lits^2)$). Additionally, the effectiveness of the distance metric depends on the quality of the initial support sets. Despite these challenges, Plaisted’s work laid the foundation for modern relevance filtering techniques in automated reasoning, providing a mathematically rigorous way to manage the "knowledge explosion" in AI systems.

Summary updated

BibTeX
@inproceedings{plaisted1980efficient,
  author = {David A. Plaisted},
  title = {{An Efficient Relevance Criterion for Mechanical Theorem Proving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure