×

zbMATH — the first resource for mathematics

Possibilistic logic: a retrospective and prospective view. (English) Zbl 1076.68084
Summary: Possibilistic logic is a weighted logic introduced and developed since the mid-1980s, in the setting of artificial intelligence, with a view to develop a simple and rigorous approach to automated reasoning from uncertain or prioritized incomplete information. Standard possibilistic logic expressions are classical logic formulas associated with weights, interpreted in the framework of possibility theory as lower bounds of necessity degrees. Possibilistic logic handles partial inconsistency since an inconsistency level can be computed for each possibilistic logic base. Logical formulas with a weight strictly greater than this level are immune to inconsistency and can be safely used in deductive reasoning. This paper first recalls the basic features of possibilistic logic, including information fusion operations. Then, several extensions that mainly deal with the nature and the handling of the weights attached to formulas, are suggested or surveyed: the leximin-based comparison of proofs, the use of partially ordered scales for the weights, or the management of fuzzily restricted variables. Inference principles that are more powerful than the basic possibilistic inference in case of inconsistency are also briefly considered. The interest of a companion logic, based on the notion of guaranteed possibility functions, and working in a way opposite to the one of usual logic, is also emphasized. Its joint use with standard possibilistic logic is briefly discussed. This position paper stresses the main ideas only and refers to previous published literature for technical details.

