 Proof: We proceed by induction on the complexity of the formula or, in other words, on the number of formation rules that are applied. The Lemma clearly holds for atomic formulas. Let \(n\) be a natural number, and suppose that the Lemma holds for any formula constructed from \(n\) or fewer instances of clauses (2)–(7). Let \(\theta\) be a formula constructed from \(n+1\) instances. The Lemma holds if the last clause used to construct \(\theta\) was either (3), (4), or (5). If the last clause used to construct \(\theta\) was (2), then \(\theta\) is \(\neg \psi\). Since \(\psi\) was constructed with \(n\) instances of the rule, the Lemma holds for \(\psi\) (by the induction hypothesis), and so it holds for \(\theta\). Similar reasoning shows the Lemma to hold for \(\theta\) if the last clause was (6) or (7). By clause (8), this exhausts the cases, and so the Lemma holds for \(\theta\), by induction.