In this paper we provide a detailed proof-theoretical analysis of a natural deduction system for classical propositional logic that (i) represents classical proofs in a more natural way than standard Gentzen-style natural deduction, (ii) admits of a simple normalization procedure such that normal proofs enjoy the Weak Subformula Property, (iii) provides the means to prove a Non-contamination Property of normal proofs that is not satisfied by normal proofs in the Gentzen tradition and is useful for applications, especially in formal argumentation, (iv) naturally leads to defining a notion of depth of a proof, to the effect that, for every fixed natural k, normal k-depth deducibility is a tractable problem and converges to classical deducibility as k tends to infinity.

Normality, Non-contamination and Logical Depth in Classical Natural Deduction / M. D’Agostino, D. Gabbay, S. Modgil. - In: STUDIA LOGICA. - ISSN 0039-3215. - 108:2(2020 Apr 01), pp. 291-357. [10.1007/s11225-019-09847-4]

Normality, Non-contamination and Logical Depth in Classical Natural Deduction

M. D’Agostino
Primo
;
2020-04-01

Abstract

In this paper we provide a detailed proof-theoretical analysis of a natural deduction system for classical propositional logic that (i) represents classical proofs in a more natural way than standard Gentzen-style natural deduction, (ii) admits of a simple normalization procedure such that normal proofs enjoy the Weak Subformula Property, (iii) provides the means to prove a Non-contamination Property of normal proofs that is not satisfied by normal proofs in the Gentzen tradition and is useful for applications, especially in formal argumentation, (iv) naturally leads to defining a notion of depth of a proof, to the effect that, for every fixed natural k, normal k-depth deducibility is a tractable problem and converges to classical deducibility as k tends to infinity.
Natural deduction; Classical propositional logic; Normal proofs; Non-contamination; Tractable reasoning
Settore M-FIL/02 - Logica e Filosofia della Scienza
Settore MAT/01 - Logica Matematica
Dipartimenti di Eccellenza 2018-2022 - Dipartimento di FILOSOFIA
23-mar-2019
Article (author)
File in questo prodotto:
File Dimensione Formato  
DAgostino2019_Article_NormalityNon-contaminationAndL.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 948.19 kB
Formato Adobe PDF
948.19 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
NNC_rev2.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 436.61 kB
Formato Adobe PDF
436.61 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/637126
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact