NP-containment for the coherence test of assessments of conditional probability: a fuzzy logical approach. (English) Zbl 1110.03012

Summary: In this paper we investigate the problem of testing the coherence of an assessment of conditional probability following a purely logical setting. In particular we prove that the coherence of an assessment of conditional probability \(\chi\) can be characterized by means of the logical consistency of a suitable theory \(T_{\chi}\) defined on the modal-fuzzy logic \(FP_k(R\text{Ł}_\Delta)\) built up over the many-valued logic \(R\text{Ł}_\Delta\). Such modal-fuzzy logic was previously introduced by the author [Lect. Notes Comput. Sci. 3571, 714–725 (2005; Zbl 1109.03018)] in order to treat conditional probability by means of a list of simple probabilities following the well-known (smart) ideas exposed by J. Y. Halpern [“Lexicographic probability, conditional probability, and nonstandard probability”, in: Proceedings of the eighth conference on theoretical aspects of rationality and knowledge, 17–30 (2001)] and by G. Coletti and R. Scozzafava [Probabilistic logic in a coherent setting. Dordrecht: Kluwer (2003; Zbl 1040.03017)]. Roughly speaking, such logic is obtained by adding to the language of \(R\text{Ł}_\Delta\) a list of \(k\) modalities for “probably” and axioms reflecting the properties of simple probability measures. Moreover we prove that the satisfiability problem for modal formulas of \(FP_k(R\text{Ł}_\Delta)\) is NP-complete. Finally, as main result of this paper, we prove that the problem of establishing the coherence of rational assessments of conditional probability is NP-complete.


03B48 Probability and inductive logic
03B52 Fuzzy logic; logic of vagueness
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI


[1] Baaz, M.: Infinite-valued Gödel logics with 0-1-projections and relativizations. In: Hájek, P. (ed.) GÖDEL 96, LNL 6, pp. 23–33 Springer, Heidelberg (1996) · Zbl 0862.03015
[2] Buckley J. Fuzzy Probabilities. Physica, (2003)
[3] Cintula P. (2001). \({\Pi\frac12}\) propositional and predicate logicsFuzzy Sets Systems 124: 21–34 · Zbl 0994.03015
[4] Cintula P. (2003). Advances in the Ł{\(\Pi\)} and Ł \({\Pi\frac12}\) logics. Arch. Math. Logic 42: 449–468 · Zbl 1026.03017
[5] Chvátal V. (1983). Linear Programming. W. Freeman, San Francisco
[6] Cook S.A. and Reckhow R.A. (1979). The relative efficiency of propositional proof systems. J. Symbolic Logic 44(1): 33–50 · Zbl 0409.03010
[7] Coletti, G., Scozzafava, R.: Probabilistic logic in a coherent setting. Trends Logic 15 (2002) · Zbl 1005.60007
[8] Esteva F., Godo L. and Hájek P. (2000). Reasoning about probability using fuzzy logic. Neural Netw. World 10(5): 811–824
[9] Esteva F., Godo L. and Montagna F. (2001). Ł{\(\Pi\)} and Ł \({\Pi\frac12}\) : two complete fuzzy systems joining Łukasiewicz and Product logics. Arch. Mathe. Logic 40: 39–67 · Zbl 0966.03022
[10] Fagin R., Halpern Y. and Megiddo N. (1990). A logic for reasoning about probability. Inf. Comput. 87: 78–128 · Zbl 0811.03014
[11] Flaminio T.: A Zero-Layer Based Fuzzy Probabilistic Logic for Conditional Probability. Lecture Notes in Computer Science, vol. 3571. In: Godo, L. (ed.) 8th European Conference on Symbolic and Quantitative Approaches on Reasoning under Uncertainty ECSQARU’05. Barcelona (2005) · Zbl 1109.03018
[12] Flaminio T. and Montagna F. (2005). A logical and algebraic treatment of conditional probability. Arch. Math. Logic 44: 245–262 · Zbl 1064.03016
[13] Gallier J.H. (1986). Logic for Computer Science. Harper & Row, New York · Zbl 0605.03004
[14] Georgakopoulos G., Kavvalios D. and Papadimitriou C.H. (1998). Probabilistic satisfiability. J. Complex. 4: 1–11 · Zbl 0647.68049
[15] Gerla B. (2001). Rational Łukasiewicz logic and divisible MV-algebras. Neural Netw. Worlds 25: 1–13
[16] Gerla, B.: Many-valued logics of continuous t-norms and their functional representation. Ph.D. Thesis, University of Milan (2001)
[17] Marchioni, E., Godo, L.: A logic for reasoning about coherent conditional probability: a fuzzy modal logic approach. Lecture Notes in Artificial Intelligence, vol. 3229. In: Alferes, J.J., Leite, J. (eds.) 9th European Conference on Logics in Artificial Intelligence JELIA’04, pp. 213–225. Lisbon (2004) · Zbl 1111.68683
[18] Halpern, Y.J.: Lexicographic probability, conditional probability, and nonstandard probability. In: Proceedings of the Eighth Conference on Theoretical Aspects of Rationality and Knowledge, pp. 17–30 (2001)
[19] Hähnle, R.: Many valued logics and mixed integer programming. Ann. Math. Artif. Intell. 12, 3, 4:37–39 (1994)
[20] Hájek, P.: Metamathematics of Fuzzy Logic. Kluwer (1998) · Zbl 0937.03030
[21] Hájek P. and Tulipani S. (2001). Complexity of fuzzy probabilistic logics. Fundamenta Inf. 45: 207–213 · Zbl 0972.03025
[22] Mundici, D.: Averaging the truth-value in Łukasiewicz logic. Studia Logica 113–127 (1995) · Zbl 0836.03016
[23] Mundici, D., Riečan, B.: Probability on MV-algebras. In: Pap, E. (ed.) Chapter in Handbook of Measure Theory. North Holland, Amsterdam (2002)
[24] Paris, J.: The uncertain reasoner’s companion–a mathematical prospective. Cambridge Tracts in Theoretical Computer Science, vol. 39. Cambridge University Press (1994) · Zbl 0838.68104
[25] Kroupa, T.: Representation and extension of states on MV-algebras. Arch. Math. Logic (to appear) · Zbl 1101.06008
[26] Pretolani D. (2005). Probability logic and optimization SAT: the PSAT and CPA models. Ann. Math. and Artif. Intell. 43: 211–221 · Zbl 1075.68086
[27] Schrijver A. (1986). Theory of Linear and Integral Programming. Willey, New York · Zbl 0665.90063
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.