This book develops a view of logic as a theory of information-driven agency and intelligent interaction between many agents - with conversation, argumentation and games as guiding examples. It provides one uniform account of dynamic logics for acts of inference, observation, questions and communication, that can handle both update of knowledge and revision of beliefs. It then extends the dynamic style of analysis to include changing preferences and goals, temporal processes, group action and strategic interaction in games. Throughout, the book (...) develops a mathematical theory unifying all these systems, and positioning them at the interface of logic, philosophy, computer science and game theory. A series of further chapters explores repercussions of the 'dynamic stance' for these areas, as well as cognitive science. (shrink)

A comprehensive examination of the interfaces of logic, computer science, and game theory, drawing on twenty years of research on logic and games.

We show how belief revision can be treated systematically in the format of dynamicepistemic logic, when operators of conditional belief are added. The core engine consists of definable update rules for changing plausibility relations between worlds, which have been proposed independently in the dynamic-epistemic literature on preference change. Our analysis yields two new types of modal result. First, we obtain complete logics for concrete mechanisms of belief revision, based on compositional reduction axioms. Next, we show how various abstract postulates for (...) belief revision can be analyzed by standard modal frame correspondences for model-changing operations. (shrink)

Current dynamic epistemic logics for analyzing effects of informational events often become cumbersome and opaque when common knowledge is added for groups of agents. Still, postconditions involving common knowledge are essential to successful multi-agent communication. We propose new systems that extend the epistemic base language with a new notion of ‘relativized common knowledge’, in such a way that the resulting full dynamic logic of information flow allows for a compositional analysis of all epistemic postconditions via perspicuous ‘reduction axioms’. We also (...) show how such systems can deal with factual alteration, rather than just information change, making them cover a much wider range of realistic events. After a warm-up stage of analyzing logics for public announcements, our main technical results are expressivity and completeness theorems for a much richer logic that we call LCC. This is a dynamic epistemic logic whose static base is propositional dynamic logic (PDL), interpreted epistemically. This system is capable of expressing all model-shifting operations with finite action models, while providing a compositional analysis for a wide range of informational events. This makes LCC a serious candidate for a standard in dynamic epistemic logic, as we illustrate by analyzing some complex communication scenarios, including sending successive emails with both ‘cc’ and ‘bcc’ lines, and other private announcements to subgroups. Our proofs involve standard modal techniques, combined with a new application of Kleene’s theorem on finite automata, as well as new Ehrenfeucht games of model comparison. (shrink)

Statements not only update our current knowledge, but also have other dynamic effects. In particular, suggestions or commands ?upgrade' our preferences by changing the current order among worlds. We present a complete logic of knowledge update plus preference upgrade that works with dynamic-epistemic-style reduction axioms. This system can model changing obligations, conflicting commands, or ?regret'. We then show how to derive reduction axioms from arbitrary definable relation changes. This style of analysis also has a product update version with preferences between (...) actions, as well as worlds. Some illustrations are presented involving defaults and obligations. We conclude that our dynamic framework is viable, while admitting a further extension to more numerical ?utility update'. (shrink)

In _Modal Logic for Open Minds,_ Johan van Benthem provides an up-to-date introduction to the field of modal logic, outlining its major ideas and exploring the numerous ways in which various academic fields have adopted it. Van Benthem begins with the basic theories of modal logic, semantics, bisimulation, and axiomatics, and also covers more advanced topics, such as expressive power and computational complexity. The book then moves to a wide range of applications, including new developments in information flow, intelligent agency, (...) and games. Taken together, the chapters show modal logic at the crossroads of philosophy, mathematics, linguistics, computer science, and economics. Most of the chapters are followed by exercises, making this volume ideal for undergraduate and graduate students in philosophy, computer science, symbolic systems, cognitive science, and linguistics. (shrink)

In _Modal Logic for Open Minds,_ Johan van Benthem provides an up-to-date introduction to the field of modal logic, outlining its major ideas and exploring the numerous ways in which various academic fields have adopted it. Van Benthem begins with the basic theories of modal logic, semantics, bisimulation, and axiomatics, and also covers more advanced topics, such as expressive power and computational complexity. The book then moves to a wide range of applications, including new developments in information flow, intelligent agency, (...) and games. Taken together, the chapters show modal logic at the crossroads of philosophy, mathematics, linguistics, computer science, and economics. Most of the chapters are followed by exercises, making this volume ideal for undergraduate and graduate students in philosophy, computer science, symbolic systems, cognitive science, and linguistics. (shrink)

