×

Nonmonotonic reasoning, preferential models and cumulative logics. (English) Zbl 0782.03012

Summary: Many systems that exhibit nonmonotonic behavior have been described and studied already in the literature. The general notion of nonmonotonic reasoning, though, has almost always been described only negatively, by the property it does not enjoy, i.e. monotonicity. We study here general patterns of nonmonotonic reasoning and try to isolate properties that could help us map the field of nonmonotonic reasoning by reference to positive properties. We concentrate on a number of families of nonmonotonic consequence relations, defined in the style of Gentzen. Both proof-theoretic and semantic points of view are developed in parallel. The former point of view was pioneered by Gabbay, while the latter has been advocated by Shoham. Five such families are defined and characterized by representation theorems, relating the two points of view. One of the families of interest, that of preferential relations, turns out to have been studied by E. W. Adams. The preferential models proposed here are a much stronger tool than Adams’ probabilistic semantics. The basic language used in this paper is that of propositional logic. The extension of our results to first-order predicate calculi and the study of the computational complexity of the decision problems described in this paper will be treated in another paper.

MSC:

03B60 Other nonclassical logic
68T27 Logic in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adams, E. W., Probability and the logic of conditional, (Hintikka, J.; Suppes, P., Aspects of Inductive Logic (1966), North-Holland: North-Holland Amsterdam) · Zbl 0202.30001
[2] Adams, E. W., The Logic of Conditionals (1975), Reidel: Reidel Dordrecht, Netherlands · Zbl 0202.30001
[3] Avron, A., Simple consequence relations, (LFCS Report Series 87-30 (1987), Department of Computer Science, University of Edinburgh) · Zbl 0733.03007
[4] Burgess, J. P., Quick completeness proofs for some logics of conditionals, Notre Dame J. Formal Logic, 22, 76-84 (1981) · Zbl 0416.03020
[5] Clark, L., Negation as failure, (Gallaire, H.; Minker, J., Logics and Data Bases (1978), Plenum: Plenum New York), 293-322
[6] Delgrande, J. P., A first-order logic for prototypical properties, Artificial Intelligence, 33, 105-130 (1987) · Zbl 0654.68106
[7] Delgrande, J. P., An approach to default reasoning based on a first-order conditional logic: Revised report, Artificial Intelligence, 36, 63-90 (1988) · Zbl 0646.03015
[8] Etherington, D. W.; Mercer, R. E.; Reiter, R., On the adequacy of predicate circumscription for closed-world reasoning, Comput. Intell., 1, 11-15 (1985)
[9] Freund, M.; Lehmann, D., Faithful models and preferential inference operations, (Manuscript (1989))
[10] Gabbay, D. M., Theoretical foundations for non-monotonic reasoning in expert systems, (Apt, K. R., Proceedings NATO Advanced Study Institute on Logics and Models of Concurrent Systems. Proceedings NATO Advanced Study Institute on Logics and Models of Concurrent Systems, La Colle-sur-Loup, France (1985), Springer: Springer Berlin), 439-457 · Zbl 0581.68068
[11] D.M. Gabbay, Personal communication (March 1989).; D.M. Gabbay, Personal communication (March 1989).
[12] Gentzen, G., Über die Existenz unabhängiger Axiomensysteme zu unendlichen Satzsystemen, Math. Ann., 107, 329-350 (1932)
[13] Gentzen, G., (Szabo, M. E., The Collected Papers of Gerhard Gentzen (1969), North-Holland: North-Holland Amsterdam) · Zbl 0209.30001
[14] Ginsberg, M. L., Counterfactuals, Artificial Intelligence, 30, 35-79 (1986) · Zbl 0655.03011
[15] Halpern, J. Y.; Moses, Y., Towards a theory of knowledge and ignorance: Preliminary report, (Proceedings Workshop on Non-Monotonic Reasoning. Proceedings Workshop on Non-Monotonic Reasoning, New Paltz, NY (1984)), 125-143 · Zbl 0581.68067
[16] Hoare, C. A.R., An axiomatic basis for computer programming, Commun. ACM, 12, 576-580 (1969) · Zbl 0179.23105
[17] Israel, D. J., What’s wrong with nonmonotonic logic?, (Proceedings AAAI-80. Proceedings AAAI-80, Stanford, CA (1980)), 99-101
[18] Kraus, S.; Lehmann, D.; Magidor, M., Preferential models and cumulative logics, (Tech. Rept. TR 88-15 (1988), Leibniz Center for Computer Science, Department of Computer Science, Hebrew University: Leibniz Center for Computer Science, Department of Computer Science, Hebrew University Jerusalem) · Zbl 0782.03012
[19] Lehmann, D., Preferential models and cumulative logics, (Shapiro, E., Fifth Israeli Symposium on Artificial Intelligence, Vision and Pattern Recognition. Fifth Israeli Symposium on Artificial Intelligence, Vision and Pattern Recognition, Tel Aviv, Israel (1988)), 365-381
[20] Lehmann, D., What does a conditional knowledge base entail?, (Brachman, R.; Levesque, H. J., Proceedings First International Conference on Principles of Knowledge Representation and Reasoning. Proceedings First International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Ont. (1989)) · Zbl 0709.68104
[21] Lehmann, D.; Kraus, S., Nonmonotonic logics: Models and proofs, (European Workshop on Logical Methods in Artificial Intelligence. European Workshop on Logical Methods in Artificial Intelligence, Roscoff (Finistère), France (1988)), 58-64
[22] Lehmann, D.; Magidor, M., Rational logics and their models: a study in cumulative logic, (Tech. Rept. TR 88-16 (1988), Leibniz Center for Computer Science, Department of Computer Science, Hebrew University: Leibniz Center for Computer Science, Department of Computer Science, Hebrew University Jerusalem) · Zbl 0818.68137
[23] Lewis, D. K., Completeness and decidability of three logics of counterfactual conditionals, Theoria, 37, 74-85 (1971) · Zbl 0229.02023
[24] Lewis, D. K., (Counterfactuals (1973), Harvard University Press: Harvard University Press Cambridge, MA)
[25] Lewis, D. K., Intensional logics without iterative axioms, J. Philos. Logic, 3, 457-466 (1974) · Zbl 0296.02014
[26] Lifschitz, V., On the satisfiability of circumscription, Artificial Intelligence, 28, 17-27 (1986) · Zbl 0589.03020
[27] D. Makinson, Personal communication (April 1988).; D. Makinson, Personal communication (April 1988).
[28] Makinson, D., General theory of cumulative inference, (Reinfrank, Proceedings Second International Workshop on Non-Monotonic Reasoning. Proceedings Second International Workshop on Non-Monotonic Reasoning, Lecture Notes in Computer Science (1989), Springer: Springer Berlin) · Zbl 0675.03007
[29] McCarthy, J., Circumscription: A form of non-monotonic reasoning, Artificial Intelligence, 13, 27-39 (1980) · Zbl 0435.68073
[30] McDermott, D.; Doyle, J., Non-monotonic logic I, Artificial Intelligence, 13, 41-72 (1980) · Zbl 0435.68074
[31] Moore, R. C., Possible-world semantics for autoepistemic logic, (Proceedings Workshop on Non-Monotonic Reasoning. Proceedings Workshop on Non-Monotonic Reasoning, New Paltz, NY (1984)), 396-401
[32] Nute, D., Conditional logic, (Gabbay, D. M.; Guenthner, F., Handbook of Philosophical Logic (1984), Reidel: Reidel Dordrecht, Netherlands), 387-439, Chapter II.8 · Zbl 0875.03017
[33] Pearl, J., (Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA)
[34] Pearl, J.; Geffner, H., Probabilistic semantics for a subset of default reasoning, (TR CSD-8700XX, R-93-III (1988), Computer Science Department, University of California: Computer Science Department, University of California Los Angeles, CA)
[35] Reiter, R., A logic of default reasoning, Artificial Intelligence, 13, 81-132 (1980) · Zbl 0435.68069
[36] Reiter, R., Nonmonotonic reasoning, (Annual Reviews in Computer Science, 2 (1987), Annual Reviews Inc), 147-186
[37] Scott, D. S., Completeness and axiomatizability, (Henkin, L.; etal., Proceedings Tarski Symposium. Proceedings Tarski Symposium, Proceedings of Symposia in Pure Mathematics (1971), Association for Symbolic Logic, American Mathematical Society: Association for Symbolic Logic, American Mathematical Society Providence, RI), 411-435
[38] Shoham, Y., A semantical approach to nonmonotonic logics, (Proceedings Logics in Computer Science. Proceedings Logics in Computer Science, Ithaca, NY (1987)), 275-279
[39] Shoham, Y., (Reasoning about Change-80 (1988), MIT Press: MIT Press Cambridge, MA)
[40] Stalnaker, R. C., A theory of conditionals, (American Philosophical Quarterly Monograph Series, 2 (1968), Blackwell: Blackwell Oxford), 98-112
[41] Tarski, A., Uber einige fundamentale Begriffe der Metamatematik, C. Séances Soc. Sci. Lettres Varsovie., 23, 22-29 (1930)
[42] Tarski, A., Fundamentale Begriffe der Methodologie der deduktiven Wissenschaften, Monatshefte Math. Phys., 37, 361-404 (1930)
[43] Tarski, A., Grundzüge des Systemenkalkül, I, Fund. Math., 25, 503-526 (1935)
[44] Tarski, A., (Logic, Semantics, Metamathematics, Papers from 1923-1938 (1956), Clarendon Press: Clarendon Press Oxford) · Zbl 0075.00702
[45] Touretzky, D. S., (The Mathematics of Inheritance Systems: Research Notes in Artificial Intelligence (1986), Pitman: Pitman London), Morgan Kaufmann, Los Altos, CA · Zbl 0675.68006
[46] van Benthem, J., Foundations of conditional logic, J. Philos. Logic, 13, 303-349 (1984) · Zbl 0544.03011
[47] Veltman, F., Logics for conditionals, (Ph.D. Thesis (1986), Filosofisch Instituut, Universiteit van: Filosofisch Instituut, Universiteit van Amsterdam)
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.