Currently (as of P3 Spring 2024) being taught at KTH.
Meeting: Thursdays 13:15-15:00 in 1625 (Lindstedtsvägen 3, E-building, 6th floor).
Course book: Reasoning about Knowledge (Fagin-Halpern-Moses-Vardi), MIT Press 2004.
For questions and to submit homework, please contact me by email under (my first name) at kth.se.
RAK Chapter 1.
Motivating examples for reasoning about knowledge. The Cheryl's Birthday problem. Common knowledge as the limit of "everyone knows that everyone knows that...". The Muddy Children puzzle. Overview of the rest of the course.
Homework 1a (due before Wk 3's class): RAK 1.1
RAK Chapters 2.1 to 2.3.
Review of propositional logic, its valuations and interpretations. Inductive definitions. Modalities. Formal definition of epistemic modal logic, and its interpretation using Kripke structures. Common knowledge as a modality. A formal account of the Muddy Children puzzle.
Homework 1b (due before Wk 3's class): (1) Give a Kripke structure for the Cheryl's Birthday problem, formalize the kids' successive statements as modal formulae, and show how the structure is updated in each step. (2) RAK 2.9.
RAK Chapter 2.4 and parts of 3.1.
Properties of Knowledge. Axioms of epistemic logic and the properties of the underlying model that imply them. Other modalities for which fewer axioms hold: Belief, Time.
Homework 2a (due before Wk 5's class): RAK 2.11, 2.12
An annotated example of how to use Parsec to write a parser in Haskell.
RAK Chapter 3.1.
Axiom systems for modal logic and their soundness. Building up to completeness: consistent and maximal consistent sets for a given axiom system.
Homework 2b (due before Wk 5's class): RAK 3.2, 3.3, 3.7
Grammar for specifying formulae and structures for our model checker (markdown).
RAK Chapter 3.1.
Proving completeness of System K. Completeness of larger axiom systems with respect to restricted classes of models. Equivalence of Kripke structures with respect to a language, and how it gives rise to a partial converse (every model of the axiom systems we saw has an equivalent structure in its corresponding class).
Homework 3a (due before Wk 7's class): Work out the details of the proof of Thm 3.1.5 in RAK and write it out rigorously.
Notes on the Lattice of Information.
Comparing the knowledge of different agents syntactically and semantically. Knowledge ordering of partitions. Lattice structure of this ordering: the Lattice of Information. Joins are distributed knowledge, and meets are common knowledge.
Homework 3b (due before Wk 7's class): See bottom of the notes.