= Solution
Proceed by <structural induction> on a Boolean formula $F$. A leaf computes $x_i$ or $\neg x_i$, so its measure is $1$, equal to its leaf count. If the root is an AND gate with subformulae computing $g,h$, then
$$
\mu(g\wedge h)\leq\mu(g)+\mu(h)
$$
by property 2; the induction hypothesis bounds this by the sum of the two subformula sizes, which is the size of $F$. Property 3 gives the identical argument for an OR gate. Consequently every formula computing $f$ has size at least $\mu(f)$, so $\mu(f)$ is a formula-size lower bound.
Back to article page
