David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Synthese 167 (2):271 - 315 (2009)
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
Nuel Belnap (1977). How a Computer Should Think. In G. Ryle (ed.), Contemporary Aspects of Philosophy. Oriel Press Ltd..
Kent Bendall (1978). Natural Deduction, Separation, and the Meaning of Logical Operators. Journal of Philosophical Logic 7 (1):245 - 276.
Carlo Cellucci (1995). On Quine's Approach to Natural Deduction'. In Paolo Leonardi & Marco Santambrogio (eds.), On Quine: New Essays. Cambridge University Press. 314--335.
Citations of this work BETA
Marie Duží (2010). The Paradox of Inference and the Non-Triviality of Analytic Information. Journal of Philosophical Logic 39 (5):473 - 510.
Luciano Floridi (2010). Information, Possible Worlds and the Cooptation of Scepticism. Synthese 175 (1):63 - 88.
Similar books and articles
Hartley Slater (2008). Harmonising Natural Deduction. Synthese 163 (2):187 - 198.
M. W. Bunder (1982). Deduction Theorems for Weak Implicational Logics. Studia Logica 41 (2-3):95 - 108.
Peter Milne (1994). Classical Harmony: Rules of Inference and the Meaning of the Logical Constants. Synthese 100 (1):49 - 94.
Kosta Došen (1992). Modal Logic as Metalogic. Journal of Logic, Language and Information 1 (3):173-201.
Yannis Delmas-Rigoutsos (1997). A Double Deduction System for Quantum Logic Based on Natural Deduction. Journal of Philosophical Logic 26 (1):57-67.
Greg Restall & Francesco Paoli (2005). The Geometry of Non-Distributive Logics. Journal of Symbolic Logic 70 (4):1108 - 1126.
James W. Garson (2010). Expressive Power and Incompleteness of Propositional Logics. Journal of Philosophical Logic 39 (2):159-171.
Torben BraÜner (2005). Natural Deduction for First-Order Hybrid Logic. Journal of Logic, Language and Information 14 (2):173-198.
Andrzej Indrzejczak (2003). A Labelled Natural Deduction System for Linear Temporal Logic. Studia Logica 75 (3):345 - 376.
Added to index2009-01-28
Total downloads43 ( #45,114 of 1,413,259 )
Recent downloads (6 months)9 ( #23,880 of 1,413,259 )
How can I increase my downloads?