Epistemic logic and, more generally, logics of knowledge and belief, originated with philosophers such as Jaakko Hintikka and David Lewis in the early 1960s. Since then, such logics have played a significant role not only in philosophy, but also in computer science, artificial intelligence, and economics. This handbook reports significant progress in a field that, while more mature, continues to be very active. This book should make it easier for new researchers to enter the field, and give experts a chance to appreciate work in related areas. The book starts with a gentle introduction to the logics of knowledge and belief; it gives an overview of the area and the material covered in the book. The following eleven chapters, each written by a leading researcher (or researchers), cover the topics of only knowing, awareness, knowledge and probability, knowledge and time, the dynamics of knowledge and of belief, model checking, game theory, agency, knowledge and ability, and security protocols. The chapters have been written so that they can be read independently and in any order. Each chapter ends with a section of notes that provides some historical background, including references, and a detailed bibliography.
Author(s): Hans van Ditmarsch, Joseph Y. Halpern, Wiebe van der Hoek, Barteld Kooi (eds.)
Publisher: College Publications
Year: 2015
Language: English
Pages: 673
Handbook of Epistemic Logic (2015) ......Page 2
Contents ......Page 4
Preface ......Page 12
Contributors ......Page 14
1.1 Introduction to the Book ......Page 18
1.2 Basic Concepts and Tools ......Page 19
1.2.1 Language ......Page 23
1.2.2 Semantics ......Page 25
1.2.3 Expressivity and Succinctness ......Page 38
1.2.4 Reasoning problems ......Page 43
1.2.5 Axiomatisation ......Page 49
1.3 Overview of the Book ......Page 59
1.4 Notes ......Page 62
References ......Page 66
PART I. Informational Attitudes ......Page 70
2.1 Introduction ......Page 72
2.2 Single-Agent Only Knowing ......Page 73
2.2.1 Syntax and Semantics ......Page 74
2.2.2 Some properties of OL ......Page 75
2.2.3 Proof Theory ......Page 76
2.2.4 Only Knowing and Autoepistemic Logic ......Page 79
2.2.5 Honesty ......Page 81
2.3 Multi-Agent Only Knowing ......Page 82
2.3.1 The Canonical-Model Approach ......Page 83
2.3.2 Proof Theory ......Page 85
2.3.3 Honesty Revisited ......Page 86
2.4 Notes ......Page 89
References ......Page 91
3.1 Introduction ......Page 94
3.2.1 Some properties of awareness in natural languages ......Page 96
3.2.2 Some properties of awareness in a formal language ......Page 97
3.3.1 Awareness structures ......Page 99
3.3.2 Impossibility of unawareness in Kripke frames ......Page 108
3.3.3 Unawareness frames ......Page 111
3.3.4 Unawareness structures ......Page 117
3.3.5 Generalized standard models ......Page 121
3.3.6 Product models ......Page 124
3.4.1 Type spaces with unawareness ......Page 129
3.4.2 Speculative trade and agreement ......Page 133
3.5.1 Propositional quantifiers and extended awareness structures ......Page 135
3.5.2 First-order logic with unawareness of objects ......Page 138
3.5.3 Neighborhood semantics and first-order logic with awareness ......Page 144
3.5.4 Awareness of unawareness without quantifiers ......Page 146
3.6 Notes ......Page 150
References ......Page 158
Chapter 4. Epistemic Probabilistic Logic (Lorenz Demey, Joshua Sack) ......Page 164
4.1 Introduction ......Page 165
4.2 Probabilistic Propositional Logic ......Page 167
4.2.1 Probabilistic Models ......Page 168
4.2.2 Language and Semantics ......Page 169
4.2.3 The Expressivity of Linear Combinations ......Page 172
4.2.4 Proof System ......Page 175
4.2.5 Decidability and Complexity ......Page 177
4.3.1 Probabilistic Relational Models ......Page 178
4.3.2 Language and Semantics ......Page 179
4.3.3 Expressivity of Linear Combinations ......Page 185
4.3.4 Proof System ......Page 186
4.3.5 Decidability and Complexity ......Page 187
4.4.1 Adding Probabilities to Interpreted Systems ......Page 188
4.4.2 Language and Semantics ......Page 190
4.4.3 Temporal and Dynamic Epistemic Logic ......Page 191
4.5.1 Language and Semantics ......Page 193
4.5.2 Proof System ......Page 198
4.5.4 Higher-Order Information in Public Announcements ......Page 199
4.6.1 Probabilistic Product Update ......Page 202
4.6.2 Language and Semantics ......Page 206
4.6.3 Proof System ......Page 208
4.7 Further Developments and Applications ......Page 210
4.8 Conclusion ......Page 211
4.9 Notes ......Page 212
References ......Page 215
PART II. Dynamics of Informational Attitudes ......Page 220
Chapter 5. Knowledge and Time (Clare Dixon, Claudia Nalon, Ram Ramanujam) ......Page 222
5.1.1 A temporal logic of knowledge ......Page 223
5.1.2 Structural investigations ......Page 224
5.2.1 Syntax ......Page 226
5.2.2 Semantics ......Page 227
5.3 Complexity ......Page 230
5.4.1 First order fragments ......Page 234
5.5 Axiomatisation ......Page 236
5.6 Reasoning ......Page 238
5.6.1 Resolution ......Page 240
5.6.2 Tableau ......Page 244
5.7 Knowledge and communication ......Page 250
5.7.1 The history based model ......Page 251
5.8 Levels of knowledge ......Page 252
5.9 Knowledge based semantics ......Page 254
5.10 Automata theory of knowledge ......Page 256
5.10.2 Finite state automata ......Page 257
5.10.3 Distributed alphabets ......Page 258
5.10.4 Epistemic transition systems ......Page 259
5.10.5 Behaviours ......Page 262
5.11 Applications ......Page 264
5.12 In conclusion ......Page 266
5.13 Notes ......Page 267
References ......Page 271
Chapter 6. Dynamic Epistemic Logic (Lawrence S. Moss) ......Page 278
6.1 Introduction ......Page 279
6.1.1 Scenarios ......Page 280
6.1.2 General notes on this chapter ......Page 284
6.2 Public Announcements and PAL ......Page 285
6.2.1 Public Announcement Logic PAL ......Page 288
6.2.2 Announcing a true fact might falsify it ......Page 290
6.2.3 Sound and complete logical systems ......Page 292
6.2.4 Succinctness and complexity ......Page 299
6.3 Additions to PAL ......Page 301
6.3.1 Common knowledge and relativized common knowledge ......Page 302
6.3.2 Iterated announcements ......Page 305
6.3.3 Arbitrary announcement logic ......Page 307
6.4.1 Private announcements and more general epistemic actions ......Page 308
6.4.2 The update product ......Page 310
6.4.3 Slower version of the update product ......Page 313
6.4.4 DEL based on epistemic actions ......Page 316
6.5 Conclusions ......Page 322
6.6 Notes ......Page 324
References ......Page 327
Chapter 7. Dynamic Logics of Belief Change (Johan van Benthem, Sonja Smets) ......Page 330
7.1.1 The AGM account of belief revision ......Page 331
7.1.2 Conditionals and the Ramsey Test ......Page 334
7.2 Modal logics of belief revision ......Page 335
7.3.1 Static logic of knowledge and belief ......Page 339
7.3.2 Plausibility models ......Page 340
7.4.1 From knowledge to belief, hard and soft information ......Page 347
7.4.2 Belief change under hard information ......Page 348
7.4.3 From dynamics to statics: safe and strong belief ......Page 349
7.4.4 Belief change under soft information: radical upgrade ......Page 350
7.4.5 Conservative upgrade and other revision policies ......Page 353
7.5.1 Relation transformers as PDL programs ......Page 354
7.5.2 Product update in general dynamic-epistemie logic ......Page 355
7.5.3 Priority update ......Page 359
7.6 Belief revision and probability dynamics ......Page 362
7.7 Time, iterated update, and learning ......Page 366
7.7.1 Epistemic temporal logic ......Page 367
7.7.2 Protocols in dynamic epistemic logic ......Page 370
7.7.3 Representing DEL inside temporal logic ......Page 372
7.7.4 Beliefs over time ......Page 373
7.7.5 Iterated belief upgrades and limit behavior ......Page 374
7.7.6 From belief revision to formal learning theory ......Page 377
7.8.1 Iterated beliefs in games ......Page 380
7.8.3 Informational cascades ......Page 383
7.8.4 Influence in social networks ......Page 387
7.9.1 Postulational and constructive approaches ......Page 389
7.9.3 Belief revision and evidence ......Page 392
7.9.4 Combining information and preference ......Page 393
7.9.5 Group belief and merge ......Page 394
7.9.6 Belief revision and social choice ......Page 395
7.10 Notes ......Page 396
References ......Page 402
PART III. Applications ......Page 412
Chapter 8. Model Checking Temporal Epistemic Logic (Alessio Lomuscio, Wojciech Penczek) ......Page 414
8.1 Introduction ......Page 415
8.2.1 Syntax ......Page 417
8.2.2 Interpreted systems semantics ......Page 418
8.2.3 Interleaved interpreted systems ......Page 419
8.2.4 Temporal-epistemic specifications ......Page 420
8.3 OBDD-based Symbolic Model Checking ......Page 422
8.3.1 State space representation and labelling ......Page 423
8.3.2 MCMAS ......Page 427
8.4 SAT-based Symbolic Model Checking ......Page 428
8.4.1 Bounded Model Checking ......Page 429
8.4.2 Unbounded Model Checking ......Page 432
8.5 Extensions to Real-Time Epistemic Logic ......Page 435
8.5.1 Example ......Page 437
8.6 Partial Order Reductions ......Page 438
8.6.1 Evaluation ......Page 440
8.7 Notes ......Page 441
References ......Page 450
Chapter 9. Epistemic Foundations of Game Theory (Giacomo Bonanno) ......Page 460
9.1 Introduction ......Page 461
9.2 Epistemic Models of Strategic-Form Gaines ......Page 462
9.3 Common Belief of Rationality. Semantics ......Page 466
9.4 Common Belief of Rationality: Syntax ......Page 470
9.5 Common Belief versus Common Knowledge ......Page 475
9.6 Probabilistic Beliefs and Payoffs ......Page 483
9.7 Dynamic Games with Perfect Information ......Page 486
9.8 The Semantics of Belief Revision ......Page 490
9.9 Common Belief of Rationality ......Page 491
9.10 Notes ......Page 497
References ......Page 501
10.1 Introduction ......Page 506
10.2 Bratman’s theory of Belief-Desire-Intention ......Page 507
10.2.1 Cohen and Levesque’s approach to intentions ......Page 510
10.2.2 Rao & Georgeif’s BDI logic ......Page 519
10.3 KARO Logic ......Page 527
10.4 BDI-modalities in STIT logic ......Page 537
10.4.1 BDI modalities in instantaneous stit ......Page 538
10.4.2 BDI modalities inXSTIT: dynamic attitudes ......Page 545
10.6 Notes ......Page 548
References ......Page 554
Chapter 11. Knowledge and Ability (Thomas Agotnes, Valentin Goranko, Wojciech Jamroga, Michael Wooldridge) ......Page 560
11.1 Philosophical Treatments ......Page 561
11.2 Ability in Artificial Intelligence ......Page 565
11.3 Logics for Abilities of Agents and Coalitions ......Page 569
11.3.1 Concurrent Game Models ......Page 570
11.3.2 Plays and strategies ......Page 571
11.3.3 Expressing Local Coalitional Powers: Coalition Logic ......Page 573
11.3.4 Alternating-time temporal logics ......Page 575
11.4.1 Incomplete Information and Uniform Strategies ......Page 580
11.4.2 Reasoning about Abilities under Uncertainty ......Page 583
11.4.3 Impact of Knowledge on Strategic Ability ......Page 587
11.5.1 Towards an Epistemic Extension of ATL ......Page 590
11.5.2 Epistemic Levels of Strategic Ability ......Page 592
11.5.3 Expressing Epistemic Levels of Ability and Constructive Knowledge ......Page 593
11.5.4 Closer Look at Constructive Knowledge ......Page 596
11.5.5 Public Announcements ......Page 598
11.7 Notes ......Page 600
References ......Page 603
12.1 Introduction ......Page 608
12.2 Cryptographic Protocols ......Page 611
12.2.1 Protocols ......Page 612
12.2.2 Cryptography ......Page 616
12.2.3 Attackers ......Page 624
12.2.4 Modeling Knowledge ......Page 626
12.2.5 Reasoning about Cryptographic Protocols ......Page 630
12.3 Information Flow in Multi-Level Systems ......Page 639
12.3.1 Information Flow in Event Systems ......Page 641
12.3.2 Language-Based Noninterference ......Page 644
12.4 Beyond Confidentiality ......Page 647
12.5 Perspectives ......Page 651
12.6 Notes ......Page 655
References ......Page 663
