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

Authors
Luciano Floridi
Oxford University
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 Philosophy   Metaphysics   Philosophy of Language   Logic   Epistemology   Computer Science, general   Philosophy of Science
Categories (categorize this paper)
ISBN(s)
DOI 10.1007/s11229-008-9409-4
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

References found in this work BETA

The Logical Basis of Metaphysics.Michael Dummett - 1991 - Harvard University Press.
Truth and Other Enigmas.Michael Dummett - 1978 - Cambridge, MA, USA: Harvard University Press.
Knowledge and the Flow of Information.F. Dretske - 1989 - Trans/Form/Ação 12:133-139.
A Useful Four-Valued Logic.N. D. Belnap - 1977 - In J. M. Dunn & G. Epstein (eds.), Modern Uses of Multiple-Valued Logic. D. Reidel.

View all 28 references / Add more references

Citations of this work BETA

What a Maker’s Knowledge Could Be.Luciano Floridi - 2018 - Synthese 195 (1):465-481.
What is a Philosophical Question?Luciano Floridi - 2013 - Metaphilosophy 44 (3):195-221.
A Plea for Non-Naturalism as Constructionism.Luciano Floridi - 2017 - Minds and Machines 27 (2):269-285.
Perception and Testimony as Data Providers.Luciano Floridi - 2014 - Logique Et Analyse 57 (226):71–95.
The Paradox of Inference and the Non-Triviality of Analytic Information.Marie Duží - 2010 - Journal of Philosophical Logic 39 (5):473 - 510.

View all 21 citations / Add more citations

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 index
2009-01-28

Total views
309 ( #33,393 of 2,498,533 )

Recent downloads (6 months)
20 ( #42,703 of 2,498,533 )

How can I increase my downloads?

Downloads

My notes