Obvious Logical Inferences

Martin Davis

Abstract

In automated reasoning, a significant gap exists between what a human considers an "obvious" logical step and what a computer requires to verify a proof. Martin Davis proposes a formal definition for obviousness: an inference is obvious if its Herbrand proof requires no more than one substitution instance of each clause. By implementing this as a dedicated "OBVIOUS" rule, formal proofs can be compressed by an order of magnitude, bridging the gap between human intuition and mechanical verification.

Introduction

During the late 1970s, users of proof-checking systems like Stanford’s FOL (First-Order Logic) encountered a persistent bottleneck. While a human could intuitively grasp a logical conclusion, the software often required a manual, granular guide through every step—eliminating quantifiers, applying propositional calculus, and reinstating quantifiers. A deduction that a human performs instantly might require 17 lines of formal code. Davis sought a way for computers to recognize these "obvious" jumps without the computational cost of full-blown automated theorem proving.

Defining "Obviousness"

The central contribution of this paper is a formal thesis: An inference is "obvious" precisely when a Herbrand proof of its correctness can be found using no more than one substitution instance of each clause. This definition captures the essence of human intuition: a connection feels "obvious" when we do not need to reuse the same fact in multiple, different ways to reach the conclusion.

Methodology: The OBVIOUS Rule

To automate this definition, Davis proposed a mechanism based on the "linked conjuncts" method. The process involves four primary steps:

  1. Negation: The system negates the proposed conclusion.
  2. Skolemization: It converts the premises and the negated conclusion into a list of clauses in conjunctive normal form.
  3. Unification: It searches for matches between literals and their negations, constrained to using only one copy of each clause.
  4. Satisfiability Testing: It uses the Davis-Putnam procedure to check if the resulting clauses are truth-functionally unsatisfiable.
Figure 1: Clausal representation of a logical problem from Quine's Methods of Logic, used to demonstrate the OBVIOUS rule.

By limiting the search to a single substitution per clause, the system avoids the state-space explosion typical of general theorem provers, making the rule both efficient and predictable.

Results and Evaluation

The method was evaluated using classic logic examples, such as those from W.V.O. Quine’s Methods of Logic, and by re-running existing proofs from the Stanford FOL system.

  • Proof Compression: In a primary example, a proof that originally required 17 lines was reduced to a single line using the OBVIOUS rule.
  • Efficiency: Across various proofs, including those in Robert Filman’s dissertation, the implementation shortened total proof length by a factor of approximately 10.
  • Integration: The rule was successfully integrated into the Stanford FOL system, demonstrating its practical utility in real-world proof-checking environments.

Discussion and Limitations

While the "one-substitution" rule is a powerful heuristic, it is not exhaustive. Some inferences humans find obvious might require multiple substitutions, and the initial implementation struggled with "sorts" (typed variables). Davis suggested that future work could refine the unification algorithm to handle these types or use pre-processors to make them explicit. Nonetheless, the thesis provides a robust foundation for making automated reasoning tools more aligned with human cognitive processes.

Summary updated

BibTeX
@inproceedings{davis1981obvious,
  author = {Martin Davis},
  title = {{Obvious Logical Inferences}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1981},
}
Figure