# Number of tautologies of a given size?

Fix some complete set of $$L$$ logical connectives such as $$\{ \wedge, \neg \}, \{\Rightarrow, \neg \}, \{\ \vee, \wedge, \neg \}, \{ \uparrow\}, \{\wedge, \vee, \neg, \Rightarrow \}$$ - I'll assume all formulas involve only the connectives in $$L$$ (I'm curious how this changes the answers to the questions below). The size of a formula $$\phi$$ with connectives in $$L$$ is the number of nodes of $$\phi$$ where $$\phi$$ is considered as a labeled tree (with variables labeling the leaves and connectives in $$L$$ labeling the internal edges).

What is known in terms of bounds on the number of tautologies (using the connectives in $$L$$) of size $$n$$ (or maybe size at most $$n$$ is more natural?)? Here, I want to consider two tautologies $$\tau_1$$ and $$\tau_2$$ to be the same if there is some bijection on the variables that when applied to the variables in $$\tau_1$$ yields $$\tau_2$$.

I'll say a tautology $$\tau$$ is reducible if there is some smaller tautology $$\tau_0$$ and a substitution $$\sigma$$ of formulas in for variables into $$\tau_0$$ yields $$\tau$$ - otherwise $$\tau$$ is irreducible.

Are almost all tautologies irreducible? Are there bounds on the number of irreducible (or reducible) tautologies of a given size?

• oeis.org/A256120 Commented May 4, 2022 at 1:09
• Related is the MSE question Proportion of true statements that are provable and some results by Marek Zaionc. Commented May 4, 2022 at 5:37
• i think that universal algebraists miiiight be able to say more about this then logicians. i also think it might be more natural to ask this for a language containing all 16 binary connectives. (There is actually a psychologist Zellweger who created and advocated for such a system.) Commented May 13, 2022 at 21:31