TAOCP 7.1.2 Exercise 10

Exercise 10. ▶ [20] Modify Algorithm L so that it computes $D(f)$ instead of $L(f)$.

Verified: no
Solve time: 6m28s

We restart from a clean separation between syntactic formula depth and the algorithm’s labels, removing all circular use of the computed function $D$.

Corrected Solution

1. Formal notion of depth

A Boolean formula is built from:

variables $x_1,\dots,x_n$,
constants $0,1$,
unary connective $\neg$,
binary connectives $\land,\lor,\oplus$.

The depth of a formula $F$, written $\operatorname{depth}(F)$, is defined syntactically by:

$\operatorname{depth}(x_i)=0$, $\operatorname{depth}(0)=\operatorname{depth}(1)=0$,
$\operatorname{depth}(\neg G)=\operatorname{depth}(G)+1$,
$\operatorname{depth}(G \circ H)=1+\max(\operatorname{depth}(G),\operatorname{depth}(H))$, for $\circ\in{\land,\lor,\oplus}$.

For a Boolean function $f$, define

$$ D^*(f)=\min{\operatorname{depth}(F): F \text{ computes } f}. $$

The goal is to compute $D^*(f)$ for all $f$.

2. Modified Algorithm L (Algorithm D)

We maintain sets $L_r$: the set of Boolean functions whose minimal known depth is $r$.

We also maintain a table $D(f)$, initially undefined.

D0. Initialization

Set:

$L_0$ contains all variables $x_i$, constants $0,1$, and all projections they immediately define.
For each such basic function $f$, set $D(f)=0$.

D1. Unary closure (negation)

For each $g \in L_r$, form $\neg g$ and assign:

$$ D(\neg g) = r+1, \quad \text{place } \neg g \in L_{r+1}. $$

(If already assigned, keep the minimum value.)

D2. Binary construction

For all $i,j \le r$, for all $g \in L_i$, $h \in L_j$, and each $\circ \in {\land,\lor,\oplus}$, form:

$$ f = g \circ h. $$

Let

$$ d = 1 + \max(i,j). $$

If $D(f)$ is undefined or $d < D(f)$, set

$$ D(f)=d,\quad f \in L_d. $$

D3. Iteration

Repeat D1 and D2 for $r=0,1,2,\dots$ until no new functions are added.

Since there are finitely many Boolean functions, the process stabilizes.

3. Correctness proof

We prove that for every Boolean function $f$,

$$ D(f)=D^*(f). $$

Lemma 1 (Soundness)

If $f$ is assigned value $D(f)=r$, then there exists a formula computing $f$ of depth $r$.

Proof.

We argue by construction.

If $f\in L_0$, it is a variable or constant, hence has a depth-0 formula.
If $f=\neg g$ and $g\in L_r$, then by construction $f$ is computed by $\neg F_g$, increasing depth by 1, hence depth $r+1$.
If $f=g\circ h$ with $g\in L_i$, $h\in L_j$, then by induction $g,h$ have formulas of depths $i,j$, so $f$ has a formula of depth $1+\max(i,j)=D(f)$.

Thus every assigned value is achievable by a formula of that depth. ∎

Lemma 2 (No premature assignment)

If $D(f)=r$, then there is no formula for $f$ of depth $<r$.

Proof.

Assume $f$ has a formula $F$ of depth $t<r$.

We prove by induction on the structure of $F$ that the algorithm assigns $f$ a value $\le t$.

If $F$ is a variable or constant, then $t=0$ and $D(f)=0$.
If $F=\neg G$, then $\operatorname{depth}(G)=t-1$. By induction, $D(G)=t-1$, so the algorithm assigns $D(f)=t$.
If $F=G\circ H$, then

$$ t=1+\max(\operatorname{depth}(G),\operatorname{depth}(H)). $$

By induction, $D(G)=\operatorname{depth}(G)$ and $D(H)=\operatorname{depth}(H)$, so the algorithm forms $f$ at stage $t$.

Hence the algorithm would assign $f$ at depth at most $t$, contradicting $D(f)=r>t$. ∎

Lemma 3 (Completeness and exactness)

If $D^*(f)=r$, then the algorithm assigns $D(f)=r$.

Proof.

Let $F$ be a minimal-depth formula for $f$, with $\operatorname{depth}(F)=r$.

We proceed by structural induction on $F$.

If $F$ is a variable or constant, then $r=0$, and the algorithm assigns $D(f)=0$.
If $F=\neg G$, then $\operatorname{depth}(G)=r-1$. By induction, $D(G)=r-1$, and the unary step assigns $D(f)=r$.
If $F=G\circ H$, then

$$ r=1+\max(\operatorname{depth}(G),\operatorname{depth}(H)). $$

By induction, $D(G)=\operatorname{depth}(G)$ and $D(H)=\operatorname{depth}(H)$. The binary step constructs $f$ at depth $r$, so $D(f)\le r$. Lemma 2 rules out $D(f)<r$, hence $D(f)=r$.

Thus every function of minimal depth $r$ is assigned exactly $r$. ∎

4. Conclusion

From Lemmas 1–3, for every Boolean function $f$,

$$ D(f)=D^*(f), $$

so the modified Algorithm L correctly computes minimal formula depth.

The essential correction is the strict separation between:

syntactic depth $D^*(f)$, defined on formula trees,
algorithmic labels $D(f)$, justified only after induction.

This removes circular reasoning and ensures correctness by structural induction on formulas rather than on already-defined values.