Short Proofs of Tautologies using the Schema of Equivalence

&
In Egon Börger, Yuri Gurevich & Karl Meinke (eds.), Computer Science Logic. 7th Workshop, CSL '93, Swansea. Selected Papers. Berlin: Springer. pp. 33-35 (1994)
  Copy   BIBTEX

Abstract

It is shown how the schema of equivalence can be used to obtain short proofs of tautologies A , where the depth of proofs is linear in the number of variables in A .

Categories

Keywords

Reprint years

Links

PhilArchive

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Algorithmic Structuring of Cut-free Proofs.Matthias Baaz & Richard Zach - 1993 - In Börger Egon, Kleine Büning Hans, Jäger Gerhard, Martini Simone & Richter Michael M. (eds.), Computer Science Logic. CSL’92, San Miniato, Italy. Selected Papers. Springer. pp. 29–42.
Resolution over linear equations and multilinear proofs.Ran Raz & Iddo Tzameret - 2008 - Annals of Pure and Applied Logic 155 (3):194-224.
The complexity of propositional proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
The Depth of Resolution Proofs.Alasdair Urquhart - 2011 - Studia Logica 99 (1-3):349-364.
Lower Bounds for cutting planes proofs with small coefficients.Maria Bonet, Toniann Pitassi & Ran Raz - 1997 - Journal of Symbolic Logic 62 (3):708-728.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
Lower Bounds for Cutting Planes Proofs with Small Coefficients.Maria Bonet, Toniann Pitassi & Ran Raz - 1997 - Journal of Symbolic Logic 62 (3):708-728.
Generalizing proofs in monadic languages.Matthias Baaz & Piotr Wojtylak - 2008 - Annals of Pure and Applied Logic 154 (2):71-138.
On me number of steps in proofs.Jan Krajíèek - 1989 - Annals of Pure and Applied Logic 41 (2):153-178.
On the number of steps in proofs.Jan Kraj\mIček - 1989 - Annals of Pure and Applied Logic 41 (2):153-178.
On the complexity of proof deskolemization.Matthias Baaz, Stefan Hetzl & Daniel Weller - 2012 - Journal of Symbolic Logic 77 (2):669-686.
Describing proofs by short tautologies.Stefan Hetzl - 2009 - Annals of Pure and Applied Logic 159 (1-2):129-145.
That We See That Some Diagrammatic Proofs Are Perfectly Rigorous.Jody Azzouni - 2013 - Philosophia Mathematica 21 (3):323-338.
Provability logics with quantifiers on proofs.Rostislav E. Yavorsky - 2001 - Annals of Pure and Applied Logic 113 (1-3):373-387.

Analytics

Added to PP
2017-10-10

Downloads
363 (#52,654)

6 months
47 (#83,682)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Matthias Baaz
TU Wien
Richard Zach
University of Calgary

Citations of this work

Add more citations

References found in this work

Some results on speed-up.Tsuyoshi Yukami - 1984 - Annals of the Japan Association for Philosophy of Science 6 (4):195-205.

Add more references