What's the density of tautologies in propositional formulas?
I know that, if we write down a propositional formula as a binary tree, if we allow \(k\) connectives, and if we consider only *alpha-congruent* propositional formulas (meaning: \(A\implies B\) is considered "the same" as \(X\implies Y\)) then there are:
\[ P_{n}(k) = k^{n}2^{2n+1}B_{n+1}C_{n} \]
different formulas, where \(B_{n+1}\) is the Bell number describing the possible choices of propositional variables, \(C_{n}\) is the Catalan number describing distinct binary trees, and we can negate each connective or leaf which gives us the factor \(2^{2n+1}\), and each internal node of a binary tree can be one of \(k\) possible connectives...usually \(k=4\). (This grows fast, like \(P_{n}(4)\sim n!30^{n}\) or so.)
There's a rough upper bound we can infer quickly. For example, if \(V_{n}(k)\) is the number of valid propositional formulas with exactly \(n\) connectives (and there are \(k\) possible primitive binary connectives to pick from), if \(U_{n}(k)\) is the number of unsatisfiable ("contradictory") propositional formulas in \(n\) binary connectives, then we have \(V_{n}(k)=U_{n}(k)\) since negating a valid formula makes it unsatisfiable (and negating an unsatisfiable formula makes it valid). This suggests that
\[ 2V_{n}(k)\leq P_{n}(k)\implies \frac{V_{n}(k)}{P_{n}(k)}\leq\frac{1}{2}\]
But this is rather coarse of an upper bound.
I know \(V_{0}(4)=0\) and \(V_{1}(4)=12\), but beyond that things just grow too quickly for me :(