Public Announcement Logic

Origin. Plaza introduced PAL (1989). Simplest dynamic epistemic logic. Models truthful public announcements. Announces φ: eliminate worlds where φ false. Foundation for more complex epistemic updates. Extensively studied fragment of DEL.

Models. Knowledge change from announcements. Before announcement: agents have uncertainty. Announcement of φ: all learn φ is true. After: only φ-worlds remain. Common knowledge created. Simple but powerful epistemic dynamics.

Formalism.

Syntax: φ ::= p | ¬φ | φ ∧ ψ | Kₐφ | [!φ]ψ | ⟨!φ⟩ψ

[!φ]ψ: "after announcing φ, ψ holds" ⟨!φ⟩ψ: "φ can be announced and then ψ holds"

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

Restriction: M|φ = (W', R', V') where

W' = {w ∈ W : M, w ⊨ φ}
R'ₐ = Rₐ ∩ (W' × W')
V'(p) = V(p) ∩ W'

Reduction axioms:

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

Group knowledge:

Eᴳφ: everyone in G knows φ
Cᴳφ: common knowledge in G
[!φ]Cᴳψ: common knowledge after announcement

Symbols.

Symbol	Unicode	Name	Meaning
[!φ]	—	Announcement	After public φ
⟨!φ⟩	—	Possible ann	Can announce φ
Kₐ	—	Knows	Agent a knows
Eᴳ	—	Everyone	All in G know
Cᴳ	—	Common	Common knowledge
\|	—	Restriction	Model restriction

Metatheory. PAL equally expressive as epistemic logic (via reduction). Reduction eliminates [!] operators. Decidable (PSPACE for multi-agent). Complete axiomatization via reduction. Not closed under uniform substitution (unusual).

Applies to. Puzzle solving (muddy children). Protocol analysis. Information flow. Security (what announcements reveal). Game theory. Social epistemology.

Limitations. Only truthful announcements. Public only (no private). Idealized communication. More complex updates need full DEL. Announcement may not be expressible.