product iamge

Knowledge, chance, and change [PhD Thesis]

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

Author(s): Barteld Kooi
Series: ILLC Dissertation Series DS-2003-01
Publisher: University of Amsterdam
Year: 2003

Language: English
Pages: 184
City: Amsterdam

1 Introduction 1
2 Epistemic logic 3
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Language and semantics . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Proof systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 General and common knowledge . . . . . . . . . . . . . . . . . . . 7
2.5 Bisimulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Strong completeness and disharmony 11
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 The in¯nitary proof system PDL! . . . . . . . . . . . . . . . . . . 12
3.3 Strong completeness: the canonical model for PDL! . . . . . . . . 16
3.4 Generalization to other modal logics . . . . . . . . . . . . . . . . 19
3.4.1 Epistemic logic . . . . . . . . . . . . . . . . . . . . . . . . 21
3.5 Comparison to other work . . . . . . . . . . . . . . . . . . . . . . 23
3.6 Program (dis)harmony . . . . . . . . . . . . . . . . . . . . . . . . 25
3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 Information change 33
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.1.1 Muddy children . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.2 Byzantine generals . . . . . . . . . . . . . . . . . . . . . . 36
4.1.3 Sum and product . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.4 Cluedo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.1.5 Lecture or Amsterdam . . . . . . . . . . . . . . . . . . . . 38
4.2 Multi-agent systems . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Dynamic epistemic logic . . . . . . . . . . . . . . . . . . . . . . . 42
4.3.1 Updating with programs . . . . . . . . . . . . . . . . . . . 43
4.3.2 Learning to preserve S5 . . . . . . . . . . . . . . . . . . . 47
4.3.3 Epistemic actions . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.4 Changing modalities . . . . . . . . . . . . . . . . . . . . . 56
4.4 From action terms to action sentences . . . . . . . . . . . . . . . . 58
4.4.1 Action language . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4.2 Dyadic hybrid epistemic logic . . . . . . . . . . . . . . . . 69
4.5 Where do we go? . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5 Intensional and statistical probability 77
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2 Languages and Models . . . . . . . . . . . . . . . . . . . . . . . . 80
5.2.1 The intensional probability logic IPL . . . . . . . . . . . . 80
5.2.2 The statistical probability logic SPL . . . . . . . . . . . . . 82
5.3 The relation between IPL and SPL . . . . . . . . . . . . . . . . . . 84
5.4 The probabilistic epistemic logic PEL . . . . . . . . . . . . . . . . 86
5.4.1 Language and semantics . . . . . . . . . . . . . . . . . . . 86
5.4.2 Sample space assignments . . . . . . . . . . . . . . . . . . 88
5.4.3 The generalized statistical probability logic GSPL . . . . . 90
5.5 Toward correspondence theory for probability logics . . . . . . . . 94
5.5.1 Correspondences . . . . . . . . . . . . . . . . . . . . . . . 95
5.5.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6 Probabilistic dynamic epistemic logic 99
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.3 Language and semantics . . . . . . . . . . . . . . . . . . . . . . . 101
6.4 Reasoning about probability . . . . . . . . . . . . . . . . . . . . . 105
6.4.1 Building a Model . . . . . . . . . . . . . . . . . . . . . . . 105
6.4.2 Proof system, soundness and completeness . . . . . . . . . 108
6.5 Bisimulation for probabilistic dynamic epistemic logic . . . . . . . 114
6.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.7 Conclusion and further research . . . . . . . . . . . . . . . . . . . 119
7 The Monty Hall dilemma 121
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.2 A semantical analysis . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.3 A syntactic analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
8 Mastermind 129
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
8.2 Game theoretic analysis . . . . . . . . . . . . . . . . . . . . . . . 130
8.3 A simple strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8.4 Looking one step ahead . . . . . . . . . . . . . . . . . . . . . . . . 131
8.5 Empirical results . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
8.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
9 Trying to resolve the two-envelope problem 141
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
9.2 A purely logical paradox . . . . . . . . . . . . . . . . . . . . . . . 143
9.3 The two-envelope paradox . . . . . . . . . . . . . . . . . . . . . . 146
9.4 The two-envelope problem . . . . . . . . . . . . . . . . . . . . . . 146
10 Conclusion 149
Samenvatting 153
Bibliography 156
Index 169