TAOCP 7.1.4 Exercise 186
In a ZDD, each level corresponds to a variable, and a node labeled $k$ represents a decision on $x_k$, where the low edge excludes the variable and the high edge includes it in the represented family...
Section 7.1.4: Binary Decision Diagrams
Exercise 186. [10] [10] What Boolean function of {x1, x2, x3, x4, x5, x6} has the ZDD ‘ ⊥ ⊤ 3 ’?
Verified: no
Solve time: 1m46s
In a ZDD, each level corresponds to a variable, and a node labeled $k$ represents a decision on $x_k$, where the low edge excludes the variable and the high edge includes it in the represented family of sets. The sink $\perp$ represents the empty family, while $\top$ represents the family containing only the empty set.
The ZDD shown is a single node labeled $x_3$ whose low edge goes to $\perp$ and high edge goes to $\top$. This means that when $x_3=0$, no subset is accepted, and when $x_3=1$, the only accepted subset is the empty continuation after choosing $x_3$.
Thus the represented family consists of exactly one set: ${3}$. All other variables $x_1,x_2,x_4,x_5,x_6$ do not appear in any node, so they must be forced to $0$ in every satisfying assignment.
Therefore the Boolean function is the indicator of the single assignment in which $x_3=1$ and all other variables are $0$:
$$ f(x_1,x_2,x_3,x_4,x_5,x_6) = x_3 \cdot \overline{x_1},\overline{x_2},\overline{x_4},\overline{x_5},\overline{x_6}. $$
Equivalently, it is the characteristic function of the singleton set ${{3}}$ in subset representation.