nach oben

Erschienen in:

2012 | OriginalPaper | Buchkapitel

Structures of Oppositions in Public Announcement Logic

verfasst von : Lorenz Demey

Erschienen in: Around and Beyond the Square of Opposition

Verlag: Springer Basel

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we study dynamic epistemic logic, and in particular public announcement logic, using the tools of n-opposition theory. Dynamic epistemic logic is a contemporary development of epistemic logic, which takes into account changes of knowledge through time. It studies, for example, public announcements and the influence they have on the agents’ knowledge. n-Opposition theory is a systematic generalization of the traditional squares of oppositions. In the paper we provide introductions to the intuitions behind and the formal details of both of these disciplines. We construct a square and a hexagon of oppositions for the structural properties of public announcement. We then generalize this to opposition structures for any partially functional process, and show how this generalization can be used to support the structuralist philosophy surrounding n-opposition theory. Next, we focus on the epistemic properties of public announcement, and construct an octagon and a (three-dimensional) rhombic dodecahedron of oppositions. Many of the techniques applied in this paper were originally developed by Smessaert (Logica Univers. 3:303–332, 2009); they are thus shown to be very powerful and widely applicable. Summing up: we establish a strong connection between public announcement logic and n-opposition theory, and show that this connection has definite advantages for both of the disciplines involved.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel How to Square Knowledge and Belief

Nächstes Kapitel Logical Opposition and Collective Decisions

The most comprehensive account of this work was presented by Lenzen during the Second World Conference on the Square of Oppositions (Corte, June 17–20, 2010).

I would like to emphasize that Moretti has already shown how Lenzen’s original squares for epistemic logic can be generalized to higher-order structures of oppositions (in particular, tetraicosahedra) [22, pp. 306–308]. In other words, he has used the ‘contemporary’ machinery of n-opposition theory to look at ‘classical’ epistemic logic.

This heuristic role is not often acknowledged. A notable exception are Davey and Priestley, who write that “Diagram-drawing is as much an art as a science […] good diagrams can be a real asset to understanding and to theorem-proving” [8, p. 11].

The aim is to keep this paper more or less self-contained. We do presuppose, however, a (very) basic knowledge of classical, ‘static’ epistemic logic, i.e. modal S5 and its Kripke semantics.

Hintikka, for example, rules out occasions “on which people are engaged in gathering new factual information. Uttered on such an occasion, the sentences ‘I don’t know whether p’ and [later] ‘I know that p’ need not be inconsistent” [16, pp. 7–8]. Contrast this with our Example 1.

The restriction from epistemic dynamics in general to public announcements (and thus also from ‘full’ dynamic epistemic logic to public announcement logic) is mainly for expository reasons, and because public announcement logic was, historically speaking, the first system of dynamic epistemic logic to be developed [13, 23]. Most of the results in subsequent sections can easily be generalized from public announcement logic to full dynamic epistemic logic. For the beginnings of such a generalization, see Subsect. 3.3.

This subsection is not meant to be an exhaustive overview of PAL. For example, we do not discuss axiom systems for PAL, their soundness and completeness, or the interesting phenomenon of ‘non-successful formulas’. For an in-depth introduction to PAL, the reader is referred to [33, ch. 4].

For any state w∈W, we define R _i[w]:={v∈W∣(w,v)∈R _i}.

PAL also has a stronger notion of validity. A formula φ is said to be schematically valid iff all of its substitution instances φ[ψ/p] are valid (where φ[ψ/p] is the formula that results from uniformly replacing every occurrence of p in φ with an occurrence of ψ). Obviously, schematic validity implies validity. In logics which have the uniform substitution property (if φ is valid, then every substitution instance φ[ψ/p] is valid), validity also implies schematic validity, and thus the two notions coincide. PAL, however, does not have the uniform substitution property, and hence in PAL schematic validity is strictly stronger than validity [28, 29]. Also see Footnote 15.

Note that if φ is false in all states in $\mathbb{M}$, then the updated model $\mathbb{M}|\varphi$ is empty, and thus not well-defined. However, the formal semantics defined above guarantees that this will never have any practical consequences, because the updated model $\mathbb{M}|\varphi$ is used only when $\mathbb{M},w\models\varphi$ (in which case $\mathbb{M}|\varphi$ is well-defined).

