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?

  • 2
    $\begingroup$ oeis.org/A256120 $\endgroup$
    – RobPratt
    Commented May 4, 2022 at 1:09
  • $\begingroup$ Related is the MSE question Proportion of true statements that are provable and some results by Marek Zaionc. $\endgroup$ Commented May 4, 2022 at 5:37
  • $\begingroup$ 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.) $\endgroup$ Commented May 13, 2022 at 21:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.