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

AAAI Conferences

We introduce a new semantics for a logic of explicit and implicit beliefs based on the concept of multi-agent belief base. Differently from existing Kripke-style semantics for epistemic logic in which the notions of possible world and doxastic/epistemic alternative are primitive, in our semantics they are non-primitive but are defined from the concept of belief base. We provide a complete axiomatization and a decidability result for our logic.


Rethinking Epistemic Logic with Belief Bases

arXiv.org Artificial Intelligence

We introduce a new semantics for a logic of explicit and implicit beliefs based on the concept of multi-agent belief base. Differently from existing Kripke-style semantics for epistemic logic in which the notions of possible world and doxastic/epistemic alternative are primitive, in our semantics they are non-primitive but are defined from the concept of belief base. We provide a complete axiomatization and prove decidability for our logic via a finite model argument. We also provide a polynomial embedding of our logic into Fagin & Halpern's logic of general awareness and establish a complexity result for our logic via the embedding.


Multi-Agent Only Knowing on Planet Kripke

AAAI Conferences

The idea of only knowing is a natural and intuitive notion to precisely capture the beliefs of a knowledge base. However, an extension to the many agent case, as would be needed in many applications, has been shown to be far from straightforward. For example, previous Kripke frame-based accounts appeal to proof-theoretic constructions like canonical models, while more recent works in the area abandoned Kripke semantics entirely. We propose a new account based on Moss’ characteristic formulas, formulated for the usual Kripke semantics. This is shown to come with other benefits: the logic admits a group version of only knowing, and an operator for assessing the epistemic entrenchment of what an agent or a group only knows is definable. Finally, the multi-agent only knowing operator is shown to be expressible with the cover modality of classical modal logic, which then allows us to obtain a completeness result for a fragment of the logic.


Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results

AAAI Conferences

We introduce epistemic quantified boolean logic (EQBL), an extension of propositional epistemic logic with quantification over propositions. We show that EQBL can express relevant properties about agents’ knowledge in multi-agent contexts, such as “agent a knows as much as agent b”. We analyse the expressiveness of EQBL through a translation into monadic second-order logic, and provide completeness results w.r.t. various classes of Kripke frames. Finally, we prove that model checking EQBL is PSPACE-complete. Thus, the complexity of model checking EQBL is no harder than for (non-modal) quantified boolean logic.


An Extended Interpreted System Model for Epistemic Logics

AAAI Conferences

The interpreted system model offers a computationally grounded model, in terms of the states of computer processes, to S5 epistemic logics. This paper extends the interpreted system model, and provides a computationally grounded one, called the interpreted perception system model, to those epistemic logics other than S5. It is usually assumed, in the interpreted system model, that those parts of the environment that are visible to an agent are correctly perceived by the agent as a whole. The essential idea of the interpreted perception system model is that an agent may have incorrect perception or observations to the visible parts of the environment and the agent may not be aware of this. The notion of knowledge can be defined so that an agent knows a statement iff the statement holds in those states that the agent can not distinguish (from the current state) by using only her correct observations. We establish a logic of knowledge and certainty, called KC logic, with a sound and complete proof system. The knowledge modality in this logic is S4 valid. It becomes S5 if we assume an agent always has correct observations; and more interestingly, it can be S4.2 or S4.3 under other natural constraints on agents and their sensors to the environment.