TAOCP 7.1.1 Exercise 24
Let $A_k(x_1,\dots,x_{2^k})$ denote the Boolean function defined by a complete binary tree of height $k$ (with $2^k$ leaves), where the root is labeled $\wedge$ and levels alternate between $\wedge$ a...
Exercise 24. [M30] [M30] Consider the complete binary tree with $2^k$ leaves, illustrated here for $k = 3$. Operate alternately with $\wedge$ or $\vee$ on each level, using $\wedge$ at the root, obtaining for example $((x_1\wedge x_2)\vee(x_3\wedge x_4))\wedge((x_5\wedge x_6)\vee(x_7\wedge x_8))$. How many prime implicants does the resulting function contain?
Verified: yes
Solve time: 1m31s
Setup
Let $A_k(x_1,\dots,x_{2^k})$ denote the Boolean function defined by a complete binary tree of height $k$ (with $2^k$ leaves), where the root is labeled $\wedge$ and levels alternate between $\wedge$ and $\vee$ downwards.
For $k=0$, set $A_0(x_1)=x_1$.
Define also the complementary family $O_k$ by letting $O_k$ be the same construction but with root labeled $\vee$.
The tree structure yields the decompositions
$$ A_k ;=; O_{k-1}(x_1,\dots,x_{2^{k-1}})\ \wedge\ O_{k-1}(x_{2^{k-1}+1},\dots,x_{2^k}), $$
$$ O_k ;=; A_{k-1}(x_1,\dots,x_{2^{k-1}})\ \vee\ A_{k-1}(x_{2^{k-1}+1},\dots,x_{2^k}), $$
for $k\ge 1$.
Let $a_k$ be the number of prime implicants of $A_k$, and let $o_k$ be the number of prime implicants of $O_k$.
The goal is to determine $a_k$.
A prime implicant of a monotone function is a minimal set of variables whose assignment $x_i=1$ forces the function value $1$.
Solution
The functions $A_k$ and $O_k$ are monotone, since they are constructed using only $\wedge$ and $\vee$. Therefore each prime implicant corresponds uniquely to a minimal choice of subsolutions in the defining tree.
Consider $A_k = O_{k-1}^{(L)} \wedge O_{k-1}^{(R)}$, where $L$ and $R$ denote the left and right sets of variables. A prime implicant of $A_k$ must contain a prime implicant of $O_{k-1}^{(L)}$ and independently a prime implicant of $O_{k-1}^{(R)}$, since both factors of the conjunction must evaluate to $1$. Minimality forces no additional variables.
Conversely, the union of a prime implicant of $O_{k-1}^{(L)}$ with a prime implicant of $O_{k-1}^{(R)}$ yields a minimal satisfying assignment for $A_k$, since removing any variable destroys one of the two required subconditions.
The variables of the two subtrees are disjoint, so every ordered pair of prime implicants contributes a distinct prime implicant of $A_k$. Hence
$$ a_k ;=; (o_{k-1})^2. $$
Now consider $O_k = A_{k-1}^{(L)} \vee A_{k-1}^{(R)}$. A satisfying assignment for $O_k$ requires at least one of the two subfunctions to be $1$. Minimality excludes assignments that satisfy both sides simultaneously, since any variable in the second satisfied side would then be removable while preserving truth.
Thus every prime implicant of $O_k$ is obtained by choosing exactly one side and then choosing a prime implicant of that side. The two sides are disjoint, so no duplication occurs. Hence
$$ o_k ;=; a_{k-1} + a_{k-1} ;=; 2a_{k-1}. $$
The initial values are $a_0=1$ and $o_0=1$, since each corresponds to a single variable.
Substituting $o_{k-1}=2a_{k-2}$ into $a_k=(o_{k-1})^2$ gives
$$ a_k ;=; (2a_{k-2})^2 ;=; 4a_{k-2}^2. $$
Define $b_k = \log_2 a_k$. Then
$$ b_k = 2 + 2b_{k-2}. $$
With $b_0=0$ and $b_1=0$, iteration yields
$$ b_2=2,\quad b_3=2,\quad b_4=6,\quad b_5=6,\quad b_6=14, $$
and the pattern separates by parity. For $k=2m$,
$$ b_{2m} = 2(2^m - 1), $$
verified by induction using $b_{2m}=2+2b_{2m-2}$ and the identity $2(2^m-1)=2+2(2(2^{m-1}-1))$.
For $k=2m+1$, the same recurrence with shift gives
$$ b_{2m+1} = 2(2^m - 1), $$
verified using $b_{2m+1}=2+2b_{2m-1}$ and the same closed form for $b_{2m-1}$.
Therefore, for all $k\ge 0$,
$$ a_k = 2^{,2(2^{\lfloor k/2\rfloor}-1)}. $$
Thus the number of prime implicants of the given Boolean function is
$$ \boxed{2^{,2(2^{\lfloor k/2\rfloor}-1)}}. $$
This completes the proof. ∎
Verification
Each step in the decomposition preserves disjointness of variable sets, so Cartesian products of implicants apply without interaction between subtrees. In the disjunction case, minimality excludes combining implicants from both sides since removing any variable from a double-sided assignment preserves truth in at least one subtree, contradicting primeness. The recurrence relations follow directly from these two structural constraints and the base cases $A_0(x)=x$, $O_0(x)=x$.
Notes
The alternating structure causes exponential squaring every two levels via $a_k=4a_{k-2}^2$, which produces a doubly exponential growth in the exponent of $2$. The dependence only on $\lfloor k/2\rfloor$ reflects that every pair of adjacent levels converts OR structure into AND structure and back without changing the effective branching count, only the aggregation rule applied at the root level.