TAOCP 7.1.1 Exercise 131
A Boolean function $f:\{0,1\}^n\to\{0,1\}$ is Horn iff its set of true assignments is closed under intersection.
Exercise 131. [HM42] Table 3 makes it clear that there are many more Horn functions than Krom functions. What is the asymptotic number of Horn functions, as $n \to \infty$?
Verified: no
Solve time: 4m53s
A Boolean function $f:{0,1}^n\to{0,1}$ is Horn iff its set of true assignments is closed under intersection. Equivalently, these true sets are exactly the Moore families (closure systems) on $[n]$, i.e. families $\mathcal{F}\subseteq 2^{[n]}$ such that
- $A,B\in\mathcal{F}\Rightarrow A\cap B\in\mathcal{F}$,
- $[n]\in\mathcal{F}$.
Thus $H(n)$, the number of Horn functions, equals the number of Moore families on an $n$-element set.
Step 1: Reduction to a classical counting problem
Moore families are in one-to-one correspondence with closure operators on $[n]$, and it is a classical theorem that these are equinumerous with antichains of subsets of $[n]$. Hence
$$ H(n) = M(n), $$
where $M(n)$ is the $n$-th Dedekind number, i.e. the number of monotone Boolean functions (equivalently, antichains in the Boolean lattice).
Step 2: Known asymptotics of Dedekind numbers
A deep result (Korshunov) gives the asymptotic behavior of Dedekind numbers:
$$ \log_2 M(n) = (1+o(1))\binom{n}{\lfloor n/2\rfloor}. $$
Using Stirling’s approximation,
$$ \binom{n}{\lfloor n/2\rfloor} = \left(\frac{2^n}{\sqrt{\pi n/2}}\right)(1+o(1)). $$
Therefore,
$$ \log_2 H(n) = (1+o(1))\binom{n}{\lfloor n/2\rfloor} = (1+o(1))\frac{2^n}{\sqrt{\pi n/2}}. $$
Step 3: Final asymptotic form
Exponentiating,
$$ H(n) = 2^{(1+o(1))\binom{n}{\lfloor n/2\rfloor}} = 2^{(1+o(1))\frac{2^n}{\sqrt{\pi n/2}}}. $$
Final answer
$$ \boxed{ H(n) = 2^{(1+o(1))\binom{n}{\lfloor n/2\rfloor}} = 2^{(1+o(1))\frac{2^n}{\sqrt{\pi n/2}}} } $$