Counting proofs in propositional logic

&
Archive for Mathematical Logic 48 (2):185-199 (2009)
  Copy   BIBTEX

Abstract

We give a procedure for counting the number of different proofs of a formula in various sorts of propositional logic. This number is either an integer (that may be 0 if the formula is not provable) or infinite

Categories

Keywords

Reprint years

DOI

10.1007/s00153-009-0119-5

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,219

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

The three dimensions of proofs.Yves Guiraud - 2006 - Annals of Pure and Applied Logic 141 (1):266-295.
Quantified propositional logic and the number of lines of tree-like proofs.Alessandra Carbone - 2000 - Studia Logica 64 (3):315-321.
Some remarks on lengths of propositional proofs.Samuel R. Buss - 1995 - Archive for Mathematical Logic 34 (6):377-394.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
The Basic Intuitionistic Logic of Proofs.Sergei Artemov & Rosalie Iemhoff - 2007 - Journal of Symbolic Logic 72 (2):439 - 451.
Introduction to Mathematics of Satisfiability.Victor W. Marek - 2009 - Taylor & Francis.
On meta complexity of propositional formulas and propositional proofs.Pavel Naumov - 2008 - Archive for Mathematical Logic 47 (1):35-52.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
The number of lines in Frege proofs with substitution.Alasdair Urquhart - 1997 - Archive for Mathematical Logic 37 (1):15-19.
Actuality in Propositional Modal Logic.Allen P. Hazen, Benjamin G. Rin & Kai F. Wehmeier - 2013 - Studia Logica 101 (3):487-503.
Isomorphic formulae in classical propositional logic.Kosta Došen & Zoran Petrić - 2012 - Mathematical Logic Quarterly 58 (1):5-17.
A Syntactic Embedding of Predicate Logic into Second-Order Propositional Logic.Morten H. Sørensen & Paweł Urzyczyn - 2010 - Notre Dame Journal of Formal Logic 51 (4):457-473.
On different intuitionistic calculi and embeddings from int to S.Uwe Egly - 2001 - Studia Logica 69 (2):249-277.
Lower Bounds to the size of constant-depth propositional proofs.Jan Krajíček - 1994 - Journal of Symbolic Logic 59 (1):73-86.

Analytics

Added to PP
2013-11-23

Downloads
68 (#231,141)

6 months
2 (#1,157,335)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Basic proof theory.A. S. Troelstra - 1996 - New York: Cambridge University Press. Edited by Helmut Schwichtenberg.
Logic and structure.D. van Dalen - 1980 - New York: Springer Verlag.

Add more references