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 content being viewed by others
Explore related subjects
Discover the latest articles and news from researchers in related subjects, suggested using machine learning.References
Bar-Hillel, Y. (eds) (1964) Language and information: Selected essays on their theory and application. Addison-Wesley, Reading, Mass
Belnap, N. D., Jr. (1976). How a computer should think. In G. Ryle (Ed.), Contemporary aspects of philosophy (pp. 30–55). Oriel Press.
Belnap N.D. Jr. (1977) A useful four-valued logic. In: Dunn J.M., Epstein G. (eds) Modern uses of multiple-valued logics. Reidel, Dordrecht, pp 8–37
Bendall K. (1978) Natural deduction, separation, and the meaning of the logical operators. Journal of Philosophical Logic 7: 245–276
Bremer M., Cohnitz D. (2004) Information and information flow. An introduction. Frankfurt and Lancaster, Ontos Verlag
Cadoli, M., & Schaerf, M. (1992). Tractable reasoning via approximation. In Proceedings of the AAAI Workshop on Tractable Reasoning, pp. 12–15.
Carnap R., Bar-Hillel Y. (1953) An outline of a theory of semantic information. In: Bar-Hillel Y. (eds) Language and information: Selected essays on their theory and application. Addison-Wesley, Reading, Mass, pp 221–274
Cellucci C. (1988) Efficient natural deduction. In: Cellucci C., Sambin G. (eds) Temi e prospettive della logica e della filosofia della scienza contemporanee (Vol I). CLUEB, Bologna, pp 29–57
Cellucci C. (1995) On Quine’s approach to natural deduction. In: Leonardi P., Santambrogio M. (eds) On Quine: New essays. Cambridge University Press, Cambridge, pp 314–335
Cook, S. A. (1971). The complexity of theorem-proving procedures. In STOC’71: Proceedings of the third annual ACM symposium on Theory of computing (pp. 151–158). New York, NY, USA: ACM Press.
Corcoran J. (1998) Information-theoretic logic. In: Martfnez L.V.-F.C., Rivas U. (eds) Truth in perspective. Aldershot, Ashgate Publishing Limited, pp 113–135
Crawford, J. M., & Etherington, D. W. (1998). A non-deterministic semantics for tractable inference. In AAAI/IAAI, pp. 286–291.
D’Agostino, M. (1999). Tableaux methods for classical propositional logic. In M. D’Agostino, D. Gabbay, R. Hähnle, & J. Posegga (Eds.), Handbook of tableaux methods (pp. 45–123). Kluwer Academic Publishers.
D’Agostino, M. (2005). Classical natural deduction. In S. N. Artëmov, H. Barringer, A. S. d’Avila Garcez, L. C. Lamb, & J. Woods (Eds.), We will show them! (1) (pp. 429–468). College Publications.
D’Agostino M., Mondadori M. (1994) The taming of the cut. Journal of Logic and Computation 4: 285–319
D’Agostino, M., & Mondadori, M. (1999). La logica è davvero analitica? Bollettino Filosofico, Università della Calabria, 15.
Dalal, M. (1996). Anytime families of tractable propositional reasoners. In Proceedings of the Fourth International Symposium on AI and Mathematics (AI/MATH-96), pp. 42–45.
Dalal M. (1998) Anytime families of tractable propositional reasoners. Annals of Mathematics and Artificial Intelligence 22: 297–318
Dretske, F. I. (1981). Knowledge and the Flow of Information. Oxford: Blackwell. Reprinted in 1999. Stanford, CA: CSLI Publications.
Dummett M. (1978) Truth and other Enigmas. Duckworth, London
Dummett M. (1991) The logical basis of metaphysics. Duckworth, London
Finger, M. (2004a). Polynomial approximations of full propositional logic via limited bivalence. In 9th European Conference on Logics in Artificial Intelligence (JELIA 2004), Lecture notes in artificial intelligence (Vol. 3229, pp. 526–538). Springer.
Finger, M. (2004b). Towards polynomial approximations of full propositional logic. In A. L. Bazzan & S. Labidi (Eds.), XVII Brazilian Symposium on Artificial Intelligence (SBIA 2004), Lecture notes in artificial intel Lingence (Vol. 3171, pp. 11–20). Springer.
Finger M., Gabbay D. (2006) Cut and pay. Journal of Logic, Language and Information 15(3): 195–218
Finger M., Wasserman R. (2004) Approximate and limited reasoning: Semantics, proof theory, expressivity and control. Journal of Logic and Computation 14(2): 179–204
Floridi L. (2004) Outline of a theory of strongly semantic information. Minds and Machines 14(2): 197–222
Floridi L. (2005) Is information meaningful data?. Philosophy and Phenomenological Research 70(2): 351–370
Gentzen, G. (1935). Unstersuchungen über das logische Schliessen. Math Zeitschrift, 39, 176–210. English translation in Szabo, M. (Ed.). (1969). The collected papers of Gerhard Gentzen. Amsterdam: North-Holland.
Hempel, C. (1945). Geometry and empirical science. American Mathematical Monthly, 52.
Hintikka J. (1973) Logic, language games and information. Kantian themes in the philosophy of logic. Clarendon Press, Oxford
Leblanc H. (1966) Two shortcomings of natural deduction. Journal of Philosophy LXIII: 29–37
Popper, K. (1934). Logik Der Forschung: Zur Erkenntnistheorie Der Modernen Naturwissenschaft. Wien: J. Springer. Eng. tr. The logic of scientific discovery (London: Hutchinson, 1959).
Sequoiah-Grayson S. (2008) The scandal of deduction. Hintikka on the information yield of deductive inferences. The Journal of Philosophical Logic 37(1): 67–94
Shannon, C., & Weaver, W. (1949). The mathematical theory of communication. Urbana: University of Illinois Press. Foreword by R. E. Blahut and B. Hajek.
Smullyan R.M. (1965) Analytic natural deduction. Journal of Symbolic Logic 30: 123–139
Szabo, M. (eds) (1969) The collected papers of Gerhard Gentzen. North-Holland, Amsterdam
Tennant, N. (1990). Natural logic. Edinburgh University Press.
Weir A. (1986) Classical harmony. Notre Dame Journal of Formal Logic 27(4): 459–482
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
D’Agostino, M., Floridi, L. The enduring scandal of deduction. Synthese 167, 271–315 (2009). https://doi.org/10.1007/s11229-008-9409-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11229-008-9409-4