×

A logic for reasoning about probabilities. (English) Zbl 0811.03014

Summary: We consider a language for reasoning about probability which allows us to make statements such as “the probability of \(E_ 1\) is less than \({1\over 3}\)” and “the probability of \(E_ 1\) is at least twice the probability of \(E_ 2\)”, where \(E_ 1\) and \(E_ 2\) are arbitrary events. We consider the case where all events are measurable (i.e., represent measurable sets) and 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) Nilsson’s probabilistic logic. As we show elsewhere, the general (nonmeasurable) case corresponds precisely to replacing probability measures by Dempster-Shafer belief functions. In both cases, we provide a complete axiomatization and show that the problem of deciding satisfiability is NP-complete, no worse than that of propositional logic. As a tool for proving our complete axiomatizations, we give a complete axiomatization for reasoning about Boolean combinations of linear inequalities, which is of independent interest. This proof and others make crucial use of results from the theory of linear programming. We then extend the language to allow reasoning about conditional probability and show that the resulting logic is decidable and completely axiomatizable, by making use of the theory of real closed fields.

MSC:

03B48 Probability and inductive logic
68T27 Logic in artificial intelligence
68Q25 Analysis of algorithms and problem complexity
03B25 Decidability of theories and sets of sentences
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abadi, M.; Halpern, J. Y., Decidability and expressiveness for first-order logics of probability, (Proceedings, 30th IEEE Symposium on Foundations of Computer Science (1989)), 148-153
[2] Bacchus, F., Representing and Reasoning with Probabilistic Knowledge, (Ph.D. thesis (1988), University of Alberta), also issued as Waterloo Unviersity Technical Report CS-88-31
[3] Berman, L., The complexity of logical theories, Theoret. Comput. Sci., 11, 71-77 (1980) · Zbl 0475.03017
[4] Ben-Or, M.; Kozen, D.; Reif, J., The complexity of elementary algebra and geometry, J. Comput. System Sci., 32, No. 1, 251-264 (1986) · Zbl 0634.03031
[5] Canny, J. F., Some algebraic and geometric computations in PSPACE, (Proceedings, 20th ACM Symposium on Theory of Computing (1988)), 460-467
[6] Carnap, R., Logical Foundations of Probability (1950), Univ. of Chicago Press: Univ. of Chicago Press Chicago · Zbl 0040.07001
[7] Chvátal, V., Linear Programming (1983), Freeman: Freeman San Francisco · Zbl 0318.05002
[8] Dempster, A. P., A generalization of Bayesian inference, J. Roy. Statist. Soc. Ser. B, 30, 205-247 (1968) · Zbl 0169.21301
[9] Enderton, H. B., A Mathematical Introduction to Logic (1972), Academic Press: Academic Press San Diego, CA · Zbl 0298.02002
[10] Farkas, J., Theorie der enfachen ungleichungen, J. Reine Angew. Math., 124, 1-27 (1902) · JFM 32.0169.02
[11] Feller, W., (An Introduction to Probability Theory and Its Applications, Vol. 1 (1957), Wiley: Wiley New York) · Zbl 0077.12201
[12] Feldman, Y., A decidable propositional probabilistic dynamic logic with explicit probabilities, Inform. and Control, 63, 11-38 (1984) · Zbl 0592.68031
[13] Fagin, R.; Halpern, J. Y., Reasoning about knowledge and probability: Preliminary report, (Vardi, M. Y., Proceedings, Second Conference on Theoretical Aspects of Reasoning about Knowledge (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 277-293 · Zbl 0699.03010
[14] Fagin, R.; Halpern, J. Y., Uncertainty, belief, and probability, (Proceedings, Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89). Proceedings, Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89), IBM Research Report RJ 6191 (1989)), 1161-1167, April 1988
[15] Fagin, R.; Halpern, J. Y.; Megiddo, N., A logic for reasoning about probabilities, (Proceedings, 3rd IEEE Symposium on Logic in Computer Science (1988)), 277-291
[16] Fourier, J. B.J., Solution d’une question particulière du calcul des inégalités, Nouveau Bull. Sci. Soc. Philomathique Paris, 99-100 (1826)
[17] Fischer, M. J.; Rabin, M. O., Super-exponential complexity of Presburger arithmetic, (Karp, R. M., Complexity of Computation, SIAM-AMS Proceedings, Vol. 7 (1974)), 27-42 · Zbl 0319.68024
[18] Gaifman, H., Concerning measures in first order calculi, Israel J. Math., 2, 1-18 (1964) · Zbl 0192.03302
[19] Gaifman, H., A theory of higher order probabilities, (Halpern, J. Y., Theoretical Aspects of Reasoning about Knowledge: Proceedings, 1986 Conference (1986), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 275-292
[20] Guggenheimer, H.; Freedman, R. S., Foundations of probabilistic logic, (Proceedings, Tenth International Joint Conference on Artificial Intelligence (IJCAI-87) (1987)), 939-941
[21] Georgakopoulos, G.; Kavvadias, D.; Papadimitriou, C. H., Probabilistic satisfiability, J. Complexity, 4, No. 1, 1-11 (1988) · Zbl 0647.68049
[22] Hall, M., Combinatorial Theory (1967), Ginn (Blaisdell): Ginn (Blaisdell) Boston · Zbl 0196.02401
[23] Halmos, P., Measure Theory (1950), Van Nostrand: Van Nostrand Princeton, NJ · Zbl 0040.16802
[24] Halpern, J. Y., An analysis of first-order logics of probability, (Proceedings, Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89) (1989)), 1375-1381 · Zbl 0875.78012
[25] Haddawy, P.; Frisch, A. M., Convergent deduction for probabilistic logic, (Proceedings, Third AAAI Uncertainty in Artificial Intelligence Workshop (1987)) · Zbl 0809.03016
[26] Hoover, D. N., Probability logic, Ann. of Math. Logic, 14, 287-313 (1978) · Zbl 0394.03033
[27] Halpern, J. Y.; Rabin, M. O., A logic to reason about likelihood, Artificial Intell., 32, No. 3, 379-405 (1987) · Zbl 0621.03011
[28] Halpern, J. Y.; Tuttle, M. R., Knowledge, probability, and adversaries, (Proceedings, 8th ACM Symposium on Principles of Distributed Computing (1989)), 103-118 · Zbl 0783.68120
[29] Kavvadias, D., An Algorithmic Approach to Probabilistic Logic, (Ph.D. thesis (1988), Patras University)
[30] Keisler, H. J., Probability quantifiers, (Barwise, J.; Feferman, S., Model-Theoretic Logics (1985), Springer-Verlag: Springer-Verlag New York/Berlin), 509-556
[31] Kozen, D., Probabilistic PDL, J. Comput. System Sci., 30, 162-178 (1985) · Zbl 0575.03013
[32] Kuhn, H. W., Solvability and consistency for linear equations and inequalities, Amer. Math. Monthly, 63, 217-232 (1956) · Zbl 0070.25001
[33] Lehmann, D.; Shelah, S., Reasoning about time and chance, Inform. and Control, 53, 165-198 (1982) · Zbl 0523.03016
[34] Lukasiewicz, J., Logical foundations of probability theory, (Berkowski, L., Lukasiewicz Selected Works (1970), North-Holland: North-Holland Amsterdam), 16-43
[35] Mendelson, E., Introduction to Mathematical Logic (1964), Van Nostrand: Van Nostrand Princeton, NJ · Zbl 0192.01901
[36] Motzkin, T. S., The assignment problem, (Curtiss, J. H., Numerical Analysis. Numerical Analysis, Proceedings of Symposia in Applied Mathematics, Vol. VI (1956), McGraw-Hill: McGraw-Hill New York), 109-125 · Zbl 0071.24803
[37] Nilsson, N., Probabilistic logic, Artificial Intell., 28, 71-87 (1986) · Zbl 0589.03007
[38] Nutter, J. T., Uncertainty and probability, (Proceedings, Tenth International Joint Conference on Artificial Intelligence (IJCAI-87) (1987)), 373-379
[39] Rota, G. C., On the foundations of combinatorial theory, I, Theory of Möbius functions, Z. Wahrsch. Verw. Gebiete, 2, 340-368 (1964) · Zbl 0121.02406
[40] Royden, H. L., Real Analysis (1964), Macmillan Co: Macmillan Co New York · Zbl 0197.03501
[41] Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley: Wiley New York · Zbl 0665.90063
[42] Shafer, G., A Mathematical Theory of Evidence (1976), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ · Zbl 0359.62002
[43] Shoenfield, J. R., Mathematical Logic (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0155.01102
[44] Tarski, A., A Decision Method for Elementary Algebra and Geometry (1951), Univ. of California Press: Univ. of California Press Berkeley · Zbl 0044.25102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.