PPC (Pisa Proof Checker): a tool for experiments in theory of proving and mathematical theory of computation

Article type: Research Article

Authors: Aiello, Luigia^a | Aiello, Mario^a | Attardi, Giuseppe^a | Prini, Gianfranco^a

Affiliations: [a] Istituto di Elaborazione dell’Informazione, Consiglio Nazionale delle Ricerehe, Pisa Istituto di Scienze dell’Informazione, Università di Pisa

Abstract: An interactive proof checker is a system which is able of building a formal proof (in some deductive calculus) by executing commands provided by the user. Proof checkers are useful both for making experiments in proof construction within various formal systems and for proving theorems in those fields of mathematics (such as mathematical theory of computation) where proofs are necessarily very large and unfeasible by hand. Two levels may be distinguished in a proof checker. The lower one implements the proof management routines, and is independent of any particular logic. The higher one implements the inference rules of a particular logical calculus. Powerful higher level rules are also needed to make the use of the checker practical. Almost all routine steps may be then generated automatically, and the user has just to give some “hints” to the checker, which transforms an “informal argument” into a formal proof.

Keywords: automatic theorem proving, denotational semantics of programming languages, mathematical theory of computation, proof of formal properties of programs

DOI: 10.3233/FI-1977-1116

Journal: Fundamenta Informaticae, vol. 1, no. 1, pp. 251-275, 1977