The Handbook of Modal Logic contains 20 articles, which collectively introduce contemporary modal logic, survey current research, and indicate the way in which the field is developing. The articles survey the field from a wide variety of perspectives: the underling theory is explored in depth, modern computational approaches are treated, and six major applications areas of modal logic (in Mathematics, Computer Science, Artificial Intelligence, Linguistics, Game Theory, and Philosophy) are surveyed. The book contains both well-written expository articles, suitable for beginners (...) approaching the subject for the first time, and advanced articles, which will help those already familiar with the field to deepen their expertise. Please visit: http://people.uleth.ca/~woods/RedSeriesPromo_WP/PubSLPR.html - Compact modal logic reference - Computational approaches fully discussed - Contemporary applications of modal logic covered in depth. (shrink)

We discuss games of both perfect and imperfect information at two levels of structural detail: players’ local actions, and their global powers for determining outcomes of the game. We propose matching logical languages for both. In particular, at the ‘action level’, imperfect information games naturally model a combined ‘dynamic-epistemic language’ – and we find correspondences between special axioms and particular modes of playing games with their information dynamics. At the ‘outcome level’, we present suitable notions of game equivalence, plus some (...) simple representation results. (shrink)

Logic is not just about single-agent notions like reasoning, or zero-agent notions like truth, but also about communication between two or more people. What we tell and ask each other can be just as 'logical' as what we infer in Olympic solitude. We show how such interactive phenomena can be studied systematically by merging epistemic and dynamic logic.

What precisely are fragments of classical first-order logic showing “modal” behaviour? Perhaps the most influential answer is that of Gabbay 1981, which identifies them with so-called “finite-variable fragments”, using only some fixed finite number of variables (free or bound). This view-point has been endorsed by many authors (cf. van Benthem 1991). We will investigate these fragments, and find that, illuminating and interesting though they are, they lack the required nice behaviour in our sense. (Several new negative results support this claim.) (...) As a counterproposal, then, we define a large fragment of predicate logic characterized by its use of only bounded quantification. This so-called guarded fragment enjoys the above nice properties, including decidability, through an effectively bounded finite model property. (These are new results, obtained by generalizing notions and techniques from modal logic.) Moreover, its own internal finite variable hierarchy turns out to work well. Finally, we shall make another move. The above analogy works both ways. Modal operators are like quantifiers, but quantifiers are also like modal operators. This observation inspires a generalized semantics for first-order predicate logic with accessibility constraints on available assignments (cf. N´emeti 1986, 1992) which moves the earlier quantifier restrictions into the semantics. This provides a fresh look at the landscape of possible predicate logics, including candidates sharing various desirable features with basic modal logic – in particular, its decidability. (shrink)

A variety of logical frameworks have been developed to study rational agents interacting over time. This paper takes a closer look at one particular interface, between two systems that both address the dynamics of knowledge and information flow. The first is Epistemic Temporal Logic (ETL) which uses linear or branching time models with added epistemic structure induced by agents’ different capabilities for observing events. The second framework is Dynamic Epistemic Logic (DEL) that describes interactive processes in terms of epistemic event (...) models which may occur inside modalities of the language. This paper systematically and rigorously relates the DEL framework with the ETL framework. The precise relationship between DEL and ETL is explored via a new representation theorem characterizing the largest class of ETL models corresponding to DEL protocols in terms of notions of Perfect Recall , No Miracles , and Bisimulation Invariance . We then focus on new issues of completeness . One contribution is an axiomatization for the dynamic logic of public announcements constrained by protocols, which has been an open problem for some years, as it does not fit the usual ‘reduction axiom’ format of DEL. Finally, we provide a number of examples that show how DEL suggests an interesting fine-structure inside ETL. (shrink)

This paper adds evidence structure to standard models of belief, in the form of families of sets of worlds. We show how these more fine-grained models support natural actions of “evidence management”, ranging from update with external new information to internal rearrangement. We show how this perspective leads to new richer languages for existing neighborhood semantics for modal logic. Our main results are relative completeness theorems for the resulting dynamic logic of evidence.

Game-theoretic solution concepts describe sets of strategy profiles that are optimal for all players in some plausible sense. Such sets are often found by recursive algorithms like iterated removal of strictly dominated strategies in strategic games, or backward induction in extensive games. Standard logical analyses of solution sets use assumptions about players in fixed epistemic models for a given game, such as mutual knowledge of rationality. In this paper, we propose a different perspective, analyzing solution algorithms as processes of learning (...) which change game models. Thus, strategic equilibrium gets linked to fixed-points of operations of repeated announcement of suitable epistemic statements. This dynamic stance provides a new look at the current interface of games, logic, and computation. (shrink)

