Populational Announcement Logic (PPAL) Vitor Machado1 and Mario Benevides1,2 1 Institute of Mathematics Federal University of Rio de Janeiro 2 System Engineering and Computer Science Program (PESC/COPPE) Federal University of Rio de Janeiro Abstract. Populational Announcement Logic (PPAL), is a variant of the standard Public Announcement Logic (PAL) with a fuzzy semantics, where instead of specific agents we have populations and groups. The semantics and the announcement logic are defined, and an example is provided. We briefly talk about decidability and model checking. We conclude that the main advantage of PPAL over DEL and PAL is the flexibility to work with non-priorly defined agents. Keywords: epistemic logic, modal logic, knowledge representation 1 Introduction Epistemic logics attempt to provide ways to reason about knowledge representa- tion models [15]. C. I. Lewis published back in 1918 the book “Survey of Symbolic Logic”, possibly the first systematic approach to the matter [12]. Later in 1951, Von Wright’s “An Essay in Modal Logic” introduced a concept called “modality” to better represent the semantics of knowledge [16], providing operators such as “usually” and “always” to qualify propositional statements. It is considered the first important work regarding modal logic. A further development is Dynamic Logic, which reasons about actions and their effects [11]. Dynamic Epistemic Logic (DEL) is conceived to reason about actions that change agents’ knowledge and beliefs. It is not interested in justifying whether something is knowledge or not, but in inferring something from said knowledge. The first Dynamic Epistemic Logic was proposed independently by [14] and [10], and is called Public Announcement Logic (PAL), a logic which allows simple public actions which alter the state of knowledge for its agents. Later [2,3] proposed the Action Model Logic approach, allowing for more complex reasoning. 1.1 Motivation and Objectives This work aims to specify a variation of PAL where knowledge is represented across populations and groups of populations, instead of discrete agents as it is normally done. The motivation behind this is to provide a framework that is capable of dealing with applications where one intends to reason about evolution 2 Vitor Machado and Mario Benevides of knowledge across populations instead of individual agents. It is specially designed for model checking, because it is not necessary to specify agents (or populations in this case) beforehand, and instead these populations can be defined in the middle of the execution by the announcement operators of the language. To achieve this we have introduced and defined a “fuzzyfied” variant of PAL that allows partial announcements to its agents (called “populations” and “groups”). We formalize the model, language and semantics, and give an example where an initial model is given and some announcements are made which modify it, in order to illustrate its applicability in a scenario where knowledge evolves across populations as announcements are made. 1.2 Roadmap In section 2 we introduce Public Announcement Logic (PAL), showing a classical example to illustrate its use. In section 3, we introduce Populational Announce- ment Logic (PPAL), explain its purpose and differences with respect to PAL and define its language, semantics and model. We also talk about decidability and a model checker. Section 4 provides two basic examples of PPAL, showing how the model evolves after an announcement. Section 5 provides a conclusion, some final remarks and future works. 2 Public Announcement Logic (PAL) Now, we will briefly introduce the Public Announcement Logic, an extension to Multi-Agent Epistemic Logic which has been investigated in Computer Science [8] to represent and reason about agents or groups of agents’ knowledge and beliefs. It is the first actual Dynamic Epistemic Logic, developed by Plaza in [14]. 2.1 Language and Semantics The language is as follows in BNF notation: 𝜙 ::= 𝑝 |¬𝜙 | 𝜙1 ∧ 𝜙2 | 𝐾𝑎 𝜙 | [𝜑]𝜙 where 𝑝 ∈ 𝛷, the set of countably many proposition symbols, and 𝑎 ∈ 𝒜, a finite set of agents. The operators ∨ and → can be derived from the others similarly to propositional logic. The modal operator of public announcement [𝜑]𝜙 has the intended meaning: “after the announcement of 𝜑, 𝜙 holds”. The effect of announcing 𝜑 publicly is a restriction in the model to contain only states where 𝜑 is true. Definition 1 Given a multi-agent epistemic model ℳ = ⟨𝑆, ∼𝑎 , 𝑉 ⟩, the notion of satisfaction ℳ, 𝑠 |= 𝜙 is defined as follows: – ℳ, 𝑠 |= 𝑝 iff 𝑠 ∈ 𝑉 (𝑝) – ℳ, 𝑠 |= ¬𝜑 iff ℳ, 𝑠 ̸|= 𝜑 Populational Announcement Logic (PPAL) 3 – ℳ, 𝑠 |= 𝜑 ∧ 𝜓 iff ℳ, 𝑠 |= 𝜑 and ℳ, 𝑠 |= 𝜓 – ℳ, 𝑠 |= 𝐾𝑎 𝜑 iff ∀𝑠′ ∈ 𝑆 : 𝑠 ∼𝑎 𝑠′ ⇒ ℳ, 𝑠′ |= 𝜑 – ℳ, 𝑠 |= [𝜑]𝜙 iff ℳ, 𝑠 |= 𝜑 ⇒ ℳ|𝜑, 𝑠 |= 𝜙 where ℳ|𝜑 is a new model obtained by restricting ℳ to have only states where 𝜑 holds. 2.2 Example This example is from [6]. Suppose we have a card game with three cards: 0, 1 and 2, and three players 𝑎, 𝑏 and 𝑐. Each player receives a card and does not know the other players cards. We use proposition symbols 0𝑥 , 1𝑥 , 2𝑥 for 𝑥 ∈ {𝑎, 𝑏, 𝑐} meaning “player 𝑥 has card 0, 1 or 2”. We name each state by the cards that each player has in that state, for instance 012 is the state where player 𝑎 has card 0, player 𝑏 has card 1 and player 𝑐 has card 2. Figure 1 shows the epistemic model 𝐻𝑒𝑥𝑎1 which represents the epistemic state of each agent. 012 a 021 c b 102 a 120 b c b c 201 a 210 Fig. 1. Initial epistemic model (𝐻𝑒𝑥𝑎1 ). We are now going to make a public announcement and check the knowledge of an agent after that. Consider an announcement that agent 𝑎 does not have card 1 (¬1𝑎 ), and after that we want to check if agent 𝑐 knows if agent 𝑎 has the card 0 (𝐾𝑐 0𝑎 ). This can be expressed as: 𝐻𝑒𝑥𝑎1 , 012 |= [¬1𝑎 ]𝐾𝑐 0𝑎 (1) The epistemic model 𝐻𝑒𝑥𝑎2 representing the epistemic state of each agent after the announcement is shown in figure 2. We can check if 𝐾𝑐 0𝑎 holds in the new model 𝐻𝑒𝑥𝑎2 : 𝐻𝑒𝑥𝑎2 , 012 |= 𝐾𝑐 0𝑎 (2) Now, we have to check if 0𝑎 is true in every state connected to state 012 via the relation ∼𝑐 . Since there are no other states other than 012 itself, we check only this state: 𝐻𝑒𝑥𝑎2 , 012 |= 0𝑎 (3) Which is true because 012 ∈ 𝑉 ′ (0𝑎 ), and therefore 𝐻𝑒𝑥𝑎2 , 012 |= 𝐾𝑐 0𝑎 is also true. 4 Vitor Machado and Mario Benevides 012 a 021 c b 201 a 210 Fig. 2. Epistemic model after announcement (𝐻𝑒𝑥𝑎2 ). 3 Populational Announcement Logic (PPAL) Now we introduce PPAL, where we have populations and groups instead of agents. It works like a “fuzzyfied” version of PAL, where announcements act upon fractions of populations, so it does not make sense to talk explicitly of private or public announcements. It should be noticed that in the limit case where announcements are made to the whole population, PPAL behaves similarly to PAL with public announcements. This allows us much more flexibility, as we can define the populations of the system beforehand. Also, it allows expressing partial knowledge in a much more natural way. As a motivation, consider the following example: A famous politician is under suspicion of money laundering and bribery. Elections are coming up, and this politician expects to be re-elected, but people are less willing to vote for him if they are aware of both charges against him. Not everyone in the population is aware of the charges, however. With PPAL we can model announcements made by a TV program which only a certain amount of the population sees, and then we can assert the overall knowledge of the population in regards to the politician. For instance, the formula [𝑙]0.3 𝐺 𝐾𝐺 (𝑙 ∧ 𝑏) (4) represents an announcement made to a fraction of 0.3 of a group 𝐺, that the politician is in fact guilty of money laundering (𝑙), and a subsequent knowledge assertion of whether 𝐺 knows that the politician is corrupt or not (guilty of money laundering and bribery). We will return to this example in section 4. 3.1 Populations and Groups Definition 2 A population represents a collection of individuals. A population 𝑃 has size 𝑃 ∈ R>0 . It is defined as a real number because announcements split populations into a group with two populations, and their sizes will be then fractions of the population’s size. Populational Announcement Logic (PPAL) 5 Note that while a population represents many individuals, actual individuals are never directly expressed or referenced (as in DEL). Individuals are represented solely by the size of the population. The motivation for this comes down to the fact that we are mostly interested in representing and working with the knowledge of populations or fractions of populations, thus there is no purpose in modelling actual individuals. Next we will define the notion of groups. Definition 3 A group 𝐺 can be empty, a population or a disjoint set of groups: 𝐺 := ∅ | 𝑃 | {𝐺0 , 𝐺1 , . . . , 𝐺𝑛 } (5) The size of a group 𝐺 is defined as: ⎧ ⎨0 if 𝐺 = ∅, 𝐺= 𝑃 if 𝐺 = 𝑃 , ⎩ ∑︀ 𝐺𝑖 ∈𝐺 𝑖 if 𝐺 = {𝐺0 , 𝐺1 , . . . , 𝐺𝑛 }. 𝐺 The reason for having two definitions for “groups” and “populations” is the fact that announcements operate splitting groups into populations, as will be seen in section 3.4 and in subsection 4. Having groups and populations allows for a clearer definition of announcements, because if we only had populations there would be no easy way to reference, as a whole, the same individuals that we could reference before the announcement was made and they were a single population. 3.2 Model Since the announcements apply to fractions of a population, they work similarly to private announcements. Due to this, the many worlds approach is used. Each population has its own model, representing its current knowledge of the world: 𝑀𝑃 ,𝐺 Definition 4 A model for a population 𝑃 , 𝑀𝑃 = ⟨𝑇, ∼ , 𝑉 ⟩ is composed of a set of states 𝑇 , a valuation function that maps propositional symbols in 𝛷 into 𝑀𝑃 ,𝐺 subsets of 𝑇 , 𝑉 : 𝛷 → 2𝑇 , and a family of binary relations over 𝑇 , ∼ . For example, an edge representing the doubts of population 𝑃 in regards to group 𝑀𝑃 ,𝐺 𝐺 would be in the relation ∼ . Definition 5 A model 𝑀𝐺 , for a group 𝐺 = {𝐺0 , 𝐺1 , . . . , 𝐺𝑛 } is defined as the set of models of each of its groups. That is, 𝑀𝐺 = {𝑀𝐺0 , 𝑀𝐺1 , . . . , 𝑀𝐺𝑛 }. Since announcements split groups into populations, groups appearing on a branch after a split are not known to groups on other branches. That is, they will not appear on these groups’ models. 6 Vitor Machado and Mario Benevides 3.3 Language The language is as follows in BNF notation: 𝜙 ::= 𝑝 | ¬𝜙 | 𝜙1 ∧ 𝜙2 | 𝜙1 ∨ 𝜙2 | 𝜙1 → 𝜙2 |𝐾𝐺 𝜙 | 𝐵𝐺 𝜙 | [𝜙1 ]𝑟𝐺 𝜙2 (6) where 𝑟 ∈ 𝑈 = [0, 1], 𝐺 denotes a group and 𝑝 ∈ 𝛷. The modal operators have the following intended meaning: – 𝐾𝐺 𝜙 and 𝐵𝐺 𝜙: “the group 𝐺 knows/believes that 𝜙 is true”; – [𝜙1 ]𝑟𝐺 𝜙2 : “𝜙2 is true on group 𝐺’s model after the announcement of 𝜙1 to fraction 𝑟 of the individuals in 𝐺”, where 𝐺 = {𝑃1 , 𝑃2 } and 𝑃1 = 𝐺𝑟. This expression describes a partial announcement which defines two new populations, one of them with additional knowledge announced and other that did not received the new information announced. 3.4 Semantics This section presents the semantics of PPAL. We start by redefining (fuzzifying) the valuation functions 𝑉 defined in 4 and 5. In order to achieve that, we define an evaluation function 𝑒 : 𝑝 × (𝑀𝐺 , 𝑠) → 𝑈 where 𝑝 ∈ 𝛷, 𝑀𝐺 is a model for 𝐺, 𝑠 is a state and 𝑈 is the unit interval [0, 1]. We can define the semantics as follows: 𝐸𝑀𝐺 ,𝑠 (𝑝) = 𝑒(𝑝, (𝑀𝐺 , 𝑠)) 𝐸𝑀𝐺 ,𝑠 (¬𝜙) = 𝑁 𝑂𝑇 (𝐸𝑀𝐺 ,𝑠 (𝜙)) 𝐸𝑀𝐺 ,𝑠 (𝜙 ∧ 𝜓) = 𝐴𝑁 𝐷(𝐸𝑀𝐺 ,𝑠 (𝜙), 𝐸𝑀𝐺 ,𝑠 (𝜓)) 𝐸𝑀𝐺 ,𝑠 (𝜙 ∨ 𝜓) = 𝑂𝑅(𝐸𝑀𝐺 ,𝑠 (𝜙), 𝐸𝑀𝐺 ,𝑠 (𝜓)) 𝐸𝑀𝐺 ,𝑠 (𝜙 → 𝜓) = 𝐼𝑀 𝑃 (𝐸𝑀𝐺 ,𝑠 (𝜙), 𝐸𝑀𝐺 ,𝑠 (𝜓)) 𝐸𝑀𝐺 ,𝑠 (𝐾𝐺′ 𝜙) = 𝐾(𝜙, (𝑀𝐺 , 𝑠), 𝐺′ ) 𝐸𝑀𝐺 ,𝑠 (𝐵𝐺′ 𝜙) = 𝐵(𝜙, (𝑀𝐺 , 𝑠), 𝐺′ ) 𝐸𝑀𝐺 ,𝑠 ([𝜙]𝑟𝐺𝑛𝑒𝑤 𝜓) = 𝐸𝑀𝐺𝑛𝑒𝑤 ,𝑠 (𝜓) where ∃𝐺1 , 𝐺2 such that 𝐺𝑛𝑒𝑤 = {𝐺1 , 𝐺2 }, and 𝑀𝐺𝑛𝑒𝑤 = {𝑀𝐺1 , 𝑀𝐺2 } such that 𝑀𝐺1 = 𝑀𝐺 |𝑟𝜙 and 𝑀𝐺2 = 𝑀𝐺 |1−𝑟⊤ . ⊤ is a symbol for 𝑡𝑟𝑢𝑒. 𝑀𝐺 |𝑟𝜙 is defined as the new model obtained from 𝑀𝐺 by removing all states where ¬𝜙 holds, and multiplying all the sizes inside it by 𝑟. Depending on the choice of the evaluation function we can have different semantics. One possible evaluation function is the crisp evaluation. Suppose 𝑀𝐺 ,𝑆 ′ 𝑀𝐺 = ⟨𝑇, ∼ , 𝑉 ⟩ 𝑒(𝑝, (𝑀𝐺 , 𝑠)) = 1 if 𝑝 ∈ 𝑉 (𝑝) , and 0 otherwise (7) Below, we give some properties about the fuzzy functions that are used in the definition of satisfaction. At this point we choose not to define a particular fuzzy semantics and instead define classes for each operation. One can choose any Populational Announcement Logic (PPAL) 7 semantics which satisfies the following properties, and we provide an example for each of the classes. It is also important to note that this work is concerned with model checking and for that the notion of satisfaction is enough. For this reason we did not define the consequence relation. 3.5 Fuzzy Negation An unary operation 𝑁 𝑂𝑇 : 𝑈 → 𝑈 is a fuzzy negation if – 𝑁 𝑂𝑇 (0) = 1; – 𝑁 𝑂𝑇 (1) = 0; – 𝑥 ≤ 𝑦 → 𝑁 𝑂𝑇 (𝑦) ≤ 𝑁 𝑂𝑇 (𝑥). For instance, a possible negation function is 𝑁 𝑂𝑇 (𝑥) = 1 − 𝑥. 3.6 Fuzzy Conjunction A binary operation 𝐴𝑁 𝐷 : 𝑈 2 → 𝑈 is a fuzzy conjunction if – 𝐴𝑁 𝐷(𝑥, 𝑦) = 𝐴𝑁 𝐷(𝑦, 𝑥); – 𝐴𝑁 𝐷(𝑥, 𝐴𝑁 𝐷(𝑦, 𝑧)) = 𝐴𝑁 𝐷(𝐴𝑁 𝐷(𝑥, 𝑦), 𝑧); – 𝑦 ≤ 𝑧 → 𝐴𝑁 𝐷(𝑥, 𝑦) ≤ 𝐴𝑁 𝐷(𝑥, 𝑧); – 𝐴𝑁 𝐷(𝑥, 1) = 𝑥. These also define precisely the class of t-norm functions, which are widely used in fuzzy logics as they are considered “well-behaved” functions [7]. For instance, a possible conjunction function is 𝐴𝑁 𝐷(𝑥, 𝑦) = 𝑚𝑖𝑛{𝑥, 𝑦}. 3.7 Fuzzy Disjunction A binary operation 𝑂𝑅 : 𝑈 2 → 𝑈 is a fuzzy disjunction if – 𝑂𝑅(𝑥, 𝑦) = 𝑂𝑅(𝑦, 𝑥); – 𝑂𝑅(𝑥, 𝑂𝑅(𝑦, 𝑧)) = 𝑂𝑅(𝑂𝑅(𝑥, 𝑦), 𝑧); – 𝑦 ≤ 𝑧 → 𝑂𝑅(𝑥, 𝑦) ≤ 𝑂𝑅(𝑥, 𝑧); – 𝑂𝑅(𝑥, 0) = 𝑥. These also define precisely the class of t-conorm functions, analogous to the t-norm class. For instance, a possible disjunction function is 𝑂𝑅(𝑥, 𝑦) = 𝑚𝑎𝑥{𝑥, 𝑦}. 3.8 Fuzzy Implication A binary operation 𝐼𝑀 𝑃 : 𝑈 2 → 𝑈 is a fuzzy implication if – 𝑥 ≤ 𝑦 → 𝐼𝑀 𝑃 (𝑥, 𝑧) ≥ 𝐼𝑀 𝑃 (𝑦, 𝑧); – 𝑦 ≥ 𝑧 → 𝐼𝑀 𝑃 (𝑥, 𝑦) ≥ 𝐼𝑀 𝑃 (𝑥, 𝑧); – 𝐼𝑀 𝑃 (0, 𝑥) = 1; – 𝐼𝑀 𝑃 (𝑥, 1) = 1; – 𝐼𝑀 𝑃 (1, 0) = 0. For instance, a possible implication function is 𝐼𝑀 𝑃 (𝑥, 𝑦) = 𝑚𝑖𝑛{1, 1 − 𝑥 + 𝑦}, also known as the Łukasiewicz implication. 8 Vitor Machado and Mario Benevides 3.9 Fuzzy Knowledge Assertion A ternary operation 𝐾 : 𝜑 × (𝑀𝑆 , 𝑠) × 𝐺 → 𝑈 is a fuzzy knowledge assertion if 𝑀𝑆 ,𝑃 – if 𝐺 = 𝑃 then ∀𝑠′ ∈ 𝑇 |𝑠 ∼ 𝑠′ [𝐸𝑀𝑆 ,𝑠′ (𝜙) = 1 → 𝐾(𝜙, (𝑀𝑆 , 𝑠), 𝑃 ) = 1]; 𝑀𝑆 ,𝑃 – if 𝐺 = 𝑃 then ∀𝑠′ ∈ 𝑇 |𝑠 ∼ 𝑠′ [𝐸𝑀𝑆 ,𝑠′ (¬𝜙) = 1 → 𝐾(𝜙, (𝑀𝑆 , 𝑠), 𝑃 ) = 0]; – 𝐾(𝜙, (𝑀𝑆 , 𝑠), 𝐺) ≤ 𝑚𝑎𝑥𝐺′ ∈𝐺 {𝐾(𝜙, (𝑀𝑆 , 𝑠), 𝐺′ )}; – 𝐾(𝜙, (𝑀𝑆 , 𝑠), 𝐺) ≥ 𝑚𝑖𝑛𝐺′ ∈𝐺 {𝐾(𝜙, (𝑀𝑆 , 𝑠), 𝐺′ )}. For instance, a possible knowledge assertion function is 𝐾(𝜙, (𝑀𝑆 , 𝑠), 𝐺) = ⎧ ∑︀ 𝐺′ ′ ⎨ 𝐺′ ∈𝐺 𝐺 𝐾(𝜙, (𝑀𝑆 , 𝑠), 𝐺 ) if 𝐺 ̸= 𝑃 , ⎪ 𝑀𝑆 ,𝑃 ⎪ 1 if ∀𝑠′ ∈ 𝑇 |𝑠 ∼ 𝑠′ → 𝐸𝑀𝑆 ,𝑠′ (𝜙), 0 otherwise. ⎩ Note here that we slightly abuse notation for binary relations when they appear 𝑀𝐺 ,𝑃 referring to models of groups, such as the expression ∼ , which represents the binary relation for the model of population 𝑃 contained inside 𝑀𝐺 . Intuitively, it means that the knowledge of a group is equal to the weighted average knowledge of its contained groups, is equal to 1 when the group is a 𝑀𝑆 ,𝐺 single population and 𝜙 is true in every state connected to state 𝑠 via ∼ , and 0 otherwise. A single population knows something only when it is true in every conceivable world this population contemplates. 3.10 Fuzzy Belief Assertion A ternary operation 𝐵 : 𝜑 × (𝑀𝑆 , 𝑠) × 𝐺 → 𝑈 is a fuzzy belief assertion if 𝑀𝑆 ,𝑃 – if 𝐺 = 𝑃 then ∃𝑠′ ∈ 𝑇 |𝑠 ∼ 𝑠′ [𝐸𝑀𝑆 ,𝑠′ (𝜙) = 1 → 𝐵(𝜙, (𝑀𝑆 , 𝑠), 𝑃 ) > 0]; 𝑀𝑆 ,𝑃 – if 𝐺 = 𝑃 then ∃𝑠′ ∈ 𝑇 |𝑠 ∼ 𝑠′ [𝐸𝑀𝑆 ,𝑠′ (¬𝜙) = 1 → 𝐵(𝜙, (𝑀𝑆 , 𝑠), 𝑃 ) < 1]; 𝑀𝑆 ,𝑃 – if 𝐺 = 𝑃 then ∀𝑠′ ∈ 𝑇 |𝑠 ∼ 𝑠′ [𝐸𝑀𝑆 ,𝑠′ (𝜙) = 1 → 𝐵(𝜙, (𝑀𝑆 , 𝑠), 𝑃 ) = 𝐾(𝜙, (𝑀𝑆 , 𝑠), 𝑃 )]; – 𝐵(𝜙, (𝑀𝑆 , 𝑠), 𝐺) ≤ 𝑚𝑎𝑥𝐺′ ∈𝐺 {𝐵(𝜙, (𝑀𝑆 , 𝑠), 𝐺′ )}; – 𝐵(𝜙, (𝑀𝑆 , 𝑠), 𝐺) ≥ 𝑚𝑖𝑛𝐺′ ∈𝐺 {𝐵(𝜙, (𝑀𝑆 , 𝑠), 𝐺′ )}. For instance, a possible population belief assertion function is 𝐵(𝜙, (𝑀𝑆 , 𝑠), 𝐺) = 𝐺′ ⎧ ∑︀ ′ ⎨ 𝐺′ ∈𝐺 𝐺 𝐵(𝜙, (𝑀𝑆 , 𝑠), 𝐺 ) if 𝐺 ̸= 𝑃 , ⎪ ∑︀ 𝐸𝑀 ,𝑠′ (𝜙) ′ 𝑆 if 𝐺 ̸= ∅, ⎩ 𝑠 ∈𝑁𝑠 ⎪ 𝑁𝑠 0 otherwise. 𝑀𝑆 ,𝐺 𝑠′ are the neighbours of 𝑠 via relation ⋃︀ where 𝑁𝑠 = 𝑀𝑆 ,𝐺 ∼ . 𝑠′ ∈𝑇 |𝑠 ∼ 𝑠′ Populational Announcement Logic (PPAL) 9 Which is functionally similar to 𝐾, but allowing any number in the interval 𝑀𝑆 ,𝑃 [0, 1]. For example, if in half of the states connected to state 𝑠 via ∼ , 𝜙 evaluates to 1 and in the other half to 0, then 𝐵(𝜙, (𝑀𝑆 , 𝑠), 𝑃 ) = 0, 5. And also similarly to 𝐾, the belief of a group is equal to the weighted average beliefs of its contained groups. 3.11 Decidability An important aspect of model checking a logical system is that of decidability. In this section we show that any valid finite formula of the PPAL language over a finite model is in fact decidable. We use induction over the size 𝑠 of the formula for this proof. Definition 6 The size 𝑠 for each expression of the language is defined as follows: – 𝑠(𝑝) = 1; – 𝑠(𝜙1 ∧ 𝜙2 ) = 𝑠(𝜙1 ∨ 𝜙2 ) = 𝑠(𝜙1 → 𝜙2 ) = 𝑠(𝜙1 ) + 𝑠(𝜙2 ) + 1; – 𝑠(𝐾𝐺 𝜙) = 𝑠(𝐵𝐺 𝜙) = 𝑠(𝜙) + 1 + |𝐺|; – 𝑠([𝜙1 ]𝑟𝐺 𝜙2 ) = 𝑠(𝜙1 ) + 𝑠(𝜙2 ) + 1 + |𝐺|. Next, we can proceed to the induction basis step where 𝑠 = 1, that is, the case of a formula consisting of a single propositional symbol. 𝐸𝑀𝐺 ,𝑠 (𝑝) = 𝑒(𝑝, (𝑀𝐺 , 𝑠)) evaluates to 1 or 0 in a finite model, and therefore is decidable. We then consider the induction hypothesis to be that any formula with size 𝑠 is decidable. Now it remains necessary to take the inductive step, assuming the induction hypothesis and proving that formulas with size 𝑠 + 𝛿 are also decidable, where 𝛿 ∈ R>0 . Note that 𝛿 is in the real interval because the size |𝐺| of a group 𝐺 can be a real value. Inductive step: 1. 𝐸𝑀𝐺 ,𝑠 (¬𝜙) = NOT (𝐸𝑀𝐺 ,𝑠 (𝜙)): NOT is a simple mathematical function which evaluates to a value in 𝑈 for any input in 𝑈 . Since 𝐸𝑀𝐺 ,𝑠 (𝜙) is decidable by hypothesis, this formula is decidable. 𝐸𝑀𝐺 ,𝑠 (𝜙 ∧ 𝜓), 𝐸𝑀𝐺 ,𝑠 (𝜙 ∨ 𝜓) and 𝐸𝑀𝐺 ,𝑠 (𝜙 → 𝜓) are all decidable due to the same arguments; 2. 𝐸𝑀𝐺 ,𝑠 (𝐾𝐺′ 𝜙) = K (𝜙, (𝑀𝐺 , 𝑠), 𝐺′ ): (a) It is trivially decidable when 𝐺′ = ∅, because its evaluation will always be equal to 0; (b) It is decidable when 𝐺′ = 𝑃 , as the formula is resolved via calculations of 𝐸𝑀𝐺 ,𝑠′ (𝜙) which is decidable by hypothesis; (c) In the case where 𝐺′ = {𝐺′0 , 𝐺′1 , . . . , 𝐺′𝑛 }, the sum will range recursively over every 𝐺′𝑖 ∈ 𝐺′ . The sizes |𝐺′𝑖 | are strictly smaller than |𝐺| because by definition the group 𝐺′ is composed of a disjoint set of groups. Due to this, 𝑠(𝐾𝐺′𝑖 𝜙) < 𝑠(𝐾𝐺′ 𝜙) and 𝐾𝐺′𝑖 𝜙 is decidable by hypothesis. 𝐾𝐺′ 𝜙 is resolved via calculations of 𝐾𝐺′𝑖 𝜙, therefore, the formula is decidable. 3. 𝐸𝑀𝐺 ,𝑠 (𝐵𝐺′ 𝜙) = B(𝜙, (𝑀𝐺 , 𝑠), 𝐺′ ): (a) It is trivially decidable when 𝐺′ = ∅, because its evaluation will always be equal to 0; 10 Vitor Machado and Mario Benevides (b) When 𝐺′ = 𝑃 , the sum ranges over all neighbours 𝑠′ of state 𝑠, but since the model is finite and 𝐸𝑀𝐺 ,𝑠′ (𝜙) is decidable by hypothesis, it is decidable; (c) In the case where 𝐺′ = {𝐺′0 , 𝐺′1 , . . . , 𝐺′𝑛 }, the same argument used in 2b shows this formula is decidable. 4. 𝐸𝑀𝐺 ,𝑠 ([𝜙]𝑟𝐺′ 𝜓) = 𝐸𝑀𝐺′ ,𝑠 (𝜓): 𝑀𝐺 is finite and therefore 𝑀𝐺′ is also finite as it contains exactly twice the number of elements in 𝑀𝐺 . To define 𝑀𝐺′ we need to calculate 𝐸𝑀𝐺 ,𝑠 (𝜙) for every 𝑠 ∈ 𝑇 , which are decidable by hypothesis. 𝐸𝑀𝐺′ ,𝑠 (𝜓) is also decidable by hypothesis. Also note that it is not possible to write a formula that divides the group indefinitely, as that would require us to write down an infinite number of announcements. Therefore, the formula is decidable. Hence we have covered every possible case and shown that they are all decidable, therefore successfully showing that any valid finite formula of the PPAL language over a finite model is decidable using the specified operator functions. Notice however, that recursive formulas such as 𝜙 := [𝜙]𝑟𝐺′ 𝜓 or 𝜙 := [𝜓]𝑟𝐺′ 𝜙 are not included in the language definition, and they would break the language’s property of being decidable. 3.12 Model Checker A general-purpose Java library implementing the aforementioned language and semantics, and a model checker have been developed. Both programs are covered by unit and integration testing to ensure consistency with the PPAL language and semantics. The source-code of both library and model checker are available on GitHub3 . The main current implementations of model checkers available for epistemic logics are MCK [9], MCMAS [13] and DEMO [5]. A recent development called SMCDEL [4] formalizes a new structure to represent DEL models which allows for symbolic model checking, a model which uses binary decision diagrams (BDDs) [1] to represent models instead of having every state directly represented in the system. Due to this, SMCDEL also provides better performance over the other model checkers. 4 The Corrupt Politician In this section we continue the example introduced in section 3, where a simple model is established and some assertions are made to probe the knowledge represented by this model. For clarity’s sake, we name the states with the set of propositional symbols, or their negation, that hold in it. For instance, state {𝑎, ¬𝑏} is the state where 𝑎 and ¬𝑏 are true. Also, we will omit the full math for some of the simplest equations due to space constraints. 3 https://github.com/vittau/PPAL Populational Announcement Logic (PPAL) 11 4.1 Initial Model Suppose an initial model composed of a single population 𝑃 with size 𝑃 = 1, two propositions 𝑙 (money laundering) and 𝑏 (bribery), and a real state 𝑟 = {𝑙, 𝑏}, which means the politician in fact is guilty of the charges against him. The evaluation function is the same as defined before. This model is as shown in figure 3. ¬𝑙, ¬𝑏 𝑃 𝑃 𝑃 𝑃 ¬𝑙, 𝑏 𝑙, ¬𝑏 𝑃 𝑃 𝑙, 𝑏 Fig. 3. Initial state. For brevity, let us call 𝜙 = 𝑙 ∧ 𝑏 here onwards. As expected if we assert how much of the population would not vote on the politician, that is, if we ask: 𝐸𝑀𝑃 ,𝑟 (𝐾𝑃 (𝜙)) (8) It will evaluate to 0, as there are 𝑃 edges connecting the state 𝑟 to other states. 4.2 First Announcement Then, a TV program aired revealing the politician in fact did money laundering, but given that only 30% of the population watched the program, only a fraction of the population is now aware of this fact. This is equivalent to the announcement [𝑙]0.3 1 2 𝐺 , where 𝐺 = {𝑃 , 𝑃 } is a group containing the two populations resulting from the announcement: 𝑃 1 who received the announcement, and 𝑃 2 who did not. Figure 4 shows the resultant model G. If we were now to assert how much of the population would not vote on the politician, we would be asking: 𝐸𝑀𝑃 ,𝑟 ([𝑙]0.3 𝐺 𝐾𝐺 (𝜙)) (9) The announcement [𝑙]0.3 𝐺 generates group 𝐺, which contains populations 𝑃1 and 𝑃2 , where the former received the announcement. 𝐾𝐺 (𝜙) will still evaluate to 0, as there are still 𝑃1 and 𝑃2 edges connecting the state 𝑟 to other states. That is, both populations remain in doubt about whether 𝑟 is the real state or not. 12 Vitor Machado and Mario Benevides ¬𝑙, ¬𝑏 ¬𝑙, ¬𝑏 𝑃2 1 2 𝑃2 𝑃2 𝑃 ,𝑃 𝑃 1, 𝑃 2 𝑃 1, 𝑃 2 𝑃2 ¬𝑙, 𝑏 𝑙, ¬𝑏 ¬𝑙, 𝑏 𝑙, ¬𝑏 𝑃 1, 𝑃 2 𝑃 1, 𝑃 2 𝑃 1, 𝑃 2 𝑃 1, 𝑃 2 𝑃2 𝑙, 𝑏 𝑙, 𝑏 Fig. 4. Model 𝐺 (𝑃 1 ’s to the left, 𝑃 2 ’s to the right). We could also make an assertion in regards to the belief of the population, that is: 𝐸𝑀𝑃 ,𝑟 ([𝑙]0.3 𝐺 𝐵𝐺 (𝜙)) (10) To evaluate the belief we must evaluate 𝐸𝑀𝐺 ,𝑟 (𝐵𝐺 (𝜙)), which expands into ∑︁ 𝐺′ 𝐵(𝜙, (𝑀𝐺 , 𝑟), 𝐺) = 𝐵(𝜙, (𝑀𝐺 , 𝑟), 𝐺′ ) 𝐺′ ∈𝐺 𝐺 ∑︁ 𝐸𝑀 1 ,𝑟 (𝜙) ∑︁ 𝐸𝑀 2 ,𝑟 (𝜙) (11) 𝑃 𝑃 = 0.3 + 0.7 𝑟 ′ ∈𝑁𝑟 𝑁𝑟 𝑟 ′ ∈𝑁𝑟 𝑁𝑟 = 0.3 · 1/2 + 0.7 · 1/4 = 0.325 The first sum evaluates to 1/2 because out of two neighbour states to 𝑟 ({𝑙, 𝑏} itself and {𝑙, ¬𝑏}), 𝜙 is only true in 𝑟. The second has all four states as neighbours, but 𝜙 is only true in 𝑟 again. The result 0.325 demonstrates a small belief at this moment that the politician is in fact corrupt. 4.3 Second Announcement Now, let us consider another TV program aired, and this time covering 40% of the same original population, and it was told that the politician is in fact guilty of bribery. This corresponds to the announcement [𝑏]0.4 ′ 1 2 𝐺′ , where 𝐺 = {𝐺 , 𝐺 } is 1 a group containing the two groups resulting from the announcement: 𝐺 who received the announcement, and 𝐺2 who did not. The model resulting from both announcements is shown in figure 5. If we were now to assert how much of the population would not vote on the politician, we would be asking: 𝐸𝑀𝑃 ,𝑟 ([𝑙]0.3 0.4 𝐺 [𝑏]𝐺′ 𝐾𝐺′ (𝜙)) (12) At this moment the assertion would evaluate to 0.12, since there are no more edges connecting the state 𝑟 to anything else for population 𝑃 11 in 𝐺1 . This example shows how pieces of knowledge can build up to create useful information for certain fractions of the populations, due to them having being exposed enough to these pieces, and how it might not be intuitive to find out how much exactly of a population knows a certain fact. Populational Announcement Logic (PPAL) 13 𝑙, 𝑏 𝑙, 𝑏 𝑃 12 𝑃 12 𝑃 21 , 𝑃 22 𝑃 22 𝑃 12 𝑃 22 ¬𝑙, 𝑏 𝑙, ¬𝑏 ¬𝑙, 𝑏 𝑙, ¬𝑏 𝑃 12 𝑃 22 12 12 22 22 𝑃 𝑃 𝑃 𝑃 ¬𝑙, ¬𝑏 ¬𝑙, ¬𝑏 𝑙, 𝑏 𝑙, 𝑏 𝑃 12 𝑃 11 , 𝑃 12 𝑃 21 , 𝑃 22 𝑃 21 , 𝑃 22 𝑃 12 𝑃 21 , 𝑃 22 ¬𝑙, 𝑏 𝑙, ¬𝑏 ¬𝑙, 𝑏 𝑙, ¬𝑏 𝑃 12 𝑃 21 , 𝑃 22 12 12 21 22 21 22 𝑃 𝑃 𝑃 ,𝑃 𝑃 ,𝑃 ¬𝑙, ¬𝑏 ¬𝑙, ¬𝑏 Fig. 5. Model 𝐺′ . 𝐺1 ’s model to the left, population above received both announcements, below received only the first one; 𝐺2 ’s to the right, population above received only the second announcement, below received none. 5 Final Remarks, Future Works and Acknowledgments In this work we introduced and defined a “fuzzyfied” variant of PAL that allows partial announcements to its populations. The main advantage of PPAL over DEL and PAL is the flexibility to work with non-priorly defined agents. It is possible to define an initial population and have it evolve in a more natural way that doesn’t require a formal initial definition of every agent on the system. Therefore we believe it can be a more appropriate logic for practical use, as it would be much easier to manage a knowledge model. We also believe this work expands horizons for the definition of “dynamic” logic, as not only accessibility relations are dynamic, but the agents of the world themselves are changing and evolving. As such, it is a worthwhile topic of theoretical discussion, and not only of interest for model checking applications. 5.1 Axiomatization There is room for further development on a few directions still, and one important formalism for logics is that of axiomatization, that is, a set of tautologies (formulas that are always true in the logic), called axioms in this case, that can be used to derive all other formulas in the language. 5.2 Symbolic Model Checking We did not attempt symbolic model checking, a way to represent all reachable states using only sets of states and formulas for transition relations, which can improve performance. One such approach is based on the previously mentioned BDDs, which provide a compact way to represent and check valuations in Boolean functions, and equivalent Boolean sub-expressions are uniquely represented. 5.3 Acknowledgments We wish to thank the research agencies CNPq, CAPES and FAPERJ for their support. 14 Vitor Machado and Mario Benevides References 1. Akers, S.B.: Binary decision diagrams. IEEE Trans. Comput. 27(6), 509–516 (1978) 2. Baltag, A., Moss, L.S.: Logics for epistemic programs. Synthese 139(2), 165–224 (2004) 3. Baltag, A., Moss, L.S., Solecki, S.: The logic of public announcements, common knowledge and private suspicions. Proceedings of TARK’98 pp. 43–56 (1998) 4. van Benthem, J., van Eijck, J., Gattinger, M., Su, K.: Symbolic model checking for dynamic epistemic logic. In: van der Hoek, W., Holliday, W.H., Wang, W.f. (eds.) Logic, Rationality, and Interaction, Lecture Notes in Computer Science, vol. 9394, pp. 366–378. Springer Berlin Heidelberg (2015) 5. van Ditmarsch, H., van Eijck, J., HernÃąndez-AntÃşn, I., Sietsma, F., Simon, S., Soler-Toscano, F.: Modelling cryptographic keys in dynamic epistemic logic with demo. 10th International Conference on Practical Applications of Agents and Multi-Agent Systems 156, 155–162 (2012) 6. van Ditmarsch, H., van der Hoek, W., Kooi, B.: Dynamic epistemic logic. Synthese Library 337 (2007) 7. Esteva, F., Godo, L., Noguera, C.: First-order t-norm based fuzzy logics with truth-constants: distinguished semantics and completeness properties. Annals of Pure and Applied Logic 161, 185–202 (2009) 8. Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Reasoning about knowledge (1995) 9. Gammie, P., van der Meyden, R.: Mck: Model checking the logic of knowledge. Computer Aided Verification 3114, 479–483 (2004) 10. Gerbrandy, J., Groeneveld, P.W.: Reasoning about information change. Journal of Logic, Language and Information (6), 147–169 (1997) 11. Harel, D.: Dynamic Logic, pp. 497–604. Springer Netherlands, Dordrecht (1984) 12. Lewis, C.I.: A survey of symbolic logic (1918) 13. Lomuscio, A., Raimondi, F.: mcmas: A model checker for multi-agent systems. Tools and Algorithms for the Construction and Analysis of Systems 3920, 450–454 (2006) 14. Plaza, J.A.: Logics of public communications. Synthese 158(2), 165–179 (1989) 15. Shapiro, S.C.: Knowledge representation. Encyclopedia of Cognitive Science 2, 671–680 (2003) 16. von Wright, G.H.: An essay in modal logic (1951)