Belief revision, conditional logic and nonmonotonic reasoning. (English) Zbl 0834.03008

Wobcke, Wayne

Notre Dame J. Formal Logic 36, No. 1, 55-102 (1995).

The central concern of this wide-ranging paper is to develop an account of belief revision that follows the general idea of the AGM paradigm, but which also gives us information about iterated revision. The strategy is to take one of the presentations of the well-known AGM approach, namely that in terms of epistemic entrenchment relations, and refine it to ensure that the output of a revision is of the same kind as the input, viz. a belief set with associated entrenchment relation. Specifically, the author proposes a rule for taking any entrenchment relation representable as a ranking into the positive integers, to a new such relation that reassigns the rank of a given formula whilst making “as little change as possible” to the ranks of other formulae. Postulates are given for the generated revision operations. The author also discusses questions of computability, and the translation of his rule into the languages of nonmonotonic inference and of conditionals.
Reviewer’s comments: Readers should take care with the following technical points. (1) Whilst every revision operation on a fixed belief set \(K\) satisfying the AGM postulates \(K^*1\) to \(K^*8\) can be characterized by an epistemic entrenchment relation, not quite all of them can be characterized by the author’s ranked epistemic entrenchment relations – indeed, presumably not all of them can be characterized by well-ordered entrenchment relations. In other words, even in the non- iterative context, the author’s construction concerns a slightly proper subset of the AGM functions. (2) On page 66 the author claims that there are no infinite descending chains of ranked epistemic entrenchments under his relation \(\leq\). However, all that is guaranteed by the definition is that any infinite descending chain will have a greatest lower bound – which need not be an element of the chain unless we assume, for example, that the language admits only finitely many non-equivalent formulae. The author has stated to the reviewer that nothing in what follows appears to depend on this slip (an appeal to the descending chain condition on page 75 being replaceable by an appeal to glb and adding the assumption that the base \(\Gamma\) is finite). (3) Concerning theorem 5.4, there is no guarantee the maximum value, there referred to, exists in general. However, it will exist when \(\Gamma\) is finite. (4) There is an inaccuracy in the paraphrase given just before the formal enunciation of theorem 3.3. It should read “the consequences of \(\neg A\) are ranked in \(K^+_{A,\alpha}\) the same as in \(K\), whilst consequences of \(A\) have their rank increased to \(\alpha\) if less than \(\alpha\) in \(K\)”. (5) In definition 5.1 “each non-theorem” is intended to mean “each non- theorem in \(\Gamma\)”.

Reviewer: D.Makinson (Ville d’Avray)

MSC:

03B60

Other nonclassical logic

Keywords:

belief change; nonmonotonic reasoning; belief revision; AGM; iterated revision; epistemic entrenchment relations; computability; conditionals

References:

