The enduring scandal of deduction: is propositional logic really uninformative?

Synthese 167 (2):271-315 (2009)
  Copy   BIBTEX

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.

Similar books and articles

Mimesis as Scandal: Rousseau and Derrida.Jeremiah L. Alberg - 2015 - Contagion: Journal of Violence, Mimesis, and Culture 22:31-42.
Scandals Must Come.Jeremiah L. Alberg - 2013 - Contagion: Journal of Violence, Mimesis, and Culture 20:87-99.
On Quine's Approach to Natural Deduction'.Carlo Cellucci - 1995 - In Paolo Leonardi & Marco Santambrogio (eds.), On Quine: New Essays. Cambridge University Press. pp. 314--335.
The Two Steps of the B-Deduction.Markku Leppäkoski - 1998 - Kantian Review 2:107-116.
The Proof Structure of Kant's A-Deduction.Michael Barker - 2001 - Kant Studien 92 (3):259-282.
Apperception and Analyticity in the B-Deduction.Henry E. Allison - 1993 - Grazer Philosophische Studien 44 (1):233-252.

Analytics

Added to PP
2009-01-28

Downloads
617 (#25,457)

6 months
171 (#14,360)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Luciano Floridi
Yale University
Marcello D'Agostino
Università degli Studi di Milano

Citations of this work

What a maker’s knowledge could be.Luciano Floridi - 2018 - Synthese 195 (1):465-481.
A plea for non-naturalism as constructionism.Luciano Floridi - 2017 - Minds and Machines 27 (2):269-285.
What is a philosophical question?Luciano Floridi - 2013 - Metaphilosophy 44 (3):195-221.
The Paradox of Inference and the Non-Triviality of Analytic Information.Marie Duží - 2010 - Journal of Philosophical Logic 39 (5):473 - 510.
Perception and testimony as data providers.Luciano Floridi - 2014 - Logique Et Analyse 57 (226):71–95.

View all 25 citations / Add more citations

References found in this work

The logical basis of metaphysics.Michael Dummett - 1991 - Cambridge, Mass.: Harvard University Press.
Truth and other enigmas.Michael Dummett - 1978 - Cambridge: Harvard University Press.
Knowledge and the flow of information.F. Dretske - 1989 - Trans/Form/Ação 12:133-139.

View all 29 references / Add more references