Questions are triggers for explicit events of ‘issue management’. We give a complete logic in dynamic-epistemic style for events of raising, refining, and resolving an issue, all in the presence of information flow through observation or communication. We explore extensions of the framework to multi-agent scenarios and long-term temporal protocols. We sketch a comparison with some alternative accounts.

Modern logic is undergoing a cognitive turn, side-stepping Frege’s ‘antipsychologism’. Collaborations between logicians and colleagues in more empirical fields are growing, especially in research on reasoning and information update by intelligent agents. We place this border-crossing research in the context of long-standing contacts between logic and empirical facts, since pure normativity has never been a plausible stance. We also discuss what the fall of Frege’s Wall means for a new agenda of logic as a theory of rational agency, and what (...) might then be a viable understanding of ‘psychologism’ as a friend rather than an enemy of logical theory. (shrink)

Preference is a basic notion in human behaviour, underlying such varied phenomena as individual rationality in the philosophy of action and game theory, obligations in deontic logic (we should aim for the best of all possible worlds), or collective decisions in social choice theory. Also, in a more abstract sense, preference orderings are used in conditional logic or non-monotonic reasoning as a way of arranging worlds into more or less plausible ones. The field of preference logic (cf. Hansson [10]) studies (...) formal systems that can express and analyze notions of preference between various sorts of entities: worlds, actions, or propositions. The art is of course to design a language that combines perspicuity and low complexity with reasonable expressive power. In this paper, we take a particularly simple approach. As preferences are binary relations between worlds, they naturally support standard unary modalities. In particular, our key modality ♦ϕ will just say that is ϕ true in some world which is at least as good as the current one. Of course, this notion can also be indexed to separate agents. The essence of this language is already in [4], but our semantics is more general, and so are our applications and later language extensions. Our modal language can express a variety of preference notions between propositions. Moreover, as already suggested in [9], it can “deconstruct” standard conditionals, providing an embedding of conditional logic into more standard modal logics. Next, we take the language to the analysis of games, where some sort of preference logic is evidently needed ([23] has a binary modal analysis different from ours). We show how a qualitative unary preference modality suffices for defining Nash Equilibrium in strategic games, and also the Backward Induction solution for finite extensive games. Finally, from a technical perspective, our treatment adds a new twist. Each application considered in this paper suggests the need for some additional access to worlds before the preference modality can unfold its true power.. (shrink)

Current dynamic-epistemic logics model different types of information change in multi-agent scenarios. We generalize these logics to a probabilistic setting, obtaining a calculus for multi-agent update with three natural slots: prior probability on states, occurrence probabilities in the relevant process taking place, and observation probabilities of events. To match this update mechanism, we present a complete dynamic logic of information change with a probabilistic character. The completeness proof follows a compositional methodology that applies to a much larger class of dynamic-probabilistic (...) logics as well. Finally, we discuss how our basic update rule can be parameterized for different update policies, or learning methods. (shrink)

