We present a unifying semantic and proof-theoretical framework for investigating depth-bounded approximations to Boolean Logic in which the number of nested applications of a single structural rule, representing the classical Principle of Bivalence (classical cut), 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 operational rules are shared by all approximation systems and are justified by an "informational semantics" whereby the meaning of a logical operator is specified solely in terms of the information that is actually possessed by an agent.

Informational semantics, non-deterministic matrices and feasible deduction / M. D'Agostino. - In: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. - ISSN 1571-0661. - 305(2014 Jul), pp. 35-52.

Informational semantics, non-deterministic matrices and feasible deduction

M. D'Agostino
Primo
2014-07

Abstract

We present a unifying semantic and proof-theoretical framework for investigating depth-bounded approximations to Boolean Logic in which the number of nested applications of a single structural rule, representing the classical Principle of Bivalence (classical cut), 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 operational rules are shared by all approximation systems and are justified by an "informational semantics" whereby the meaning of a logical operator is specified solely in terms of the information that is actually possessed by an agent.
classical propositional logic; informational semantics; non-deterministic matrices; computational complexity; natural deduction; semantic tableaux
Settore M-FIL/02 - Logica e Filosofia della Scienza
Article (author)
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S1571066114000504-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 226.65 kB
Formato Adobe PDF
226.65 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
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/328730
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact