Dynamic Epistemic Logic

This article tells the story of the rise of dynamic epistemic logic. The rise began in the 1960s with the creation and development of epistemic logic, the logic of knowledge, Then in the late 1980s came dynamic epistemic logic, the logic of change of knowledge. Much of it was motivated by puzzles and paradoxes.

The number of active researchers in these logics grows significantly every year because there are so many relations and applications to computer science, to multi-agent systems, to philosophy, and to cognitive science.

The modal knowledge operators in epistemic logic are formally interpreted by employing binary accessibility relations in multi-agent Kripke models (relational structures), where these relations should be equivalence relations to respect the properties of knowledge. The operators for change of knowledge correspond to another sort of modality, more akin to a dynamic modality. A peculiarity of this dynamic modality is that it is interpreted by transforming the Kripke structures used to interpret knowledge, und nicht, at least not on first sight, by an accessibility relation given with a Kripke model. Although called “dynamic epistemic logic,” this two-sorted modal logic applies to more general settings than the logic of merely S5 knowledge.

The present article discusses in depth the early history of dynamic epistemic logic. It then mentions briefly a number of more recent developments involving factual change, eins (of several) standard translations to temporal epistemic logic, and a relation to situation calculus (a well-known framework in artificial intelligence to represent change). Special attention is then given to the relevance of dynamic epistemic logic for belief revision, for speech act theory, and for philosophical logic. The part on philosophical logic pays attention to Moore sentences, the Fitch paradox, and the Surprise Examination.

Inhaltsverzeichnis
Einführung
An Example Scenario
A History of DEL
Announcements
Other Informative Events
DEL and Belief Revision
DEL and Language
DEL and Philosophy
Referenzen und weiterführende Literatur
1. Einführung

In this overview we tell the story of the rise of dynamic epistemic logic. It is a bit presumptious to call it a rise, but we can only observe this rather peculiar phenomenon. The number of active researchers in these logics grows every year because there are so many relations to computer science, to multi-agent systems, to philosophy, and to cognitive science. It all began with the logic of knowledge in the 1960s, and much of it was motivated by puzzles and paradoxes.

Dynamic logic is the logic of changing knowledge. The starting point of dynamic epistemic logic (DEL) is therefore the logic of knowledge. A founding publication is [42]. We refer to [41] for an overview of epistemic logic and references. A key feature of epistemic logic is that the information state of several agents can be represented by a Kripke model. Given a set of agents and a set of propositional variables, a Kripke model consists of a set of states, a set of accessibility relations (each one a binary relation on the domain), namely one for each agent, and a valuation (that tells which propositional variables are true in which states). In epistemic logic the set of states of a Kripke model is interpreted as a set of epistemic alternatives. The information state of an agent consists of those epistemic alternatives that are possible according to the agent, which is represented by the binary accessibility relation Rα. An agent α knows that a proposition φ is true in a state a of a Kripke model M (M; a ⊨ Kαφ), if and only if that proposition φ is true in all the states that agent α considers possible in that state (das ist, which are Rα-accessible from a). A proposition known by agent α may itself pertain to the knowledge of some agent (for instance if one considers the formula KαKβψ). Auf diese Weise, a Kripke model with accessibility relations for all the agents represents the (higher-order) information of all relevant agents simultaneously.

In DEL, information change is modeled by transforming Kripke models. Since DEL is mostly about information change due to communication, the model transformations usually do not involve factual change. The bare physical facts of the world remain unchanged, but the agents’ information about the world changes. In terms of Kripke models that means that the accessibility relations of the agents have to change (and consequently the set of states of the model might change as well). Modal operators in dynamic epistemic languages denote these model transformations. The accessibility relation associated with these operators is not one within the Kripke model, but pertains to the transformation relation between the Kripke models, as the example in the next section will show.

In Section 2 an example scenario is presented which can be captured by DEL. In Section 3 an historical overview of the main approaches in DEL is presented, with details on their modelling techniques. Section 4 discusses how to model belief revision in DEL. Section 5 connects ideas between speech act theory and DEL. Endlich, Section 6 is on the relation between DEL and philosophy: it deals with Moore-sentences, the Fitch-paradox, and the Surprise Examination.

2. An Example Scenario

Figure 1: A Kripke model for the situation in which two agents are each given a red or a white card.

Consider the following scenario: Ann and Bob are each given a card that is either red or white on one side (the face side) and nondescript on the other side (the back side). They only see their own card, and so they are ignorant about the other agent’s card. There are four possibilities: both have white cards, both have red cards, Ann has a white card and Bob has a red card, or the other way round. These are the states of the model, and are represented by informative names such as rw, meaning Ann was dealt a red card (die) and Bob was dealt a white card (w). Let us assume that both have red cards, das ist, let the actual state be rr. This is indicated by the double lines around state rr in Figure 1. The states of the Kripke model are connected by lines, which are labeled (α or β, denoting Ann or Bob respectively) to indicate that the agents cannot distinguish the states thus connected. (To be complete it should also be indicated that no state can ever be distinguished from itself. For readability these “reflexive lines” are not drawn, but indeed the accessibility relations Rα and Rβ are equivalence relations, since epistemic indistinguishability is reflexive, symmetric and transitive.) In the model of Figure 1 there are no α-lines between those states where Ann has different cards, das ist, she can distinguish states at the top, where she has a red card, from those at the bottom, where she has a white one. Ebenfalls, Bob is able to distinguish the left half from the right half of the model. This represents the circumstance that Ann and Bob each know the colour of their own card but not the colour of the other’s card. In the Kripke model of Figure 1 we also see that the higher-order information is represented correctly. Both agents know that the other agent knows the colour of his or her card, and they know that they know this, und so weiter. It is remarkable that a single Kripke model can represent the information of both agents simultaneously.

Figure 2: A Kripke model for the situation after Ann tells Bob she has a red card.

Figure 3: A Kripke model for the situation after Ann might have looked at Bob’s card.

Suppose that after picking up their cards, Ann truthfully says to Bob “I have a red card”. The Kripke model representing the resulting situation is displayed in Figure 2. Now both agents know that Ann has a red card, and they know that they know she has a red card, und so weiter: it is common knowledge among them. (A formula φ is common knowledge among a group of agents if everyone in the group knows that φ, everyone knows that everyone knows that φ, and so on.) Hence there is no need anymore for states where Ann has a white card, so those do not appear in the Kripke model. Note that in the new Kripke model there are no longer any lines labeled β. No matter how the cards were dealt, Bob only considers one state to be possible: the actual one. In der Tat, Bob is now fully informed.

Now that Bob knows the colour of Ann’s card, Bob puts his card face down on the table, and leaves the room for a moment. When he returns he considers it possible that Ann took a look at his card, but also that she didn’t. Assuming she did not look, the Kripke model representing the resulting situation is the one displayed in Figure 3. In contrast to the previous model, there are in this model lines for Bob again. This is because he is no longer completely informed about the situation. He does not know whether Ann knows the colour of his card, yet he still knows that both Ann and he have a red card. Only his higher-order information has changed. Ann on the other hand knows whether she has looked at Bob’s card and also knows whether she knows the colour of Bob’s card. She also knows that Bob considers it possible that she knows the colour of his card. In the model of Figure 3 we see that two states representing the same factual information can differ by virtue of the lines connecting them to other states: the state rr on the top and rr on the bottom only differ in higher-order information.

In this section, we have seen two ways in which information change can occur. Going from the first model to the second, the information change was public, in the sense that all agents received the same information. Going from the second to the third model involved information change where not all agents had the same information, because Bob did not know whether Ann looked at his card while he was away. The task of DEL is to provide a logic with which to describe these kinds of information change.

3. A History of DEL

DEL did not arise in a scientific vacuum. The “dynamic turn” in logic and semantics ([72], [34] und [60]) very much inspired DEL, and DEL itself can also be seen as a part of the dynamic turn. The formal apparatus of DEL is a lot like propositional dynamic logic (PDL) [40] and quantified dynamic logic (QDL) [39]. There is also a relation to update semantics (US) [36, 93] — not all formulas are interpreted dynamically, as there, but formulas and updates are clearly distinguished.

The study of epistemic logic within computer science and AI led to the development of epistemic temporal logic (ETL) in order to model information change in multi-agent systems (sehen [25] und [55]). Rather than model change by modal operators that transform the model, change is modeled by the progression of time in these approaches. Yet the kinds of phenomena studied by ETL and DEL largely overlap.

After this brief sketch of the context in which DEL was developed, the remainder of the section focuses on the development of its two main approaches. The first is public announcement logic, which is presented in Section 3.1. Der Zweite, presented in Section 3.2, is the dominant approach in DEL (sometimes identified with DEL).

An. Announcements

The original publication: Plaza The first dynamic epistemic logic, called public announcement logic (PAL), was developed by Plaza in [61]. This was published in 1989. The example where Ann says to Bob that she has a red card is an example of a public announcement. A public announcement is a communicative event where all agents receive the same information and it is common knowledge among them that this is so. The language of PAL is given by the following Backus-Naur Form:

Besides the usual propositional language, Kαφ is read as agent α knows that φ, und [φ] ψ is read as after φ is announced ψ is the case. In the example above, we could for instance translate “After it is announced that Ann has a red card, Bob knows that Ann has a red card” as [rα]Kβrα.

An announcement is modeled by removing the states where the announcement is false, das ist, by going to a submodel. This model transformation is the main feature of PAL’s semantics.

In clause (v) the condition that the announced formula be true at the actual state entails that only truthful announcements can take place. The model MΙφ is the model obtained from M by removing all non-φ states. The new set of states consists of the φ-states of M. Infolgedessen, the accessibility relations as well as the valuation are restricted to these states . The propositional letters true at a state remain true after an announcement. This reflects the idea that communication can only bring about information change, not factual change.

Gerbrandy and Groeneveld’s approach A logic similar to PAL was developed independently by Gerbrandy and Groeneveld in [32], which is more extensively treated in Gerbrandy’s PhD thesis [30]. There are three main differences between this approach and Plaza’s approach. Erstens, Gerbrandy and Groeneveld do not use Kripke models in the semantics of their language. Stattdessen, they use structures called possibilities which are defined by means of non-wellfounded set theory [1], a branch of set theory where the foundation axiom is replaced by another axiom. Possibilities and Kripke models are closely linked: possibilities correspond to bisimulation classes of Kripke models [18]. Später, Gerbrandy provided semantics without using non-wellfounded set theory for a simplified version of his public announcement logic [31].

The second difference is that Gerbrandy and Groeneveld also consider announcements that are not truthful. In their view, a logic for announcements should model what happens when new information is taken to be true by the agents. Daher, according to them, what happens to be true deserves no special status. This is more akin to the notion of update in US. In terms of Kripke models this means that by updating, agents may no longer consider the actual state to be possible, das ist, Rα may no longer be reflexive. In a sense it would therefore be more accurate to call this logic a dynamic doxastic logic (a dynamic logic of belief) rather than a dynamic epistemic logic, since according to most theories, knowledge implies truth, whereas beliefs need not be true.

Drittens, their logic is more general in the sense that subgroup announcements are treated (where only a subgroup of the group of all agents acquires new information); and especially private announcements are considered, where only one agent gets information. These announcements are modeled in such a way that the agents who do not receive information do not even consider it possible that anyone has learned anything. In terms of Kripke models, this is another way in which Rα may lose reflexivity.

Adding common knowledge Semantics for public, group and private announcements using Kripke models was proposed by Baltag, Moss, and Solecki in [14]. This semantics is equivalent to Gerbrandy’s semantics (as was shown in [58]). The main contribution in [14] to PAL was that their approach also covered common knowledge, which is an important concept when one is interested in higher-order information and plays an important role in social interaction (vgl. [92]). The inclusion of common knowledge poses a number of technical problems.

b. Other Informative Events

Groeneveld and Gerbrandy’s approach In addition to a logic for announcements Gerbrandy also developed a system for more general information change involving many agents, each of whom may have a different perspective. This is for instance the case when Ann may look at Bob’s card.

In order to model this information change it is important to realize that distinct levels of information are not distinctly represented in a Kripke model. For instance what Ann actually knows about the cards depends on Rα, but what Bob knows about what Ann knows about the cards depends on Rα as well. Therefore changing something in the Kripke model, such as cutting a line, changes the information on many levels. In order to come to grips with this issue it really pays to use non-wellfounded semantics. One of the ways to think about the possibilities defined by Gerbrandy and Groeneveld is as infinite trees. In such a tree, distinct levels of information are represented by certain paths in the tree. By manipulating the appropriate part of the tree, one can change the agents’ information at the appropriate level. This insight stems from Groeneveld [37] and was also used by Renardel de Lavalette in [62], who introduces treelike lean modal structures using ordinary set theory in the semantics of a dynamic epistemic logic.

