Epistemic Equilibrium Logic

Luis Fariñas del Cerro, Andreas Herzig, Ezgi Iraz SuIJCAI 2015

Abstract

Epistemic specifications extend Answer Set Programming (ASP) by allowing reasoning across multiple answer sets. Historically, defining a robust semantics for these specifications has been difficult, often leading to counter-intuitive results. This paper presents Epistemic Equilibrium Logic, which extends the logic of Here-and-There with epistemic modal operators. By integrating truth minimization with ignorance maximization, the framework provides a stable semantics that characterizes strong equivalence, offering a powerful tool for the formal analysis and optimization of epistemic logic programs.

Introduction

In Answer Set Programming (ASP), a program typically yields multiple "answer sets," representing different valid solutions. Epistemic specifications extend this by allowing programmers to reason across these sets—for instance, determining if a fact is known to be true in every possible answer set. While this concept was pioneered by Michael Gelfond in the early 1990s, the field has lacked a stable mathematical semantics. Previous attempts often resulted in counter-intuitive behaviors or failed to align with the underlying logic of ASP, the logic of Here-and-There (HT).

The core challenge lies in balancing two competing requirements: the minimization of truth (believing only what is necessary) and the maximization of ignorance (considering all possible world views to avoid unwarranted knowledge assumptions).

Theoretical Framework

The authors construct their framework through a three-tiered approach:

  1. Epistemic Here-and-There (EHT) Logic: The standard 3-valued HT logic is extended with two modal operators: $K$ ("it is known") and $\hat{K}$ ("it is possible"). This creates a monotonic logic where models are collections of HT models.
  2. Epistemic Equilibrium Models (EEM): A minimality criterion is applied to EHT models, mirroring how standard Equilibrium Logic defines answer sets by selecting the "most minimal" models.
  3. Autoepistemic Equilibrium Models (AEEM): To capture the "world view" intuition, EEMs are further refined by selecting models that are maximal under a specific preference ordering, ensuring the maximization of ignorance.
Comparison of formulas, world views, and Epistemic Equilibrium Models (EEMs).

Key Insights

A critical finding is that EHT logic preserves the heredity property of HT logic: if a formula holds in a "here" state, it remains true in the "there" state. This maintains the logic's status as a proper intermediate logic between intuitionistic and classical modal logic.

Furthermore, the operators $K$ and $\hat{K}$ are not simple duals. This non-duality is a characteristic of intuitionistic-style logics and is essential for correctly interpreting the "default negation" prevalent in logic programming. Perhaps most significantly, the authors prove that EHT logic provides the necessary foundation for testing strong equivalence. Two programs are strongly equivalent if they can be interchanged in any context without affecting the outcome; the authors demonstrate that EHT logic is the exact tool needed to verify this property for epistemic programs.

Results and Semantic Alignment

The proposed AEEM semantics aligns with the most intuitive results in existing literature while providing a more rigorous logical grounding. The framework's robustness is particularly evident in its handling of complex edge cases involving nested negations and epistemic operators.

Comprehensive comparison of epistemic specifications and their corresponding models.

The "Strong Equivalence Theorem" established in this work proves that two epistemic theories share the same AEEMs if and only if they are equivalent in EHT logic. This result is a powerful asset for program optimization and formal verification within the ASP community.

Conclusion and Future Directions

While Epistemic Equilibrium Logic provides a solid foundation for single-agent reasoning, several avenues for future research remain. Extending the framework to multi-agent epistemic logic would allow for reasoning about the knowledge of other agents. Additionally, the computational complexity of finding AEEMs and checking EHT validity needs further investigation to facilitate the development of efficient solvers. Finally, integrating the logic with other language features, such as aggregates or choice rules, would broaden its practical applicability.

Summary updated

BibTeX
@inproceedings{cerro2015epistemic,
  author = {Luis Fariñas del Cerro and Andreas Herzig and Ezgi Iraz Su},
  title = {{Epistemic Equilibrium Logic}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure