Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 124 / 5 / ii / 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$, thenby 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.