Van Ditmarsch’s approach Inspired by Gerbrandy and Groeneveld’s work, Van Ditmarsch developed a dynamic epistemic logic for modeling information change in knowledge games, where the goal of the players is to obtain knowledge of some aspect of the game. Clue and Battleships are typical examples of knowledge games. Players are never deceived in such games and therefore the dynamic epistemic logic of Gerbrandy and Groeneveld in which reflexivity might be lost, seems unsuitable. In Van Ditmarsch’s Ph.D. These [86], a logic is presented where all model transformations are from Kripke models with equivalence relations to Kripke models with equivalence relations, which is thus tailored to information change involving knowledge. This approach was further streamlined by Van Ditmarsch in [87] and later extended to include concurrent actions (when two or more events occur at the same time) in [90]. One of the open problems of these logics is that a completeness proof for the axiom systems has not been obtained.

The dominant approach: Baltag, Moss and Solecki Another way of modeling complex informative events was developed by [14], which has become the dominant approach in DEL. Their approach is highly intuitive and is lying at the basis of many papers in the field: In der Tat, many refer to this approach simply as DEL. Their key insight was that information changing events can be modeled in the same way as situations involving information. Given a situation, such as when Ann and Bob each have a card, one can easily provide a Kripke model for such a situation. One simply considers which states might occur and which of those states the agents cannot distinguish. One can do the same with events involving information. Given a scenario, such as Ann possibly looking at Bob’s card, one can determine which events might occur: either she looks and sees it is red (she learns that rβ) or she sees that it is white (she learns that wβ), or she does not look at the card (she learns nothing new, indicated by the tautology Τ). It is clear that Ann can distinguish these particular events, but Bob cannot. Such models are called action models or event models.

An event model A is a triple consisting of a set of events E, a binary relation over E for each agent, and a precondition function which assigns a formula to each event. This precondition determines under what circumstances the event can actually occur. Ann can only truthfully say that she has a red card, if in fact she does have a red card. The event model for the event where Ann might have looked at Bob’s card is

Figure 4: An event model for when Ann might look at Bob’s card.

Figure 5: The product update for the models of Figure 3 and Figure 4.

given in Figure 4, where each event is represented by its precondition.

The Kripke model of the situation following the event is constructed with a procedure called a product update. For each state in the original Kripke model one determines which events could take place in that state (das ist, one determines whether the precondition of the event is true at that state). The set of states of the new model consists of those pairs of states and events (An, e), which represent the result of event e occurring in state a. The new accessibility relation is now easy to determine. If two states were indistinguishable to an agent and two events were also indistinguishable to that agent, then the result of those events taking place in those states should also be indistinguishable. This implication also holds the other way round: if the result of two events happening in two states are indistinguishable, then the original states and events should be indistinguishable as well. (Van Benthem [73] characterizes product update as having perfect recall, no miracles, and uniformity .) The basic facts about the world do not change due to a

Figure 6: The product update for the models of Figure 1 and Figure 4.

merely communicative event. And so the valuation in simply follows the old valuation in a.

The model in Figure 5 is the result of a product update of the model in Figure 2 and the event model of Figure 4. One can see that this is the same as the model in Figure 3 (except for the names of the states), which indicates that product update yields the intuitively right result.

One may wonder whether the model in Figure 4 represents the event accurately. According to the event model Bob considers it possible that Ann looks at his card and sees that it is white. Bob, Jedoch, already knows that the card is red, and therefore should not consider this event possible. This criticism is justified and one could construct an event model that takes this into account, but the beauty of the event model is precisely that it is detached from the agents’ information about the world in such a way that it provides an accurate model of just the information the agents have about the event. This means that product update yields the right outcome regardless of the Kripke model of the situation in which the event occurred. For instance taking the product update with the model of Figure 1, yields the Kripke model depicted in Figure 6, which represents the situation where Ann might look at Bob’s card immediately after the cards were dealt. The resulting model also represents that situation correctly. This indicates that in DEL static information and dynamic information can be separated.

In the logical language of DEL these event models appear as modalities [Ein, e], where e is taken to be the event that actually occurs. The language is given by the following Backus-Naur Form

Clauses (Ich)–(iv) are the same as for PAL. In clause (v) is the reflexive transitive closure of the union of the accessibility relations of members of Γ. Clause (vi) is a standard clause for dynamic modalities, except that the accessibility relation for dynamic modalities is a relation on the class of all Kripke models. In clause (vii) it is required that the precondition of the event model is true in the actual state, thus ensuring that , the new actual state, exists in the product update. Clauses (viii) und (ix) are the usual semantics for non-deterministic choice and sequential composition.

Not only informative events where different agents have a different perspective can be modeled in DEL, but also public announcements can be thought of in terms of event models. A public announcement can be modeled by an event model containing just one event: the announcement. All agents know this is the actual event, so it is the only event considered possible. In der Tat, DEL is a generalization of PAL.

Criticism, alternatives, and extensions Many people feel somewhat uncomfortable with having models as syntactical objects. Baltag and Moss have tried to accommodate this by proposing different languages while maintaining an underlying semantics using event models [10, 13]. This issue is extensively discussed in [91, Section 6.1]. There are alternatives using hybrid logic [70], and algebraic logic ([11], [12]). Most papers just use event models in the language.

DEL has been extended in various ways. Operators for factual change [85, 81] and past operators from temporal logic have been added [64, 5]. DEL has been combined with probability [45], justification logic [63] and extended such that belief revision is also within its grasp. Connections have been made between DEL and various other logics. Its relation to PDL, ETL [80], AGM belief revision, and situation calculus [83] has been studied. DEL has been applied to a number of puzzles and paradoxes from recreational mathematics and philosophy. It has also been applied to problems in game theory (sehen [79] for a very detailed survey), as well as issues in computer security [94]. Complexity and succinctness of DEL has been investigated in [54, 69, 6]. Two recent overviews of DEL are [17, 78]. In the next section we pay attention to DEL and belief revision.

4. DEL and Belief Revision

Something you cannot model in DEL is changing your mind. Once you know a fact, you know it forever, das ist, once is true, it remains true after every update. Even when we have weaker constraints on the accessibility relations (for belief, or even general accessibility), this remains the case. But sometimes, when you believe a fact, you change your mind, and you may come to believe the opposite. This is not shocking or anything, it might have been that you merely did not believe it firmly. This means a change of into or, using the better suited belief modality for that: a change of into . In a different community, that of (AGM) belief revision, this is the most natural operation around—indeed called ‘belief revision’. In this section we shortly survey interactions between such AGM belief revision and dynamic epistemic logic.

Belief revision has been studied from the perspective of structural properties of reasoning about changing beliefs [29], from the perspective of changing, growing and shrinking knowledge bases, and from the perspective of models and other structures of belief change wherein such knowledge bases may be interpreted, or that satisfy assumed properties of reasoning about beliefs. A typical approach involves preferential orders to express increasing or decreasing degrees of belief [48, 56], where these works refer to the ‘systems of spheres’ in [51, 38]. Within this tradition multi-agent belief revision has also been investigated, Zum Beispiel, belief merging [46]. Belief operators are normally not explicit in the logical language, so that higher-order beliefs (I know that you are ignorant of a certain proposition) cannot be formalized. Iterated belief revision may also be problematic.

The link between belief revision and modal logic, das ist, explicit belief modalities and belief change modalities in the logical language, was made in a strand of research known as dynamic doxastic logic. This was proposed and investigated by Segerberg and collaborators in works such as [68, 52, 67, 22]. These works are distinct from other approaches to belief revision in modal logics, without dynamic modal operators, wie zum Beispiel [19, 50, 20], that also influenced the development of dynamic logics combining knowledge and belief change. In dynamic doxastic logics belief operators are in the logical language, and belief revision operators are dynamic modalities. Higher-order belief change, das ist, to revise one’s beliefs about one’s own or other agents’ beliefs and ignorance, are considered problematic in dynamic doxastic logic, sehen [52]. In [68, 67] belief revision is restricted to propositional formulas (factual revision). Es gibt

dynamic doxastic logics wherein [*φ] merely means belief revision with φ according to some externally defined strategy, as in AGM style (this is the general setup in [68], not unlike the nonepistemic/doxastic modal setup in [71]), but there are also dynamic doxastic logics, wie zum Beispiel [67], wherein [*φ] is a recipe operating on a semantic structure and outputting a novel structure, the standard approach in dynamic epistemic logic.

Belief revision in dynamic epistemic logic was initiated in [4, 88, 77, 15]. From these, [4, 88] propose a treatment involving degrees of belief and based on degrees of plausibility among states in structures interpreting such logics, so-called quantitative dynamic belief revision; wohingegen [77, 15] propose a treatment involving comparative statements about plausibilities (a binary relation between states denoting more/less plausible), so-called qualitative dynamic belief revision. The latter is clearly more suitable for logics of belief revision, and for notions such as conditional belief. The analogue of the AGM postulate of success must be given up when one incorporates higher-order belief change as in dynamic epistemic logic, where again a prime mover are Moore-sentences of the form ‘proposition p is true but you don’t know it’, which cannot after acceptance be believed by you. Many more works on dynamic belief revision have appeared since, Zum Beispiel, [33, 53, 24]. A prior, independent, strand to model belief revision was in temporal epistemic logic, and was initiated in the mid 1990s in [28]. Their integrated treatment of belief, Wissen, plausibilities, and change is similar to the more recent developments to model belief revision in dynamic epistemic logic, and the relation between the two approaches is incompletely understood.

For an example of belief revision in dynamic epistemic logic, consider one agent and a proposition p that the agent is uncertain about. The agent could be Ann, who is uncertain whether Bob has a red card, as in the proposition before. We get a Kripke model depicted in Figure 7, not dissimilar from that in Figure 2. There are two states of the world, one where p is false and another one where p is true. Let us suggestively call them 0 and 1, bzw.. The agent has epistemic preferences among these states. Namely, she considers it most plausible that 1 is the actual state, das ist,, that p is true, and less plausible that 0 is the actual state. We write 1 < 0 where, as common in the area, the minimal element in the order is the most plausible state (and not, as maybe to be expected, the least plausible state). Let us further assume that p is false. Figure 7: Ann believes p but considers epistemically possible. The agent believes a proposition when it holds in the most plausible states. For example, she believes that p is true. This is formalized as We write (for belief) instead of (for knowledge) as beliefs may be mistaken. Indeed, the agent believes that p but in fact p is false! But we also distinguish a modality for knowledge. The agent knows a proposition when it holds in all plausible states. These are her strongest beliefs, or knowledge. In the case of this example her factual knowledge only involves tautologies such as p ∨ This is described as (p ∨) Now imagine that the agent wants to revise her current beliefs. She believes that p is true, but has been given sufficient reason to be willing to revise her beliefs with instead. We can accomplish that when we allow a model transformation that makes the 0 state more plausible than the 1 state. There are various ways to do that. In this simple example we can simply observe that it suffices to make the state satisfying the revision formula , that is, 0, more plausible than the other state, 1. See Figure 8. As a consequence of that, the agent now believes : is true. Therefore, the revision was successful. This can already be expressed in the initial situation by using a dynamic modal operator [*] for the relation induced by the program “belief revision with ”, followed by what should hold after that program is executed. In this dynamic modal setting we can then write that ΛΛ[*] was already true at the outset. Figure 8: Ann revises her belief with In dynamic epistemic logic, unlike in the original AGM or the subsequent DDL setting, beliefs and knowledge can also be about modal formulas. For example, we not only have that , but we also have that the agent believes that she does not know whether p. We might say: Ann is aware that her belief in p is not very strong, that it is defeasible. 5. DEL and Language Consider the connection between DEL and speech act theory. Speech act theory started with the work of [7], who argued that language is used to perform all sorts of actions; we make promises, we ask questions, we issue commands, and so forth. An example of a speech act is a bartender who says “The bar will be closed in five minutes” [8]. Austin distinguishes three kinds of acts that are performed by the bartender (i) the locutionary act of uttering the words, (ii) the illocutionary act of informing his clientele that the bar will close in five minutes, and (iii) the perlocutionary act of getting the clientele to order one last drink and leave. Truth conditions, which determine whether an indicative sentence is true of false, are generalized to success conditions to determine whether a speech act is successful or not. In speech act theory there are several distinctions when it comes to the ways in which something can be wrong with a speech act [7, p. 18]. Here we do not make such distinctions and simply speak of success conditions. Searle gives in [66, p. 66] the following success conditions, among others, for an assertion that p by speaker S to hearer H: S has evidence (reasons, and so forth) for the truth of p. It is not obvious to both S and H that H knows (does not need to be reminded of, and so forth) p. S believes p Speech act theory has been embraced by the multi-agent systems community, for example, by the Foundation for Intelligent Physical Agents (FIPA). FIPA is an IEEE Computer Society standards organization that promotes agent-based technology and the interoperability of its standards with other technologies. It published a Communicative Act Library Specification [26] that includes a specification of the inform action, which is similar to Searle’s analysis of assertions. It is worthwhile to join this analysis of assertions to the analysis of public announcements in PAL. It is clear from the list of success conditions that one usually only announces what one believes (or knows) to be true. So, an extra precondition for an announcement that φ by an agent α , should be that . Public announcements are indeed modeled in this way in [61]. As an example, consider the case when Ann tells Bob she has a red card: it is more appropriate to model this as an announcement that rather than the announcement that rα. Fortunately, these formulas were equivalent in the model under consideration. Suppose that Ann had said “We do not both have white cards”. When this is modeled as an announcement that , we obtain the model in Figure 9(a). However, Ann only knows this statement to be true when she in fact has a red card herself. Indeed, when we look at the result of the announcement that we obtain the model in Figure 9(b). We see that the result of this Figure 9: An illustration of the difference between the effect of the announcement that φ and the announcement that φ and an announcement that only changes the agents’ higher-order information announcement is the same as when Ann says that she has a red card (see Figure 2). By making presuppositions part of the announcement, we are in a way accommodating the precondition (see also [44]). The second success condition in Searle’s analysis conveys that an announcement ought to provide the hearer with new information. In the light of DEL, one can revise this second success condition by saying that p is not common knowledge, thus taking higher-order information into account. It seems natural to assume that a speaker wants to achieve common knowledge of p, since that plays an important role in coordinating social actions; and so lack of common knowledge of p is a condition for the success of announcing p. Consider the situation where Ann did look at Bob’s card when he was away and found out that he has a red card (Figure 9(c)). Suppose that upon Bob’s return Ann tells him “I do not know that you have a white card”. Both Ann and Bob already know this, and they also both know that they both know it. Therefore Searle’s second condition is not fulfilled, and so according to his analysis there is something wrong with Ann’s assertion. The result of this announcement is given in Figure 9(d). We see that the information of the agents has changed. Now Bob no longer considers it possible that Ann considers it possible that Bob considers it possible that Ann knows that Bob has a white card. And so the announcement is informative. One can give more and more involved examples to show that indeed change of common knowledge is a more natural requirement for announcements than Searle’s second condition, especially multi-agent scenarios. Van Benthem [76] analyzes question and answer episodes using DEL. One of the success conditions of questions as speech acts is that the speaker does not know the answer [66, p. 66]. Therefore posing a question can reveal crucial information to the hearer in such a way that the hearer only knows the answer after the question has been posed ([74],[91, p. 61],[82]). Professor a is program chair of a conference on Changing Beliefs. It is not allowed to submit more than one paper to this conference, a rule all authors of papers did abide to (although the belief that this rule makes sense is gradually changing, but this is besides the point here). Our program chair a likes to have all decisions about submitted papers out of the way before the weekend, since on Saturday he is due to travel to attend a workshop on Applying Belief Change. Fortunately, although there appears not to be enough time to notify all authors, just before he leaves for the workshop, his reliable secretary assures him that she has informed all authors of rejected papers, by personally giving them a call and informing them about the sad news concerning their paper. Freed from this burden, Professor a is just in time for the opening reception of the workshop, where he meets the brilliant Dr. b. The program chair remembers that b submitted a paper to Changing Beliefs, but to his own embarrassment he must admit that he honestly cannot remember whether it was accepted or not. Fortunately, he does not have to demonstrate his ignorance to b, because b’s question ‘Do you know whether my paper has been accepted?’ does make a reason as follows: a is sure that would b’s paper have been rejected, b would have had that information, in which case b had not shown his ignorance to a. So, instantaneously, a updates his belief with the fact that b’s paper is accepted, and he now can answer truthfully with respect to this new revised belief set. This phenomenon shows that when a question is regarded as a request [49], the success condition that the hearer is able to grant the request, that is, provide the answer to the question, must be fulfilled after the request has been made, and not before. (However, it is not commonly agreed upon in the literature that questions can be regarded as requests (cf. [35, Section 3].) This analysis of questions in DEL fits well within the broad interest in questions in dynamic semantics [3]. Recent work on DEL and questions is [2, 59, 23]. 6. DEL and Philosophy The role of public announcements as typical informative speech acts focussed the attention on a number of situations wherein that form of success cannot be achieved. This has been investigated mainly within philosophical logic, under the heading of ‘Moore sentences’ and the ‘Fitch paradox’. The ‘Moore sentence’ was introduced by Moore in [57] and his original analysis is that p ∧¬Kp (p is true and I don’t know/believe it) cannot sincerely be uttered. As this is an informative speech act, you are supposed to believe your beliefs. It seems incoherent, and maybe even paradoxical, to believe a proposition stating that you do not believe it. In the DEL setting we can give this a dynamic interpretation. It is then no longer paradoxical. If I tell you “You don’t know that I play cello”, this has the conversational implicature “You don’t know that I play cello and it is true that I play cello”. This has the form p ∧¬Kp. Suppose I were tell you again “You don’t know that I play cello.” Then you can respond: “You’re lying. You just told me that you play cello.” We can analyze what is going on here in modal logic. We model your uncertainty, for which a single epistemic modality suffices. Initially, there are two possible worlds, one in which p is true and another one in which p is false, and that you cannot distinguish from one another. Although in fact p is true, you don’t know that: p ∧¬Kp. The announcement of p ∧¬Kp results in a restriction of these two possibilities to those where the announcement is true: in the p-world, p ∧¬Kp is true, but in the :p-world, p ∧¬Kp is false. In the model restriction consisting of the single world where p is true, p is known: Kp. Given that Kp is true, so is¬p ∨ Kp, and ¬p ∨ Kp is equivalent to ¬(p ∧ ¬Kp), the negation of the announced formula. So, announcement of p ∧ ¬Kp makes it false! Gerbrandy [30, 31] calls this phenomenon an unsuccessful update; the matter is also taken up in [89, 43, 84]. We continue with some words on the Fitch paradox [27]. A standard analysis of the Fitch paradox is as follows – see the excellent review of the literature on Fitch’s paradox in the Stanford Encyclopedia of Philosophy [21], and the volume dedicated on knowability [65]. The existence of unknown truths is formalized as ∃p (p ∧ ¬Kp). The requirement that all truths are th-knowable is formalized as ∀p (p → ◊ Kp), where ◊ formalizes the existence of some process after which p is known, or an accessible world in which p is known. Fitch’s paradox is that the existence of unknown truths is inconsistent with the requirement that all truths are knowable. The Moore-sentence p ∧ ¬ Kp witnesses the existential statement ∃p (p ∧ ¬Kp). Assume that it is true. From ∃p (p ∧ ¬Kp) follows the truth of its instance (p ∧ ¬Kp) → ◊ K(p ∧ ¬Kp), and from that and p ∧ ¬Kp follows ◊ K(p ∧ ¬Kp). Whatever the interpretation of ◊, it results in having to evaluate K(p ∧ ¬Kp). But this is inconsistent for knowledge and belief. We now get to the relation between knowable and DEL. The suggestion to interpret ‘knowable’ as ‘known after an announcement’ was made by van Benthem in [75], and [9] proposes a logic where ‘φ is knowable’ is interpreted in that way. In this setting, ◊p stands for ‘there is an announcement after which p (is true)’, so that ◊Kp stands for ‘there is an announcement after which p is known’, which is a form of ‘proposition p is knowable’. For example, consider the proposition p for ‘it rains in Liverpool’. Suppose you are ignorant about p: ¬(Kp ∨ K¬p). First, suppose that p is true. I can announce to you here and now that it is raining in Liverpool (according to your expectations, maybe…), after which you know that: 〈 p〉 Kp stands for ‘p is true and after announcing p, p is known’ (〈φ〉 is the dual of [φ], that is, 〈φ〉ψ is defined by abbreviation as ¬[φ]¬ψ ). Now, suppose that p is false. In a similar way, after I announce that, you know that; so that we have 〈¬p〉 K¬p. If you already knew whether p, having its value announced does not have any informative consequence for you. Therefore, 〈p〉 Kp ∨ 〈¬p〉 K ¬p is a validity. Therefore we also have〈p〉 (Kp ∨ K ¬p) ∨ 〈¬p〉 (Kp ∨ K ¬p) . We can generalize the statement ‘there is a proposition p such that after its announcement, p is known’, to ‘there exists a proposition q, such that after its announcement, p is known’, where q is not necessarily the same as p. Then we have informally captured the meaning of ◊Kp. In other words, this operator is a quantification over announcements. But we have then just proved that ◊ (Kp ∨ K ¬p)is a validity. For more on such matters, see [9, 84]. Another paradox in philosophical logical circles that has been analyzed with DEL methods (and that has similar ‘Moore sentences’-like symptoms) is the Surprise Examination. This has been investigated in works as [30, 31, 89], and more recently by Baltag and Smets using plausibility epistemic structures, along the lines of [16]. Parts of the materials for this overview have been taken from [88, 47, 84], and subsequently revised to make it into a single comprehensive text. 7. References and Further Reading [1] P. Aczel. Non-Well-Founded Sets. CSLI Publications, Stanford, CA, 1988. CSLI Lecture Notes 14. [2] T. Agotnes, J. van Benthem, H. van Ditmarsch, and S. Minica. Question-Answer games, ˚ 2011. [3] M. Aloni, A. Butler, and P. Dekker, editors. Questions in Dynamic Semantics. Elsevier, Amsterdam, 2007. [4] G. Aucher. A combined system for update logic and belief revision. In Proc. of 7th PRIMA, pages 1–17. Springer, 2005. LNAI 3371. [5] G. Aucher and A. Herzig. From DEL to EDL : Exploring the power of converse events. In K. Mellouli, editor, Proc. of ECSQARU, LNCS 4724, pages 199–209. Springer, 2007. [6] G. Aucher and F. Schwarzentruber. On the complexity of dynamic epistemic logic. In Proc. of 14th TARK, 2013. [7] J. L. Austin. How to Do Things with Words. Clarendon Press, Oxford, 1962. [8] K. Bach. Speech acts. In E. Craig, editor, Routledge Encyclopedia of Philosophy, volume 8, pages 81–87. Routledge, London, 1998. [9] P. Balbiani, A. Baltag, H. van Ditmarsch, A. Herzig, T. Hoshi, and T. De Lima. ‘Knowable’ as ‘known after an announcement’. Review of Symbolic Logic, 1(3):305–334, 2008. [10] A. Baltag. A logic for suspicious players: epistemic actions and belief-updates in games. Bulletin of Economic Research, 54(1):1–45, 2002. [11] A. Baltag, B. Coecke, and M. Sadrzadeh. Algebra and sequent calculus for epistemic actions. Electronic Notes in Theoretical Computer Science, 126:27–52, 2005. [12] A. Baltag, B. Coecke, and M. Sadrzadeh. Epistemic actions as resources. J. of Logic Computat., 17(3):555–585, 2007. [13] A. Baltag and L. S. Moss. Logics for epistemic programs. Synthese, 139:165–224, 2004. [14] A. Baltag, L. S. Moss, and S. Solecki. The logic of public announcements, common knowledge, and private suspicions. In I. Gilboa, editor, Proceedings of TARK 98, pages 43–56, 1998. [15] A. Baltag and S. Smets. A qualitative theory of dynamic interactive belief revision. In Proc. of 7th LOFT, Texts in Logic and Games 3, pages 13–60. Amsterdam University Press, 2008. [16] A. Baltag and S. Smets. Group belief dynamics under iterated revision: fixed points and cycles of joint upgrades. In Proc. of 12th TARK, pages 41–50, 2009. [17] A. Baltag, H. van Ditmarsch, and L.S. Moss. Epistemic logic and information update. In J. van Benthem and P. Adriaans, editors, Handbook on the Philosophy of Information, pages 361–456, Amsterdam, 2008. Elsevier. [18] P. Blackburn, M. de Rijke, and Y. Venema. Modal Logic. Cambridge University Press, Cambridge, 2001. Cambridge Tracts in Theoretical Computer Science 53. [19] O. Board. Dynamic interactive epistemology. Games and Economic Behaviour, 49:49–80, 2004. [20] G. Bonanno. A simple modal logic for belief revision. Synthese (Knowledge, Rationality & Action), 147(2):193–228, 2005. [21] B. Brogaard and J. Salerno. Fitch’s paradox of knowability, 2004. http://plato. stanford.edu/archives/sum2004/entries/fitch-paradox/. [22] J. Cantwell. Some logics of iterated belief change. Studia Logica, 63(1):49–84, 1999. [23] I. Ciardelli and F. Roelofsen. Inquisitive dynamic epistemic logic. Manuscript, 2013. [24] C. Degremont. ´ The Temporal Mind. Observations on the logic of belief change in interactive systems. PhD thesis, University of Amsterdam, 2011. ILLC Dissertation Series DS-2010-03. [25] R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning about Knowledge. MIT, Cambridge, Massachusetts, 1995. [26] FIPA. FIPA communicative act library specification, 2002. http://www.fipa.org/. [27] F.B. Fitch. A logical analysis of some value concepts. The Journal of Symbolic Logic, 28(2):135–142, 1963. [28] N. Friedman and J.Y. Halpern. A knowledge-based framework for belief change – part i: Foundations. In Proc. of 5th TARK, pages 44–64. Morgan Kaufmann, 1994. [29] P. Gardenfors. ¨ Knowledge in Flux: Modeling the Dynamics of Epistemic States. Bradford Books, MIT Press, Cambridge, MA, 1988. 17 [30] J. Gerbrandy. Bisimulations on Planet Kripke. PhD thesis, University of Amsterdam, 1998. ILLC Dissertation Series DS-1999-01. [31] J. Gerbrandy. The surprise examination in dynamic epistemic logic. Synthese, 155(1):21– 33, 2007. [32] J. Gerbrandy and W. Groeneveld. Reasoning about information change. J. Logic, Lang., Inform., 6:147–169, 1997. [33] P. Girard. Modal logic for belief and preference change. PhD thesis, Stanford University, 2008. ILLC Dissertation Series DS-2008-04. [34] P. Gochet. The dynamic turn in twentieth century logic. Synthese, 130(2):175–184, 2002. [35] J. Groenendijk and M. Stokhof. Questions. In J. van Benthem and A. ter Meulen, editors, Handbook of Logic and Language, pages 1055–1124. Elsevier, Amsterdam, 1997. [36] J. Groenendijk, M. Stokhof, and F. Veltman. Coreference and modality. In S. Lappin, editor, The Handbook of Contemporary Semantic Theory, pages 179–213. Blackwell, Oxford, 1996. [37] W. Groeneveld. Logical Investigations into Dynamic Semantics. PhD thesis, University of Amsterdam, 1995. ILLC Dissertation Series DS-1995-18. [38] A. Grove. Two modellings for theory change. Journal of Philosophical Logic, 17:157–170, 1988. [39] D. Harel. First-Order Dynamic Logic. LNCS 68. Springer, 1979. [40] D. Harel. Dynamic logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, volume II, pages 497–604, Dordrecht, 1984. Kluwer Academic Publishers. [41] Vincent Hendricks and John Symons. Epistemic logic. In Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Spring 2006. [42] J. Hintikka. Knowledge and Belief. Cornell University Press, Ithaca, NY, 1962. [43] W. Holliday and T. Icard. Moorean phenomena in epistemic logic. In L. Beklemishev, V. Goranko, and V. Shehtman, editors, Advances in Modal Logic 8, pages 178–199. College Publications, 2010. [44] J. Hulstijn. Presupposition accommodation in a constructive update semantics. In G. Durieux, W. Daelemans, and S. Gillis, editors, Proceedings of CLIN VI, 1996. [45] J. Gerbrandy J. van Benthem and B. Kooi. Dynamic update with probabilities. Studia Logica, 93(1):67–96, 2009. [46] S. Konieczny and R. Pino Perez. Merging information under constraints: A logical frame- ´ work. Journal of Logic and Computation, 12(5):773–808, 2002. [47] B.P. Kooi. Dynamic epistemic logic. In J. van Benthem and A. ter Meulen, editors, Handbook of Logic and Language, pages 671–690. Elsevier, 2011. Second edition. [48] S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence, 44:167–207, 1990. [49] R. Lang. Questions as epistemic requests. In H. Hiz, editor, ˙ Questions, pages 301–318. Reidel, Dordrecht, 1978. [50] N. Laverny. Revision, mises ´ a jour et planification en logique doxastique graduelle ` . PhD thesis, Institut de Recherche en Informatique de Toulouse (IRIT), Toulouse, France, 2006. [51] D.K. Lewis. Counterfactuals. Harvard University Press, Cambridge (MA), 1973. [52] S. Lindstrom and W. Rabinowicz. DDL unlimited: dynamic doxastic logic for introspective ¨ agents. Erkenntnis, 50:353–385, 1999. [53] F. Liu. Changing for the Better: Preference Dynamics and Agent Diversity. PhD thesis, University of Amsterdam, 2008. ILLC Dissertation Series DS-2008-02. [54] C. Lutz. Complexity and succinctness of public announcement logic. In Proceedings AAMAS 06, Hakodate, Japan, 2006. [55] J.-J. Ch. Meyer and W. van der Hoek. Epistemic Logic for AI and Computer Science. Cambridge University Press, Cambridge, 1995. [56] T.A. Meyer, W.A. Labuschagne, and J. Heidema. Refined epistemic entrenchment. Journal of Logic, Language, and Information, 9:237–259, 2000. [57] G.E. Moore. A reply to my critics. In P.A. Schilpp, editor, The Philosophy of G.E. Moore, pages 535–677. Northwestern University, Evanston IL, 1942. The Library of Living Philosophers (volume 4). [58] L. S. Moss. From hypersets to Kripke models in logics of announcements. In J. Gerbrandy, M. Marx, M. de Rijke, and Y. Venema, editors, JFAK. Essays Dedicated to Johan van Benthem on the Occasion of his 50th Birthday, Amsterdam, 1999. Amsterdam University Press. [59] Michal Peli and Ondrej Majer. Logic of questions and public announcements. In Nick Bezhanishvili, Sebastian Lbner, Kerstin Schwabe, and Luca Spada, editors, Logic, Language, and Computation, pages 145–157. Springer, 2011. LNCS 6618. [60] J. Peregrin, editor. Meaning: the dynamic turn. Elsevier, Amsterdam, 2003. 19 [61] J. Plaza. Logics of public communications. Synthese, 158(2):165–179, 2007. This paper was originally published as Plaza, J. A. (1989). Logics of public communications. In M. L. Emrich, M. S. Pfeifer, M. Hadzikadic, and Z.W. Ras (Eds.), Proceedings of ISMIS: Poster session program (pp. 201–216). Publisher: Oak Ridge National Laboratory, ORNL/DSRD- 24. [62] G. R. Renardel de Lavalette. Changing modalities. J. Logic and Comput., 14(2):253–278, 2004. [63] B. Renne. A survey of dynamic epistemic logic. manuscript, 2008. [64] J. Sack. Adding Temporal Logic to Dynamic Epistemic Logic. PhD thesis, Indiana University, Bloomington, USA, 2007. [65] J. Salerno, editor. New Essays on the Knowability Paradox. Oxford University Press, Oxford, UK, 2009. [66] J. R. Searle. Speach Acts, An Essay in the Philosophy of Language. Cambridge University Press, Cambridge, 1969. [67] K. Segerberg. Irrevocable belief revision in dynamic doxastic logic. Notre Dame Journal of Formal Logic, 39(3):287–306, 1998. [68] K. Segerberg. Two traditions in the logic of belief: bringing them together. In H. J. Ohlbach and U. Reyle, editors, Logic, Language, and Reasoning, pages 135–147, Dordrecht, 1999. Kluwer. [69] P. Iliev T. French, W. van der Hoek and B. Kooi. On the succinctness of some modal logics. Artificial Intelligence, 197:56–85, 2013. [70] B. D. ten Cate. Internalizing epistemic actions. In M. Martinez, editor, Proceedings of the NASSLLI 2002 student session, pages 109 – 123, Stanford University, 2002. [71] J. van Benthem. Semantic parallels in natural language and computation. In Logic Colloquium ’87, Amsterdam, 1989. North-Holland. [72] J. van Benthem. Exploring Logical Dynamics. CSLI Publications, Stanford, 1996. [73] J. van Benthem. Games in dynamic-epistemic logic. Bulletin of Economic Research, 53(4):219–248, 2001. [74] J. van Benthem. Logics for information update. In J. van Benthem, editor, Proceedings of TARK 2001, pages 51–67, San Francisco, 2001. Morgan Kaufmann. [75] J. van Benthem. What one may come to know. Analysis, 64(2):95–105, 2004. [76] J. van Benthem. ‘one is a lonely number’: on the logic of communication. In Z. Chatzidakis, P. Koepke, and W. Pohlers, editors, Logic Colloquium ’02. ASL, Poughkeepsie, 2006. 20 [77] J. van Benthem. Dynamic logic of belief revision. Journal of Applied Non-Classical Logics, 17(2):129–155, 2007. [78] J. van Benthem. Logical Dynamics of Information and Interaction. Cambridge University Press, 2011. [79] J. van Benthem. Logic in Games. MIT Press, 2013. To appear. [80] J. van Benthem, J.D. Gerbrandy, T. Hoshi, and E. Pacuit. Merging frameworks for interaction. Journal of Philosophical Logic, 38:491–526, 2009. [81] J. van Benthem, J. van Eijck, and B. Kooi. Logics of communication and change. Information and Computation, 204(11):1620–1662, 2006. [82] W. van der Hoek and R. Verbrugge. Epistemic logic: a survey. In L.A. Petrosjan and V.V. Mazalov, editors, Game theory and Applications, volume 8, pages 53–94, 2002. [83] H. van Ditmarsch, A. Herzig, and T. De Lima. From situation calculus to dynamic epistemic logic. Journal of Logic and Computation, 21(2):179–204, 2011. [84] H. van Ditmarsch, W. van der Hoek, and P. Iliev. Everything is knowable – how to get to know whether a proposition is true. Theoria, 78(2):93–114, 2012. [85] H. van Ditmarsch, W. van der Hoek, and B. Kooi. Dynamic epistemic logic with assignment. In Proc. of 4th AAMAS, pages 141–148. ACM, 2005. [86] H. P. van Ditmarsch. Knowledge games. PhD thesis, University of Groningen, 2000. ILLC Dissertation Series DS-2000-06. [87] H. P. van Ditmarsch. Descriptions of game actions. J. Logic, Lang., Inform., 11:349–365, 2002. [88] H. P. van Ditmarsch. Prolegomena to dynamic logic for belief revision. Synthese, 147:229– 275, 2005. [89] H. P. van Ditmarsch and B. Kooi. The secret of my success. Synthese, 151(2):201–232, 2006. [90] H. P. van Ditmarsch, W. van der Hoek, and B. Kooi. Concurrent dynamic epistemic logic. In V. F. Hendricks, K. F. Jørgensen, and S. A. Pedersen, editors, Knowledge Contributors, pages 45–82. Kluwer, Dordrecht, 2003. [91] H. P. van Ditmarsch, W. van der Hoek, and B. Kooi. Dynamic Epistemic Logic. Springer, Berlin, 2007. [92] Peter Vanderschraaf and Giacomo Sillari. Common knowledge. In Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Fall 2007. 21 [93] F. Veltman. Defaults in update semantics. Journal of Philosophical Logic, 25:221–261, 1996. [94] Y. Wang, L. Kuppusamy, and J. van Eijck. Verifying epistemic protocols under common knowledge. In Proc. of 12th TARK, pages 257–266. ACM, 2009. Author Information Hans van Ditmarsch Email: [email protected] University of Lorraine France and Wiebe van der Hoek Email: [email protected] The University of Liverpool United Kingdom and Barteld Kooi Email: [email protected] University of Groningen Netherlands