On the asymptotic density of tautologies in logic of implication and negation

• Autorzy: Zaionc M.
• Języki publikacji: EN

Abstrakty

EN

The paper solves the problem of finding the asymptotic probability of the set of tautologies of classical logic with one propositional variable, implication and negation. We investigate the proportion of tautologies of the given length n among the number of all formulas of length n. We are especially interested in asymptotic behavior of this proportion when $n \impl \infty$. If the limit exists it represents the real number between 0 and 1 which we may call density of tautologies for the logic investigated. In the paper [2] the existence of this limit for classical (and at the same time intuitionistic) logic of implication built with exactly one variable is proved. The present paper answers the question "how much does the introduction of negation influence the "density of tautologies" in the propositional calculus of one variable?" While in the case of implicational calculus the limit exists and is about 72.36\% (see Theorem 4.6 in the paper [2] ), in our case the limit exists as well, but negation lowers the density of tautologies to the level of about 42.32%.

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Reports on Mathematical Logic
• Rocznik: 2005
• Tom: Nr 39
• Strony: 67--87
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Zaionc M.

• Computer Science Department, Jagiellonian University, Nawojki 11, 30-072 Krakow, Poland,

Bibliografia

• [1] Comtet, L. (1974) Advanced combinatorics. The art of finite and infinite expansions. Revised and enlarged edition. Reidel, Dordrecht.
• [2] Moczurad M, Tyszkiewicz J, Zaionc M. (2000) ”Statistical properties of simple types ” Mathematical Structures in Computer Science, vol 10 (2000), pp 575-594.
• [3] Robins, H. (1955) A remark on Stirling formula, Ammer. Math. Monthly 62 (1955), pp 26-29.
• [4] Statman, R. (1980) On the existence of closed terms in the typed λ-calculus. In: Hindley, J.R., and Seldin,J., (eds.)Combinatory Logic, Lambda Calculus and Formalism, Academic Press, New York.
• [5] Szeg¨o, G. (1975) Orthogonal polynomials. Fourth edition.AMS, Colloquium Publications, 23, Providence.
• [6] Wilf, H.S. (1994) Generatingfunctionology. Second edition.Academic Press, Boston.