Zofia Kostrzycka
-
Density of truth in modal logics
dmtcs:3500 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2006,
DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
-
https://doi.org/10.46298/dmtcs.3500
Density of truth in modal logicsArticle
Authors: Zofia Kostrzycka 1,2
NULL
Zofia Kostrzycka
1 University of Technology
2 Opole University of Technology
The aim of this paper is counting the probability that a random modal formula is a tautology. We examine $\{ \to,\Box \}$ fragment of two modal logics $\mathbf{S5}$ and $\mathbf{S4}$ over the language with one propositional variable. Any modal formula written in such a language may be interpreted as a unary binary tree. As it is known, there are finitely many different formulas written in one variable in the logic $\mathbf{S5}$ and this is the key to count the proportion of tautologies of $\mathbf{S5}$ among all formulas. Although the logic $\mathbf{S4}$ does not have this property, there exist its normal extensions having finitely many non-equivalent formulas.
Volume: DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
Section: Proceedings
Published on: January 1, 2006
Imported on: May 10, 2017
Keywords: density of truth,Grzegorczyk's logic,S5 modal logic,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
Bibliographic References
3 Documents citing this article
Hervé Fournier;Danièle Gardy;Antoine Genitrini;Bernhard Gittenberger, 2011, The fraction of large random trees representing a given Boolean function in implicational logic, Random Structures and Algorithms, 40, 3, pp. 317-349, 10.1002/rsa.20379.
Hervé Fournier;Danièle Gardy;Antoine Genitrini;Bernhard Gittenberger, Lecture notes in computer science, Complexity and Limiting Ratio of Boolean Functions over Implication, pp. 347-362, 2008, 10.1007/978-3-540-85238-4_28.
Zofia Kostrzycka;Marek Zaionc, 2008, Asymptotic Densities in Logic and Type Theory, Studia Logica, 88, 3, pp. 385-403, 10.1007/s11225-008-9110-0.