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.

Metatheory. S5 is sound and complete for frames whose accessibility relation is an equivalence, and KD45 for serial, transitive, Euclidean frames; T, 4, 5 and D are Sahlqvist formulas, so both logics are canonical and both frame classes are elementary. Both have the finite model property. Ladner (1977) showed that single-agent S5 satisfiability is NP-complete — an S5 model collapses to one cluster, so a model of size |φ| suffices — while K, T and S4 are PSPACE-complete. Halpern and Moses (1992) showed that with two or more agents the collapse fails and Kₙ, Tₙ, S4ₙ, S5ₙ and KD45ₙ are all PSPACE-complete, that adding distributed knowledge leaves them PSPACE-complete, and that adding common knowledge raises satisfiability to EXPTIME-complete. The common-knowledge logics are not compact: {Eᵏφ : k ∈ ℕ} together with ¬Cφ is finitely satisfiable but unsatisfiable, so no finitary Hilbert system is strongly complete, and the standard axiomatization is weakly complete using a fixed-point axiom and an induction rule.

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 is forced by normality: necessitation gives Kᵢφ for every validity and the K axiom closes knowledge under implication, so the agent knows every consequence of what it knows and cannot fail to know a tautology. S5 adds negative introspection, ¬Kᵢφ → Kᵢ¬Kᵢφ, which Williamson (Knowledge and Its Limits, 2000) argues no agent with margins for error satisfies, and the KK principle Kφ → KKφ has been in dispute since Hintikka. Fitch's paradox (1963) uses only distribution over conjunction, factivity and necessitation to turn the knowability principle φ → ◇Kφ into the collapse φ → Kφ, so the language cannot state a modest verificationism. Knowledge is truth in all indistinguishable worlds and nothing else, so justification has no representation and Gettier cases are invisible. Common knowledge makes the logic non-compact and, by Halpern and Moses (1990), unattainable in asynchronous systems or over unreliable channels.

© 2026 Lingenic LLC