Logic in Computer Science (LICS 1988)

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

Authors: Ronald Fagin Joseph Y. Halpern Nimrod Megiddo

Abstract

A language for reasoning about probability is considered that allows statements such as `the probability of E<sub>1</sub> is less than 1/3' and `the probability of E₁ is at least twice the probability of E₂', where E ₁ and E₂ 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

BibTeX

  @InProceedings{FaginHalpernMegiddo-Alogicforreasoninga,
    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}
  }