TAOCP 7.1.4 Exercise 3

Exercise 3. [16] [16] How many Boolean functions f(x1, . . . , xn) have BDD size 3 or less?

Verified: no
Solve time: 2m47s

Solution

Let $f(x_1,x_2,\dots,x_n)$ be a Boolean function and let its BDD size $B(f)$ be the number of nodes in its reduced ordered BDD, including the sinks $\bot,\top$.

A BDD of size at most $3$ can contain only the two sinks and at most one branch node, since every branch node contributes at least one additional node beyond the sinks and no node can be duplicated in a reduced BDD.

Hence $B(f)\le 3$ implies that every non-sink function is represented by a single branch node, so the root is labeled by some variable $x_i$, and both outgoing edges from the root must go directly to sinks.

Thus every such function has the form

$$ f(x_1,\dots,x_n) = \begin{cases} c_0 & x_i = 0,\ c_1 & x_i = 1, \end{cases} $$

where $c_0,c_1 \in {0,1}$ and not both are equal, since otherwise the root would collapse to a sink and the BDD would have size $1$.

This produces exactly three nonconstant cases for each choice of variable $x_i$:

$$ (c_0,c_1) \in {(0,1),(1,0),(0,0),(1,1)} $$

but the last two pairs yield constant functions, already accounted for by size $1$, so only $(0,1)$ and $(1,0)$ correspond to size $3$.

These two functions are exactly

$$ f(x_1,\dots,x_n)=x_i, \qquad f(x_1,\dots,x_n)=\neg x_i. $$

There are $n$ choices of the variable $x_i$. For each choice there are exactly two functions of size $3$, namely projection and negation of that variable. These constructions are distinct since different choices of $i$ yield distinct truth tables.

The constant functions contribute size $1$ only and do not affect the count for size at most $3$.

Therefore the total number of Boolean functions with $B(f)\le 3$ equals the number of constant functions plus the number of single-variable projections and their negations:

$$ 2 + 2n. $$

Thus the number of Boolean functions $f(x_1,\dots,x_n)$ with BDD size $3$ or less is

\boxed{2n+2}. $$ ∎