A Semantically Guided Deductive System for Automatic Theorem-Proving

Raymond ReiterIJCAI 1973

Abstract

In this foundational 1973 work, Raymond Reiter introduces System L, a theorem-proving architecture that bridges the gap between formal logic and domain-specific intuition. By combining a natural deduction component with a semantic model of the problem domain, the system can prune "dead-end" search branches and suggest intelligent inferences. This approach addresses the combinatorial explosion typical of resolution-based systems by mimicking the way human mathematicians use diagrams and examples to guide their proofs.

Introduction: The Challenge of Combinatorial Explosion

In the early 1970s, automated theorem proving (ATP) was dominated by resolution-based systems. While mathematically elegant, these systems often generated a massive number of potential logical steps, most of which were irrelevant to the final proof. This led to a "combinatorial explosion" that made complex proofs computationally infeasible.

Existing attempts to mitigate this issue relied on domain-dependent heuristics—hand-coded rules of thumb. However, Reiter argued these were often ad hoc, difficult to maintain, and primarily syntactically driven. Crucially, they lacked a mechanism to recognize "dead alleys" based on the actual properties of the mathematical objects under consideration.

System Architecture: The Dual-Component Approach

Reiter’s proposed solution, System L, features a dual-component architecture designed to integrate syntax and semantics seamlessly.

The Deductive Component

Unlike the resolution methods of the time, System L utilizes natural deduction. This style of logic more closely resembles human reasoning, breaking down complex goals into smaller, manageable subgoals. For example, to prove a conjunction $A \land B$, the system first attempts to prove $A$ and then $B$.

Rules 1-5 of System L's deductive component, illustrating the natural deduction approach to subgoals.

The Semantic Component

The semantic component maintains a model—a concrete example where the axioms of the domain hold true. In geometry, this might be a digital coordinate-based diagram; in group theory, it could be a finite multiplication table.

The interaction between these components is continuous:

  1. Pruning: When a subgoal is generated, the system checks it against the semantic model. If the statement is false in the model, the entire search branch is immediately abandoned.
  2. Inference Suggestion: The model can suggest specific values for variables, such as identifying a particular point in a geometric construction.
  3. Dynamic Evolution: The model is not static. If a proof requires new constructions (e.g., drawing an auxiliary line), the system updates the model to include these new objects.

Evaluation and Results

System L was evaluated using classic problems from propositional logic, Euclidean geometry, and group theory. A key highlight was its performance in geometry, where it successfully handled complex proofs that previously required manual human "hints."

A geometric model of a trapezoid used by System L to discover necessary auxiliary lines for a proof.

The system demonstrated significant efficiency by avoiding "blind alleys" through semantic pruning. This reduced the need for arbitrary search depth limits, allowing the prover to find deep proofs that purely syntactic systems would miss.

Key Insights

The primary innovation of System L is the use of semantics as a filter. By falsifying logical paths using concrete examples, the system ensures that it only pursues subgoals that are at least true in a specific instance of the problem. This "naturalness" aligns ATP more closely with human mathematical practice, where diagrams often precede formal symbol manipulation.

Limitations and Future Work

Despite its successes, Reiter noted several limitations. System L is not logically "complete," meaning there are certain tautologies it cannot prove due to its specific rule structure. Furthermore, the system's performance is highly dependent on the quality of the provided model; a "special case" model (like using a square to represent all rectangles) could lead to the accidental pruning of valid paths. Finally, representing models for infinite domains and managing the computational overhead of constant semantic checking remain ongoing challenges in the field.

Summary updated

BibTeX
@inproceedings{reiter1973semantically,
  author = {Raymond Reiter},
  title = {{A Semantically Guided Deductive System for Automatic Theorem-Proving}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1973},
}
Figure