We present a unifying semantical and proof-theoretical framework for investigating depth-bounded approximations to Boolean Logic, namely approximations in which the number of nested applications of a single structural rule, representing the classical Principle of Bivalence, is bounded above by a fixed natural number. These approximations provide a hierarchy of tractable logical systems that indefinitely converge to classical propositional logic. The framework we present here brings to light a general approach to logical inference that is quite different from the standard Gentzen-style approaches, while preserving some of their nice proof-theoretical properties, and is common to several proof systems and algorithms, such as KE, KI and Stålmarck’s method.
Semantics and proof-theory of depth-bounded Boolean logics / M. D'Agostino, M. Finger, D.M. Gabbay. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 480(2013 Apr), pp. 43-68.
Semantics and proof-theory of depth-bounded Boolean logics
M. D'Agostino
;
2013
Abstract
We present a unifying semantical and proof-theoretical framework for investigating depth-bounded approximations to Boolean Logic, namely approximations in which the number of nested applications of a single structural rule, representing the classical Principle of Bivalence, is bounded above by a fixed natural number. These approximations provide a hierarchy of tractable logical systems that indefinitely converge to classical propositional logic. The framework we present here brings to light a general approach to logical inference that is quite different from the standard Gentzen-style approaches, while preserving some of their nice proof-theoretical properties, and is common to several proof systems and algorithms, such as KE, KI and Stålmarck’s method.File | Dimensione | Formato | |
---|---|---|---|
TCS9255.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
762.37 kB
Formato
Adobe PDF
|
762.37 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
TCS20013.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
462.36 kB
Formato
Adobe PDF
|
462.36 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.