A compact representation of proofs

Studia Logica 46 (4):347 - 370 (1987)
A structure which generalizes formulas by including substitution terms is used to represent proofs in classical logic. These structures, called expansion trees, can be most easily understood as describing a tautologous substitution instance of a theorem. They also provide a computationally useful representation of classical proofs as first-class values. As values they are compact and can easily be manipulated and transformed. For example, we present an explicit transformations between expansion tree proofs and cut-free sequential proofs. A theorem prover which represents proofs using expansion trees can use this transformation to present its proofs in more human-readable form. Also a very simple computation on expansion trees can transform them into Craig-style linear reasoning and into interpolants when they exist. We have chosen a sublogic of the Simple Theory of Types for our classical logic because it elegantly represents substitutions at all finite types through the use of the typed -calculus. Since all the proof-theoretic results we shall study depend heavily on properties of substitutions, using this logic has allowed us to strengthen and extend prior results: we are able to prove a strengthen form of the firstorder interpolation theorem as well as provide a correct description of Skolem functions and the Herbrand Universe. The latter are not straightforward generalization of their first-order definitions.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1007/BF00370646
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 16,667
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
Raymond M. Smullyan (1968). First-Order Logic. New York [Etc.]Springer-Verlag.
Dag Prawitz (1968). Hauptsatz for Higher Order Logic. Journal of Symbolic Logic 33 (3):452-457.

View all 9 references / Add more references

Citations of this work BETA
Willem Heijltjes (2010). Classical Proof Forestry. Annals of Pure and Applied Logic 161 (11):1346-1366.
Stefan Hetzl (2010). On the Form of Witness Terms. Archive for Mathematical Logic 49 (5):529-554.
Richard McKinley (2013). Canonical Proof Nets for Classical Logic. Annals of Pure and Applied Logic 164 (6):702-732.

Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

17 ( #160,237 of 1,726,249 )

Recent downloads (6 months)

7 ( #99,332 of 1,726,249 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.