Approximation of Classical Logic via Depth Bounded Boolean Logics




Marcelo Finger,

Department of Computer Science, Cornell University

on leave from:
 Department of Computer Science, IME
 University of Sao Paulo

Monday, May 11, 2013
4:00pm 5130
Upson Hall



We present the general notion of approximations of logics and discuss our recent results.

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.

Joint work with Marcello D'Agostino and Dov Gabbay