Third Annual IEEE Symposium on

Logic in Computer Science (LICS 1988)

Paper: A logic for reasoning about probabilities (at LICS 1988)

Authors: Ronald Fagin Joseph Y. Halpern Nimrod Megiddo


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 E2', where E 1 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


    author = 	 {Ronald Fagin and Joseph Y. Halpern and Nimrod Megiddo},
    title = 	 {A logic for reasoning about probabilities},
    booktitle =  {Proceedings of the Third Annual IEEE Symp. on Logic in Computer Science, {LICS} 1988},
    year =	 1988,
    editor =	 {Yuri Gurevich},
    month =	 {July}, 
    pages =      {410--421},
    location =   {Edinburgh, Scotland, UK}, 
    publisher =	 {IEEE Computer Society Press}