Abstract
The aim of the present chapter is to overview three important tools for knowledge representation that are strongly interrelated. All three can be traced back to a fundamental limitation of classical logic: its connectives are truth-functional, which does not allow to reason about some concepts such as modalities and “if-then” relationships between propositions. To witness, most of the students in an introductory course on logic have a hard time to accept that the implication “if A then B” should be identified with “A is false or B is true”. Indeed, such an identification leads to validities that are rather counter-intuitive, such as “B implies A implies B” or “A implies B, or B implies A”. In introductory courses it is often omitted that the above interpretation of the so-called material implication was subject of much concern among scholars in the past. Their work led to the development of several families of formalisms that will be presented in this chapter: modal logics, conditional logics, and nonmonotonic formalisms. The next three sections detail the definitions of each of these: the modal logics K and S5, the conditional logics due to Stalnaker and Lewis, and the preferential and rational nonmonotonic reasoning formalisms. We then study the relationship between conditional logics and dynamic epistemic logics. The latter are a family of modal logics that got popular recently. We show that they can be viewed as particular logics of indicative conditionals: they are in the Stalnaker family and violate all of Lewis’s principles.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We note that knowledge and belief are part of an agent’s mental attitudes. Other such attitudes exist and cannot be represented by means of truth-functional operators either. These attitudes are presented in detail in chapter “,Formalization of Cognitive-Agent Systems, Trust, and Emotions” of this volume.
- 2.
Note that one might as well wish to avoid validity of the nested conditional formula \(\lnot A\Rightarrow (A\Rightarrow B) \). Such a project does not require a material implication, which amounts to studying \(\Rightarrow \) as a ‘full-fledged’ implication operator that is an alternative to \(\rightarrow \). This can e.g. be done in a logical language with operators \(\Rightarrow \), \(\lnot \), \(\wedge \) and \(\vee \). This leads us to so-called substructural logics such as intuitionistic logic or linear logic (Troelstra 1992). However, most researchers in AI tend a less radical position and study extensions of classical logic by a further logical operator \(\Rightarrow \). We consequently restrict our presentation to such approaches.
- 3.
The example is Goodman’s (1947), who proposes the requirement that \(A'\) should be cotenable with \(A\) for such an inference. His paper is dedicated to the quest of a definition of such a conditional; however, having discussed several unsatisfactory proposals he ends up defining cotenability in terms of the conditional, thus resulting in a circular definition.
- 4.
Precisely, for Nute’s weak conditional logic W the following holds: “Any \(\square \)-normal extension of the conditional logic W which is closed under one, is closed under all” (Nute 1980). It is however not the case that the principles are always equivalent: for example, in System C of Sect. 4.1, monotony and transitivity are equivalent, but monotony does not imply contraposition.
- 5.
The terms ‘postulate’ and ‘axiom’ both designate formal properties that are desired to hold. As customary we call such a property ‘axiom’ when it is formulated in the object language and ‘postulate’ when it is formulated in the metalanguage (see e.g. the AGM revision postulates Alchourrón et al. 1985). Inference rules are therefore particular postulates having one or more object language formulas as premisses and a single object language formula as conclusion.
- 6.
Actually axiom (4) is superfluous: it can be derived from (T) and (5).
- 7.
We have adapted the original notation.
- 8.
The link with theories of uncertainty is deepened in chapter “Representations of Uncertainty in Artificial Intelligence: Probability and Possibility” of this volume.
- 9.
As noted in Makinson (1993), the condition of transitivity that was initially imposed by Burgess can be abandoned. One might as well restrict the \(\le _w\) to strict preorders.
- 10.
Indeed, the first implies the second in presence of the axiom (\({\text {MOD}_{0}}\)).
- 11.
Actually defaults with free variables are considered to be abbreviations to be replaced by their closed instances.
- 12.
We refer to chapter “Main Issues in Belief Revision, Belief Merging and Information Fusion” of this volume for an exposition of AGM theory.
References
Alchourrón C, Gärdenfors P, Makinson D (1985) On the logic of theory change: partial meet contraction and revision functions. J Symb Log 50:510–530
Alenda R, Olivetti N, Pozzato GL (2016) Nested sequent calculi for normal conditional logics. J Log Comput 26(1):7–50. https://doi.org/10.1093/logcom/ext034
Arló Costa H (1995) Epistemic conditionals, snakes and stars. In: Crocco G, Fariñas del Cerro L, Herzig A (eds) Conditionals: from philosophy to computer science. Studies in logic and computation, vol 5. Oxford University, Oxford, pp 193–239
Arló Costa H, Shapiro S (1992) Maps between nonmonotonic and conditional logics. In: Nebel B, Rich C, Swartout W (eds) Proceedings of the 4th international conference on knowledge representation and reasoning (KR’92). Morgan Kaufmann, San Francisco, pp 553–564
Baader F, Hollunder B (1995) Embedding defaults into terminological knowledge representation formalisms. J Autom Reason 14(1):149–180
Balbiani P, van Ditmarsch H, Herzig A, de Lima T (2012) Some truths are best left unsaid. In: Ghilardi S, Moss L (eds) Advances in modal logic (AiML), pp 1–15. Copenhagen, 22/08/2012–25/08/2012, College Publications. http://www.collegepublications.co.uk, www.irit.fr/~Andreas.Herzig/P/Aiml12.html
Balduccini M, Janhunen T (eds) (2017) Logic programming and nonmonotonic reasoning-14th international conference, LPNMR 2017, Espoo, Finland, 3-6 July 2017, proceedings. Lecture notes in computer science, vol 10377. Springer, Berlin. https://doi.org/10.1007/978-3-319-61660-5
Bell J (1990) The logic of nonmonotonicity. Artif Intell J 41:365–374
Benferhat S, Bonnefon JF, Neves RDS (2004) An experimental analysis of possibilistic default reasoning. In: Dubois D, Welty CA, Williams MA (eds) KR. AAAI Press, pp 130–140
Besnard P (1989) An introduction to default logic. Springer, Berlin
Booth R, Casini G, Varzinczak IJ (eds) (2017) Proceedings of the 4th international workshop on defeasible and ampliative reasoning (DARe-17) co-located with the 14th international conference on logic programming and nonmonotonic reasoning (LPNMR 2017), Espoo, Finland, 3 July 2017. CEUR workshop proceedings, vol 1872, CEUR-WS.org. http://ceur-ws.org/Vol-1872
Bradley R, Stefánsson HO (2017) Counterfactual desirability. Br J Philos Sci 68(2):485–533. https://doi.org/10.1093/bjps/axv023
Brewka G (1991) Cumulative default logic: in defense of nonmonotonic inference rules. Artif Intell J 50:183–205
Fariñas del Cerro L, Herzig A (1991) A modal analysis of possibility theory. In: Proceedings of the European conference on symbolic and quantitative approaches to uncertainty (ECSQAU’91). LNCS, vol 548. Springer, Berlin, pp 58–62. http://www.irit.fr/PERSONNEL/LILaC/Herzig/P/Ecsquau91.pdf (short version; long version published in FAIR’91)
Chellas BF (1975) Basic conditional logics. J Philos Log 4:133–153
Chellas BF (1980) Modal logic: an introduction. Cambridge University, Cambridge
Crocco G, Lamarre P (1992) On the connection between conditional logics and nonmonotonic logics. In: Nebel B, Rich C, Swartout W (eds) Proceedings of the 4th international conference on knowledge representation and reasoning (KR’92). Morgan Kaufmann, San Francisco, pp 565–571
Crocco G, Fariñas del Cerro L, Herzig A (1995) Conditionals: from philosophy to computer science. Studies in logic and computation. Oxford University, USA
Cross CB (2016) Embedded counterfactuals and possible worlds semantics. Philos Stud 173(3):665–673
Delgrande J, Schaub T, Jackson W (1994) Alternative approaches to default logic. Artif Intell J 70(1–2):167–237
Doherty P, Łukaszewicz W (1992) Defaults as first-class citizens. In: 22nd international symposium on multiple-valued logic (SMVL’92). IEEE computer society, Sendai, Japan, pp 146–154
Donini FM, Nardi D, Rosati R (2002) Description logics of minimal knowledge and negation as failure. ACM Trans Comput Log 3(2):177–225
Douven I (2016) Experimental approaches to the study of conditionals. A companion to experimental philosophy. Wiley, New Jersey, pp 545–554
Etherington D (1987) Formalizing nonmonotonic reasoning systems. Artif Intell J 31(1):41–48
Gabbay DM (1985) Theoretical foundations for non-monotonic reasoning in expert systems. In: Apt KR (ed) Logics and models of concurrent systems. Springer, Berlin, pp 439–457
Gärdenfors P, Makinson D (1994) Nonmonotonic inference based on expectation ordering. Artif Intell J 65:197–245
Gerbrandy J (1999) Bisimulations on planet Kripke. PhD thesis, University of Amsterdam
Gerbrandy J, Groeneveld W (1997) Reasoning about information change. J Log Lang Inf 6(2)
Giordano L, Gliozzi V, Olivetti N, Pozzato GL (2013) A non-monotonic description logic for reasoning about typicality. Artif Intell 195:165–202. https://doi.org/10.1016/j.artint.2012.10.004, http://www.sciencedirect.com/science/article/pii/S0004370212001269
Girlando M, Lellmann B, Olivetti N, Pozzato GL (2016) Standard sequent calculi for Lewis’ logics of counterfactuals. In: Michael L, Kakas AC (eds) Logics in artificial intelligence - 15th European conference, JELIA 2016, Larnaca, Cyprus, 9–11 November 2016, proceedings. Lecture notes in computer science, vol 10021, pp 272–287. https://doi.org/10.1007/978-3-319-48758-8_18
Goodman N (1947) The problem of counterfactual conditionals. J Philos 44:113–128
Herzig A (1998) Logics for belief base updating. In: Dubois D, Gabbay D, Prade H, Smets P (eds) Handbook of defeasible reasoning and uncertainty management, vol 3 - Belief change. Kluwer, Dordrecht, pp 189–231
Hintikka J (1962) Knowledge and belief. Cornell University Press, Ithaca
Holliday WH, Hoshi T, Icard III TF (2011) Schematic validity in dynamic epistemic logic: decidability. In: Proceedings of the third international conference on logic, rationality, and interaction. Springer, Berlin, LORI’11, pp 87–96. http://dl.acm.org/citation.cfm?id=2050423.2050429
Kern-Isberner G, Wassermann R (2016) Proceedings of the 16th international workshop on non-monotonic reasoning (NMR 2016) Cape Town, South Africa, 22–24 April 2016. Technische Universität, Department of Computer Science, Fakultät für Informatik (fi)
Konolige K (1995) Autoepistemic logic. In: Gabbay DM, Hogger CJ, Robinson JA (eds) Handbook of logic in artificial intelligence and logic programming, vol 3 (Nonmonotonic reasoning and uncertain reasoning). Oxford Science Publications, pp 217–295
Kooi B (2007) Expressivity and completeness for public update logic via reduction axioms. J Appl Non Class Log 17(2):231–253
Koutras CD, Rantsoudis C (2017) In all but finitely many possible worlds: model-theoretic investigations on overwhelming majority default conditionals. J Log Lang Inf 26(2):109–141. https://doi.org/10.1007/s10849-017-9251-5
Kraus S, Lehmann D, Magidor M (1990) Nonmonotonic reasoning, preferential models and cumulative logics. Artif Intell J 44:167–207
Kripke S (1963) Semantical analysis of modal logic. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 9:67–96
Laverny N, Lang J (2005) From knowledge-based programs to graded belief-based programs, part II: off-line reasoning. In: Proceedings of the 9th international joint conference on artificial intelligence (IJCAI’05). Edinburgh, Gallus, pp 497–502
Sombé L (1994) Revision and updating in knowledge bases. Int J Intell Syst 9(1):1–180 (Besnard P, Cholvy L, Cordier MO, Dubois D, Fariñas del Cerro L, Froidevaux C, Lévy F, Moinard Y, Prade H, Schwind C, Siegel P)
Lehmann D, Magidor M (1992) What does a conditional knowledge base entail? Artif Intell J 55:1–60
Levi I (1996) For the sake of the argument: Ramsey test conditionals, inductive inference, and nonmonotonic reasoning. Cambridge University, Cambridge
Lewis C, Langford CH (1959) Symbolic logic. Dover reprint, original Published (1932)
Lewis D (1973) Counterfactuals. Basil Blackwell, Oxford
Lewis D (1979) Counterfactual dependence and time’s arrow. Nous 13:455–476
Lifschitz V (2008) What is answer set programming? In: Fox D, Gomes CP (eds) AAAI. AAAI, pp 1594–1597
Lindström S, Rabinowicz W (1995) The Ramsey test revisited. In: Crocco G, Fariñas del Cerro L, Herzig A (eds) Conditionals: from philosophy to computer science. Studies in logic and computation, vol 5. Oxford University, Oxford, pp 147–192
Makinson D (1993) Five faces of minimality. Stud Log 52:339–379
Makinson D (1994) General patterns in nonmonotonic reasoning. In: Gabbay DM, Hogger CJ, Robinson JA (eds) Handbook of logic in artificial intelligence and logic programming, vol 3. Oxford University, Oxford, pp 35–110
Marek V, Truszczynski M (1989) Relating autoepistemic and default logics. In: Brachman RJ, Levesque HJ, Reiter R (eds) 1st international conference on principles of knowledge representation and reasoning (KR’89). Morgan Kaufmann, Toronto, Canada, pp 276–288
McCarthy J (1980) Circumscription, a form of nonmonotonic reasoning. Artif Intell J 13:27–39
McCarthy J (1986) Applications of circumscription to formalizing common-sense knowledge. Artif Intell J 28(1):1038–1044
McCarthy J (1990) Formalizing common sense: papers. Ablex, Norwood
McDermott D, Doyle J (1980) Non-monotonic logic I. Artif Intell J 13:41–72. Special issue in non-monotonic reasoning
Moore RC (1985) Semantical considerations on nonmonotonic logic. Artif Intell 25(1)
Neves RDS, Bonnefon JF, Raufaste E (2002) An empirical test of patterns for nonmonotonic inference. Ann Math Artif Intell 34(1–3):107–130
Nute D (1980) Topics in conditional logic. D. Reidel, Dordrecht
Nute D (1984) Conditional logic. In: Gabbay DM, Günthner F (eds) Handbook of philosophical logic, vol 2. D. Reidel, Dordrecht, pp 387–439
Pfeifer N (2014) Reasoning about uncertain conditionals. Stud Log 102(4):849–866
Plaza JA (1989) Logics of public communications. In: Emrich ML, Pfeifer MZ, Hadzikadic M, Ras ZW (eds) Proceedings of the 4th international symposium on methodologies for intelligent systems, pp 201–216. Reprinted in Synthese 158:2, pp 165–179 (2007)
Reiter R (1980) A logic for default reasoning. Artif Intell J 13:81–132. Special issue in non-monotonic reasoning
Ryan M, Schobbens PY (1997) Intertranslating counterfactuals and updates. J Log Lang Inf 6(2):123–146 (Preliminary version in: W. Wahlster (ed.) Proceedings of the ECAI’96)
Stalnaker R (1968) A theory of conditionals. In: studies in logical theory, American philosophical quarterly (Monograph Series, No. 2), Blackwell, Oxford, pp 98–112 (reprinted in Sosa E (ed) Causation and conditionals. Oxford University, Oxford 1975; reprinted in Harper WL, Stalnaker R, Pearce G (eds) Ifs. Reidel, Dordrecht 1981; reprinted in Harper WL, Skyrms B (eds) Causation in decision, belief change and statistics, vol 2. Reidel, Dordrecht 1988, pp 105–134; reprinted in Jackson F (ed) Conditionals. Oxford University, Oxford Readings in Philosophy 1991)
Stalnaker R (1992) What is a nonmonotonic consequence relation? In: (Informal) Working notes of the 4th international workshop on nonmonotonic reasoning. Plymouth, Vermont
Troelstra AS (1992) Lectures on linear logic. Lecture notes, vol 29, CSLI (Center for the Study of Language and Information), Stanford
van Benthem J (2006) One is a lonely number: on the logic of communication. In: Chatzidakis Z, Koepke P, Pohlers W (eds) Logic colloquium’02. ASL and Peters AK, Wellesley MA, pp 96–129, Technical report PP-2002-27, ILLC Amsterdam (2002)
van Ditmarsch HP (2000) Knowledge games. PhD thesis, Groningen University, ILLC dissertation series, Grafimedia
Acknowledgements
Thanks are due to Ricardo Caferra for his careful reading of the first version of the French version of this chapter and to Henri Prade and Christos Rantsoudis for the same job on the present English version. Thanks are also due to Hans van Ditmarsch for his comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Herzig, A., Besnard, P. (2020). Knowledge Representation: Modalities, Conditionals, and Nonmonotonic Reasoning. In: Marquis, P., Papini, O., Prade, H. (eds) A Guided Tour of Artificial Intelligence Research. Springer, Cham. https://doi.org/10.1007/978-3-030-06164-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-06164-7_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-06163-0
Online ISBN: 978-3-030-06164-7
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)