Data di Pubblicazione:
2015
Citazione:
An informational view of classical logic / M. D'Agostino. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 606(2015 Nov), pp. 79-97. [10.1016/j.tcs.2015.06.057]
Abstract:
We present an informational view of classical propositional logic that stems from a kind of informational semantics whereby the meaning of a logical operator is specified solely in terms of the information that is actually possessed by an agent. In this view the inferential power of logical agents is naturally bounded by their limited capability of manipulating “virtual information”, namely information that is not implicitly contained in the data. Although this informational semantics cannot be expressed by any finitely- valued matrix, it can be expressed by a non-deterministic 3-valued matrix that was first introduced by W.V.O. Quine, but ignored by the logical community. Within the general framework presented in [21] we provide an in-depth discussion of this informational semantics and a detailed analysis of a specific infinite hierarchy of tractable approximations to classical propositional logic that is based on it. This hierarchy can be used to model the inferential power of resource-bounded agents and admits of a uniform proof-theoretical characterization that is half-way between a classical version of Natural Deduction and the method of semantic tableaux.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
classical propositional logic; informational semantics; non-deterministic matrices; computational complexity; natural deduction; semantic tableaux
Elenco autori:
M. D'Agostino
Link alla scheda completa:
Link al Full Text: