TAOCP 7.1.2 Exercise 9
Algorithm L assigns to each normal Boolean function $f$ its minimum length $L(f)$ but does not retain any information about how the value $L(f)$ is achieved.
Section 7.1.2: Boolean Evaluation
Exercise 9. [20] Algorithm L determines the lengths of shortest formulas for all functions $f$, but it gives no further information. Extend the algorithm so that it also provides actual minimum-length formulas like (6).
Verified: yes
Solve time: 2m05s
Solution
Algorithm L assigns to each normal Boolean function $f$ its minimum length $L(f)$ but does not retain any information about how the value $L(f)$ is achieved. To recover actual minimum-length formulas, the construction of $L(f)$ must be augmented so that every newly discovered function is accompanied by a witness decomposition into a binary operator applied to previously constructed functions.
For each normal function $f$, introduce auxiliary storage consisting of a record
$\operatorname{par}(f) = (\circ_f, g_f, h_f, \epsilon_f, \delta_f),$
where $\circ_f$ is one of the five normal binary operators used in step L5, $g_f$ and $h_f$ are earlier functions, and $\epsilon_f, \delta_f \in {0,1}$ indicate whether the inputs are complemented in the sense of L5 (so $\epsilon_f = 1$ means $g$ is replaced by $\bar{g}$, and $\delta_f = 1$ means $h$ is replaced by $\bar{h}$). For initial variables $x_k$, the record $\operatorname{par}(x_k)$ is undefined.
The invariant maintained is that whenever $L(f) = r$, the stored record $\operatorname{par}(f)$ corresponds to a decomposition
$f = g_f^{(\epsilon_f)} \circ_f h_f^{(\delta_f)},$
where $g_f^{(0)} = g_f$ and $g_f^{(1)} = \bar{g}_f$, and similarly for $h_f$, with $L(g_f) + L(h_f) + 1 = r$.
Algorithm L is modified only at step L6, where new functions are first assigned their length.
In step L5, each candidate construction already determines the data needed for reconstruction. When computing a candidate value
$f = g \circ h,$
or any of the variants involving complemented arguments listed in L5, the algorithm passes along the corresponding operator $\circ$ and the flags indicating whether $g$ and $h$ were complemented in that computation.
Step L6 is replaced by the following augmented version.
L6'. [Is $f$ new?] If $L(f) = \infty$, set $L(f) \leftarrow c - 1$, $c \leftarrow c - 1$, and place $f$ in list $r$. Store also
$\operatorname{par}(f) \leftarrow (\circ, g, h, \epsilon, \delta),$
where $(\circ, g, h, \epsilon, \delta)$ are the data used in the current invocation of step L5 that produced $f$. Terminate the algorithm if $c = 0$.
This modification ensures that every function receives exactly one parent record at the moment its optimal length is first discovered.
To extract a minimum-length formula for any function $f$, define a recursive reconstruction procedure $\Phi(f)$ as follows. If $f$ is one of the initial variables $x_k$, then $\Phi(f) = x_k$. If $f$ is not an initial variable, then $\operatorname{par}(f) = (\circ, g, h, \epsilon, \delta)$ and the formula for $f$ is obtained by substituting recursively:
$\Phi(f) = \Phi(g^{(\epsilon)}) \circ \Phi(h^{(\delta)}),$
where $g^{(\epsilon)} = \bar{g}$ if $\epsilon = 1$ and $g$ otherwise, and similarly for $h^{(\delta)}$.
The correctness of the construction follows from the invariant of L6'. Each function is created only once at the moment its minimal length is certified, so the stored decomposition always corresponds to a chain of length exactly $L(f)$, and recursive expansion replaces each stored node by the binary operation that created it without altering the number of operators.
Thus $\Phi(f)$ is a formula with exactly $L(f)$ binary operators, and no formula with fewer operators can exist, since any such formula would contradict the minimality condition used in step L6'.
This completes the proof. ∎