Informational Semantics, Non-Deterministic Matrices and Feasible Deduction

https://doi.org/10.1016/j.entcs.2014.06.004Get rights and content
Under a Creative Commons license
open access

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.

Keywords

Classical Propositional Logic
Informational Semantics
Non-deterministic matrices
Computational Complexity
Natural Deduction
Semantic Tableaux

Cited by (0)

1

This paper elaborates on ideas and results stemming from my collaboration with Marcelo Finger, Luciano Floridi and Dov Gabbay. I wish to thank Maribel Fernandez and Marcelo Finger for inviting me to present this work at LSFA2013 and all the participants for the stimulating discussion.