Logic for reasoning about probabilities.

Abstract

A language for reasoning about probability is considered that allows statements such as 'the probability of E1 is less than 1/3' and 'the probability of E1 is at least twice the probability of E 2', where E1 and E2 are arbitrary events. The case is treated in which all events are measurable (i.e., represent measurable sets), as well as the more general case, which is also of interest in practice, where they may not be measurable. The measurable case is essentially a formalization of (the propositional fragment of) N. Nilson's (1986) probabilistic logic, while the general (nonmeasurable) case corresponds precisely to replacing probability functions by Dempster-Shafer belief functions. In both cases, an elegant complete axiomization is provided, and it is shown that the problem of deciding satisfiability is NP-complete.