clarke@csri.toronto.edu (Jim Clarke) (11/24/88)
AI/THEORY SEMINAR - Monday, November 28, 11 a.m. in Room PA 105 (PA = Pharmacy Building, 19 Russell Street) Joseph Y. Halpern IBM Almaden Research Centre "An Analysis of First-Order Logics of Probability" We consider two approaches to giving semantics to first-order logics of probability. The first approach puts a probability on the domain, and is appropriate for giving semantics to formulas involving statistical in- formation such as ``The probability that a (typical) bird flies is greater than .9.'' The second approach puts a probability on possible worlds, and is appropriate for giving semantics to formulas describing degrees of be- lief, such as ``The probability that Tweety (a particular bird) flies is greater than .9.'' The two approaches can be easily combined, allowing us to reason in a straightforward way about statistical information and de- grees of belief. We then consider issues of decidability and expressive- ness for the corresponding logics of probability. It turns out that it takes very little to make reasoning about probability highly undecidable. For example, when the probability is on the domain, if the language con- tains only unary predicates then the validity problem is decidable. Howev- er, if the language contains even one binary predicate, the validity prob- lem is even harder than the validity problem for full second order arith- metic with set variables (technically, it is Pi2_1 complete). This means it is certainly not axiomatizable. We do provide sound axiom systems that we show are complete for interesting subcases (for example, in the case that probability is on the domain and the language contains only unary predicates). This suggests that our axioms are powerful enough to enable us to carry out a great deal of interesting reasoning about probability. Finally, we show that, although the two approaches capture quite different intuitions about probability, there is a precise sense in which they are equi-expressive. The results on decidability are joint with Martin Abadi. -- Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4 (416) 978-4058 BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke