Epistemic Logic

Origin. Jaakko Hintikka's Knowledge and Belief (1962) established epistemic logic as a formal discipline. Builds on modal logic with knowledge and belief as modalities. Extended to multi-agent systems by Halpern, Moses, and others (1980s-1990s). Common knowledge formalized by David Lewis (1969) and Aumann (1976).

Models. Knowledge and belief of agents. What does agent i know? What do multiple agents know about each other's knowledge? When is something common knowledge (everyone knows that everyone knows that...)? The logic of "knowing that," "believing that," and their interactions.

Formalism.

Syntax: Propositional logic extended with epistemic operators for each agent i:

Kᵢφ: agent i knows that φ
Bᵢφ: agent i believes that φ
Cφ: it is common knowledge that φ (everyone knows, everyone knows everyone knows, ad infinitum)
Eφ: everyone knows that φ
Dφ: distributed knowledge — the agents collectively know φ (pooling information would reveal it)

Semantics: Kripke models with one accessibility relation per agent. M = (W, {Rᵢ}ᵢ∈Agents, V).

M, w ⊨ Kᵢφ iff for all v, if wRᵢv then M, v ⊨ φ

Agent i knows φ at w iff φ is true in all worlds agent i considers possible from w. The accessibility relation Rᵢ represents i's epistemic uncertainty.

For knowledge: Rᵢ is typically an equivalence relation (S5), giving:

Kᵢφ → φ (truth: you only know truths)
Kᵢφ → KᵢKᵢφ (positive introspection)
¬Kᵢφ → Kᵢ¬Kᵢφ (negative introspection)

For belief: weaker constraints (KD45), allowing false beliefs.

Common knowledge: Cφ ≡ Eφ ∧ EEφ ∧ EEEφ ∧ ... (infinite conjunction). Semantically: φ is common knowledge iff φ holds in all worlds reachable by any finite sequence of accessibility relations.

Symbols.

Symbol	Unicode	Name	Meaning
K	—	Knowledge	Agent knows that
Kᵢ	—	Agent i knows	Subscripted for agent i
B	—	Belief	Agent believes that
Bᵢ	—	Agent i believes	Subscripted for agent i
C	—	Common knowledge	All agents know, know they know, ...
E	—	Everyone knows	All agents know
D	—	Distributed knowledge	Collective knowledge
□	U+25A1	Necessity	Generic knowledge operator
◇	U+25C7	Possibility	Compatible with knowledge

Metatheory. Single-agent S5 epistemic logic is decidable (NP-complete). Multi-agent epistemic logic with common knowledge is decidable but EXPTIME-complete. Soundness and completeness hold for standard systems. Common knowledge is not finitely axiomatizable over S5 — requires an inference rule. Distributed knowledge creates a closure: if D(φ → ψ) and Dφ, then Dψ, even if no single agent can perform the inference.

Applies to. Distributed systems (what do processes know about global state?). Game theory (common knowledge of rationality). Security protocols (what does the attacker know?). Economics (Aumann's agreement theorem). Philosophy (analysis of knowledge, Gettier problems). AI (multi-agent systems, knowledge representation).

Limitations. Logical omniscience: agents know all logical consequences of what they know — unrealistic for bounded agents. The standard semantics makes knowledge closed under entailment. Various approaches address this: impossible worlds, awareness logic, resource-bounded reasoning. The truth condition (Kφ → φ) distinguishes knowledge from belief but doesn't capture justification (Gettier cases). Dynamics of knowledge (learning, communication) require extensions like Public Announcement Logic.