DECIDABILITY AND EXPRESSIVENESS FOR 1ST-ORDER LOGICS OF PROBABILITY

被引:54
作者
ABADI, M [1 ]
HALPERN, JY [1 ]
机构
[1] IBM CORP,ALMADEN RES CTR,SAN JOSE,CA 95120
关键词
D O I
10.1006/inco.1994.1049
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider decidability and expressiveness issues for two first-order logics of probability. In one, the probability is on possible worlds, while in the other, it is on the domain. It turns out that in both cases it takes very little to make reasoning about probability highly undecidable. We show that when the probability is on the domain, if the language contains only unary predicates then the validity problem is decidable. However, if the language contains even one binary predicate, the validity problem is PI1(2) complete, as hard as elementary analysis with free predicate and function symbols. With equality in the language, even with no other symbol, the validity problem is at least as hard as that for elementary analysis, PI(infinity)1 hard. Thus, the logic cannot be axiomatized in either case. When we put the probability on the set of possible worlds, the validity problem is PI1(2) complete with as little as one unary predicate in the language, even without equality. With equality, we get PI(infinity)1 hardness with only a constant symbol. We then turn our attention to an analysis of what causes this overwhelming complexity. For example, we show that if we require rational probabilities then we drop from PI1(2) to PI1(1). In many contexts it suffices to restrict attention to domains of bounded size; fortunately, the logics are decidable in this case. Finally, we show that, although the two logics capture quite different intuitions about probability, there is a precise sense in which they are equi-expressive. (C) 1994 Academic Press, Inc.
引用
收藏
页码:1 / 36
页数:36
相关论文
共 28 条
[1]  
BACCHUS F, 1988, 4TH P WORKSH UNC ART, P15
[2]  
Bacchus F., 1990, REPRESENTING REASONI
[3]   THE COMPLEXITY OF ELEMENTARY ALGEBRA AND GEOMETRY [J].
BENOR, M ;
KOZEN, D ;
REIF, J .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1986, 32 (02) :251-264
[4]  
CARNAP R, 1950, LOGICAL F PROBABILIT
[5]  
Chang C. C., 1990, MODEL THEORY, V73
[6]  
Dreben B., 1979, DECISION PROBLEM SOL
[7]  
Enderton H. B., 2001, MATH INTRO LOGIC, V2nd ed
[8]   A LOGIC FOR REASONING ABOUT PROBABILITIES [J].
FAGIN, R ;
HALPERN, JY ;
MEGIDDO, N .
INFORMATION AND COMPUTATION, 1990, 87 (1-2) :78-128
[9]  
FELDMAN YA, 1984, J COMPUT SYST SCI, V28, P193, DOI 10.1016/0022-0000(84)90065-5
[10]  
FELDMAN YA, 1984, THESIS WEIZMANN I SC