The Enduring Scandal of Deduction: Is Propositional Logic Really Uninformative?

Synthese 167 (2):271 - 315 (2009)
Abstract
Deductive inference is usually regarded as being "tautological" or "analytical": the information conveyed by the conclusion is contained in the information conveyed by the premises. This idea, however, clashes with the undecidability of first-order logic and with the (likely) intractability of Boolean logic. In this article, we address the problem both from the semantic and the proof-theoretical point of view. We propose a hierarchy of propositional logics that are all tractable (i.e. decidable in polynomial time), although by means of growing computational resources, and converge towards classical propositional logic. The underlying claim is that this hierarchy can be used to represent increasing levels of "depth" or "informativeness" of Boolean reasoning. Special attention is paid to the most basic logic in this hierarchy, the pure "intelim logic", which satisfies all the requirements of a natural deduction system (allowing both introduction and elimination rules for each logical operator) while admitting of a feasible (quadratic) decision procedure. We argue that this logic is "analytic" in a particularly strict sense, in that it rules out any use of "virtual information", which is chiefly responsible for the combinatorial explosion of standard classical systems. As a result, analyticity and tractability are reconciled and growing degrees of computational complexity are associated with the depth at which the use of virtual information is allowed.
Keywords Boolean logic  Tractability  Semantic information  Analytical reasoning  Natural deduction
Categories (categorize this paper)
DOI 10.1007/s11229-008-9409-4
Options
 Save to my reading list
Follow the author(s)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 30,727
Through your library
References found in this work BETA

No references found.

Add more references

Citations of this work BETA
What is A Philosophical Question?Luciano Floridi - 2013 - Metaphilosophy 44 (3):195-221.

Add more citations

Similar books and articles
Natural Deduction for First-Order Hybrid Logic.Torben BraÜner - 2005 - Journal of Logic, Language and Information 14 (2):173-198.
Modal Logic as Metalogic.Kosta Došen - 1992 - Journal of Logic, Language and Information 1 (3):173-201.
Aspects of Analytic Deduction.Athanassios Tzouvaras - 1996 - Journal of Philosophical Logic 25 (6):581-596.
The Geometry of Non-Distributive Logics.Greg Restall & Francesco Paoli - 2005 - Journal of Symbolic Logic 70 (4):1108 - 1126.
The Content of Deduction.Mark Jago - 2013 - Journal of Philosophical Logic 42 (2):317-334.
Added to PP index
2011-05-29

Total downloads
78 ( #69,786 of 2,197,330 )

Recent downloads (6 months)
3 ( #97,207 of 2,197,330 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature