Depth-bounded Reasoning. Classical Propositional Logic

<p></p><p><span style=background-color: rgba(237 237 228 1); color: rgba(0 0 0 1)>The cost of reasoning i.e. the cognitive or computational effort required by non-ideal resource-bounded (human or artificial) agents in order to perform non-trivial inferences is a crucial issue in philosophy AI economics and cognitive (neuro)science. Accounting for this fundamental variable in modelling real-world reasoning and decision-making is one of the most important and difficult challenges in the theory of rationality. With this volume we are launching a series that under the general title of Logic and Bounded Rationality aims to create a community of researchers from several areas that wish to cooperate towards a systematic </span><em style=background-color: rgba(237 237 228 1); color: rgba(0 0 0 1)>logical</em><span style=background-color: rgba(237 237 228 1); color: rgba(0 0 0 1)> view of bounded rationality.</span></p><p></p><p><span style=background-color: rgba(237 237 228 1); color: rgba(0 0 0 1)>However a key stumbling block for any effort in this direction is that a basic component of many reasoning and decision making tasks namely </span><em style=background-color: rgba(237 237 228 1); color: rgba(0 0 0 1)>deductive reasoning in propositional logic</em><span style=background-color: rgba(237 237 228 1); color: rgba(0 0 0 1)> is computationally hard. Hence in this first volume of the series we offer a novel view of classical propositional logic. We present an informational semantics for the classical operators whose proof-theoretical presentation is a system of classical natural deduction that unlike Gentzen's and Prawitz's systems yields a simple way of measuring the depth of an inference. This approach leads to defining in a natural way a sequence of tractable depth-bounded deduction systems. As recent applications in formal argumentation and non-monotonic reasoning suggest our approach provides a plausible model for representing rational agents with increasing albeit limited computational resources.</span></p>