Natural deduction systems for classical, intuitionistic and modal logics were deeply investigated by Prawitz [D. Prawitz, Natural Deduction: A Proof-theoretical Study, in: Stockholm Studies in Philosophy, vol. 3, Almqvist and Wiksell, Stockholm, 1965. Reprinted at: Dover Publications, Dover Books on Mathematics, 2006] from a proof-theoretical perspective. Prawitz proved weak normalization for classical logic only for a language without logical or, there exists and with a restricted application of reduction ad absurdum. Reduction steps related to logical or, there exists and classical (...) negation bring about many problems solved only rather recently. For classical S5 modal logic, Prawitz defined a normalizable system, but for a language without logical or, there exists, ◊ and, for a propositional language without ◊, Medeiros [M.da P.N. Medeiros, A new S4 classical modal logic in natural deduction, Journal of Symbolic Logic 71 799–809] presented a normalizable system for classical S4. We can mention many cut-free Gentzen systems for S4, S5 and K45/K45D, some normalizable natural deduction systems for intuitionistic modal logics and one more for full classical S4, but not for full classical S5. Here our focus is on the definition of a classical and normalizable natural deduction system for S5, taking not only □ and ◊ as primitive symbols, but also all connectives and quantifiers, including classical negation, disjunction and the existential quantifier. The normalization procedure is based on the strategy proposed by Massi [C.D.B. Massi, Provas de normalizaçaõ para a lógica clássica, Ph.D. Thesis, Departamento de Filosofia, UNICAMP, Campinas, 1990] and Pereira and Massi [L.C. Pereira, C.D.B. Massi, Normalização para a lógica clássica, in: O que nos faz pensar, Cadernos de Filosofia da PUC-RJ, vol. 2, 1990, pp. 49–53] for first-order classical logic to cope with the combined use of classical negation, disjunction and the existential quantifier. Here we extend such results to deal with □ and ◊ too. The elimination rule for ◊ uses the notions of connection and of essentially modal formulas already proposed by Prawitz for the introduction of □. Beyond weak normalization, we also prove the subformula property for full S5. (shrink)

The axiomatic presentation of modal systems and the standard formulations of natural deduction and sequent calculus for modal logic are reviewed, together with the difficulties that emerge with these approaches. Generalizations of standard proof systems are then presented. These include, among others, display calculi, hypersequents, and labelled systems, with the latter surveyed from a closer perspective.

This book provides a detailed exposition of one of the most practical and popular methods of proving theorems in logic, called Natural Deduction. It is presented both historically and systematically. Also some combinations with other known proof methods are explored. The initial part of the book deals with Classical Logic, whereas the rest is concerned with systems for several forms of Modal Logics, one of the most important branches of modern logic, which has wide applicability.

Anderson and Belnap presented indexed Fitch-style natural deduction systems for the relevant logics R, E, and T. This work was extended by Brady to cover a range of relevant logics. In this paper I present indexed tree natural deduction systems for the Anderson–Belnap–Brady systems and show how to translate proofs in one format into proofs in the other, which establishes the adequacy of the tree systems.

The concept of “necessity of thought” plays a central role in Dag Prawitz’s essay “Logical Consequence from a Constructivist Point of View” (Prawitz 2005). The theme is later developed in various articles devoted to the notion of valid inference (Prawitz, 2009, forthcoming a, forthcoming b). In section 1 I explain how the notion of necessity of thought emerges from Prawitz’s analysis of logical consequence. I try to expound Prawitz’s views concerning the necessity of thought in sections 2, 3 and 4. (...) In sections 5 and 6 I discuss some problems arising with regard to Prawitz’s views. (shrink)

Two common forms of natural deduction proof systems are found in the Gentzen–Prawitz and Jaśkowski–Fitch systems. In this paper, I provide translations between proofs in these systems, pointing out the ways in which the translations highlight the structural rules implicit in the systems. These translations work for classical, intuitionistic, and minimal logic. I then provide translations for classical S4 proofs.

This volume is dedicated to Prof. Dag Prawitz and his outstanding contributions to philosophical and mathematical logic. Prawitz's eminent contributions to structural proof theory, or general proof theory, as he calls it, and inference-based meaning theories have been extremely influential in the development of modern proof theory and anti-realistic semantics. In particular, Prawitz is the main author on natural deduction in addition to Gerhard Gentzen, who defined natural deduction in his PhD thesis published in 1934. The book opens with an (...) introductory paper that surveys Prawitz's numerous contributions to proof theory and proof-theoretic semantics and puts his work into a somewhat broader perspective, both historically and systematically. Chapters include either in-depth studies of certain aspects of Dag Prawitz's work or address open research problems that are concerned with core issues in structural proof theory and range from philosophical essays to papers of a mathematical nature. Investigations into the necessity of thought and the theory of grounds and computational justifications as well as an examination of Prawitz's conception of the validity of inferences in the light of three “dogmas of proof-theoretic semantics” are included. More formal papers deal with the constructive behaviour of fragments of classical logic and fragments of the modal logic S4 among other topics. In addition, there are chapters about inversion principles, normalization of proofs, and the notion of proof-theoretic harmony and other areas of a more mathematical persuasion. Dag Prawitz also writes a chapter in which he explains his current views on the epistemic dimension of proofs and addresses the question why some inferences succeed in conferring evidence on their conclusions when applied to premises for which one already possesses evidence. (shrink)

In this paper we study natural deduction for the intuitionistic and classical (normal) modal logics obtained from the combinations of the axioms T, B, 4 and 5. In this context we introduce a new multi-contextual structure, called T-sequent, that allows to design simple labelfree natural deduction systems for these logics. After proving that they are sound and complete we show that they satisfy the normalization property and consequently the subformula property in the intuitionistic case.