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

D’Agostino, M.; Gabbay, D.; Modgil, S.

doi:10.1007/s11225-019-09847-4

IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca

IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.

AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.

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.

Titolo:	Normality, Non-contamination and Logical Depth in Classical Natural Deduction
Autori:	D'AGOSTINO, MARCELLO Gabbay, Dov Modgil, Sanjay mostra contributor esterni nascondi contributor esterni
Parole Chiave:	Natural deduction; Classical propositional logic; Normal proofs; Non-contamination; Tractable reasoning
Settore Scientifico Disciplinare:	Settore M-FIL/02 - Logica e Filosofia della Scienza Settore MAT/01 - Logica Matematica
Data di pubblicazione:	2019
Rivista:	STUDIA LOGICA
Tipologia:	Article (author)
Data ahead of print / Data di stampa:	18-feb-2019
Digital Object Identifier (DOI):	http://dx.doi.org/10.1007/s11225-019-09847-4
Appare nelle tipologie:	01 - Articolo su periodico

File in questo prodotto:

File	Descrizione	Tipologia	Licenza
uncorrected_proofs.pdf		Post-print, accepted manuscript ecc. (versione accettata dall'editore)		Administrator Richiedi una copia
DAgostino2019_Article_NormalityNon-contaminationAndL.pdf		Publisher's version/PDF		Administrator Richiedi una copia

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