[1]	Alchourrón, C. E., P. Gärdenfors and D. Makinson, “On the logic of theory change: partial meet contraction and revision functions,” The Journal of Symbolic Logic , vol. 50 (1985), pp. 510–530. JSTOR: · Zbl 0578.03011 · doi:10.2307/2274239
[2]	Arlo-Costa, H. L., and S. J. Shapiro, “Maps between nonmonotonic and conditional logic,” pp. 553–564 in Proceedings of the Third International Conference on Principles of Knowledge, Representation, and Reasoning , Morgan Kaufmann, San Mateo, 1992.
[3]	Bell, J., “Pragmatic logics,” pp. 50–60 in Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning , Morgan Kaufmann, San Mateo, 1991. · Zbl 0760.03007
[4]	Boutilier, C., “Revision sequences and nested conditionals,” pp. 519–525 in Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence , Morgan Kaufmann, San Mateo, 1993.
[5]	Chang, C. L., and R. C. T. Lee, Symbolic Logic and Mechanical Theorem Proving , Academic Press, New York, 1973. · Zbl 0263.68046
[6]	Crocco, G., and P. Lamarre, “On the connection between non-monotonic inference systems and conditional logics,” pp. 565–571 in Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning , Morgan Kaufmann, San Mateo, 1992.
[7]	Dalal, M., “Investigations into a theory of knowledge base revision: preliminary report,” pp. 475–479 in Proceedings of the Seventh National Conference on Artificial Intelligence (AAAI-88) , Morgan Kaufmann, San Mateo, 1988.
[8]	Darwiche, A., and J. Pearl, “On the logic of iterated belief revision,” pp. 5–23 in Proceedings of the Fourth Conference on Theoretical Aspects of Reasoning About Knowledge , Morgan Kaufmann, San Mateo, 1994. · Zbl 1018.03012 · doi:10.1016/S0004-3702(96)00038-0
[9]	Delgrande, J. P., “A first-order conditional logic for prototypical properties,” Artificial Intelligence , vol. 33 (1987), pp. 105–130. · Zbl 0654.68106 · doi:10.1016/0004-3702(87)90053-1
[10]	Delgrande, J. P., “An approach to default reasoning based on a first-order conditional logic: revised report,” Artificial Intelligence , vol. 36 (1988), pp. 63–90. · Zbl 0646.03015 · doi:10.1016/0004-3702(88)90079-3
[11]	Dixon, S. E., “A finite base belief revision system,” pp. 445–451 in Proceedings of the Sixteenth Australian Computer Science Conference , Queensland University of Technology, Brisbane, 1993.
[12]	Dixon, S. E., and W. R. Wobcke, “The implementation of a first-order logic AGM belief revision system,” pp. 40–47 in Proceedings of the Fifth IEEE International Conference on Tools with Artificial Intelligence , IEEE Computer Society Press, Los Alamitos, 1993.
[13]	Dixon, S. E. and W. R. Wobcke, “A nonmonotonic reasoning belief revision system,” pp. 151–160 in Proceedings of the Eighteenth Australasian Computer Science Conference , Flinders University of South Australia, University of Adelaide, and University of South Australia, Adelaide, 1995.
[14]	Elio, R. E., and F. J. Pelletier, “Human benchmarks on AI’s benchmark problems,” pp, 406–411 in Proceedings of the Fifteenth Annual Conference of the Cognitive Science Society , Lawrence Erlhaum, Hillsdale, 1993.
[15]	Etherington, D. W., Reasoning with Incomplete Information , Pitman, London, 1987. · Zbl 0694.68003
[16]	Fariñas del Cerro, L., A. Herzig and J. Lang, “From ordering-based nonmonotonic reasoning to conditional logics,” Artificial Intelligence , vol. 66 (1994), pp. 375–393. · Zbl 0807.68083 · doi:10.1016/0004-3702(94)90031-0
[17]	Fuhrmann, A., “Theory contraction through base contraction,” Journal of Philosophical Logic , vol. 20 (1991), pp. 175–203. · Zbl 0723.03010 · doi:10.1007/BF00284974
[18]	Gabbay, D. M., “Theoretical foundations for non-monotonic reasoning in expert systems,” pp. 439–457 in Proceedings of the NATO Advanced Study Institute on Logics and Models of Concurrent Systems , edited by K. R. Apt, Springer-Verlag, Berlin, 1985. · Zbl 0581.68068
[19]	Gärdenfors, P., “Belief revisions and the Ramsey Test for conditionals,” Philosophical Review , vol. 95 (1986), pp. 81–93.
[20]	Gärdenfors, P., “Variations on the Ramsey Test: more triviality results,” Studia Logica , vol. 46 (1987), pp. 319–325. · Zbl 0639.03024 · doi:10.1007/BF00370643
[21]	Gärdenfors, P., Knowledge in Flux , MIT Press, Cambridge, 1988. · Zbl 1229.03008
[22]	Gärdenfors, P., “Belief revision and nonmonotonic logic: two sides of the same coin?” pp. 768–773 in Proceedings of the Ninth European Conference on Artificial Intelligence , Pitman, London, 1990. · Zbl 0797.03019
[23]	Gärdenfors, P., “Nonmonotonic inferences based on expectations: a preliminary report,” pp. 585–590 in Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning , Morgan Kaufmann, San Mateo, 1991. · Zbl 0766.68118
[24]	Gärdenfors, P., S. Lindström, M. Morreau and W. Rabinowicz, “The negative Ramsey Test: another triviality result,” pp. 129–134 in The Logic of Theory Change , edited by A. Fuhrmann and M. Morreau, Springer-Verlag, Berlin, 1991. · Zbl 0925.03133
[25]	Gärdenfors, P., and D. Makinson, “Revisions of knowledge systems using epistemic entrenchment,” pp. 83–95 in Proceedings of the Second Conference on Theoretical Aspects of Reasoning About Knowledge , Morgan Kaufmann, Los Altos, 1988. · Zbl 0711.03009
[26]	Geffner, H. A., Default Reasoning: Causal and Conditional Theories , MIT Press, Cambridge, 1992. · Zbl 1193.68235
[27]	Geffner, H. A., and J. Pearl, “Conditional entailment: bridging two approaches to default reasoning,” Artificial Intelligence , vol. 53 (1992), pp. 209–244. · Zbl 1193.68235 · doi:10.1016/0004-3702(92)90071-5
[28]	Ginsberg, M. L., and D. E. Smith, “Reasoning about action I: a possible worlds approach,” Artificial Intelligence , vol. 35 (1988), pp. 165–195. · Zbl 0645.68109 · doi:10.1016/0004-3702(88)90011-2
[29]	Goldszmidt, M., P. Morris and J. Pearl, “A maximum entropy approach to nonmonotonic reasoning,” pp. 646–652 in Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI-90) , AAAI Press, Menlo Park, 1990.
[30]	Goldszmidt, M., and J. Pearl, “On the relation between rational closure and system \(Z\),” pp. 130–140 in Proceedings of the Third International Workshop on Nonmonotonic Reasoning .
[31]	Goldszmidt, M., and J. Pearl, “System \(Z^+\): a formalism for reasoning with variable-strength defaults,” pp. 399–404 in Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91) , AAAI Press, Menlo Park, 1991.
[32]	Grove, A., “Two modellings for theory change,” Journal of Philosophical Logic , vol. 17 (1988), pp. 157–170. · Zbl 0639.03025 · doi:10.1007/BF00247909
[33]	Hansson, S. O., “New operators for theory change,” Theoria , vol. 55 (1989), pp. 114-136. · Zbl 0722.03028 · doi:10.1111/j.1755-2567.1989.tb00725.x
[34]	Hansson, S. O., “Belief contraction without recovery,” Studia Logica , vol. 50 (1991), pp. 251-260. · Zbl 0748.03008 · doi:10.1007/BF00370186
[35]	Hansson, S. O., “A dyadic representation of belief,” pp. 89–121 in Belief Revision , edited by P. Gärdenfors, Cambridge University Press, Cambridge, 1992.
[36]	Katsuno, H. and K. Satoh, “A unified view of consequence relation, belief revision and conditional logic,” pp. 406–412 in Proceedings of the Twelfth International Joint Conference on Artificial Intelligence , Morgan Kaufmann, San Mateo, 1991. · Zbl 0747.68080
[37]	Kraus, S., D. Lehmann, and M. Magidor, “Nonmonotonic reasoning, preferential models and cumulative logics,” Artificial Intelligence , vol. 44 (1990), pp. 167–207. · Zbl 0782.03012 · doi:10.1016/0004-3702(90)90101-5
[38]	Lehmann, D. and M. Magidor, “What does a conditional knowledge base entail?” Artificial Intelligence , vol. 55 (1992), pp. 1–60. · Zbl 0762.68057 · doi:10.1016/0004-3702(92)90041-U
[39]	Levi, I., “Iteration of conditionals and the Ramsey Test,” Synthese , vol. 76 (1988), pp. 49–81. · doi:10.1007/BF00869641
[40]	Lewis, D. K., Counterfactuals , Blackwell, Oxford, 1973. · Zbl 0989.03003
[41]	Lifschitz, V., “Benchmark problems for formal nonmonotonic reasoning,” pp. 202–219 in Non-Monotonic Reasoning , edited by M. Reinfrank, J. de Kleer, M. L. Ginsberg and E. Sandewall, Springer-Verlag, Berlin, 1989. · Zbl 0675.68057
[42]	Makinson, D., “On the status of the postulate of recovery in the logic of theory change,” Journal of Philosophical Logic , vol. 16 (1987), pp. 383–394. · Zbl 0632.03008 · doi:10.1007/BF00431184
[43]	Makinson, D., “General theory of cumulative inference,” pp. 1–18 in Non-Monotonic Reasoning , edited by M. Reinfrank, J. de Kleer, M. L. Ginsberg and E. Sandewall, Springer-Verlag, Berlin, 1989. · Zbl 0675.03007
[44]	Makinson, D., and P. Gärdenfors, “Relations between the logic of theory change and nonmonotonic logic,” pp. 185–205 in The Logic of Theory Change , edited by A. Fuhrmann and M. Morreau, Springer-Verlag, Berlin, 1991. · Zbl 0925.03130 · doi:10.1007/BFb0018421
[45]	McCarthy, J. M., and P. J. Hayes, “Some philosophical problems from the standpoint of artificial intelligence,” pp. 463–502 in Machine Intelligence 4 , edited by B. Meltzer and D. Michie, Edinburgh University Press, Edinburgh, 1969. · Zbl 0226.68044
[46]	Moore, R. C., “Semantical considerations on nonmonotonic logic,” Artificial Intelligence , vol. 25 (1985), pp. 75–94. · Zbl 0569.68079 · doi:10.1016/0004-3702(85)90042-6
[47]	Morreau, M., “Epistemic semantics for counterfactuals,” Journal of Philosophical Logic , vol. 21 (1992), pp. 33–62. · Zbl 0752.03013 · doi:10.1007/BF00126496
[48]	Nayak, A. C., “Foundational belief change” Journal of Philosophical Logic , vol. 23 (1994), pp. 495–533. · Zbl 0810.03018 · doi:10.1007/BF01049408
[49]	Nayak, A. C., “Iterated belief change based on epistemic entrenchment,” Erkenntnis , vol. 41 (1994), pp. 353–390. · doi:10.1007/BF01130759
[50]	Nayak, A. C., N. Y. Foo, M. Pagnucco and A. Sattar, “Entrenchment kinematics 101,” pp. 157–164 in Proceedings of the Seventh Australian Joint Conference on Artificial Intelligence , World Scientific, Singapore, 1994.
[51]	Nebel, B., “Belief revision and default reasoning: syntax-based approaches,” pp. 417–428 in Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning , Morgan Kaufmann, San Mateo, 1991. · Zbl 0765.68198
[52]	Pearl, J., “System \(Z\): a natural ordering of defaults with tractable applications to nonmonotonic reasoning,” pp. 121–135 in Proceedings of the Third Conference on Theoretical Aspects of Reasoning About Knowledge , Morgan Kaufmann, San Mateo, 1990.
[53]	Peppas, P., N. Y. Foo and W. R. Wobcke, “Events as theory operators,” pp. 413–426 in Proceedings of the First World Conference on the Fundamentals of Artificial Intelligence , Angkor, Paris, 1991.
[54]	Poole, D., “A logical framework for default reasoning,” Artificial Intelligence , vol. 36 (1988), pp. 27–47. · Zbl 0647.68094 · doi:10.1016/0004-3702(88)90077-X
[55]	Ramsey, F. P., “General propositions and causality,” pp. 237–255 in F. P. Ramsey The Foundations of Mathematics and Other Logical Essays , Routledge and Kegan Paul, New York, 1931. · Zbl 0002.00501
[56]	Rott, H., “A nonmonotonic conditional logic for belief revision,” pp. 135–181 in The Logic of Theory Change , edited by A. Fuhrmann and M. Morreau, Springer-Verlag, Berlin, 1991. · Zbl 0925.03134 · doi:10.1007/BFb0018420
[57]	Rott, H., “Preferential belief change using generalized epistemic entrenchment,” Journal of Logic, Language and Information , vol. 1 (1992), pp. 45–78. · Zbl 0794.03039 · doi:10.1007/BF00203386
[58]	Spohn, W., “Ordinal conditional functions: a dynamic theory of epistemic states,” pp. 105–134 in Causation in Decision, Belief Change, and Statistics, II , edited by W. L. Harper and B. Skyrms, Kluwer Academic Publishers, Dordrecht, 1988.
[59]	Stalnaker, R. C., “A theory of conditionals,” pp. 98–112 in Studies in Logical Theory , edited by N. Rescher, Blackwell, Oxford, 1968.
[60]	van Fraassen, B. C., “Singular terms, truth-value gaps, and free logic,” Journal of Philosophy , vol. 63 (1966), pp. 481–495.
[61]	Williams, M. A., “Two operators for theory base change,” pp. 259–265 in Proceedings of the Fifth Australian Joint Conference on Artificial Intelligence , World Scientific, Singapore, 1992.
[62]	Williams, M. A., “Transmutations of knowledge systems,” pp. 619–629 in Proceedings of the Fourth International Conference on Principles of Knowledge Representation and Reasoning , Morgan Kaufmann, San Mateo, 1994.
[63]	Wobcke, W. R., “On the use of epistemic entrenchment in nonmonotonic reasoning,” pp. 324–328 in Proceedings of the Tenth European Conference on Artificial Intelligence , Wiley, Chichester, 1992.
[64]	Wobcke, W. R., “Algorithms for iterative belief revision,” pp. 165–172 in Proceedings of the Seventh Australian Joint Conference on Artificial Intelligence , World Scientific, Singapore, 1994.