TAOCP 7.1.1 Exercise 117
A term in a disjunctive normal form (DNF) is a conjunction of literals, each literal being either $x_i$ or $\bar{x}_i$ for some $1 \le i \le n$.
Exercise 117. [M26] A disjunctive normal form is called irredundant if none of its implicants implies another. Let $b'(n)$ be the maximum number of implicants in an irredundant DNF, over all Boolean functions of $n$ variables. Find a simple formula for $b'(n)$, and determine its asymptotic value.
Verified: yes
Solve time: 2m32s
Setup
A term in a disjunctive normal form (DNF) is a conjunction of literals, each literal being either $x_i$ or $\bar{x}_i$ for some $1 \le i \le n$. For a term $T$, write $\operatorname{lit}(T)$ for the set of literals appearing in $T$.
For two terms $T_1,T_2$, the implication relation satisfies
$$ T_1 \Rightarrow T_2 \quad \Longleftrightarrow \quad \operatorname{lit}(T_2) \subseteq \operatorname{lit}(T_1), $$
since every assignment satisfying all literals of $T_1$ necessarily satisfies every literal in $T_2$ exactly when $T_2$ is weaker.
A DNF is irredundant when no two distinct implicants satisfy $T_1 \Rightarrow T_2$.
Let $b'(n)$ denote the maximum possible number of implicants in an irredundant DNF over all Boolean functions of $n$ variables.
The task is to determine a closed expression for $b'(n)$ and its asymptotic growth.
Solution
Each term $T$ corresponds to a partial assignment on ${x_1,\dots,x_n}$ in which every variable is either fixed to $0$, fixed to $1$, or left unspecified. Hence each term corresponds to an element of ${0,1,*}^n$.
A term with exactly $k$ specified variables is formed by choosing $k$ indices from $n$ and assigning each chosen variable either $0$ or $1$. The number of such terms equals
$$ \binom{n}{k} 2^k. $$
The implication relation satisfies that a term with more specified variables implies a term with fewer specified variables whenever all fixed literals of the second occur in the first. Thus irredundancy requires that no chosen family of terms contains two elements with one coordinatewise refinement of another, which is equivalent to requiring that the family is an antichain in the poset ordered by reverse inclusion of literal sets.
Let $\mathcal{T}_k$ denote the set of all terms with exactly $k$ specified variables. If two distinct terms lie in the same $\mathcal{T}_k$, neither can imply the other, since implication strictly decreases the number of specified variables. Hence every subset of $\mathcal{T}_k$ is irredundant.
If a family contains terms from different levels $\mathcal{T}_i$ and $\mathcal{T}_j$ with $i>j$, then some term in $\mathcal{T}_i$ may imply a term in $\mathcal{T}_j$ whenever the literals of the latter are contained in the former. To avoid any implication relation entirely, the family must avoid such comparabilities, and thus must be an antichain in this graded poset.
The maximum size of such an antichain equals the maximum cardinality of a level $\mathcal{T}_k$, since each level is itself an antichain and any antichain cannot exceed the largest level by standard compression in graded product posets.
Therefore,
$$ b'(n) = \max_{0 \le k \le n} \binom{n}{k} 2^k. $$
To determine the asymptotic behavior, write
$$ \binom{n}{k}2^k = \frac{n!}{k!(n-k)!}2^k. $$
Define $k = pn$. Stirling’s approximation gives
$$ \binom{n}{pn}2^{pn} = \Theta!\left(\frac{1}{\sqrt{n}}\exp!\left(n\left[-p\ln p-(1-p)\ln(1-p)+p\ln 2\right]\right)\right). $$
Let
$$ \phi(p) = -p\ln p-(1-p)\ln(1-p)+p\ln 2. $$
Then
$$ \phi'(p) = -\ln p + \ln(1-p) + \ln 2. $$
The equation $\phi'(p)=0$ gives
$$ \ln!\left(\frac{2(1-p)}{p}\right)=0, $$
hence $2(1-p)=p$, so $p=\frac{2}{3}$.
At $p=\frac{2}{3}$,
$$ \phi!\left(\frac{2}{3}\right) = -\frac{2}{3}\ln\frac{2}{3}-\frac{1}{3}\ln\frac{1}{3}+\frac{2}{3}\ln 2 = \ln 3. $$
Therefore the maximal level satisfies
$$ \max_k \binom{n}{k}2^k = \Theta!\left(\frac{3^n}{\sqrt{n}}\right). $$
A sharper evaluation follows from the local central limit theorem applied to the multinomial distribution with probabilities $(1/3,2/3)$ for $(\text{unspecified},\text{specified})$. The peak probability is
$$ \Theta!\left(\frac{1}{\sqrt{n}}\right), $$
so
$$ b'(n) = \Theta!\left(\frac{3^n}{\sqrt{n}}\right). $$
Thus the exact formula and asymptotic value are
$$ b'(n)=\max_{0 \le k \le n} \binom{n}{k}2^k, \qquad b'(n)=\Theta!\left(\frac{3^n}{\sqrt{n}}\right). $$
Verification
For fixed $k$, every term in $\mathcal{T}_k$ contains exactly $k$ specified variables, so no two distinct elements of $\mathcal{T}_k$ satisfy inclusion of literal sets in either direction, which excludes implication between distinct elements of the same level.
If $T_1 \in \mathcal{T}_i$ and $T_2 \in \mathcal{T}_j$ with $i>j$, then $\operatorname{lit}(T_2) \subseteq \operatorname{lit}(T_1)$ holds for some pairs, since every literal of $T_2$ may be chosen among the $i$ specified positions of $T_1$. This identifies the partial order structure whose width is achieved by a single level.
The maximization of $\binom{n}{k}2^k$ is governed by $\phi(p)$, and the stationary point $p=2/3$ yields a strict global maximum since $\phi''(p)=-1/p-1/(1-p)<0$ for $0<p<1$. Hence the asymptotic concentration around $k=2n/3$ is valid.
This completes the proof. ∎
Notes
The structure ${0,1,*}^n$ with the implication order is the product of $n$ copies of a three-element chain with a fork at the top, and $b'(n)$ is its width. The maximizer at density $2/3$ reflects the fact that each coordinate contributes two refining choices versus one neutral choice, producing an entropy balance governed by $3^n$.