Die vorliegende Arbeit untersucht das sogenannte logische Allwissenheitsproblem' (Logical Omniscience Problem) der epistemischen Logik und schlägt einen neuen Ansatz zur Lösung des Problems vor. Die epistemische Logik, die ursprünglich als eine Teildisziplin der philosophischen Logik entwickelt wurde, findet heute Anwendung in so unterschiedlichen Gebieten wie Philosophie, Sprachwissenschaft, Wirtschaftswissenschaft und Informatik. In der Informatik und der Künstlichen Intelligenz ist die epistemische Logik einer der Hauptformalismen zur Wissensrepräsentation und zur Spezifikation von Multiagentensystemen geworden. Allerdings ist es eine sehr umstrittene Frage, ob die epistemische Logik für diese Anwendungen geeignet ist. Kritiker behaupten, daß die epistemische Logik die Begriffe des Wissens und des Glaubens nicht adäquat erfassen kann und folglich für die Repräsentation von Wissen ungeeignet ist. Ihre Behauptung gründet sich auf der Tatsache, daß die meisten Systeme der epistemischen Logik sehr starke Idealisierungen hinsichtlich der logischen Fähigkeiten der epistemischen Subjekte (englisch: agents) machen. Es wird z. B. angenommen, daß die epistemischen Subjekte alle logischen Wahrheiten kennen, oder daß sie alle logischen Konsequenzen einer Aussage kennen, wenn sie diese Aussage glauben. Dieses Problem is als das logische Allwissenheitsproblem' (Logical Omniscience Problem) bekannt. Es gibt in der Literatur eine Reihe von Ansätzen, dieses Problem zu lösen. Fast alle vorgeschlagenen Lösungen verfolgen die Strategie, schwächere modale Systeme zu betrachten. Ich werde zeigen, daß diese Lösungen unbefriedigend sind: in dieser Weise kann logische Allwissenheit vermieden werden, aber viele Intuitionen über die Begriffe Glauben und Wissen gehen verloren. Also können auch die schwächeren epistemischen Systeme die genannten Begriffe nicht adäquat erfassen. Ein anderer Lösungsansatz wird vorgeschlagen. Ich werde argumentieren, daß sich die Hauptprobleme der epistemischen Logik in einem statischen Rahmen nicht lösen lassen. Um diese Probleme zu lösen, müssen wir auch die Denkaktivitäten der epistemischen Subjekte in Betracht ziehen. Zur Modellierung von Wissen (und Glauben) brauchen wir eine dynamische epistemische Logik. Ich werde zeigen, daß Axiome der epistemischen Logik die folgende Form haben muß: wenn alle Prämissen einer gültigen Schlußregel gewußt (geglaubt) werden und wenn das Subjekt die notwendige Folgerung vollzieht, dann weißt (glaubt) es auch die Konklusion. Um diese Idee zu formalisieren, schlage ich vor, die epistemische Logik zu d.h., eine dynamische Komponente in die Sprache einzuführen. An einem Beispiel wird erläutert, wie die Dynamisierung' der epistemischen Logik realisiert werden kann.

An understanding of cryptographic protocols requires that we examine the knowledge of protocol participants and adversaries: When a participant receives a message, does she know who sent it? Does she know that the message is fresh, and not merely a replay of some old message? Does a network spy know who is talking to whom? This thesis studies logics of knowledge and cryptography. Specifically, the thesis addresses the problem of how to make the concept of knowledge reflect feasible computability within a Kripke-style semantics. The main contributions are as follows. 1. A generalized Kripke semantics for first-order epistemic logic and cryptography, where the later is modeled using private constants and arbitrary cryptographic operations, as in the Applied Pi-calculus. 2. An axiomatization of first-order epistemic logic which is sound and complete relative to an underlying theory of cryptographic terms, and to an omega-rule for quantifiers. Besides standard axioms and rules from first-order epistemic logic, the axiomatization includes some novel axioms for the interaction between knowledge and cryptography. 3. Epistemic characterizations of static equivalence and Dolev-Yao message deduction. 4. A generalization of Kripke semantics for propositional epistemic logic and symmetric cryptography. 5. Decidability, soundness and completeness for propositional BAN-like logics with respect to message passing systems. Completeness and decidability are generalised to logics induced from an arbitrary base of protocol specific assumptions. 6. An epistemic definition of message deduction. The definition lies between weaker and stronger versions of Dolev-Yao deduction, and coincides with weaker Dolev-Yao regarding all atomic messages. For composite messages, the definition withstands a well-known counterexample to Dolev-Yao deduction. 7. Protocol examples using mixes, a Crowds style protocol, and electronic payments. / QC 20100524