Dynamic Epistemic Logic

Origin. Plaza introduced public announcement logic (1989). Baltag, Moss, and Solecki generalized to action models (1998). Van Benthem unified dynamic and epistemic traditions. Combines epistemic logic with dynamic updates. Models how knowledge changes through communication and observation.

Models. Knowledge change through action. Epistemic logic: what agents know. Dynamic epistemic logic: how knowledge changes when events occur. Public announcements eliminate worlds where announcement is false. Private communication, lies, and observation all modeled as epistemic actions.

Formalism.

Public Announcement Logic (PAL): [!φ]ψ — "after truthfully announcing φ, ψ holds"

Semantics: M, w ⊨ [!φ]ψ iff M, w ⊨ φ implies M|φ, w ⊨ ψ where M|φ restricts to φ-worlds.

Reduction axioms:

[!φ]p ↔ (φ → p)
[!φ]¬ψ ↔ (φ → ¬[!φ]ψ)
[!φ](ψ ∧ χ) ↔ ([!φ]ψ ∧ [!φ]χ)
[!φ]Kₐψ ↔ (φ → Kₐ[!φ]ψ)

Action models: A = (E, ~ₐ, pre) where:

E: set of events
~ₐ: indistinguishability for agent a
pre: E → L (preconditions)

Product update M ⊗ A combines model and action.

Examples:

Muddy children: public announcements lead to knowledge
Card games: private communication
Cryptographic protocols: who learns what

Common knowledge update: C_G φ (common knowledge in group G) can be achieved or broken by announcements.

Symbols.

Symbol	Unicode	Name	Meaning
[!φ]	—	Announcement	After announcing φ
Kₐ	—	Knows	Agent a knows
Bₐ	—	Believes	Agent a believes
C_G	—	Common knowledge	Group G commonly knows
⊗	U+2297	Product	Model update
~ₐ	—	Indistinguishable	Agent can't distinguish
E	—	Events	Action events

Metatheory. PAL reduces to epistemic logic (expressively equivalent). Full DEL (action models) is more expressive. Model checking is PSPACE-complete. Satisfiability is decidable for PAL, undecidable for some DEL extensions. Bisimulation notions extend to action models. Complete axiomatization exists for PAL.

Applies to. Security protocol verification. Game theory (information revelation). Social epistemology. Puzzle analysis (muddy children, wise men). Multi-agent systems. Lying and deception modeling. Gossip protocols.

Limitations. Assumes perfect recall and logical omniscience. Action models must be specified — not learned. Quantifying over announcements is complex. Asynchronous and probabilistic extensions less developed. Computational complexity grows with agent count. Real communication is messier than models suggest.