Of course, this gives rise to many philosophical difficulties, e.g. concerning positive introspection: K _i φ→K _i K _i φ. These questions are not specific to epistemic dynamics (they already arise for static epistemic logic), and will therefore not be discussed here.

Thanks to Fabien Schang for advising me to be more explicit about this.

This means that $\mathbb {M},w\models\varphi$ and $\mathbb{M}|\varphi,w\not\models\varphi$, i.e. φ is initially true, but after announcing it, it becomes false. Such announcements are called ‘non-successful’; cf. Footnote 7.

For proofs of Lemmas 2.4 and 2.5, the reader is referred to [33, ch. 4].

However, it should be emphasized that PAL, as a logical system, is not a normal modal logic, because it does not have the uniform substitution property. For example, it holds that ⊨[!p]p, but $\not\models [!(p\wedge{\neg} K_{i}p)](p \wedge{\neg} K_{i}p)$ [33, p. 106].

For expository purposes, all definitions in this subsection are specific to the logic PAL and its language $\mathcal{L}$. Generalizations to any other (sufficiently expressive) logic and language are straightforward.

To the best of our knowledge, this observation (which is of course more general than the version for PAL given here) has never appeared in print before.

The Aristotelian relations generate an Aristotelian geometry, in which the opposition structures of Definition 3.3 exist. The Aristotelian relations are mutually exclusive only under the restriction to contingent formulas; furthermore, they are not exhaustive: there are pairs of formulas that stand in no Aristotelian relation at all. (For example, a formula never stands in any Aristotelian relation with itself.) In ongoing work with Hans Smessaert [11, 27], we define an oppositional geometry and an implicational geometry, each of which is generated by four relations which are (i) exhaustive and (ii) mutually exclusive (without restricting to contingent formulas). The Aristotelian geometry turns out to be a hybrid system: it shares the relations of contradiction, contrariety and subcontrariety with the oppositional geometry, and that of subalternation with the implicational geometry.

Note that the three symmetrical relations are represented by non-directed edges, whereas the asymmetrical subalternation relation is represented by directed edges going from the superaltern to the subaltern.

Contradictions are superaltern and contrary to any contingent formula. Tautologies are subaltern and subcontrary to any contingent formula. (Note that these statements do not contradict Lemma 3.2, since in both cases a non-contingent formula is involved.)

It suffices to consider the connectives ∧ and ¬, since these two are functionally complete, i.e. any other truth-functional connective (of any arity) can be written in terms of them [32, pp. 24–25].

This consistency requirement does not need to be stated explicitly for ¬-closure, because the negation of a contingency is always consistent.

means that ⊨γ↔(α∧β). Because of the commutativity of ∧, it suffices to give only the upper right half of the table.

In the specific framework of PAL, the hexagon is a bit more elegant than in other frameworks, because the conjunction and disjunction ‘reduce to’ the simpler formulas (¬)φ. (The formula φ is ‘simpler’ than the disjunction 〈!φ〉ψ∨〈!φ〉¬ψ in an obvious sense; however it should be emphasized that φ itself can be a formula of any complexity—as long as it is contingent; for example φ=K _i(p∧q)∧¬K _i r.) However, when we turn to opposition structures for the epistemic properties of public announcements in Sect. 4, we will not be able to maintain this simplicity, and we will have to work with ‘irreducibly complex’ formulas.

Computer scientists prefer the term ‘deterministic’.

In this subsection (and in this subsection only), we use ⊨ to denote PDL-validity, rather than PAL-validity.

Note that we implicitly subscribed to this structuralist philosophy when we claimed in Subsect. 3.1 that the ‘fundamental building blocks’ of opposition structures are the Aristotelian relations, rather than the concrete formulas appearing in the structures.

The original Dutch text: “Contrair zijn universele uitspraken die in kwaliteit verschillen. […] Subcontrair zijn particuliere proposities die in kwaliteit verschillen.” [9, p. 100]. De Pater and Vergauwen do state the characterizations of contrariety and subcontrariety in terms of ‘being able to be true/false together’ (cf. our Definition 3.1), but only as further lemmas about these relations, not as their definitions.

Modulo unsuccessful formulas; cf. Footnotes 7 and 13.

In the remainder of this section we will drop agent indices, since they are not crucial. We will thus use K instead of K _i to denote the knowledge operator in the formal language $\mathcal{L}$, and R instead of R _i to denote the equivalence relation in a Kripke model $\mathbb{M}$.

Note that we are here again applying the structuralist philosophy mentioned in Subsect. 3.3: we are calling two opposition structures ‘essentially the same’, because they have the same configuration of Aristotelian relations. The formulas in both structures are concerned with different topics (public announcements/necessity), and even on a higher level of abstraction they differ significantly: in Fig. 6 the formulas in the upper corners of the square are existential (〈!φ〉(¬)Kψ), whereas in Fig. 7 they are universal (□(¬)ψ).

In the remainder of this subsection, we will often refer to the formulas in F′ using the numbers they are given here. For example, we will refer to the formula ¬φ∧¬K[!φ]ψ using the number 10.

‘NO’ stands for no Aristotelian relation at all, ‘CD’ stands for contradictories, ‘C’ stands for contraries, ‘SC’ stands for subcontraries, and ‘↙/↗’ stand for subalternation. In particular, ‘↙’ says that there is a subalternation from the column-formula to the row-formula, and vice versa for ‘↗’. The table has 13×13 cells in total. Because only the upper right half is filled in, the number of entries is

$$\sum_{n=1}^{13}(14-n) = \sum _{n=1}^{13}14 - \sum_{n=1}^{13}n = (14\times13) - \frac{14\times13}{2} = \frac{14\times13}{2} = 91. $$

Of these 91 entries, 12 are ‘NO’, so in total we arrive at 91−12=79 Aristotelian relations.

Furthermore, Pellissier [24] distinguishes between strong and weak hexagons. A hexagon is strong iff the disjunction of its three contrary formulas is tautologous; a hexagon is weak iff the disjunction of its three contrary formulas is not tautologous. The six hexagons discussed here (displayed in Fig. 10) are all strong. For example, for hexagon i, note that the disjunction of its three contrary formulas (2, 5 and 6) is equivalent to φ∨¬φ.

More generally: the hexagon of oppositions for any partially functional process π (Fig. 4) can be seen as arising from the modal graph for the dynamic operators representing π.

I conjecture that this observation will have (negative) consequences for Pellissier’s view on opposition structures as ‘interpolations of consistency degrees’ ([22, p. 211], [24, Section 2]).

The term ‘complexity’ is used in an intuitive sense here (as is explained in the main text). It is well-known that from the perspective of computational complexity, PAL is equally complex as S5: the satisfiability problem of both S5 and PAL is NP-complete in the single-agent case, PSPACE-complete in the multi-agent case without common knowledge, and EXPTIME-complete in the multi-agent case with common knowledge [14, 20].

Baltag, A., Moss, L.: Logics for epistemic programs. Synthese 139, 165–224 (2004) MathSciNetMATHCrossRef

Baltag, A., Smets, S.: A qualitative theory of dynamic interactive belief revision. In: Bonanno, G., van der Hoek, W., Woolridge, M. (eds.) Logic and the Foundations of Game and Decision Theory (LOFT 7). Texts in Logic and Games, vol. 3, pp. 9–58. Amsterdam University Press, Amsterdam (2008)

Béziau, J.-Y.: New light on the square of oppositions and its nameless corner. Log. Investig. 10, 218–232 (2003)

Blanché, R.: Quantity, modality, and other kindred systems of categories. Mind 61, 369–375 (1952) CrossRef

Blanché, R.: Sur l’opposition des concepts. Theoria 19, 89–130 (1953) CrossRef

Blanché, R.: Opposition et négation. Rev. Philos. Fr. étrang. 167, 187–216 (1957)

Blanché, R.: Structures intellectuelles. Essai sur l’organisation systématique des concepts. Vrin, Paris (1966)

Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order, 2nd edn. Cambridge University Press, Cambridge (2002) MATH

de Pater, W.A., Vergauwen, R.: Logica: Formeel en Informeel. Leuven University Press, Leuven (2005)

10.

Demey, L.: Some remarks on the model theory of epistemic plausibility models. J. Appl. Non-Class. Log. 21, 375–395 (2011) CrossRef

11.

Demey, L., Smessaert, H.: Logical geometries emanating from the traditional square of oppositions. Manuscript (2011)

12.

Fitting, M., Mendelsohn, R.L.: First-Order Modal Logic. Kluwer, Dordrecht (1998) MATHCrossRef

13.

Gerbrandy, J., Groeneveld, W.: Reasoning about information change. J. Log. Lang. Inf. 6, 147–169 (1997) MathSciNetMATHCrossRef

14.

Halpern, J.Y., Moses, Y.: A guide to completeness and complexity for modal logics of knowledge and belief. Artif. Intell. 54, 319–379 (1992) MathSciNetMATHCrossRef

15.

Harel, D., Kozen, D., Tiuryn, J.: Dynamic Logic. MIT Press, Cambridge (2000) MATH

16.

Hintikka, J.: Knowledge and Belief. An Introduction to the Logic of the Two Notions. Cornell University Press, Ithaca (1962)

17.

Kozen, D., Parikh, R.: An elementary proof of the completeness of PDL. Theor. Comput. Sci. 14, 113–118 (1981) MathSciNetMATHCrossRef

18.

Lenzen, W.: Recent Work in Epistemic Logic. North-Holland, Amsterdam (1978)

19.

Lenzen, W.: Glauben, Wissen und Wahrscheinlichkeit: Systeme der epistemischen Logik. Springer, Berlin (1980) MATHCrossRef

20.

Lutz, C.: Complexity and succinctness of public announcement logic. In: Stone, P., Weiss, G. (eds.) AAMAS ’06: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 137–143. Association for Computing Machinery, New York (2006) CrossRef

21.

McNamara, P.: Deontic Logic. Stanford Encyclopedia of Philosophy (2010)

22.

Moretti, A.: The geometry of logical opposition. PhD thesis defended at the University of Neuchâtel, Switzerland (2009)

23.

Plaza, J.: Logics of public communications. In: Emrich, M.L., Pfeifer, M.S., Hadzikadic, M., Ras, Z.W. (eds.) Proceedings of the Fourth International Symposium on Methodologies for Intelligent Systems: Poster Session Program, pp. 201–216. Oak Ridge National Laboratory, Oak Ridge (1989). Reprinted in: Synthese 158, 165–179 (2007)

24.

Pellissier, R.: Setting n-opposition. Logica Univers. 2, 235–263 (2008) MathSciNetMATHCrossRef

25.

Sesmat, A.: Logique II. Les raisonnements, la logistique. Hermann, Paris (1951)

26.

Smessaert, S.: On the 3D visualisation of logical relations. Logica Univers. 3, 303–332 (2009) MathSciNetCrossRef

27.

Smessaert, H., Demey, L.: On the fourth Aristotelian relation: subalternation versus non-implication. Manuscript (2011)

28.

van Benthem, J.: One is a lonely number: logic and communication. In: Chatzidakis, Z., Koepke, P., Pohlers, W. (eds.) Logic Colloquium ’02. Lecture Notes in Logic, vol. 27, pp. 95–128. Association for Symbolic Logic & AK Peters, Wellesley (2006)

29.

van Benthem, J.: Open problems in logical dynamics. In: Gabbay, D., Goncharov, S., Zakharyashev, M. (eds.) Mathematical Problems from Applied Logic I. International Mathematical Series, vol. 4, pp. 137–192. Springer, Berlin (2006) CrossRef

30.

van Benthem, J.: Dynamic logic for belief revision. J. Appl. Non-Class. Log. 17, 129–155 (2007) MATHCrossRef

31.

van Benthem, J.: Logical Dynamics of Information and Interaction. Cambridge University Press, Cambridge (2011) MATHCrossRef

32.

van Dalen, D.: Logic and Structure, 4th edn. Springer, Berlin (2004) MATH

33.

van Ditmarsch, D., van der Hoek, W., Kooi, B.: Dynamic Epistemic Logic. Springer, Berlin (2007)

Titel: Structures of Oppositions in Public Announcement Logic
verfasst von: Lorenz Demey
Verlag: Springer Basel
Buch: Around and Beyond the Square of Opposition
Print ISBN: 978-3-0348-0378-6

Electronic ISBN: 978-3-0348-0379-3

Copyright-Jahr: 2012
DOI: https://doi.org/10.1007/978-3-0348-0379-3_22

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"