Epistemology and epistemic logic At first sight, the modern agenda of epistemology has little to do with logic. Topics include different definitions of knowledge, its basic formal properties, debates between externalist and internalist positions, and above all: perennial encounters with sceptics lurking behind every street corner, especially in the US. The entry 'Epistemology' in the Routledge Encyclopedia of Philosophy (Klein 1993) and the anthology (Kim and Sosa 2000) give an up-to-date impression of the field. Now, epistemic logic started as a (...) contribution to epistemology, or at least a tool in its modus operandi, with the seminal book Knowledge and Belief (Hintikka's 1962, 2005). Formulas like Ki for "the agent i knows that " Bi for "the agent i believes that " provided logical forms for stating and analyzing philosophical propositions and arguments. And more than that, their model-theoretic semantics in terms of ranges of alternatives provided an appealing extensional way of thinking about what agents know or believe in a given situation. In particular, on Hintikka's view, an agent knows those propositions which are true in all situations compatible with what she knows about the actual world; i.e., her current range of uncertainty. (shrink)

The subject of Time has a wide intellectual appeal across different dis ciplines. This has shown in the variety of reactions received from readers of the first edition of the present Book. Many have reacted to issues raised in its philosophical discussions, while some have even solved a number of the open technical questions raised in the logical elaboration of the latter. These results will be recorded below, at a more convenient place. In the seven years after the first publication, (...) there have been some noticeable newer developments in the logical study of Time and temporal expressions. As far as Temporal Logic proper is concerned, it seems fair to say that these amount to an increase in coverage and sophistication, rather than further break-through innovation. In fact, perhaps the most significant sources of new activity have been the applied areas of Linguistics and Computer Science (including Artificial Intelligence), where many intriguing new ideas have appeared presenting further challenges to temporal logic. Now, since this Book has a rather tight composition, it would have been difficult to interpolate this new material without endangering intelligibility. (shrink)

The general verificationist thesis says that What is true can be known or formally: φ → ◊Kφ VT Fitch's argument trivializes this principle. It uses a weak modal epistemic logic to show that VT collapses truth and knowledge, by taking a clever substitution instance for φ: P ∧ ¬KP → ◊ K(P ∧ ¬KP) Then we have the following chain of three conditionals (a) ◊ K(P ∧ ¬KP) → ◊ (KP ∧ K¬KP) in the minimal modal logic for the knowledge (...) operator K, (b) ◊ (KP ∧ K¬KP) → ◊ (KP ∧¬KP) in the modal logic T, and finally (c) ◊ (KP ∧¬KP) → ⊥ in the minimal modal logic for. (shrink)

Classical epistemic logic describes implicit knowledge of agents about facts and knowledge of other agents based on semantic information. The latter is produced by acts of observation or communication that are described well by dynamic epistemic logics. What these logics do not describe, however, is how significant information is also produced by acts of inference— and key axioms of the system merely postulate "deductive closure". In this paper, we take the view that all information is produced by acts, and hence (...) we also need a dynamic logic of inference steps showing what effort on the part of the agent makes a conclusion explicit knowledge. Strong omniscience properties of agents should be seen not as static idealizations, but as the result of dynamic processes that agents engage in. This raises two questions: (a) how to define suitable information states of agents and matching notions of explicit knowledge, (b) how to define natural processes over these states that generate new explicit knowledge. To this end, we use a static base from the existing awareness literature, extending it into a dynamic system that includes traditional acts of observation, but also adding and dropping formulas from the current ' awareness' set. We give a completeness theorem, and we show how this dynamics updates explicit knowledge. Then we extend our approach to multi-agent scenarios where awareness changes may happen privately. Finally, we mention further directions and related approaches. Our contribution can be seen as a ' dynamification' of existing awareness logics. (shrink)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 BASIC MODAL LOGIC . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.

Information is a notion of wide use and great intuitive appeal, and hence, not surprisingly, different formal paradigms claim part of it, from Shannon channel theory to Kolmogorov complexity. Information is also a widely used term in logic, but a similar diversity repeats itself: there are several competing logical accounts of this notion, ranging from semantic to syntactic. In this chapter, we will discuss three major logical accounts of information.

Logic and philosophy of science share a long history, though contacts have gone through ups and downs. This paper is a brief survey of some major themes in logical studies of empirical theories, including links to computer science and current studies of rational agency. The survey has no new results: we just try to make some things into common knowledge.

We introduce the horizontal and vertical topologies on the product of topological spaces, and study their relationship with the standard product topology. We show that the modal logic of products of topological spaces with horizontal and vertical topologies is the fusion ${\bf S4}\oplus {\bf S4}$ . We axiomatize the modal logic of products of spaces with horizontal, vertical, and standard product topologies. We prove that both of these logics are complete for the product of rational numbers ${\Bbb Q}\times {\Bbb Q}$ (...) with the appropriate topologies. (shrink)

This paper explores a new language of neighbourhood structures where existential information can be given about what kind of worlds occur in a neighbourhood of a current world. The resulting system of ‘instantial neighbourhood logic’ INL has a nontrivial mix of features from relational semantics and from neighbourhood semantics. We explore some basic model-theoretic behavior, including a matching notion of bisimulation, and give a complete axiom system for which we prove completeness by a new normal form technique. In addition, we (...) relate INL to other modal logics by means of translations, and determine its precise SAT complexity. Finally, we discuss proof-theoretic fine-structure of INL in terms of semantic tableaux and some expressive fine-structure in terms of fragments, while discussing concrete illustrations of the instantial neighborhood language in topological spaces, in games with powers for players construed in a new way, as well as in dynamic logics of acquiring or deleting evidence. We conclude with some coalgebraic perspectives on what is achieved in this paper. Many of these final themes suggest follow-up work of independent interest. (shrink)

We analyze extensive games as interactive process models, using modallanguages plus matching notions of bisimulation as varieties of gameequivalences. Our technical results show how to fit existing modalnotions into this new setting.

Dov Gabbay is a prolific logician just by himself. But beyond that, he is quite good at making other people investigate the many further things he cares about. As a result, King's College London has become a powerful attractor in our field worldwide. Thus, it is a great pleasure to be an organizer for one of its flagship events: the Augustus de Morgan Workshop of 2005. Benedikt Loewe and I proposed the topic of 'interactive logic' for this occasion, with an (...) emphasis on social software – the logical analysis and design of social procedures – and on games, arguably the formal interactive setting par excellence. This choice reflects current research interests in our logic community at ILLC Amsterdam and beyond. In this broad area of interfaces between logic, computer science, and game theory, this paper is my own attempt at playing Dov. I am, perhaps not telling, but at least asking other people to find out for me what I myself cannot. (shrink)

Rational agents base their actions on information from observation, inference, introspection, or other sources. But this information comes in different kinds, and it is usually handled by different logical mechanisms. We discuss how to integrate external ‘updating information’ and internal ‘elucidating information’ into one system of dynamic epistemic logic, by distinguishing two basic informational actions: ‘bare seeing’ versus ‘conscious realization’.

The most widely used attractive logical account of knowledge uses standard epistemic models, i.e., graphs whose edges are indistinguishability relations for agents. In this paper, we discuss more general topological models for a multi-agent epistemic language, whose main uses so far have been in reasoning about space. We show that this more geometrical perspective affords greater powers of distinction in the study of common knowledge, defining new collective agents, and merging information for groups of agents.

The intuitive notion of evidence has both semantic and syntactic features. In this paper, we develop an evidence logic for epistemic agents faced with possibly contradictory evidence from different sources. The logic is based on a neighborhood semantics, where a neighborhood N indicates that the agent has reason to believe that the true state of the world lies in N. Further notions of relative plausibility between worlds and beliefs based on the latter ordering are then defined in terms of this (...) evidence structure, yielding our intended models for evidence-based beliefs. In addition, we also consider a second more general flavor, where belief and plausibility are modeled using additional primitive relations, and we prove a representation theorem showing that each such general model is a p-morphic image of an intended one. This semantics invites a number of natural special cases, depending on how uniform we make the evidence sets, and how coherent their total structure. We give a structural study of the resulting ‘uniform’ and ‘flat’ models. Our main result are sound and complete axiomatizations for the logics of all four major model classes with respect to the modal language of evidence, belief and safe belief. We conclude with an outlook toward logics for the dynamics of changing evidence, and the resulting language extensions and connections with logics of plausibility change. (shrink)

Where is logic heading today? There is a general feeling that the discipline is broadening its scope and agenda beyond classical foundational issues, and maybe even a concern that, like Stephen Leacock’s famous horseman, it is ‘riding off madly in all directions’. So, what is the resultant vector? There seem to be two broad answers in circulation today. One is logical pluralism, locating the new scope of logic in charting a wide variety of reasoning styles, often marked by non-classical structural (...) rules of inference. This is the new program that I subscribed to in my work on sub-structural logics around 1990, and it is a powerful movement today. But gradually, I have changed my mind about the crux of what logic should become. I would now say that the main issue is not variety of reasoning styles and notions of consequence, but the variety of informational tasks performed by intelligent interacting agents, of which inference is only one among many, involving observation, memory, questions and answers, dialogue, or general communication. And logical systems should deal with a wide variety of these, making information-carrying events first-class citizens in their set-up. The purpose of this brief paper is to contrast and compare the two approaches, drawing freely on some insights from earlier published papers. In particular, I will argue that logical dynamics sets itself the more ambitious diagnostic goal of explaining why substructural phenomena occur, by ‘deconstructing’ them into classical logic plus an explicit account of the relevant informational events. (shrink)

The combination of logic and game theory provides a fine-grained perspective on information and interaction dynamics, a Theory of Play. In this paper we lay down the main components of such a theory, drawing on recent advances in the logical dynamics of actions, preferences, and information. We then show how this fine-grained perspective has already shed new light on the long-term dynamics of information exchange, as well as on the much-discussed question of extensive game rationality.

Dynamic update of information states is a new paradigm in logicalsemantics. But such updates are also a traditional hallmark ofprobabilistic reasoning. This note brings the two perspectives togetherin an update mechanism for probabilities which modifies state spaces.

Current dynamic epistemic logics often become cumbersome and opaque when common knowledge is added. In this paper we propose new versions that extend the underlying static epistemic language in such a way that dynamic completeness proofs can be obtained by perspicuous reduction axioms.