TAOCP 7.1.4 Exercise 87
The median operator $\langle fgh\rangle$ is the Boolean function that is $1$ exactly when at least two of its arguments are $1$, and $0$ otherwise.
Section 7.1.4: Binary Decision Diagrams
Exercise 87. [20] [20] If the median operator ⟨fgh⟩is implemented with a recursive subroutine analogous to (62), what are its “obvious” values?
Verified: no
Solve time: 4m36s
Solution
The median operator $\langle fgh\rangle$ is the Boolean function that is $1$ exactly when at least two of its arguments are $1$, and $0$ otherwise. In a BDD-based recursive implementation analogous to (62), the operator is evaluated by decomposing with respect to the top variable ordering and combining cofactors.
Let $f_0,f_1,g_0,g_1,h_0,h_1$ denote the cofactors of $f,g,h$ with respect to the current variable $x_k$ at the root of the recursive call, as in the construction of (62). The median function satisfies the Shannon-style decomposition
$$ \langle fgh\rangle = x_k \ ?\ \langle f_1 g_1 h_1\rangle : \langle f_0 g_0 h_0\rangle $$
only when all three arguments depend identically on $x_k$, since the median operator is not linear in its arguments. In general the correct decomposition is obtained by evaluating the operator pointwise on the Boolean values of $x_k$.
At the terminal level, the recursion reaches sink arguments where each of $f,g,h$ is either $\bot$ or $\top$. The median operator on constants is completely determined by the truth table of majority on three bits:
$$ \langle 0,0,0\rangle = 0,\quad \langle 1,1,1\rangle = 1, $$
and all mixed cases reduce to comparison of the number of $\top$ inputs.
The “obvious” values are therefore the inputs for which no further recursion or memoized BDD construction is required because the result is fixed by constant evaluation at sinks. These occur exactly when at least one of $f,g,h$ is a sink triple that forces the outcome regardless of the remaining arguments.
If two of the arguments are identical BDD nodes, say $f=g$, then
$$ \langle f f h\rangle = f, $$
since the median of a duplicated value and any third value is always the duplicated value; this follows directly from the definition of majority since either both copies of $f$ are $0$ or both are $1$, forcing the majority vote.
If one argument is $\bot$, say $f=\bot$, then the operator reduces to
$$ \langle \bot g h\rangle = g \wedge h, $$
because at least two inputs are $1$ only when both $g$ and $h$ are $1$. Symmetrically,
$$ \langle \top g h\rangle = g \vee h, $$
because at least two inputs are $1$ whenever at least one of $g$ or $h$ is $1$ together with the fixed $\top$.
These reductions terminate the recursion immediately in each case since the result is expressible without further decomposition of $g$ and $h$.
Thus the “obvious” values in the recursive implementation of $\langle fgh\rangle$ are precisely the sink-induced identities
$$ \langle \bot g h\rangle = g \wedge h,\qquad \langle \top g h\rangle = g \vee h,\qquad \langle f f h\rangle = f, $$
together with the fully constant evaluations of $\langle \bot \bot \bot\rangle$ and $\langle \top \top \top\rangle$. This completes the determination of all base cases needed for a correct BDD recursion. ∎