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$.
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:
- 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.
- Inference Suggestion: The model can suggest specific values for variables, such as identifying a particular point in a geometric construction.
- 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."
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