Marek ZAIONC
On the asymptotic density of tautologies in logic of implication and negation
A b s t r a c t. 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%.