Издательство Cambridge University Press, 1995, -368 pp.
Epistemic logic conces the notions knowledge and belief ('???????? — episteme — is Greek for 'knowledge'), and stems from philosophy where it has been developed to give a formal treatment of these notions. (Sometimes the logic of belief is separately referred to as doxastic logic, from the Greek word ????— doxa —, meaning 'surmise' or 'presumption'. In this book we shall use epistemic logic for the logic of knowledge an belief.) In [Hin62] the Finnish logician and philosopher Jaakko Hintikka presented a logic for knowledge and belief that was based on modal logic. Modal logic is a so-called philosophical logic dealing with the notions of necessity and contingency (possibility) ([Kri63], [Che80], [HC68, HC84]), and it appeared that epistemic logic could be viewed as an instance of this more general logic by interpreting necessity and possibility in an epistemic manner. For a thorough treatment of epistemic logic from the perspective of philosophy we refer to[Len80].
Especially in the last decade the use of logic and logical formalisms in artificial intelligence (AI) has increased enormously, including that of those logics that have been developed originally in and for philosophy. Epistemic logic is one of these so-called philosophical logics that has been 'discovered' by computer scientists and AI researchers. Particularly, the relevance of epistemic logic has been realised by researchers interested in the formal description of knowledge of agents in distributed and intelligent systems in order to specify or verify protocols, and represent knowledge and formalise reasoning methods, respectively. To mention a few propagators of the epistemic approach: J.Y. Halpe, Y.O. Moses, R. Fagin, M.Y. Vardi, D.J. Lehmann, H.J. Levesque and R.C. Moore. For instance, [HM85] is an excellent introduction in the area, and has provided a basis for this work.
This book grew out of lecture notes for a (part of a) course of applied logic for third-year undergraduate computer science students at the Free University in Amsterdam, and the Universities of Nijmegen and Utrecht. This book is an extended version of those notes, intended as a textbook on epistemic logic, treating both the basics and applications in computer science and, particularly, artificial intelligence. This text hopes to give an introduction to this topic accessible to undergraduates in computer science and AI. However, we also believe that the book will be of help to graduate students and researchers by rendering the specialist literature using epistemic logic accessible to them. Furthermore, it may be of interest to logicians and philosophers interested in the application of (philosophical) logic.
We now give an overview of the contents of the book. After an introduction to the topic of epistemic logic (Chapter 0), in Chapter 1 we start with the (modal) basics of multi-agent epistemic logic, including Kripke semantics and the well-known modal logics K, T, S4 and S
5. In particular, we pause at single-agent S5-logic, where we treat th6 simple models as well asthe issue of normal forms for this case. We then tu to the application of epistemic logic in the context of distributed systems, including the topic of protocol verification. This line is continued in Chapter 2, where we proceed with some notions that are particularly interesting in this context such as common and implicit (distributed) knowledge. We then consider more AI oriented issues such as the difference between knowledge and belief; the problem of logical omniscience, involving various notions of explicit and implicit belief, combining knowledge and belief into one logic; the interplay between knowledge and time; and the interplay between knowledge and action. Finally some attention is paid to the use of graded (or numerical) modalities in epistemic logic. In Chapter 3 we occupy ourselves with the issue of knowledge vs ignorance: first we discuss Halpe & Moses' elegant theory of honesty, next we digress into the realm of nonmonotonic reasoning and preferential entailment, and we end Chapter 3 with a treatment of Moore's autoepistemic logic (AEL) in which an agent is able to reason about its own knowledge (or belief), and the related logic of 'all I know' of Hector Levesque. Then in Chapter 4, we show how one can base default and counterfactual reasoning on epistemic logic, including a treatment of well-known but complicated examples such as the Yale Shooting Problem. In particular, we consider a kind of default entailment based on the theory of Chapter
3. In appendixes we consider alteative approaches to knowledge and belief, namely Konolige's 'deduction model' and the 'knowledge structures' of Fagin, Halpe and Vardi. Finally we stress that the emphasis of the book is on propositional epistemic logic, since most interesting features of epistemic logic can already be appreciated in this simple setting. Nevertheless, we felt obliged to say something about first-order epistemic logic in an appendix.
An important part of the book is the answers to all exercises, from trivial to difficult, as well as some elaborations of the theory in the main text. Students may therefore use this section interactively: first try to obtain solutions themselves to get a feel for the problems, then discover further technical tools offered in the answers and next try the exercises again. This makes the book very suited for self-study. Students themselves may choose the level of mastering the material.
A word of waing is in order, however. There is a sense in which this book is not self-contained and does not provide the complete story (definitions, elementary propositions, etc.): namely with respect to the topic of classical logic. The main text does not give an introduction into classical logic, simply because there already exist so many good introductions in the literature (see e.g. [Gal90], [Gam91], [Men64], [Tha88]). However, in order to present answers to the exercises in a systematic and somewhat standardised way, and also for readers who want to measure their knowledge of the subject of classical logic against the level we like to assume familiar, we present a number of properties of classical logic that we used in the answers in Intermezzo E. 1 in Appendix E.
Finally, a general remark about the text. Sections marked with * are rather technical, and may be skipped without loss of continuity. Exercises marked with * are more advanced (and may even need substantial further development of the theory, as is shown in the answers).
Introduction
Basics: The Modal Approach to Knowledge
Various Notions of Knowledge and Belief
Knowledge and Ignorance
Default Reasoning by Epistemic Logic
Answers to the Exercises
Epistemic logic conces the notions knowledge and belief ('???????? — episteme — is Greek for 'knowledge'), and stems from philosophy where it has been developed to give a formal treatment of these notions. (Sometimes the logic of belief is separately referred to as doxastic logic, from the Greek word ????— doxa —, meaning 'surmise' or 'presumption'. In this book we shall use epistemic logic for the logic of knowledge an belief.) In [Hin62] the Finnish logician and philosopher Jaakko Hintikka presented a logic for knowledge and belief that was based on modal logic. Modal logic is a so-called philosophical logic dealing with the notions of necessity and contingency (possibility) ([Kri63], [Che80], [HC68, HC84]), and it appeared that epistemic logic could be viewed as an instance of this more general logic by interpreting necessity and possibility in an epistemic manner. For a thorough treatment of epistemic logic from the perspective of philosophy we refer to[Len80].
Especially in the last decade the use of logic and logical formalisms in artificial intelligence (AI) has increased enormously, including that of those logics that have been developed originally in and for philosophy. Epistemic logic is one of these so-called philosophical logics that has been 'discovered' by computer scientists and AI researchers. Particularly, the relevance of epistemic logic has been realised by researchers interested in the formal description of knowledge of agents in distributed and intelligent systems in order to specify or verify protocols, and represent knowledge and formalise reasoning methods, respectively. To mention a few propagators of the epistemic approach: J.Y. Halpe, Y.O. Moses, R. Fagin, M.Y. Vardi, D.J. Lehmann, H.J. Levesque and R.C. Moore. For instance, [HM85] is an excellent introduction in the area, and has provided a basis for this work.
This book grew out of lecture notes for a (part of a) course of applied logic for third-year undergraduate computer science students at the Free University in Amsterdam, and the Universities of Nijmegen and Utrecht. This book is an extended version of those notes, intended as a textbook on epistemic logic, treating both the basics and applications in computer science and, particularly, artificial intelligence. This text hopes to give an introduction to this topic accessible to undergraduates in computer science and AI. However, we also believe that the book will be of help to graduate students and researchers by rendering the specialist literature using epistemic logic accessible to them. Furthermore, it may be of interest to logicians and philosophers interested in the application of (philosophical) logic.
We now give an overview of the contents of the book. After an introduction to the topic of epistemic logic (Chapter 0), in Chapter 1 we start with the (modal) basics of multi-agent epistemic logic, including Kripke semantics and the well-known modal logics K, T, S4 and S
5. In particular, we pause at single-agent S5-logic, where we treat th6 simple models as well asthe issue of normal forms for this case. We then tu to the application of epistemic logic in the context of distributed systems, including the topic of protocol verification. This line is continued in Chapter 2, where we proceed with some notions that are particularly interesting in this context such as common and implicit (distributed) knowledge. We then consider more AI oriented issues such as the difference between knowledge and belief; the problem of logical omniscience, involving various notions of explicit and implicit belief, combining knowledge and belief into one logic; the interplay between knowledge and time; and the interplay between knowledge and action. Finally some attention is paid to the use of graded (or numerical) modalities in epistemic logic. In Chapter 3 we occupy ourselves with the issue of knowledge vs ignorance: first we discuss Halpe & Moses' elegant theory of honesty, next we digress into the realm of nonmonotonic reasoning and preferential entailment, and we end Chapter 3 with a treatment of Moore's autoepistemic logic (AEL) in which an agent is able to reason about its own knowledge (or belief), and the related logic of 'all I know' of Hector Levesque. Then in Chapter 4, we show how one can base default and counterfactual reasoning on epistemic logic, including a treatment of well-known but complicated examples such as the Yale Shooting Problem. In particular, we consider a kind of default entailment based on the theory of Chapter
3. In appendixes we consider alteative approaches to knowledge and belief, namely Konolige's 'deduction model' and the 'knowledge structures' of Fagin, Halpe and Vardi. Finally we stress that the emphasis of the book is on propositional epistemic logic, since most interesting features of epistemic logic can already be appreciated in this simple setting. Nevertheless, we felt obliged to say something about first-order epistemic logic in an appendix.
An important part of the book is the answers to all exercises, from trivial to difficult, as well as some elaborations of the theory in the main text. Students may therefore use this section interactively: first try to obtain solutions themselves to get a feel for the problems, then discover further technical tools offered in the answers and next try the exercises again. This makes the book very suited for self-study. Students themselves may choose the level of mastering the material.
A word of waing is in order, however. There is a sense in which this book is not self-contained and does not provide the complete story (definitions, elementary propositions, etc.): namely with respect to the topic of classical logic. The main text does not give an introduction into classical logic, simply because there already exist so many good introductions in the literature (see e.g. [Gal90], [Gam91], [Men64], [Tha88]). However, in order to present answers to the exercises in a systematic and somewhat standardised way, and also for readers who want to measure their knowledge of the subject of classical logic against the level we like to assume familiar, we present a number of properties of classical logic that we used in the answers in Intermezzo E. 1 in Appendix E.
Finally, a general remark about the text. Sections marked with * are rather technical, and may be skipped without loss of continuity. Exercises marked with * are more advanced (and may even need substantial further development of the theory, as is shown in the answers).
Introduction
Basics: The Modal Approach to Knowledge
Various Notions of Knowledge and Belief
Knowledge and Ignorance
Default Reasoning by Epistemic Logic
Answers to the Exercises