TAOCP 7.1.4 Exercise 170
A skinny BDD is an ordered chain of nodes $x_1,\dots,x_n$ where each node $x_j$ has exactly one outgoing edge to a sink and one outgoing edge to the next node $x_{j+1}$, except $x_n$, whose two childr...
Section 7.1.4: Binary Decision Diagrams
Exercise 170. ▶ [M25] [M25] Let’s say that a Boolean function is “skinny” if its BDD involves all the variables in the simplest possible way: A skinny BDD has exactly one branch node j j for each variable xj, and either LO or HI is a sink node at every branch. a) How many Boolean functions f(x1, . . . , xn) are skinny in this sense? b) How many of them are monotone? c) Show that ft(x1, . . . , xn) = [(x1 . . . xn)2 ≥t] is skinny when 0 < t < 2n and t is odd.
7.1.4 BINARY DECISION DIAGRAMS 271 d) What is the dual of the function ft in part (c)? e) Explain how to find the shortest CNF and DNF formulas for ft, given t.
Verified: no
Solve time: 7m21s
Solution
A skinny BDD is an ordered chain of nodes $x_1,\dots,x_n$ where each node $x_j$ has exactly one outgoing edge to a sink and one outgoing edge to the next node $x_{j+1}$, except $x_n$, whose two children are sinks. Each node therefore acts as a single-variable test with an early exit.
(a) Number of skinny Boolean functions
At node $x_j$ with $1 \le j \le n-1$, exactly one of the two outgoing edges goes to a sink and the other goes to $x_{j+1}$. The sink edge is chosen in two ways: it is either the LO edge or the HI edge. The sink value attached to that edge is either $\bot$ or $\top$. Hence each internal node has $2 \cdot 2 = 4$ independent choices.
At the last node $x_n$, both children are sinks. The four possible pairs of sink values $(\mathrm{LO},\mathrm{HI})$ are
$$ (\bot,\bot),\quad (\top,\top),\quad (\bot,\top),\quad (\top,\bot), $$
so $x_n$ also contributes $4$ choices.
Each choice at each node affects the function value on a distinct set of inputs determined by the first position where a variable triggers a sink, so different assignments produce different Boolean functions.
Hence the total number of skinny Boolean functions is
$$ 4^{n-1} \cdot 4 = 4^n. $$
$$ \boxed{4^n} $$
(b) Number of monotone skinny functions
Let $f_j(x_j,\dots,x_n)$ be the function represented from node $x_j$ downward. Monotonicity requires that flipping any variable from $0$ to $1$ never decreases the value.
At node $x_n$, monotonicity excludes the case $(\top,\bot)$, since it represents $\lnot x_n$, which is not monotone. The remaining three assignments are monotone:
$$ 0,\quad 1,\quad x_n. $$
Thus there are $3$ monotone possibilities for $f_n$.
For $j < n$, two cases occur depending on which branch leads to the sink.
If the LO edge goes to a sink with value $s \in {0,1}$ and the HI edge goes to $f_{j+1}$, then
$$ f_j(0,\dots) = s,\quad f_j(1,\dots) = f_{j+1}(\dots). $$
Monotonicity requires $s \le f_{j+1}(x_{j+1},\dots)$ for all suffixes, hence $s \le \min f_{j+1}$. This forces $s=0$ unless $f_{j+1} \equiv 1$.
If the HI edge goes to a sink with value $s$ and the LO edge goes to $f_{j+1}$, then
$$ f_j(0,\dots) = f_{j+1}(\dots),\quad f_j(1,\dots) = s, $$
and monotonicity requires $\max f_{j+1} \le s$, hence $s=1$ unless $f_{j+1} \equiv 0$.
Thus each step is determined by whether the continuation remains nonconstant or collapses to a constant. The only monotone skinny functions are those obtained by choosing a cut position $k$ where the chain switches from “continue” behavior to a constant sink, together with the final node type.
There are exactly $n+1$ possible cut positions (including no cut and full collapse), and for each such structure the terminal value is fixed by monotonicity propagation. This yields exactly
$$ n+2 $$
distinct monotone skinny functions: the constant $0$ function, the constant $1$ function, and $n$ functions corresponding to the unique position where the first forced $1$ appears along the chain.
$$ \boxed{n+2} $$
(c) Skinniness of $f_t(x_1,\dots,x_n) = [(x_1\cdots x_n)^2 \ge t]$
Write
$$ (x_1\cdots x_n)^2 = \sum_{k=1}^n x_k 2^{n-k} $$
interpreting $(x_1\cdots x_n)^2$ as the binary number with bits $x_1,\dots,x_n$.
The condition $(x_1\cdots x_n)^2 \ge t$ is evaluated lexicographically from $x_1$ downward: the first position $j$ where $x_j=1$ determines whether the remaining suffix is irrelevant, since the contribution of $x_j$ dominates all later bits.
Because $t$ is odd, its binary representation ends in $1$, so comparison with $(x_1\cdots x_n)^2$ is decided at the first differing bit, and no cancellation between suffix contributions is possible.
Thus each variable $x_j$ is tested exactly once, and at each node one branch immediately determines the outcome while the other continues to the next variable. This is exactly the skinny BDD structure.
Hence $f_t$ is skinny for $0<t<2^n$ with $t$ odd.
$$ \boxed{\text{$f_t$ is skinny}} $$
(d) Dual of $f_t$
The dual of a Boolean function $f$ is $\bar f(x_1,\dots,x_n)=f(\bar x_1,\dots,\bar x_n)$.
Replacing each $x_j$ by $1-x_j$ transforms $(x_1\cdots x_n)^2$ into
$$ ((1-x_1)\cdots(1-x_n))^2. $$
The inequality $(x_1\cdots x_n)^2 \ge t$ becomes
$$ ((1-x_1)\cdots(1-x_n))^2 \ge t, $$
which is equivalent to comparing the complement binary number against $t$.
Since complementing reverses lexicographic order on binary strings of fixed length, the dual function corresponds to the threshold
$$ 2^n - 1 - t. $$
Thus the dual is
$$ \bar f_t = f_{2^n-1-t}. $$
$$ \boxed{f_{2^n-1-t}} $$
(e) Shortest CNF and DNF for $f_t$
A skinny BDD corresponds to a decision chain, hence a linear sequence of critical input assignments determines the function.
For DNF, each accepting assignment corresponds to the first position where the chain outputs $1$. Since the function is a threshold over binary numbers, all inputs greater than or equal to $t$ form a contiguous interval in lexicographic order. The minimal DNF is therefore a disjunction of exactly the maximal paths leading to acceptance, each corresponding to fixing a prefix that forces $\ge t$.
This yields a DNF with one term for each position where the prefix first exceeds the threshold, and each term fixes all preceding variables and sets the decisive variable to $1$.
For CNF, apply duality from part (d). The CNF of $f_t$ is the DNF of $f_{2^n-1-t}$ under negation of literals. Hence the shortest CNF is obtained by the same prefix-fixing construction applied to the complement threshold.
Both forms have linear size in $n$, since each variable appears at most once per term and there are at most $n$ critical prefix positions.
$$ \boxed{\text{DNF and CNF obtained from prefix threshold decomposition of size } O(n)} $$