Gentzen-Type Formal System Representing Properties

IJCAI 1975

TL;DR

This paper introduces TKP 1, an automatic theorem prover based on a Gentzen-type formal system designed to represent and prove properties of functions, particularly those arising from recursive programs. Its key innovation lies in its ability to directly handle functional composition and automatically generate induction hypotheses, making it efficient for program verification tasks.

What Problem Does This Paper Address?

Proving the correctness of computer programs, especially those involving recursion, is a fundamental challenge in computer science. Traditional methods often rely on manual application of induction and fixed-point theorems, which can be tedious and error-prone. The authors aim to automate this process by developing a formal system that can directly manipulate functional expressions and their compositions, thereby simplifying the proof construction for program properties. They specifically address the need for a system that can handle recursive definitions and automatically manage the inductive steps required for proving properties of such programs.

Methods

The core of TKP 1 is a Gentzen-type formal system that represents properties of functions. This system is characterized by:

  • Functional Composition: It directly handles the composition of functions (e.g., F · G(x) = G(F(x))) and logical connectives as functional operations.
  • Fixed-Point Operator and Induction: The system incorporates an operator for infinitary sums, enabling the representation and application of fixed-point operators. Crucially, it automatically generates induction hypotheses, facilitating inductive proofs.
  • Cut-less System: The formal system is designed to be cut-less, meaning that proofs can be decomposed into smaller, manageable sub-theorems, simplifying the automated proof process.
  • Symmetric Inference Rules: Inference rules are applied symmetrically to both sides of the implication symbol (→), which is represented as a sequent.
  • Pattern Matching for Assumptions/Definitions: TKP 1 uses pattern matching to apply user-provided assumptions and definitions to the current sequent, attempting to match the innermost subexpression first.

The implementation, TKP 1, is written in KLISP and consists of three phases: a translator, a prover, and a visualizer. The visualizer generates easily readable proof figures.

Datasets

Not discussed in the paper. The paper focuses on the formal system and its implementation, using a specific example (proving the equivalence of two factorial functions) to illustrate its capabilities.

Key Insights and Ideas

  • Automating Induction: The automatic generation of induction hypotheses is a significant contribution, reducing the burden on the user and streamlining the proof process for recursive programs.
  • Direct Functional Manipulation: Representing program properties directly as functionals and compositions, rather than translating them into a separate logical language, allows for a more natural and efficient proof procedure.
  • Gentzen-Type System for Programs: Adapting Gentzen's sequent calculus for program properties provides a structured and decomposable framework for automated theorem proving.
  • Readability of Proofs: The system's ability to display proof figures in a plain, easily readable form is valuable for understanding the automated reasoning process.

Key Results

The paper demonstrates the effectiveness of TKP 1 by illustrating its ability to prove the equivalence of two factorial functions. The system successfully handles functional definitions, assumptions, and automatically generates induction hypotheses to complete the proof. While specific quantitative results (e.g., performance benchmarks on a suite of problems) are not detailed, the paper asserts that TKP 1 can prove most problems described in a referenced work [8].

Limitations and Future Work

The authors acknowledge several areas for future development:

  • Dynamic Assumptions: Extending the system to accept "dynamic assumptions," such as procedural assumptions, would increase its flexibility.
  • Algebraic Theorems: Incorporating useful algebraic theorems and automatically deleting unuseful ones would enhance the system's reasoning power.
  • Interactive Facilities: Developing interactive capabilities would make the theorem prover more powerful and user-friendly.
  • Extensive Applications: The authors believe the prover has potential for more extensive applications with interactive features.

Summary updated

BibTeX
@inproceedings{1975gentzen,
  title = {{Gentzen-Type Formal System Representing Properties}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1975},
}
Figure