This paper connects the following four topics: a class of generalized graphs whose relations do not have fixed arities called hypergraphs, a family of non-normal modal logics rejecting the aggregative axiom, an epistemic framework fighting logical omniscience, and the classical group knowledge modality of `someone knows’. Through neighborhood frames as their meeting point, we show that, among many completeness results obtained in this paper, the limit of a family of weakly aggregative logics is both exactly the modal logic of hypergraphs and also the epistemic logic of local reasoning with veracity and positive introspection, and upon adding a single combinatorial axiom, it is also the logic of `someone knows’ for a fixed finite number of positively introspective agents. At the core of all these completeness results is a new canonical neighborhood model construction for monotone modal logics that is capable of dealing with all these diverse cases. We also provide an axiomatization for the logic of all non-n-colorable hypergraphs based on a filtration argument that also shows the decidability of the logics of hypergraphs we study.
(a largely extended journal version of the LORI21 conference paper)
In this paper, we give an alternative semantics to the non-normal logic of knowing how proposed by Fervari et al. (2017), based on a class of Kripke neighbor-hood models with both the epistemic relations and neighborhood structures. This alternative semantics is inspired by the same quantifier alternation pattern of ∃∀in the semantics of the know-how modality and the (monotonic) neighborhood semantics for the standard modality. We show that this new semantics is equivalent to the original Kripke semantics in terms of the validities. A key result is a representation theorem showing that the more abstract Kripke neighborhood models can be represented by the concrete Kripke models with action transitions modulo the valid formulas. We prove the completeness of the logic for the neighborhood semantics. The neighborhood semantics can be adapted to other variants of logics of knowing how. It provides us a powerful technical tool to study these logics while preserving the basic semantic intuition.
Abstract. When we say “I know why he was late”, we know not only the fact that he was late, but also an explanation of this fact. We propose a logical framework of “knowing why” inspired by the existing formal studies on why-questions, scientific explanation, and justification logic. We introduce the $Ky_i$ operator into the language of epistemic logic to express “agent i knows why phi” and propose a Kripke-style semantics of such expressions in terms of knowing an explanation of phi. We obtain two sound and complete axiomatizations w.r.t. two different model classes depending on different assumptions about introspection.
Abstract: A true lie is a lie that becomes true when announced. In a logic of announcements, where the announcing agent is not modelled, a true lie is a formula (that is false and) that becomes true when announced. We investigate true lies and other types of interaction between announced formulas, their preconditions and their postconditions, in the setting of Gerbrandy’s logic of believed announcements, wherein agents may have or obtain incorrect beliefs. Our results are on the satisfiability and validity of instantiations of these semantically defined categories, on iterated announcements, including arbitrarily often iterated announcements, and on syntactic characterization. We close with results for iterated announcements in the logic of knowledge (instead of belief), and for lying as private announcements (instead of public announcements) to different agents. Detailed examples illustrate our lying concepts.
Abstract: In this paper, we propose a decidable single-agent modal logic for reasoning about goal-directed “knowing how”, based on ideas from linguistics, philosophy, modal logic, and automated planning in AI. We first define a modal language to express “I know how to guarantee (Formula presented.) given (Formula presented.)” with a semantics based not on standard epistemic models but on labeled transition systems that represent the agent’s knowledge of his own abilities. The semantics is inspired by conformant planning in AI. A sound and complete proof system is given to capture valid reasoning patterns, which highlights the compositional nature of “knowing how”. The logical language is further extended to handle knowing how to achieve a goal while maintaining other conditions.
(This is an extended journal version of the LORI2015 paper)
Abstract. In the literature, different axiomatizations of Public Announcement Logic (PAL) have been proposed. Most of these axiomatizations share a “core set” of the so-called “reduction axioms”. In this paper, by designing non-standard Kripke semantics for the language of PAL, we show that the proof system based on this core set of axioms does not completely axiomatize PAL without additional axioms and rules. In fact, many of the intuitive axioms and rules we took for granted could not be derived from the core set. Moreover, we also propose and advocate an alternative yet meaningful axiomatization of PAL without the reduction axioms. The completeness is proved directly by a detour method using the canonical model where announcements are treated as merely labels for modalities as in normal modal logics. This new axiomatization and its completeness proof may sharpen our understanding of PAL and can be adapted to other dynamic epistemic logics.
(largely extended journal version of the LORI2011 paper)
Abstract. Security properties naturally combine temporal aspects of protocols with aspects of knowledge of the agents. Since BAN-logic, there have been several initiatives and attempts to incorporate epistemics into the analysis of security protocols. In this paper, we give an overview of work in the field and present it in a unified perspective, with comparisons on technical subtleties that have been employed in different approaches. Also, we study to which degree the use of epistemics is essential for the analysis of security protocols. We look for formal conditions under which knowledge modalities can bring extra expressive power to pure temporal languages. On the other hand, we discuss the cost of the epistemic operators in terms of model checking complexity.