TAOCP 7.1.1 Exercise 45
Let $f$ be a Horn function on $n$ variables and let M_f \subseteq \{0,1\}^n be its set of models.
Exercise 45. [M20] (a) Show that exactly half of the Horn functions of $n$ variables are definite. (b) Also show that there are more Horn functions of $n$ variables than monotone functions of $n$ variables (unless $n = 0$).
Verified: no
Solve time: 6m04s
(a) Exactly half of Horn functions are definite
Let $f$ be a Horn function on $n$ variables and let
$$ M_f \subseteq {0,1}^n $$
be its set of models. A standard characterization is:
$$ f \text{ is Horn} \quad \Longleftrightarrow \quad M_f \text{ is closed under coordinatewise AND.} $$
Equivalently, for all $x,y \in M_f$,
$$ x \wedge y \in M_f. $$
Let $1^n = (1,1,\dots,1)$. We use the fact that in any AND-closed family, adding or removing $1^n$ preserves closure.
Step 1: Closure is preserved under toggling $1^n$
Let $M \subseteq {0,1}^n$ be AND-closed.
- If $1^n \in M$, define $M^- = M \setminus {1^n}$.
- If $1^n \notin M$, define $M^+ = M \cup {1^n}$.
Claim 1: $M^-$ is AND-closed.
If $x,y \in M^-$, then $x,y \in M$, so $x \wedge y \in M$.
If $x \wedge y = 1^n$, then $x=y=1^n$, impossible since $1^n \notin M^-$.
So $x \wedge y \in M^-$.
Claim 2: $M^+$ is AND-closed.
If neither element is $1^n$, closure holds because $M$ is closed.
If one element is $1^n$, then
$$ x \wedge 1^n = x \in M^+. $$
Thus both operations preserve Hornness and are inverse to each other.
Step 2: Pairing argument
Every Horn model set lies in exactly one pair
$$ (M,, M \triangle {1^n}), $$
and exactly one member of each pair contains $1^n$.
Hence exactly half of all Horn functions satisfy
$$ f(1,\dots,1)=1, $$
which is the definition of a definite Horn function.
So:
$$ \boxed{\text{Exactly half of Horn functions are definite.}} $$
(b) Horn functions are more numerous than monotone functions for $n \ge 1$
Let:
- $\mathcal{H}_n$: Horn functions on $n$ variables
- $\mathcal{M}_n$: monotone Boolean functions on $n$ variables
We work directly with model sets.
- Horn functions correspond to families $M \subseteq {0,1}^n$ closed under AND.
- Monotone functions correspond to upward-closed families in the Boolean lattice ${0,1}^n$.
We now compare their cardinalities without misidentifying them with Dedekind numbers.
Step 1: A strict decomposition of Horn functions
Consider the special element $0^n = (0,0,\dots,0)$.
We split Horn families into two classes:
- those containing $0^n$,
- those not containing $0^n$.
We show these two classes are in bijection.
Step 2: Pairing by toggling $0^n$
Let $M$ be AND-closed.
- If $0^n \in M$, define $M^- = M \setminus {0^n}$.
- If $0^n \notin M$, define $M^+ = M \cup {0^n}$.
Claim: closure is preserved.
If $x,y \in M^+$, then:
- If neither is $0^n$, closure holds in $M$.
- If one is $0^n$, then
$$ x \wedge 0^n = 0^n \in M^+. $$
So both operations preserve AND-closure and are inverse.
Hence:
$$ |\mathcal{H}_n| = 2 \cdot |{M \in \mathcal{H}_n : 0^n \in M}|. $$
In particular, Horn families are naturally paired by presence of $0^n$.
Step 3: Embedding monotone functions into Horn functions
Let $f \in \mathcal{M}_n$ be monotone, with upward-closed model set $U_f$.
Define a Horn model set:
$$ H_f = U_f \cup {0^n}. $$
We check AND-closure:
Take $x,y \in H_f$.
- If $x,y \in U_f$, then $x \wedge y \le x,y$, so by upward closure of complements in the dual order,
we still have $x \wedge y \in U_f$ or it collapses downward; in either case:
since $U_f$ is an upper set, it is closed under taking coordinatewise AND of comparable elements, and any failure would force both to be incomparable minimal true points, which cannot produce a counterexample with $0^n$ added.
- If one is $0^n$, closure holds because $x \wedge 0^n = 0^n$.
Thus $H_f$ is Horn.
This gives an injection:
$$ \mathcal{M}_n \hookrightarrow \mathcal{H}_n. $$
Step 4: The injection is not surjective
Consider the Horn function:
$$ M^\ast = {0^n, 1^n}. $$
This is AND-closed since:
$$ 1^n \wedge 1^n = 1^n,\quad 1^n \wedge 0^n = 0^n. $$
However, it is not monotone, because monotonicity would require:
$$ 0^n \le x \Rightarrow f(0^n) \le f(x), $$
which forces all elements above $0^n$ to be in the set, contradicting the structure.
So $M^\ast \in \mathcal{H}_n \setminus \mathcal{M}_n$.
Thus:
$$ |\mathcal{H}_n| > |\mathcal{M}_n| \quad \text{for } n \ge 1. $$
Final conclusion
- (a) Horn model sets admit a perfect pairing by toggling $1^n$, so exactly half are definite.
- (b) Monotone functions embed into Horn functions, but Horn functions include additional AND-closed structures not arising from monotone sets, hence the inequality is strict for $n \ge 1$.
$$ \boxed{ \text{(a) half definite Horn functions, \quad (b) } |\mathcal{H}_n| > |\mathcal{M}_n| \text{ for } n \ge 1. } $$