Collaborating Authors

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.

Exploiting Belief Bases for Building Rich Epistemic Structures Artificial Intelligence

We introduce a semantics for epistemic logic exploiting a belief base abstraction. Differently from existing Kripke-style semantics for epistemic logic in which the notions of possible world and epistemic alternative are primitive, in the proposed semantics they are non-primitive but are defined from the concept of belief base. We show that this semantics allows us to define the universal epistemic model in a simpler and more compact way than existing inductive constructions of it. We provide (i) a number of semantic equivalence results for both the basic epistemic language with "individual belief" operators and its extension by the notion of "only believing", and (ii) a lower bound complexity result for epistemic logic model checking relative to the universal epistemic model.

Parametric Constructive Kripke-Semantics for Standard Multi-Agent Belief and Knowledge (Knowledge As Unbiased Belief) Artificial Intelligence

We propose parametric constructive Kripke-semantics for multi-agent KD45-belief and S5-knowledge in terms of elementary set-theoretic constructions of two basic functional building blocks, namely bias (or viewpoint) and visibility, functioning also as the parameters of the doxastic and epistemic accessibility relation. The doxastic accessibility relates two possible worlds whenever the application of the composition of bias with visibility to the first world is equal to the application of visibility to the second world. The epistemic accessibility is the transitive closure of the union of our doxastic accessibility and its converse. Therefrom, accessibility relations for common and distributed belief and knowledge can be constructed in a standard way. As a result, we obtain a general definition of knowledge in terms of belief that enables us to view S5-knowledge as accurate (unbiased and thus true) KD45-belief, negation-complete belief and knowledge as exact KD45-belief and S5-knowledge, respectively, and perfect S5-knowledge as precise (exact and accurate) KD45-belief, and all this generically for arbitrary functions of bias and visibility. Our results can be seen as a semantic complement to previous foundational results by Halpern et al. about the (un)definability and (non-)reducibility of knowledge in terms of and to belief, respectively.

Multi-Agent Only-Knowing Revisited Artificial Intelligence

Levesque introduced the notion of only-knowing to precisely capture the beliefs of a knowledge base. He also showed how only-knowing can be used to formalize non-monotonic behavior within a monotonic logic. Despite its appeal, all attempts to extend only-knowing to the many agent case have undesirable properties. A belief model by Halpern and Lakemeyer, for instance, appeals to proof-theoretic constructs in the semantics and needs to axiomatize validity as part of the logic. It is also not clear how to generalize their ideas to a first-order case. In this paper, we propose a new account of multi-agent only-knowing which, for the first time, has a natural possible-world semantics for a quantified language with equality. We then provide, for the propositional fragment, a sound and complete axiomatization that faithfully lifts Levesque's proof theory to the many agent case. We also discuss comparisons to the earlier approach by Halpern and Lakemeyer.

Preferential Structures for Comparative Probabilistic Reasoning

AAAI Conferences

Qualitative and quantitative approaches to reasoning about uncertainty can lead to different logical systems for formalizing such reasoning, even when the language for expressing uncertainty is the same. In the case of reasoning about relative likelihood, with statements of the form φ 􏰂≥ ψ expressing that φ is at least as likely as ψ, a standard qualitative approach using preordered preferential structures yields a dramatically different logical system than a quantitative approach using probability measures. In fact, the standard preferential approach validates principles of reasoning that are incorrect from a probabilistic point of view. However, in this paper we show that a natural modification of the preferential approach yields exactly the same logical system as a probabilistic approach — not using single probability measures, but rather sets of probability measures. Thus, the same preferential structures used in the study of non-monotonic logics and belief revision may be used in the study of comparative probabilistic reasoning based on imprecise probabilities.