In Praise of Belief Bases: Doing Epistemic Logic Without Possible Worlds

Emiliano LoriniAAAI 2018 · DOI

Abstract

Traditional epistemic logic relies on Kripke semantics, which often leads to the problem of logical omniscience and lacks grounding in the actual internal states of agents. This paper proposes the Logic of Doxastic Attitudes (LDA), a framework that replaces primitive "possible worlds" with concrete belief bases. By distinguishing between explicit and implicit beliefs, LDA provides a more realistic model for resource-bounded agents while maintaining mathematical rigor and decidability.

Introduction: The Limits of Possible Worlds

Traditional epistemic logic, the formal study of knowledge and belief, has long relied on Kripke semantics. In this framework, an agent's belief is defined by "possible worlds": an agent believes a proposition if it holds true in all worlds they consider possible. While mathematically elegant, this approach faces two significant hurdles:

  1. Logical Omniscience: It assumes agents are perfect logicians who instantly believe every logical consequence of their knowledge. This is an unrealistic assumption for both humans and resource-constrained AI.
  2. Ungroundedness: The "alternative worlds" are treated as primitives. There is no explanation for why an agent considers certain worlds possible, making it difficult to link the logic to the actual internal memory or database of a robotic agent.

To address these issues, Emiliano Lorini introduces the Logic of Doxastic Attitudes (LDA), which grounds agent beliefs in concrete belief bases—sets of formulas an agent explicitly holds.

The LDA Framework: Explicit vs. Implicit Belief

The core innovation of LDA is its two-step language construction, which separates an agent's raw data from their inferential capacity:

  • Explicit Belief ($E_i\alpha$): This represents formulas that agent $i$ actually holds in their belief base.
  • Implicit Belief ($I_i\phi$): This represents formulas that are logical consequences of the agent's explicit beliefs, given the "common ground" or shared information within the multi-agent system.

By using belief bases, the logic becomes directly implementable in AI systems, where an agent's belief base can be mapped to a symbolic database or a set of rules. This structure naturally breaks logical omniscience: an agent can explicitly believe $P$ and $P \to Q$ without necessarily having $Q$ in their explicit belief base; $Q$ remains merely an implicit belief until processed.

Semantic Foundations and Equivalence

A key theoretical contribution of this work is bridging the gap between belief-base semantics and traditional Kripke-style models. The author introduces Notional Doxastic Models (NDM) and Quasi-NDMs to facilitate this. In this framework, "possible worlds" are no longer primitive; instead, a world is considered a "doxastic alternative" for an agent if it satisfies all formulas in that agent's belief base.

Relationships between different model classes in LDA semantics.

As shown in the figure above, the paper establishes formal equivalences between these different semantic structures. Theorem 1, 2, and 3 provide the mathematical foundation for moving between belief bases, NDMs, and their finite counterparts. This equivalence ensures that the intuitive grounding of belief bases does not come at the cost of the formal rigor found in traditional epistemic logic.

Key Results and Decidability

The paper provides a sound and complete axiomatization for LDA. It utilizes the standard System KD for implicit belief and introduces a specific interaction axiom: $E_i\alpha \to I_i\alpha$, stating that any explicit belief is necessarily an implicit one.

Furthermore, despite supporting higher-order beliefs (e.g., "Agent A explicitly believes that Agent B implicitly believes $P$"), the author proves that the satisfiability problem for LDA is decidable. Through a "filtration" argument, the paper demonstrates the finite model property: if a formula is satisfiable, it is satisfiable in a finite model. This is crucial for the practical application of the logic in automated reasoning.

Conclusion and Future Directions

LDA offers a promising path forward for epistemic logic by grounding abstract reasoning in concrete agent states. While the current work focuses on doxastic attitudes (beliefs), future extensions could include extending the logic to knowledge (where beliefs must be true), modeling belief dynamics through public announcements, and leveraging the compact representation of belief bases for more efficient model-checking algorithms.

Summary updated

BibTeX
@inproceedings{lorini2018praise,
  author = {Emiliano Lorini},
  title = {{In Praise of Belief Bases: Doing Epistemic Logic Without Possible Worlds}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11560},
}
Figure