A compact representation of proofs

Studia Logica 46 (4):347 - 370 (1987)
Abstract
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)
Options
 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: 11,819
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
Peter B. Andrews (1971). Resolution in Type Theory. Journal of Symbolic Logic 36 (3):414-432.
William Craig (1957). [Omnibus Review]. Journal of Symbolic Logic 22 (4):360-363.
Jacques Herbrand (1971). Logical Writings. Dordrecht, Holland,D. Reidel Pub. Co..

View all 6 references

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

Monthly downloads

Added to index

2009-01-28

Total downloads

7 ( #192,693 of 1,100,004 )

Recent downloads (6 months)

5 ( #66,994 of 1,100,004 )

How can I increase my downloads?

My notes
Sign in to use this feature


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