Abstract
A normalizable natural deduction formulation, with subformula property, of the implicative fragment of classical logic is presented. A traditional notion of normal deduction is adapted and the corresponding weak normalization theorem is proved. An embedding of the classical logic into the intuitionistic logic, restricted on propositional implicational language, is described as well. We believe that this multiple-conclusion approach places the classical logic in the same plane with the intuitionistic logic, from the proof-theoretical viewpoint.
Similar content being viewed by others
References
Boričić B.: A note on some intermediate propositional calculi. Journal of Symbolic Logic 49, 329–333 (1984)
Boričić B.: On sequence-conclusion natural deduction systems. Journal of Philosophical Logic 14, 359–377 (1985)
Boričić B.: On certain normalizable natural deduction formulations of some propositional intermediate logics. Notre Dame Journal of Formal Logic 29(4), 563–568 (1988)
Boričić, B., On some statements of proof theory, (serbocroatian: O nekim tvrdjenjima teorije dokaza), Matematika XVII(Br. 3):40–47, 1988.
Boričić, B., On interpretation of logical sistem, (serbocroatian: O interpretaciji logičkog sistema), Matematika XIX(Br. 3):40–44, 1990.
Boričić B.: On some interpretations of classical logic. Zeitschrift für mathematishe Logik und Grundlagen der Mathematik 38, 409–412 (1992)
Boričić, B., Logic and Proof, Ekonomski fakultet, Beograd 2011, pp. 154+iv, ISBN:978-86-403-1096-3
Cellucci C.: Existential instantiation and normalization in sequent natural deduction. Annals of Pure and Applied Logic 58, 111–148 (1992)
Curry H.B.: A note on the reduction of Gentzen’s calculus LJ. Bulletin of the American Mathematical Society 45, 288–293 (1939)
Curry H.B.: Foundations of Mathematical Logic. McGraw-Hill, New York (1963)
Francez N.: Harmony in multiple-conclusions natural-deduction. Logica Universalis 8, 215–259 (2014)
Gabbay D.M.: Applications of trees to intermediate logics. Journal of Symbolic Logic 37, 135–138 (1972)
Gentzen, G., Collected Papers, in M. E. Szabo (ed.), North–Holland, Amsterdam 1969.
Girard J.Y., Taylor P., Lafont Y.: Proofs and Types. Cambridge University Press, Cambridge (1989)
Glivenko M.V.: Sur quelques points de la logique de M. Brouwer. Bulletins de la classe des sciences, Academie Royale de Belgique 15(5), 183–188 (1929)
Gödel, K., Zur intuitionistischen Arithmetik und Zahlentheorie, Ergebnisse eines Mathematischen Kolloquiums, 1932–1933, vol. 4, pp. 34–38; English transl. The Undecidable, in M. Davis (ed.), Raven Press, New York 1965, pp. 75–81; reprinted, with additional comment in Kurt Gödel, Collected Works, vol. I, in S. Feferman et al (eds.), Oxford University Press, New York 1986, pp. 282–295.
Gordeev L.: On cut elimination in the presence of Peirce rule. Archive for Mathematical Logic 26, 147–164 (1987)
Homič V.I.: A separability theorem for superintuitionistic propositional calculi. Soviet Mathematics Doklady 17(4), 1214–1216 (1976)
Homič V.I.: On the problem of separability for superintuitionistic propositional logics. Soviet Mathematics Doklady 22(2), 476–479 (1980)
Horn A.: The separation theorem of intuitionist propositional calculus. Journal of Symbolic Logic 27, 391–399 (1962)
Hosoi, T., On the separation theorem of intermediate propositional calculi, Proceedings of the Japan Academy 42:535–538, 1966a.
Hosoi T.: The separation theorem on the classical system. Journal of the Faculty of Science, University of Tokyo 12, 223–230 (1966b)
Hosoi, T., Algebraic proof of the separation theorem on classical propositional calculus, Proceedings of the Japan Academy 42:67–69, 1966c.
Johansson I.: Der Minimalkalkül, ein reduzierter intuitionistische Formalismus. Computational Mathematics 4, 119–136 (1937)
Kleene S.C.: Introduction to Metamathematics. North-Holland, Amsterdam (1952)
Kolmogorov, A. N., On the principle of excluded middle, (Russian) Math. Zbor. 32:646–667, 1925; English transl. in From Frege to Gödel: A Source-Book in Mathematical Logic, in J. van Heijenoort (ed.), Harvard University Press, London 1967, pp. 414–437.
Lopez–Escobar E.G.K.: Implicational logics in natural deduction systems. Journal of Symbolic Logic 47(1), 184–186 (1982)
Pereira L.C., Haeusler E.H., Costa V.G., Sanz W.: A new normalization strategy for the implicational fragment of classical propositional logic. Studia Logica 96(1), 95–108 (2010)
Prawitz D.: Natural Deduction. A Proof-Theoretical Study. Almquist and Wiksell, Stockholm (1965)
Read S.: Harmony and autonomy in classical logic. Journal of Philosophical Logic 29, 123–154 (2000)
Seldin J.P.: Normalization and excluded middle I. Studia Logica 48(2), 193–217 (1989)
Shoesmith, D. J., and T. J. Smiley, Multiple-Conclusion Logic, Cambridge University Press, Cambridge (1978) (Reprinted 1980).
Tennant N.W.: Natural Logic. Edinburgh University Press, Edinburgh (1978)
Zimmermann E.: Peirce’s rule in natural deduction. Theoretical Computer Science 275(1–2), 561–574 (2002)
Wajsberg M.: Untersuchungen über den Aussagenkalkúl von A. Heyting. Wiadomości matematyczne 46, 45–101 (1938)
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by Heinrich Wansing
Rights and permissions
About this article
Cite this article
Boričić, B., Ilić, M. An Alternative Normalization of the Implicative Fragment of Classical Logic. Stud Logica 103, 413–446 (2015). https://doi.org/10.1007/s11225-014-9573-0
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11225-014-9573-0