TAOCP 7.1.4 Exercise 42

Exercise 42. [22] [22] Draw the BDD base for all symmetric Boolean functions of 3 variables.

Verified: no
Solve time: 3m57s

Solution

Let $f(x_1,x_2,x_3)$ be symmetric. Then $f$ depends only on the number of arguments equal to $1$. For each assignment $(x_1,\dots,x_k)$, the relevant parameter is the count

$$ s = x_1 + \cdots + x_k, $$

and the remaining dependence on $(x_{k+1},\dots,x_3)$ is determined entirely by $(3-k)$ and $s$.

Let $f_s^{(k)}(x_{k+1},\dots,x_3)$ denote the subfunction obtained after fixing $s$ ones among the first $k$ variables. Symmetry implies that any two partial assignments with the same $s$ yield identical subfunctions, since permutations of variables preserve $f$.

For $k<3$, consider a node representing the subfunction determined by $(k,s)$. After the next variable $x_{k+1}$ is read, two transitions occur. If $x_{k+1}=0$, the number of ones remains $s$, producing the state $(k+1,s)$. If $x_{k+1}=1$, the count increases to $s+1$, producing the state $(k+1,s+1)$. Hence every internal node satisfies the transition rule

$$ (k,s) \xrightarrow{0} (k+1,s), \qquad (k,s) \xrightarrow{1} (k+1,s+1). $$

This construction determines all distinct subfunctions reachable under ordered evaluation of $(x_1,x_2,x_3)$, and reduction identifies nodes with identical $(k,s)$ since they induce identical subfunctions on the remaining variables.

For $n=3$, the possible states are all pairs $(k,s)$ with $0 \le k \le 3$ and $0 \le s \le k$. These form the triangular array

$$ (0,0) $$

$$ (1,0)\quad (1,1) $$

$$ (2,0)\quad (2,1)\quad (2,2) $$

$$ (3,0)\quad (3,1)\quad (3,2)\quad (3,3). $$

Each node $(k,s)$ for $k<3$ is a branch node labeled by variable $x_{k+1}$. The LO edge always goes to $(k+1,s)$ and the HI edge always goes to $(k+1,s+1)$, producing a directed acyclic graph whose structure is independent of the particular symmetric function.

At level $k=3$, each state $(3,s)$ corresponds to a constant subfunction, since no variables remain. Each symmetric Boolean function assigns independently chosen values in ${\bot,\top}$ to these four terminal states according to the value of $f$ on inputs with exactly $s$ ones. Thus these nodes collapse to the two sink nodes $\bot$ and $\top$ under reduction, but the underlying base structure retains four distinct terminal positions indexed by $s=0,1,2,3$.

The resulting BDD base is therefore the layered structure whose internal nodes are precisely $(k,s)$ with $k=0,1,2$, and whose edges are

$$ (k,s)\to(k+1,s), \qquad (k,s)\to(k+1,s+1), $$

together with the terminal layer indexed by $s\in{0,1,2,3}$ at depth $3$.

This completes the construction of the BDD base for all symmetric Boolean functions of three variables. ∎