Abstract We provide a logical framework in which a resource-bounded agent can be seen to perform approximations of probabilistic reasoning. Our main results read as follows. First, we identify the conditions under which propositional probability functions can be approximated by a hierarchy of depth-bounded belief functions. Second, we show that under rather palatable restrictions, our approximations of probability lead to uncertain reasoning which, under the usual assumptions in the field, qualifies as tractable.

Depth-Bounded Boolean Logics (DBBL for short) are well-understood frameworks to model rational agents equipped with limited deductive capabilities. These Logics use a parameter k>=0 to limit the amount of virtual information, i.e., the information that the agent may temporarily assume throughout the deductive process. This restriction brings several advantageous properties over classical Propositional Logic, including polynomial decision procedures for deducibility and refutability. Inspired by DBBL, we propose a limited-depth version of the popular ASP system \clingo, tentatively dubbed k-lingo after the bound k on virtual information. We illustrate the connection between DBBL and ASP through examples involving both proof-theoretical and implementative aspects. The paper concludes with some comments on future work, which include a computational complexity characterization of the system, applications to multi-agent systems and feasible approximations of probability functions.

This paper introduces and investigates Depth-bounded Belief functions, a logic-based representation of quantified uncertainty. Depth-bounded Belief functions are based on the framework of Depth-bounded Boolean logics [4], which provide a hierarchy of approximations to classical logic. Similarly, Depth-bounded Belief functions give rise to a hierarchy of increasingly tighter lower and upper bounds over classical measures of uncertainty. This has the rather welcome consequence that “higher logical abilities” lead to sharper uncertainty quantification. In particular, our main results identify the conditions under which Dempster-Shafer Belief functions and probability functions can be represented as a limit of a suitable sequence of Depth-bounded Belief functions.

We provide a standard completeness proof which uniformly applies to a large class of axiomatic extensions of Involutive Monoidal T-norm Logic (IMTL). In particular, we identify sufficient conditions on the proof calculi which ensure density elimination and then standard completeness. Our argument contrasts with all previous approaches for involutive logics which are logic-specific.