A Logic of Implicit and Explicit Belief

Hector J. LevesqueAAAI 1984

Abstract

In classical epistemic logic, agents are often modeled as "logically omniscient," meaning they are assumed to know all logical consequences of their beliefs. This assumption is computationally intractable and psychologically unrealistic for artificial intelligence. Hector Levesque’s 1984 paper proposes a formal logic that distinguishes between explicit and implicit belief. By utilizing a semantics based on partial "situations" rather than complete "possible worlds," Levesque provides a framework where reasoning about explicit beliefs is computationally efficient (linear time), offering a path toward resource-limited reasoning in AI systems.

1. Introduction: The Problem of Logical Omniscience

The modeling of knowledge and belief in AI has traditionally relied on "possible-world semantics." In this framework, an agent is said to believe a proposition $\alpha$ if $\alpha$ is true in every world the agent considers possible. While mathematically elegant, this approach suffers from the Logical Omniscience problem. If an agent believes a set of premises, they are formally required to believe every logical consequence of those premises.

For a computational agent, this is a fatal flaw. If a robot's knowledge base contains the axioms of arithmetic, possible-world semantics implies the robot "knows" every complex mathematical theorem, even those it has never computed. This makes reasoning co-NP-complete in the propositional case and undecidable in first-order logic. To build realistic AI, we need a logic that accounts for resource limitations—an agent that can believe $P$ and $P \supset Q$ without necessarily having yet derived $Q$.

2. Methods: Explicit vs. Implicit Belief

Levesque introduces a formal logic, $L$, that bifurcates the notion of belief into two distinct operators:

  • Explicit Belief ($B\alpha$): These are the propositions the agent actively holds or has "in its head."
  • Implicit Belief ($L\alpha$): These are the propositions that are logical consequences of the agent's explicit beliefs.

The goal of this logic is to allow $B\alpha$ to remain a subset of $L\alpha$ without forcing them to be identical. This allows us to model an agent that is "rational" (its beliefs have consequences) but "limited" (it hasn't realized all those consequences yet).

From Possible Worlds to Situations

The technical innovation of the paper lies in the move from Possible Worlds to Situations. In classical logic, a "world" is a complete assignment of truth values: every proposition is either true or false. Levesque’s situations are partial. A situation can:

  1. Support the truth of $P$.
  2. Support the falsity of $P$.
  3. Support neither (making the situation incomplete).
  4. Support both (making the situation incoherent).

By defining explicit belief in terms of these partial situations, the logic avoids the pitfalls of classical entailment. For example, in classical logic, a contradiction ($P \land \neg P$) implies everything. In Levesque’s logic, an agent can hold an incoherent belief without their entire belief system "exploding" into believing every possible sentence. This behavior mirrors Relevance Logic, where the relationship between a premise and a conclusion requires a meaningful connection rather than just a formal truth-functional link.

3. Key Insights: The Granularity of Belief

Levesque’s approach finds a middle ground between two extremes in AI theory:

  • Syntactic Approaches: These treat beliefs as mere strings of text. They are too "fine-grained" because they fail to recognize that "A and B" is logically the same as "B and A."
  • Possible-World Approaches: These are too "coarse-grained" because they treat all logically equivalent statements as identical, regardless of complexity.

By modeling explicit belief as a set of situations, Levesque creates a "Goldilocks" zone. If every situation the agent considers possible supports $\alpha$, then the agent explicitly believes $\alpha$. This allows for a more nuanced representation of what an agent actually "knows" versus what is merely implied by their knowledge.

4. Key Results: The Computational Payoff

The most significant contribution for computer scientists is the dramatic reduction in computational complexity for explicit reasoning:

  • Implicit Reasoning is Hard: Determining if a sentence is an implicit belief (a logical consequence) remains co-NP-complete. In the worst case, this takes exponential time relative to the size of the knowledge base (KB).
  • Explicit Reasoning is Easy: Determining if a sentence $\alpha$ is explicitly believed by a KB can be computed in $O(mn)$ time (linear relative to the size of the KB and the sentence).

This result suggests that a robot could quickly query its explicit beliefs to act in real-time, while relegating "implicit" reasoning (connecting the dots) to a background process or a more intensive planning phase.

5. Limitations and Future Work

While providing a solution to the omniscience problem, the paper identifies several areas for further development:

  • Propositional Scope: The current framework is limited to propositional logic. Extending these semantics to First-Order Logic (with quantifiers like "for all") is a necessary but difficult next step.
  • No Meta-Knowledge: The logic does not allow for "beliefs about beliefs" (e.g., "I believe that you believe P"). The author intentionally excluded this to maintain simplicity in the initial semantics.
  • The Necessary Truth Problem: The paper notes that "necessarily true" sentences (like $2+2=4$) might still be implicitly believed even if they aren't logically valid in the system, though the author suggests using "expansive" model structures as a potential fix.

6. Conclusion

Levesque’s work provides a rigorous foundation for modeling agents that are neither perfectly logical nor completely erratic. By grounding explicit belief in partial situations, he bridges the gap between the idealizations of philosophy and the practical constraints of real-world artificial intelligence.

Summary updated

BibTeX
@inproceedings{levesque1984logic,
  author = {Hector J. Levesque},
  title = {{A Logic of Implicit and Explicit Belief}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure