In the full propositional logic, 5/8 of classical tautologies are intuitionistically valid. (English) Zbl 1248.03013
Summary: We present a quantitative comparison of classical and intuitionistic logics, based on the notion of density, within the framework of several propositional languages. In the most general case – the language of the “full propositional system” – we prove that the fraction of intuitionistic tautologies among classical tautologies of size \(n\) tends to 5/8 when \(n\) goes to infinity. We apply two approaches, one with a bounded number of variables, and another, in which formulae are considered “up to the names of variables”. In both cases, we obtain the same results. Our results for both approaches are derived in a unified way based on structural properties of formulae. As a by-product of these considerations, we present a characterization of the structures of almost all random tautologies.
MSC:
| 03B20 | Subsystems of classical logic (including intuitionistic logic) |
| 03B05 | Classical propositional logic |
Keywords:
propositional formulae; tautologies; asymptotic density; intuitionistic logic; analytic combinatoricsReferences:
| [1] | Chauvin, B.; Flajolet, P.; Gardy, D.; Gittenberger, B., And/Or trees revisited, Combinatorics, Probability and Computing, 13, 4-5, 475-497 (2004) · Zbl 1077.94526 |
| [2] | Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press · Zbl 1165.05001 |
| [3] | H. Fournier, D. Gardy, A. Genitrini, M. Zaionc, Classical and intuitionistic logic are asymptotically identical, in: CSL, 2007, pp. 177-193.; H. Fournier, D. Gardy, A. Genitrini, M. Zaionc, Classical and intuitionistic logic are asymptotically identical, in: CSL, 2007, pp. 177-193. · Zbl 1179.03015 |
| [4] | Gardy, D.; David, René; Gardy, Danièle; Lescanne, Pierre; Zaionc, Marek, Random boolean expressions, Computational Logic and Applications. Computational Logic and Applications, CLA’05. Computational Logic and Applications. Computational Logic and Applications, CLA’05, Discrete Mathematics and Theoretical Computer Science, vol. AF, 1-36 (2005) · Zbl 1193.03016 |
| [5] | Genitrini, A.; Kozik, J.; Zaionc, M., Intuitionistic vs classical tautologies, quantitative comparison, Lecture Notes in Computer Science, 4941, 100-109 (2008) · Zbl 1138.03309 |
| [6] | Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics: A Foundation for Computer Science (1989), Addison-Wesley Longman Publishing Co., Inc.: Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA · Zbl 0668.00003 |
| [7] | J. Kozik, Subcritical pattern languages for And/Or trees, in: Fifth Colloquium on Mathematics and Computer Science Blaubeuren, Germany, DMTCS Proceedings, September 2008.; J. Kozik, Subcritical pattern languages for And/Or trees, in: Fifth Colloquium on Mathematics and Computer Science Blaubeuren, Germany, DMTCS Proceedings, September 2008. · Zbl 1355.68162 |
| [8] | Moczurad, M.; Tyszkiewicz, J.; Zaionc, M., Statistical properties of simple types, Mathematical Structures in Computer Science, 10, 5, 575-594 (2000) · Zbl 0966.03016 |
| [9] | Moser, L.; Wyman, M., An asymptotic formula for the bell numbers, Transactions of the Royal Society of Canada, XLIX (1955) · Zbl 0066.31001 |
| [10] | Sorensen, M.; Urzyczyn, P., Lectures on the Curry-howard Isomorphism (1998) · Zbl 1183.03004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
