##
Reports on Mathematical Logic

###
No. 39

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%.

Back to Main Menu