In this paper we set out to make a contribution towards the solution of the logical omniscience problem. We maintain that the problem can be properly solved by restricting the classical notion of logical consequence rather than by waiving closure of the propositional attitudes under logical consequence. We suggest that an interesting alternative solution could be based on Depth-Bounded Boolean Logics, a novel incremental approach to the characterization of classical propositional logic that construes it as the limit of an infinite sequence of weaker tractable logics. Agents committed to these logics can be seen as approximations to the idealized reasoning agent of standard epistemic, doxastic and information logic. The full decision problem for each of the approximating logics is solvable in polynomial time - although its complexity grows as we proceed along the approximation sequence - with no restriction to any particular syntactic fragment. Moreover, the meaning of the logical operators is the same for al l logics and is explained in purely informational terms - that is, in terms of informational interpretations of " true" and "false" - in such a way that the most basic inference principles of classical propositional logic, including disjunctive syllogism, are preserved throughout the sequence.

Tractable Depth Bounded Logics and the Problem of Logical Omniscience

D'AGOSTINO, Marcello
2010

Abstract

In this paper we set out to make a contribution towards the solution of the logical omniscience problem. We maintain that the problem can be properly solved by restricting the classical notion of logical consequence rather than by waiving closure of the propositional attitudes under logical consequence. We suggest that an interesting alternative solution could be based on Depth-Bounded Boolean Logics, a novel incremental approach to the characterization of classical propositional logic that construes it as the limit of an infinite sequence of weaker tractable logics. Agents committed to these logics can be seen as approximations to the idealized reasoning agent of standard epistemic, doxastic and information logic. The full decision problem for each of the approximating logics is solvable in polynomial time - although its complexity grows as we proceed along the approximation sequence - with no restriction to any particular syntactic fragment. Moreover, the meaning of the logical operators is the same for al l logics and is explained in purely informational terms - that is, in terms of informational interpretations of " true" and "false" - in such a way that the most basic inference principles of classical propositional logic, including disjunctive syllogism, are preserved throughout the sequence.
2010
9788876423475
Logical Omniscience; Depth Bounded Logics; Natural Deduction
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in SFERA 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: https://hdl.handle.net/11392/1387295
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact