In this paper a unified framework for dealing with a broad family of propositional multimodal logics is developed. The key tools for presentation of the logics are the notions of closure relation operation and monotonous relation operation. The two classes of logics: FiRe-logics (finitely reducible logics) and LaFiRe-logics (FiRe-logics with local agreement of accessibility relations) are introduced within the proposed framework. Further classes of logics can be handled indirectly by means of suitable translations. It is shown that the logics from (...) these classes have the finite model property with respect to the class of -formulae, i.e. each -formula has a -model iff it has a finite -model. Roughly speaking, a -formula is logically equivalent to a formula in negative normal form without occurrences of modal operators with necessity force. In the proof we introduce a substantial modification of Claudio Cerrato's filtration technique that has been originally designed for graded modal logics. The main core of the proof consists in building adequate restrictions of models while preserving the semantics of the operators used to build terms indexing the modal operators. (shrink)

We study a knowledge logic that assumes that to each set of agents, an indiscernibility relation is associated and the agents decide the membership of objects or states up to this indiscernibility relation. Its language contains a family of relative knowledge operators. We prove the decidability of the satisfiability problem, we show its EXPTIME-completeness and as a side-effect, we define a complete Hilbert-style axiomatization.

We show the completeness of a Hilbert-style system LK defined by M. Valiev involving the knowledge operator K dedicated to the reasoning with incomplete information. The completeness proof uses a variant of Makinson's canonical model construction. Furthermore we prove that the theoremhood problem for LK is co-NP-complete, using techniques similar to those used to prove that the satisfiability problem for propositional S5 is NP-complete.

This paper combines a non-contingency logic with an epistemic logic by means of fusions and products of modal systems. Some consequences of these interplays are pointed out.

This work introduces a two-dimensional modal logic to represent agents' Concurrent Common Knowledge in distributed systems. Unlike Common Knowledge, Concurrent Common Knowledge is a kind of agreement reachable in asynchronous environments. The formalization of such type of knowledge is based on a model for asynchronous systems and on the definition of Concurrent Knowledge introduced before in paper [5]. As a proper semantics, we review our concept of closed sub-product of modal logics which is based on the product of modal logics. (...) The key idea is to reason about Concurrent Knowledge under a two-dimensional approach, regarding asynchronous runs and consistent global states as dimensions. We present an axiomatic system for the logic and issue the corresponding soundness and completeness proofs. (shrink)

In a previous work we introduced the algorithm \SQEMA\ for computing first-order equivalents and proving canonicity of modal formulae, and thus established a very general correspondence and canonical completeness result. \SQEMA\ is based on transformation rules, the most important of which employs a modal version of a result by Ackermann that enables elimination of an existentially quantified predicate variable in a formula, provided a certain negative polarity condition on that variable is satisfied. In this paper we develop several extensions of (...) \SQEMA\ where that syntactic condition is replaced by a semantic one, viz. downward monotonicity. For the first, and most general, extension \SSQEMA\ we prove correctness for a large class of modal formulae containing an extension of the Sahlqvist formulae, defined by replacing polarity with monotonicity. By employing a special modal version of Lyndon's monotonicity theorem and imposing additional requirements on the Ackermann rule we obtain restricted versions of \SSQEMA\ which guarantee canonicity, too. (shrink)

The problem of finding sufficient doxastic conditions for backward induction in games of perfect information is analyzed in a syntactic framework with subjunctive conditionals. This allows to describe the structure of the game by a logical formula and consequently to treat beliefs about this structure in the same way as beliefs about rationality. A backward induction and a non-Nash equilibrium result based on higher level belief in rationality and the structure of the game are derived.

In this paper, I develop a syntactic framework for the analysis ofstrategic form games that is based on a straightforward combination ofstandard systems of doxastic, probabilistic and conditionalpropositional logic. In particular, for the probabilistic part I makeuse of the axiomatization provided in Fagin and Halpern (1994). The use ofconditionals allows to represent a strategic form game by a logicalformula in a very natural way. Also expected utility maximization can benaturally captured. I use this framework to prove a version of a (...) resulton Nash equilibrium conjectures first presented in Aumann and Brandenburger (1995). (shrink)

S4.2 is the modal logic of directed partial pre-orders and/or the modal logic of reflexive and transitive relational frames with a final cluster. It holds a distinguished position in philosophical...

We investigate an aspect of defeasibility that has somewhat been overlooked by the non-monotonic reasoning community, namely that of defeasible modes of reasoning. These aim to formalise defeasibility of the traditional notion of necessity in modal logic, in particular of its different readings as action, knowledge and others in specific contexts, rather than defeasibility of conditional forms. Building on an extension of the preferential approach to modal logics, we introduce new modal osperators with which to formalise the notion of defeasible (...) necessity and distinct possibility, and that can be used to represent expected effects, refutable knowledge, and so on. We show how KLM-style conditionals can smoothly be integrated with our richer language. We also propose a tableau calculus which is sound and complete with respect to our modal preferential semantics, and of which the computational complexity remains in the same class as that of the underlying classical modal logic. (shrink)

We investigate an axiomatization of the notion of common belief that makes use of no rules of inference and highlight the property of the set of accessibility relations that characterizes each axiom.

In public announcement logic it is assumed that all agents pay attention to the announcement. Weaker observational conditions can be modelled in action model logic. In this work, we propose a version of public announcement logic wherein it is encoded in the states of the epistemic model which agents pay attention to the announcement. This logic is called attention-based announcement logic. We give an axiomatization of the logic and prove that complexity of satisfiability is the same as that of public (...) announcement logic, and therefore lower than that of action model logic. An attention-based announcement can also be described as an action model. We extend our logic by integrating attention change. Finally, we add the notion of common belief to the language, we exploit this to formalize the concept of joint attention, that has been widely discussed in the philosophical and cognitive science literature, and we provide a corresponding axiomatization. This axiomatization also employs the auxiliary notion of attention-based relativized common belief. (shrink)

We deal with the fragment of modal logic consisting of implications of formulas built up from the variables and the constant ‘true’ by conjunction and diamonds only. The weaker language allows one to interpret the diamonds as the uniform reflection schemata in arithmetic, possibly of unrestricted logical complexity. We formulate an arithmetically complete calculus with modalities labeled by natural numbers and ω, where ω corresponds to the full uniform reflection schema, whereas n<ω corresponds to its restriction to arithmetical Πn+1-formulas. This (...) calculus is shown to be complete w.r.t. a suitable class of finite Kripke models and to be decidable in polynomial time. (shrink)

The paper presents a new logic for reasoning about the formation of beliefs through perception or through inference in non-omniscient resource-bounded agents. The logic distinguishes the concept of explicit belief from the concept of background knowledge. This distinction is reflected in its formal semantics and axiomatics: we use a non-standard semantics putting together a neighborhood semantics for explicit beliefs and relational semantics for background knowledge, and we have specific axioms in the logic highlighting the relationship between the two concepts. Mental (...) operations of perceptive type and inferential type, having effects on epistemic states of agents, are primitives in the object language of the logic. At the semantic level, they are modelled as special kinds of model-update operations, in the style of dynamic epistemic logic. Results about axiomatization, decidability and complexity for the logic are given in the paper. (shrink)

An introduction to the special issue on epistemic logic and the foundations of game theory edited by Michael Bacharach and Philippe Mongin. Contributors are Michael Bacharach, Robert Stalnaker, Salvatore Modica and Aldo Rustichini, Luc Lismont and Philippe Mongin, and Hyun-Song Shin and Timothy Williamson.

Description logics are a family of knowledge representation formalisms that are descended from semantic networks and frames via the system Kl-one. During the last decade, it has been shown that the important reasoning problems (like subsumption and satisfiability) in a great variety of description logics can be decided using tableau-like algorithms. This is not very surprising since description logics have turned out to be closely related to propositional modal logics and logics of programs (such as propositional dynamic logic), for which (...) tableau procedures have been quite successful.Nevertheless, due to different underlying institutions and applications, most description logics differ significantly from run-of-the-mill modal and program logics. Consequently, the research on tableau algorithms in description logics led to new techniques and results, which are, however, also of interest for modal logicians. In this article, we will focus on three features that play an important rôle in description logics (number restrictions, terminological axioms, and role constructors), and show how they can be taken into account by tableau algorithms. (shrink)

Knowledge based privacy policies are more declarative than traditional action based ones, because they specify only what is permitted or forbidden to know, and leave the derivation of the permitted actions to a security monitor. This inference problem is already non trivial with a static privacy policy, and becomes challenging when privacy policies can change over time. We therefore introduce a dynamic modal logic that permits not only to reason about permitted and forbidden knowledge to derive the permitted actions, but (...) also to represent explicitly the declarative privacy policies together with their dynamics. The logic can be used to check both regulatory and behavioral compliance, respectively by checking that the permissions and obligations set up by the security monitor of an organization are not in conflict with the privacy policies, and by checking that these obligations are indeed enforced. (shrink)

Logical theories for representing knowledge are often plagued by the so-called Logical Omniscience Problem. The problem stems from the clash between the desire to model rational agents, which should be capable of simple logical inferences, and the fact that any logical inference, however complex, almost inevitably consists of inference steps that are simple enough. This contradiction points to the fruitlessness of trying to solve the Logical Omniscience Problem qualitatively if the rationality of agents is to be maintained. We provide a (...) quantitative solution to the problem compatible with the two important facets of the reasoning agent: rationality and resource boundedness. More precisely, we provide a test for the logical omniscience problem in a given formal theory of knowledge. The quantitative measures we use are inspired by the complexity theory. We illustrate our framework with a number of examples ranging from the traditional implicit representation of knowledge in modal logic to the language of justification logic, which is capable of spelling out the internal inference process. We use these examples to divide representations of knowledge into logically omniscient and not logically omniscient, thus trying to determine how much information about the reasoning process needs to be present in a theory to avoid logical omniscience. (shrink)

(2012). Modal logics for reasoning about infinite unions and intersections of binary relations. Journal of Applied Non-Classical Logics: Vol. 22, No. 4, pp. 275-294. doi: 10.1080/11663081.2012.705960.

We develop a conceptually clear, intuitive, and feasible decision procedure for testing satisfiability in the full multi\-agent epistemic logic \CMAELCD\ with operators for common and distributed knowledge for all coalitions of agents mentioned in the language. To that end, we introduce Hintikka structures for \CMAELCD\ and prove that satisfiability in such structures is equivalent to satisfiability in standard models. Using that result, we design an incremental tableau-building procedure that eventually constructs a satisfying Hintikka structure for every satisfiable input set of (...) formulae of \CMAELCD\ and closes for every unsatisfiable input set of formulae. (shrink)

ABSTRACT In this paper we define two logics, KLn and BLn, and present tableau-based decision procedures for both. KLn is a temporal logic of knowledge. Thus, in addition to the usual connectives of linear discrete temporal logic, it contains a set of unary modal connectives for representing the knowledge possessed by agents. The logic BLn is somewhat similar; it is a temporal logic that contains connectives for representing the beliefs of agents. In addition to a complete formal definition of the (...) two logics and their decision procedures, the paper includes a brief review of their applications in AI and mainstream computer science, correctness proofs for the decision procedures, a number of worked examples illustrating the decision procedures, and some pointers to further work. (shrink)

While dynamic epistemic logics with common knowledge have been extensively studied, dynamic epistemic logics with distributed knowledge have so far received far less attention. In this paper we study extensions of public announcement logic ( $\mathcal{PAL }$ ) with distributed knowledge, in particular their expressivity, axiomatisations and complexity. $\mathcal{PAL }$ extended only with distributed knowledge is not more expressive than standard epistemic logic with distributed knowledge. Our focus is therefore on $\mathcal{PACD }$ , the result of adding both common and (...) distributed knowledge to $\mathcal{PAL }$ , which is more expressive than each of its component logics. We introduce an axiomatisation of $\mathcal{PACD }$ , which is not surprising: it is the combination of well-known axioms. The completeness proof, however, is not trivial, and requires novel combinations and extensions of techniques for dealing with $S5$ knowledge, distributed knowledge, common knowledge and public announcements at the same time. We furthermore show that $\mathcal{PACD }$ is decidable, more precisely that it is $\textsc {exptime}$ -complete. This result also carries over to $\mathcal{S 5\mathcal CD }$ with common and distributed knowledge operators for all coalitions (and not only the grand coalition). Finally, we propose a notion of a trans-bisimulation to generalise certain results and give deeper insight into the proofs. (shrink)

When agents know a protocol, this leads them to have expectations about future observations. Agents can update their knowledge by matching their actual observations with the expected ones. They eliminate states where they do not match. In this paper, we study how agents perceive protocols that are not commonly known, and propose a semantics-driven logical framework to reason about knowledge in such scenarios. In particular, we introduce the notion of epistemic expectation models and a propositional dynamic logic-style epistemic logic for (...) reasoning about knowledge via matching agentsÊ expectations to their observations. It is shown how epistemic expectation models can be obtained from epistemic protocols. Furthermore, a characterization is presented of the effective equivalence of epistemic protocols. We introduce a new logic that incorporates updates of protocols and that can model reasoning about knowledge and observations. Finally, the framework is extended to incorporate fact-changing actions, and a worked-out example is given. © 2013 Elsevier B.V. (shrink)

We propose a dynamic logic of lying, wherein a ‘lie that $\varphi $ ’ (where $\varphi $ is a formula in the logic) is an action in the sense of dynamic modal logic, that is interpreted as a state transformer relative to the formula $\varphi $ . The states that are being transformed are pointed Kripke models encoding the uncertainty of agents about their beliefs. Lies can be about factual propositions but also about modal formulas, such as the beliefs of (...) other agents or the belief consequences of the lies of other agents. We distinguish two speaker perspectives: (Obs) an outside observer who is lying to an agent that is modelled in the system, and (Ag) an agent who is lying to another agent, and where both are modelled in the system. We distinguish three addressee perspectives: (Cred) the credulous agent who believes everything that it is told (even at the price of inconsistency), (Skep) the skeptical agent who only believes what it is told if that is consistent with its current beliefs, and (Rev) the belief revising agent who believes everything that it is told by consistently revising its current, possibly conflicting, beliefs. The logics have complete axiomatizations, which can most elegantly be shown by way of their embedding in what is known as action model logic or in the extension of that logic to belief revision. (shrink)

Branching-time temporal logics have proved to be an extraordinarily successful tool in the formal specification and verification of distributed systems. Much of their success stems from the tractability of the model checking problem for the branching time logic CTL, which has made it possible to implement tools that allow designers to automatically verify that systems satisfy requirements expressed in CTL. Recently, CTL was generalised by Alur, Henzinger, and Kupferman in a logic known as Alternating-time Temporal Logic (ATL). The key insight (...) in ATL is that the path quantifiers of CTL could be replaced by cooperation modalities, of the form , where is a set of agents. The intended interpretation of an ATL formula is that the agents can cooperate to ensure that holds (equivalently, that have a winning strategy for ). In this paper, we extend ATL with knowledge modalities, of the kind made popular in the work of Fagin, Halpern, Moses, Vardi and colleagues. Combining these knowledge modalities with ATL, it becomes possible to express such properties as group can cooperate to bring about iff it is common knowledge in that . The resulting logic — Alternating-time Temporal Epistemic Logic (ATEL) — shares the tractability of model checking with its ATL parent, and is a succinct and expressive language for reasoning about game-like multiagent systems. (shrink)

Sound and complete axiomatizations are provided for a number of different logics involving modalities for the knowledge of multiple agents and operators for branching time, extending previous work of Halpern, van der Meyden and Vardi [to appear, SIAM Journal on Computing] for logics of knowledge and linear time. The paper considers the system constraints of synchrony, perfect recall and unique initial states, which give rise to interaction axioms. The language is based on the temporal logic CTL*, interpreted with respect to (...) a version of the bundle semantics. (shrink)

Since the early days of artificial intelligence (AI), many logics have been explored as tools for knowledge representation and reasoning. In the spirit of the Crossley Festscrift and recognizing John Crossley’s diverse interests and his legacy in both mathematical logic and computer science, I discuss examples from my own research that sit in the overlap of logic and AI, with a focus on supporting human–AI interactions.

This paper considers a new class of agent dynamic logics which provide a formal means of specifying and reasoning about the agents activities and informational, motivational and practical aspects of the behaviour of the agents. We present a Hilbert-style deductive system for a basic agent dynamic logic and consider a number of extensions of this logic with axiom schemata formalising interactions between knowledge and commitment (expressing an agent s awareness of her commitments), and interactions between knowledge and actions (expressing no (...) learning and persistence of knowledge after actions). The deductive systems are proved sound and complete with respect to a Kripke-style semantics. Each of the considered logics is shown to have the small model property and therefore decidable. (shrink)

Epistemic logic is usually employed to model two aspects of a situation: the factual and the epistemic aspects. Truth, however, is not always attainable, and in many cases we are forced to reason only with whatever information is available to us. In this paper, we will explore a four-valued epistemic logic designed to deal with these situations, where agents have only knowledge about the available information, which can be incomplete or conflicting, but not explicitly about facts. This layer of available (...) information or evidence, which is the object of the agents’ knowledge, can be seen as a database. By adopting this sceptical posture in our semantics, we prepare the ground for logics where the notion of knowledge—or more appropriately, belief—is entirely based on evidence. The technical results include a set of reduction axioms for public announcements, correspondence proofs, and a complete tableau system. In summary, our contributions are twofold: on the one hand we present an intuition and possible application for many-valued modal logics, and on the other hand we develop a logic that models the dynamics of evidence in a simple and intuitively clear fashion. (shrink)

In the paper we consider complexity of intuitionistic propositional logic and its natural fragments such as implicative fragment, finite-variable fragments, and some others. Most facts we mention here are known and obtained by logicians from different countries and in different time since 1920s; we present these results together to see the whole picture.

We define a tableau calculus for the logic of only knowing and knowing at most ON, which is an extension of Levesque's logic of only knowing O. The method is based on the possible-world semantics of the logic ON, and can be considered as an extension of known tableau calculi for modal logic K45. From the technical viewpoint, the main features of such an extension are the explicit representation of "unreachable" worlds in the tableau, and an additional branch closure condition (...) implementing the property that each world must be either reachable or unreachable. The calculus allows for establishing the computational complexity of reasoning about only knowing and knowing at most. Moreover, we prove that the method matches the worst-case complexity lower bound of the satisfiability problem for both ON and O. With respect to [22], in which the tableau calculus was originally presented, in this paper we both provide a formal proof of soundness and completeness of the calculus, and prove the complexity results for the logic ON. (shrink)

In this paper, I develop a new set of doxastic logical systems and I show how they can be used to solve several well-known problems in doxastic logic, for example the so-called problem of logical omniscience. According to this puzzle, the notions of knowledge and belief that are used in ordinary epistemic and doxastic symbolic systems are too idealised. Hence, those systems cannot be used to model ordinary human or human-like agents' beliefs. At best, they can describe idealised individuals. The (...) systems in this paper can be used to symbolise not only the doxastic states of perfectly rational individuals, but also the beliefs of finite humans. Proof-theoretically, I will use a tableau technique. Every system is combined with predicate logic with necessary identity and ‘possibilist’ quantifiers and modal logic with two kinds of modal operators for relative and absolute necessity. The semantics is a possible world semantics. Finally, I prove that every tableau system in the paper is sound and complete with respect to its semantics. (shrink)

The present paper introduces a belief merging procedure by majority using the standard format of Adaptive Logics. The core structure of the logic ADM c (Adaptive Doxastic Merging by Counting) consists in the formulation of the conflicts arising from the belief bases of the agents involved in the procedure. A strategy is then defined both semantically and proof-theoretically which selects the consistent contents answering to a majority principle. The results obtained are proven to be equivalent to a standard majority operator (...) for bases with partial support. (shrink)

We describe BDD-based decision procedures for the modal logic K. Our approach is inspired by the automata-theoretic approach, but we avoid explicit automata construction. Instead, we compute certain fixpoints of a set of types — which can be viewed as an on-the-fly emptiness of the automaton. We use BDDs to represent and manipulate such type sets, and investigate different kinds of representations as well as a “level-based” representation scheme. The latter turns out to speed up construction and reduce memory consumption (...) considerably. We also study the effect of formula simplification on our decision procedures. To prove the viability of our approach, we compare our approach with a representative selection of other approaches, including a translation of K to QBF. Our results indicate that the BDD-based approach dominates for modally heavy formulae, while search-based approaches dominate for propositionally heavy formulae. (shrink)

Recently predominant forms of anti-realism claim that all truths are knowable. We argue that in a logical explanation of the notion of knowability more attention should be paid to its epistemic part. Especially very useful in such explanation are notions of group knowledge. In this paper we examine mainly the notion of distributed knowability and show its effectiveness in the case of Fitch’s paradox. Proposed approach raised some philosophical questions to which we try to find responses. We also show how (...) we can combine our point of view on Fitch’s paradox with the others. Next we give an answer to the question: is distributed knowability factive? At the end, we present some details concerning a construction of anti-realist modal epistemic logic. (shrink)

This paper introduces the logics of super-strict implications, where a super-strict implication is a strengthening of C.I. Lewis' strict implication that avoids not only the paradoxes of material implication but also those of strict implication. The semantics of super-strict implications is obtained by strengthening the (normal) relational semantics for strict implication. We consider all logics of super-strict implications that are based on relational frames for modal logics in the modal cube. it is shown that all logics of super-strict implications are (...) connexive logics in that they validate Aristotle's Theses and (weak) Boethius's Theses. A proof-theoretic characterisation of logics of super-strict implications is given by means of G3-style labelled calculi, and it is proved that the structural rules of inference are admissible in these calculi. It is also shown that validity in the S5-based logic of super-strict implications is equivalent to validity in G. Priest's negation-as-cancellation-based logic. Hence, we also give a cut-free calculus for Priest's logic. (shrink)

Let a logical propositional calculus L0 be given. We consider arbitrary extensions of L0 by adding finitely many new axiom schemes and rules of inference. We say that a property of P of logical calculi is strongly decidable over L0 if there is an algorithm which for any finite system Rul of axiom schemes and rules of inference decides whether the system L0 + Rul has the property P or not. We consider only so-called structural rules of inference which are (...) invariant under substitution. We remind that P is called decidable over L0 if there is such an algorithm for extensions of L0 with finitely many axiom schemes . In our paper we give a method of proving strong decidability results.We take as L0 some standard calculus for intuitionistic propositional logic Int or modal logic S4 and find a number of properties strongly decidable over L0, in particular, equivalence to some known logic, pretabularity, interpolation property over Int, local tabularity over S4, which are known to be decidable. Some complexity bounds are also given. (shrink)

We consider the problem of recognizing important properties of logical calculi and find complexity bounds for some decidable properties. For a given logical system L, a property P of logical calculi is called decidable over L if there is an algorithm which for any finite set Ax of new axiom schemes decides whether the calculus L + Ax has the property P or not. In [11] the complexity of tabularity, pre-tabularity, and interpolation problems over the intuitionistic logic Int and over (...) modal logic S4 was studied, also we found the complexity of amalgamation problems in varieties of Heyting algebras and closure algebras. In the present paper we deal with positive calculi. We prove NP-completeness of tabularity, DP-hardness of pretabularity and PSPACE-completeness of interpolation problem over Int + . In addition to above-mentioned properties, we consider Beth's definability properties. Also we improve some complexity bounds for properties of superintuitionistic calculi. (shrink)

We show that several logics of common belief and common knowledge are not only complete, but also strongly complete, hence compact. These logics involve a weakened monotonicity axiom, and no other restriction on individual belief. The semantics is of the ordinary fixed-point type.