MSC:
68T37 Reasoning under uncertainty in the context of artificial intelligence
68T27 Logic in artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] T. Alsinet, Logic programming with fuzzy unification and imprecise constants: possibilistic semantics and automated deduction, Ph.D. Thesis, Technical University of Catalunya, Barcelona, 2001.
[2] T. Alsinet, L. Godo, A complete calculus for possibilistic logic programming with fuzzy propositional variables, Proc. 16th Conf. on Uncertainty in Artificial Intelligence (UAI’00), Stanford, CA, Morgan Kaufmann, San Francisco, CA, 2000, pp. 1-10.
[3] T. Alsinet, L. Godo, S. Sandri, On the semantics and automated deduction for PLFC, a logic of possibilistic uncertainty and fuzziness, Proc. 15th Conf. on Uncertainty in Artificial Intelligence, (UAI’99), Stockholm, Sweden, Morgan Kaufmann, San Francisco, CA, 1999, pp. 3-20.
[4] Alsinet, T.; Godo, L.; Sandri, S., Two formalisms of extended possibilistic logic programming with context-dependent fuzzy unificationa comparative description, Electron. notes in theoret. comput. sci., 66, 5, (2002) · Zbl 1270.68058
[5] Bacchus, F., Representing and reasoning with probabilistic knowledge, (1990), M.I.T. Press Cambridge, MA
[6] S. Benferhat, C. Cayrol, D. Dubois, J. Lang, H. Prade, Inconsistency management and prioritized syntax-based entailment, Proc. 13th Internat. Joint Conf. on Artificial Intelligence (IJCAI’93), Chambéry, August 28-September 3, 1993, pp. 640-645.
[7] Benferhat, S.; Dubois, D.; Fargier, H.; Prade, H., Decision, nonmonotonic reasoning and possibilistic logic, (), 333-358 · Zbl 0979.68113
[8] Benferhat, S.; Dubois, D.; Garcia, L.; Prade, H., On the transformation between possibilistic logic bases and possibilistic causal networks, Internat. J. approx. reason., 29, 2, 135-173, (2002) · Zbl 1015.68204
[9] S. Benferhat, D. Dubois, S. Kaci, H. Prade, Encoding information fusion in possibilistic logic: a general framework for rational syntactic merging, Proc. 14th European Conf. on Artificial Intelligence (ECAI2000), 2000, IOS Press, Berlin, pp. 3-7.
[10] S. Benferhat, D. Dubois, S. Kaci, H. Prade, Graphical readings of possibilistic logic bases, Proc. 17th Conf. on Uncertainty in Artificial Intelligence (UAI’01), Seattle, August 2-5, 2001, Morgan Kaufmann, San Francisco, CA, 2001, pp. 24-31.
[11] S. Benferhat, D. Dubois, S. Kaci, H. Prade, Bridging logical, comparative and graphical possibilistic representation frameworks, Proc. 6th European Conf. on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU-01, Toulouse, September 19-21, 2001, Lecture Notes in Artificial Intelligence, Vol. 2143, Springer, Berlin, 2001, pp. 422-431. · Zbl 1001.68573
[12] S. Benferhat, D. Dubois, S. Kaci, H. Prade, Bipolar representation and fusion of preferences in the possibilistic logic framework, Proc. 8th Internat. Conf. on Principles of Knowledge Representation and Reasoning, KR’02, Toulouse, France, Morgan Kaufmann, San Francisco, CA, 2002, pp. 421-432.
[13] S. Benferhat, D. Dubois, J. Lang, H. Prade, A. Saffiotti, P. Smets, A general approach for inconsistency handling and merging information in prioritized knowledge bases, Proc. 6th Internat. Conf. on Principles of Knowledge Representation and Reasoning, Trento, Italy, Morgan Kaufmann, San Francisco, CA, pp. 466-477, 1998.
[14] S. Benferhat, D. Dubois, H. Prade, Representing default rules in possibilistic logic, Proc. 3rd Internat. Conf. on Principles of Knowledge Representation and Reasoning (KR’92), Cambridge, MA, Morgan Kaufmann, San Francisco, CA, 1992, pp. 673-684.
[15] Benferhat, S.; Dubois, D.; Prade, H., Nonmonotonic reasoning, conditional objects and possibility theory, Artif. intell. J., 92, 259-276, (1997) · Zbl 1017.68539
[16] Benferhat, S.; Dubois, D.; Prade, H., Some syntactic approaches to the handling of inconsistent knowledge basesa comparative study—part 1: the flat case, Studia logica, 58, 17-45, (1997) · Zbl 0867.68100
[17] Benferhat, S.; Dubois, D.; Prade, H., Practical handling of exception-tainted rules and independence information in possibilistic logic, Appl. intell., 9, 101-127, (1998)
[18] Benferhat, S.; Dubois, D.; Prade, H., From semantic to syntactic approaches to information combination in possibilistic logic, (), 141-161 · Zbl 0898.68079
[19] Benferhat, S.; Dubois, D.; Prade, H., Some syntactic approaches to the handling of inconsistent knowledge bases: a comparative study. part 2: the prioritized case, (), 473-511 · Zbl 0930.68149
[20] Benferhat, S.; Dubois, D.; Prade, H., An overview of inconsistency-tolerant inferences in prioritized knowledge bases, (), 395-417 · Zbl 0942.68722
[21] S. Benferhat, D. Dubois, H. Prade, Kalman-like filtering and updating in a possibilistic setting, Proc. 14th European Conf. on Artificial Intelligence (ECAI 2000), 2000, IOS Press, Berlin, pp. 8-12.
[22] Benferhat, S.; Dubois, D.; Prade, H., Towards a possibilistic logic handling of preferences, Appl. intell., 14, 303-317, (2001) · Zbl 0986.91006
[23] Benferhat, S.; Dubois, D.; Prade, H.; Williams, M.A., A practical approach to revising prioritized knowledge bases, Studia logica, 70, 105-130, (2002) · Zbl 1004.68165
[24] S. Benferhat, S. Lagrue, O. Papini, Reasoning with partially ordered information in a possibilistic logic framework, Proc. 9th Internat. Conf. on Information Processing and Management of Uncertainty in Knowledge-based Systems, Annecy, 2003, pp. 1047-1052. (Revised version, Fuzzy Sets and Systems, this issue.) · Zbl 1076.68080
[25] P. Besnard, J. Lang, Possibility and necessity functions over non-classical logics, in: R. Lopez de Mantaras, D. Poole (Eds.), Proc. 10th Conf. on Uncertainty in Artificial Intelligence, Morgan Kaufmann, San Francisco, CA, 1994, pp. 69-76.
[26] Biacino, L.; Gerla, G., Generated necessities and possibilities, Internat. J. intell. systems, 7, 445-454, (1992) · Zbl 0761.68090
[27] Bistarelli, S.; Fargier, H.; Montanari, U.; Rossi, F.; Schiex, T.; Verfaillie, G., Semiring-based CSPs and valued cspsframeworks, properties, and comparison, Constraints, 4, 199-240, (1999) · Zbl 0946.68143
[28] L. Boldrin, A substructural connective for possibilistic logic, in: C. Froidevaux, J. Kohlas (Eds.), Symbolic and Quantitative Approaches to Reasoning and Uncertainty, (Proc. European Conf. ECSQARU’95) Springer, Fribourg, pp. 60-68.
[29] Boldrin, L.; Sossai, C., An algebraic semantics for possibilistic logic, (), 27-35
[30] Boldrin, L.; Sossai, C., Local possibilistic logic, J. appl. non-classical logics, 7, 309-333, (1997) · Zbl 0886.03018
[31] Boldrin, L.; Sossai, C., Truth-functionality and measure-based logics, (), 351-380 · Zbl 0943.03022
[32] Boutilier, C., Modal logics for qualitative possibility theory, Internat. J. approx. reason., 10, 173-201, (1994) · Zbl 0802.68144
[33] G. Brewka, Preferred subtheories: an extended logical framework for default reasoning, Proc. 11th Internat. Joint Conf. on Artificial Intelligence (IJCAI’89), Detroit, 1989, pp. 1043-1048. · Zbl 0713.68053
[34] Coletti, G.; Scozzafava, R., Probabilistic logic in a coherent setting, (2002), Kluwer Academic Publishers Dordrecht · Zbl 1005.60007
[35] L.M. De Campos, J.F. Huete, Independence concepts in possibility theory. Part I: Fuzzy Sets and Systems, 103 (1999), 127-152; Part II: Fuzzy Sets and Systems, 103 487-506. · Zbl 0951.68150
[36] Dubois, D., Belief structures, possibility theory and decomposable measures on finite sets, Comput. artif. intell., 5, 403-416, (1986) · Zbl 0657.60006
[37] Dubois, D.; Hajek, P.; Prade, H., Knowledge-driven versus data-driven logics, J. logic language inform., 9, 65-89, (2000) · Zbl 0942.03023
[38] D. Dubois, J. Lang, H. Prade, Theorem proving under uncertainty—a possibility theory-based approach, Proc. 10th Internat. Joint Conf. on Artificial Intelligence, Milano, Italy, 1987, pp. 984-986.
[39] Dubois, D.; Lang, J.; Prade, H., A possibilistic assumption-based truth maintenance system with uncertain justifications and its application to belief revision, (), 87-106
[40] Dubois, D.; Lang, J.; Prade, H., Timed possibilistic logic, Fund. inform., XV, 3-4, 211-237, (1991) · Zbl 0745.03019
[41] D. Dubois, J. Lang, H. Prade, Towards possibilistic logic programming, in: K. Furukawa (Ed.), Proc. Internat. Conf. on Logic Programming (ICLP’91), Paris, MIT Press, Cambridge, MA, 1991, pp. 581-595.
[42] Dubois, D.; Lang, J.; Prade, H., Inconsistency in possibilistic knowledge bases—to live or not live with it, (), 335-351
[43] D. Dubois, J. Lang, H. Prade, Dealing with multi-source information in possibilitic logic, Proc. 10th European Conf. on Artificial Intelligence (ECAI’92), Vienna, Austria, Wiley, New York, 1992, pp. 38-42.
[44] D. Dubois, J. Lang, H. Prade, Possibilistic logic, in: D.M. Gabbay, et al. (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. 3, Oxford University Press, Oxford, UK, 1994, pp. 439-513.
[45] Dubois, D.; Lang, J.; Prade, H., Automated reasoning using possibilistic logicsemantics, belief revision and variable certainty weights, IEEE trans. data & knowledge eng., 6, 64-71, (1994)
[46] D. Dubois, J. Lang, H. Prade, Handling uncertainty, context, vague predicates, and partial inconsistency in possibilistic logic, in: D. Driankov, P.W. Eklund, A.L. Ralescu (Eds.), Fuzzy Logic and Fuzzy Control (Proc. IJCAI’91 Workshop) Vol. 833, Springer, Berlin, 1994, pp. 45-55.
[47] Dubois, D.; Le Berre, D.; Prade, H.; Sabbadin, R., Using possibilistic logic for modeling qualitative decisionatms-based algorithms, Fund. inform., 37, 1-30, (1999) · Zbl 0930.68146
[48] D. Dubois, H. Prade, The management of uncertainty in expert systems: the possibilistic approach, in: Operational Research’84, J.P. Brans (Ed.), Proc. 10th Triennial IFORS Conf., Washington, DC, North-Holland, Amsterdam, 1984, pp. 949-964.
[49] Dubois, D.; Prade, H., Necessity measures and the resolution principle, IEEE trans. systems, man cybernet., 17, 474-478, (1987) · Zbl 0643.94053
[50] Dubois, D.; Prade, H., Possibility theory, (1988), Plenum Press New York
[51] Dubois, D.; Prade, H., Resolution principles in possibilistic logic, Internat. J. approx. reason., 4, 1-21, (1990) · Zbl 0697.68083
[52] Dubois, D.; Prade, H., Epistemic entrenchment and possibilistic logic, Artif. intell., 50, 223-239, (1991) · Zbl 0749.03019
[53] D. Dubois, H. Prade, Possibility theory as a basis for preference propagation in automated reasoning, Proc. 1st IEEE Internat. Conf. on Fuzzy Systems (FUZZ-IEEE’92), San Diego, CA, 1992, pp. 821-832.
[54] Dubois, D.; Prade, H., Conditional objects, possibility theory and default rules, (), 311-346 · Zbl 0741.68091
[55] Dubois, D.; Prade, H., Combining hypothetical reasoning and plausible inference in possibilistic logic, J. multiple valued logic, 1, 219-239, (1996) · Zbl 0892.68094
[56] Dubois, D.; Prade, H., A synthetic view of belief revision with uncertain inputs in the framework of possibility theory, Internat. J. approx. reason., 17, 295-324, (1997) · Zbl 0935.03026
[57] D. Dubois, H. Prade, Valid or complete information in databases—a possibility theory-based analysis, in: A. Hameurlain, A.M. Tjoa (Eds.), Database and Experts Systems Applications (Proc. 8th Internat. Conf. DEXA’97), Toulouse, Lecture Notes in Computer Science, Vol. 1308, Springer, Berlin, 1997, pp. 603-612.
[58] D. Dubois, H. Prade, Possibility theory: Qualitative and quantitative aspects, in: D.M. Gabbay, P. Smets (Eds.), Handbook of Defeasible Reasoning and Uncertainty Management Systems, Vol. 1, Kluwer Academic, Dordrecht, 1998, pp. 169-226. · Zbl 0924.68182
[59] Dubois, D.; Prade, H., Possibility theory, probability theory and multiple-valued logicsa clarification, Ann. math. artif. intell., 32, 35-66, (2001) · Zbl 1314.68309
[60] Dubois, D.; Prade, H.; Sandri, S., A possibilistic logic with fuzzy constants and fuzzily restricted quantifiers, (), 69-90
[61] D. Dubois, H. Prade, P. Smets, “Not impossible“ vs. “guaranteed possible” in fusion and revision, Proc. 6th European Conf. on Symbolic and Quantitative Approaches to Reasoning with Uncertainty ECSQARU-01, Toulouse, Lecture Notes in Artificial Intelligence, Vol. 2143, Springer, Berlin, 2001, pp. 522-531. · Zbl 1001.68547
[62] Esteva, F.; Garcia, P.; Godo, L., Relating and extending semantical approaches to possibilistic reasoning, Internat. J. approx. reason., 10, 4, 311-344, (1994) · Zbl 0815.68094
[63] Fariñas del Cerro, L.; Herzig, A., A modal analysis of possibility theory, (), 11-18 · Zbl 0793.03019
[64] Fariñas del Cerro, L.; Herzig, A.; Lang, J., From ordering-based nonmonotonic reasoning to conditional logics, Artif. intell., 66, 375-393, (1994) · Zbl 0807.68083
[65] Fulvio Monai, F.; Chehire, T., Possibilistic assumption-based truth maintenance system, validation in a data fusion application, (), 83-91
[66] D. Gabbay, Labelled Deductive Systems, Vol. 1, Oxford University Press, Oxford, UK, 1996. · Zbl 0858.03004
[67] Gärdenfors, P., Knowledge in flux, (1988), MIT Press Cambridge, MA · Zbl 1229.03008
[68] J. Gebhardt, R. Kruse, Background and perspectives of possibilistic graphical models, in: Qualitative and Quantitative Practical Reasoning (Proc. ECSQARU-FAPR-97), Lecture Notes in Artificial Intelligence, Vol. 1244, Springer, Berlin, 1997, pp. 108-121.
[69] Gilio, A., Probabilistic reasoning under coherence in system P, Ann. math. artif. intell., 34, 5-34, (2002) · Zbl 1014.68165
[70] Hajek, P., A qualitative fuzzy possibilistic logic, Internat. J. approx. reason., 12, 1-19, (1994) · Zbl 0819.03017
[71] Hajek, P., Metamathematics of fuzzy logic, (1998), Kluwer Academic Publishers Dordrecht, The Netherlands · Zbl 0937.03030
[72] Hajek, P.; Godo, L.; Esteva, F., Fuzzy logic and probability, (), 237-244
[73] Hajek, P.; Harmancova, D.; Esteva, F.; Garcia, P.; Godo, L., On modal logics for qualitative possibility in a fuzzy setting, (), 278-285
[74] Halpern, J., An analysis of first-order logics of probability, Artif. intell., 46, 311-350, (1990) · Zbl 0723.03007
[75] Halpern, J.; Pucella, R., A logic for reasoning about upper probabilities, J. AI res., 17, 57-81, (2002) · Zbl 1029.68134
[76] Hisdal, E., Conditional possibilities—independence and non-interactivity, Fuzzy sets and systems, 1, 283-297, (1978) · Zbl 0393.94050
[77] Hollunder, B., An alternative proof method for possibilistic logic and its application to terminological logics, Internat. J. approx. reason., 12, 85-109, (1995) · Zbl 0814.68120
[78] Jaeger, M., Automatic derivation of probabilistic inference rules, Internat. J. approx. reason., 28, 1-22, (2001) · Zbl 0984.68157
[79] J. Jahnke, M. Heitbreber, Design recovery of legacy database applications, Proc. IEEE Internat. Conf. on Fuzzy Systems, Anchorage, Al, 1998, pp. 1332-1337.
[80] Jahnke, J.; Walenstein, A., Evaluating theories for managing imperfect knowledge in human centric database reengineering environments, Internat. J. software eng. knowledge eng., 12, 77-102, (2002)
[81] S. Konieczny, J. Lang, P. Marquis, Distance-based merging: a general framework and some complexity results, Proc. 8th Internat. Conf. on Principles of Knowledge Representation and Reasoning (KR2002), Toulouse, Morgan Kaufmann, San Francisco, CA, 2002, pp. 97-108.
[82] S. Konieczny, R. Pino Pérez, On the logic of merging, Proc. 1998 Conf. on Knowledge Representation and Reasoning Principles (KR-98), Trento. Morgan Kaufmann, San Francisco, CA, 1998, pp. 488-498.
[83] Lafage, C.; Lang, J.; Sabbadin, R., A logic of supporters, (), 381-392
[84] Lang, J., Possibilistic logic as a logical framework for MIN-MAX discrete optimization problems, (), 112-126 · Zbl 0788.68134
[85] J. Lang, Logique Possibiliste: Aspects Formels, Déduction Automatique et Applications, Thèse de Doctorat, Université Paul Sabatier, Toulouse, 1991.
[86] Lang, J., Possibilistic logic: complexity and algorithms, (), 179-220 · Zbl 0984.03022
[87] J. Lang, D. Dubois, H. Prade, A logic of graded possibility and certainty coping with partial inconsistency, Proc. 7th Conf. on Uncertainty in Artificial Intelligence, UCLA, Los Angeles, July 13-15, 1991, Morgan Kaufmann, San Francisco, CA, 1991, pp. 188-196.
[88] Lau, R.; ter Hofstede, A.H.M.; Bruza, P.D., Maxi-adjustment and possibilistic deduction for adaptive information agents, J. appl. non-classical logics, 11, 1-2, 169-201, (2001) · Zbl 1091.68602
[89] Lee, R.C.T., Fuzzy logic and the resolution principle, J. ACM, 19, 109-119, (1972) · Zbl 0245.02020
[90] Lehmann, D.; Magidor, M., What does a conditional knowledge base entail?, Artif. intell. J., 55, 1-60, (1992) · Zbl 0762.68057
[91] S. Lehmke, Logics which allow degrees of truth and degrees of validity, Ph.D. Dissertation, Universitât Dortmund, Germany, 2001. · Zbl 1005.03029
[92] Lehmke, S., Degrees of truth and degrees of validity, (), 192-237 · Zbl 1005.03029
[93] Lewis, D.L., Counterfactuals, (1973), Basil Blackwell Oxford
[94] Lewis, D.L., Probabilities of conditionals and conditional probabilities, Philos. rev., 85, 297-315, (1976)
[95] Liau, C.J., Possibilistic residuated implications logics with applications, Internat. J. uncertainty, fuzziness, and knowledge-based systems, 6, 365-385, (1998) · Zbl 1087.68665
[96] Liau, C.J., On the possibility theory-based semantics for logics of preference, Internat. J. approx. reason., 20, 173-190, (1999) · Zbl 0936.03021
[97] Liau, C.J.; Lin, I.P., Possibilistic reasoninga mini-survey and uniform semantics, Artif. intell., 88, 163-193, (1996) · Zbl 0907.68180
[98] Lukasiewicz, T., Local probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events, Internat. J. approx. reason., 21, 23-61, (1999) · Zbl 0961.68135
[99] J. Pavelka, On fuzzy logic, Zeitschr. f. Math. Logik und Grundlagen d. Math. Part I: 25 (1979) 45-52; Part II: 119-134; Part III: 447-464.
[100] H. Prade, Modèles Mathématiques de l’Imprécis et de l’Incertain en vue d’Applications au Raisonnement Naturel, These de Doctorat d’Etat, Université Paul Sabatier, 1982.
[101] Rescher, N., Plausible reasoning, (1976), Van Gorcum Amsterdam
[102] Rescher, N.; Manor, R., On inference from inconsistent premises, Theory and decision, 1, 179-219, (1970) · Zbl 0212.31103
[103] Sangüesa, R.; Cortés, U.; Gisolfi, A., A parallel algorithm for building possibilistic causal networks, Internat. J. approx. reason., 18, 251-278, (1998) · Zbl 0951.68154
[104] Schiex, T., Possibilistic constraint satisfaction problems or how to handle soft constraints, (), 268-275
[105] Wong, O.; Lau, R., Possibilistic reasoning for intelligent payment agents, (), 170-180 · Zbl 0986.68723
[106] Zadeh, L., Fuzzy logic and approximate reasoning, Synthese, 30, 407-428, (1975) · Zbl 0319.02016
[107] Zadeh, L., Fuzzy sets a basis for a theory of possibility, Fuzzy sets and systems, 1, 3-28, (1978) · Zbl 0377.04002
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.