Obvious Logical Inferences

TL;DR

This paper introduces a formal definition and an implementation for "obvious" inferences in predicate logic, aiming to make automated proof-checking systems more user-friendly. By defining obviousness based on a restricted form of Herbrand proofs (requiring at most one substitution instance per clause), the authors propose a new inference rule, OBVIOUS, that significantly shortens proof lengths in existing systems.

What Problem Does This Paper Address?

Automated theorem provers and proof-checking systems for formal logic, particularly predicate logic, often generate proofs that are excessively long and difficult for humans to follow. While these systems can verify the correctness of an inference, the step-by-step process can be tedious, requiring users to manually break down complex deductions into many elementary steps. This is especially true for inferences that a human expert would consider "obvious" at a glance. The challenge is to bridge this gap between human intuition of obviousness and the granular, step-by-step nature of automated proofs.

Methods

The core of the paper is the definition of "obvious inference" and a mechanism to implement it.

  • Definition of Obviousness: The authors propose a thesis: an inference is obvious if its correctness can be demonstrated by a Herbrand proof that uses at most one substitution instance of each clause. This contrasts with standard Herbrand proofs, which might require multiple substitutions from the typically infinite Herbrand universe, making them complex and requiring significant human ingenuity.
  • OBVIOUS Inference Rule: They propose adding a new inference rule, OBVIOUS, to natural deduction proof-checking systems. This rule takes a list of premises and a proposed conclusion.
  • Algorithm: When OBVIOUS is invoked, the system performs the following:
  • Preprocessing: The conclusion is negated, and the resulting formula is Skolemized to produce a set of clauses.
  • Linked Conjunct Search: The system searches for possible matches between literals and their negations within this clause set, using only a single copy of each clause. This is inspired by the "linked conjuncts" method, which predates resolution.
  • Satisfiability Testing: A satisfiability tester (like the Davis-Putnam procedure) is used to check if the linked conjunct structure indicates unsatisfiability.
  • Implementation: An experimental version of this mechanism was implemented as an extension to the Stanford FOL (First-Order Logic) system. This involved translating the logic into LISP, setting the clause instance limit to 1, and incorporating a Skolemizing preprocessor.

Datasets

Not discussed in the paper. The paper uses examples and discusses the potential application to existing large proof libraries (like Filman's dissertation).

Key Insights and Ideas

  • Formalizing "Obviousness": The paper provides a concrete, formal definition for what constitutes an "obvious" inference in predicate logic, grounding it in the structure of Herbrand proofs.
  • Herbrand Proof Restriction: The key insight is that limiting Herbrand proofs to a single substitution instance per clause is a powerful heuristic for identifying intuitively obvious inferences. This restriction avoids the combinatorial explosion of substitutions from the Herbrand universe.
  • Bridging Human and Machine Proofs: The OBVIOUS rule acts as a bridge, allowing users to state conclusions that are intuitively clear, and the system can verify them efficiently without generating lengthy, step-by-step proofs.
  • Efficiency Gains: The proposed method offers significant potential for reducing proof lengths, making automated reasoning systems more practical for human interaction.

Key Results

  • Proof Length Reduction: In an experimental version of the OBVIOUS rule integrated with FOL, proof lengths were shortened by a factor of approximately 10 compared to standard FOL proofs.
  • Example Simplification: A specific example that required 9-17 lines in optimized FOL proofs could be verified in just 1 line using the OBVIOUS mechanism.
  • Validation: The OBVIOUS rule was tested on existing FOL proofs, demonstrating its effectiveness in shortening them.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the current implementation is a simplified version.
  • The method needs to be adapted to handle richer logic features, such as "sorts" for variables, which are common in systems like FOL. This would require modifying the unification algorithm or the preprocessor to respect these sort restrictions.
  • Future Work:
    • Developing a more general version of OBVIOUS for use with FOL that accommodates variable sorts.
  • Exploring opportunities for even more dramatic proof length reductions, especially in large proof libraries.
  • Investigating how to integrate this mechanism with other advanced proof-checking techniques.

Summary updated

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