Abstract Multi-modal versions of propositional logics S5 or S4—commonly accepted as logics of knowledge—are capable of describing static states of knowledge but they do not reflect how the knowledge changes after communications among agents. In the present paper (part of broader research on logics of knowledge and communications) we define extensions of the logic S5 which can deal with public communications. The logics have natural semantics. We prove some completeness, decidability and interpretability results and formulate a general method that solves certain kind of problems involving public communications—among them well known puzzles of Muddy Children and Mr. Sum & Mr. Product. As the paper gives a formal logical treatment of the operation of restriction of the universe of a Kripke model, it contributes also to investigations of semantics for modal logics. Keywords Logics of knowledge · Communications · Kripke models · Modal logic S5, (applicable in) distributed systems · (applicable in) expert systems
1 Introduction A students’ proverb says “No one knows everything but the true wisdom is to know whom to ask”. This emphasizes that knowledge can consist not only of ground facts but can also involve
This paper was originally published as Plaza, J. A. (1989). Logics of public communications. In M. L. Emrich, M. S. Pfeifer, M. Hadzikadic, & Z.W. Ras (Eds.), Proceedings of the fourth international symposium on methodologies for intelligent systems: Poster session program (pp. 201–216). Publisher: Oak Ridge National Laboratory, ORNL/DSRD-24. Research partly supported by NSF Grant CCR-8702307 and PSC-CUNY Grant 668283. J. Plaza (B ) Computer Science Department, SUNY Plattsburgh, 101 Broad Street, Plattsburgh, NY 12901, USA e-mail: jan.plaza@plattsburgh.edu
123
166
Synthese (2007) 158:165–179
statements about somebody else’s knowledge. Reasoning about knowledge is characteristic especially for those situations where information is exchanged. Example 1.1 Muddy Children Father: At least one of you has a muddy forehead. Child 1: I do not know whether my forehead is muddy. Child 2: I do not know whether my forehead is muddy. Child 3: I know whether my forehead is muddy or not but I won’t tell you! If the participants of the dialog can see each other (but no one can see his own forehead), is the forehead of Child 3 muddy? Example 1.2 Mr. Sum & Mr. Product Mr. Puzzle: I choose two natural numbers greater than 1. I will tell the sum of the numbers only to Mr. Sum, and their product only to Mr. Product. He tells them. Mr. Product: I do not know the numbers. Mr. Sum: I knew you didn’t. Mr. Product: But now I know! Mr. Sum: So do I! What can be the numbers if they are not greater than 100? The first of these puzzles was discussed in (Parikh 1987); the second one is a classic exercise in combinatorics and was further popularized by J. McCarthy. In this paper we propose and investigate formal logical systems which can deal with communication sessions such as those in 1.1, 1.2. The communication session of Muddy Children consists of a sequence of four public communications. In the communication session of the example 1.2 Mr. Puzzle performs two semi-public communications—one directed to Mr. Product and one—to Mr. Sum. (Semipublic communications considered in Plaza, J. A, 1988, Logics of knowledge and communications, unpublished are beyond the scope of this paper and the results will be published elsewhere.) The first communication of Mr. Product and the first communication of Mr. Sum are both based only on the knowledge acquired after Mr. Puzzle’s communications—Mr. Sum’s communication does not depend on Mr. Product’s one. Therefore, we consider them as
