I am kind of overwhelmed by this question. Can anyone give me some hints about where to start?
Propositional formulae PF are inductively defined over the Boolean constants B := {1, 0} (true and false), a finite set of propositional variables τ := {P, Q, . . .}, and the connectives {¬, ∧,∨, →}:
• B ⊆ PF
• τ ⊆ PF
• if φ∈PF, then also ¬φ∈PF
• if φ,ψ∈PF, then also φ◦ψ∈PF, for any◦∈{∧,∨,→}.
We define the depth d(φ) of a formula inductively:
• d(φ) = 0, if φ is a constant or a propositional variable,
• d(¬φ) = 1 + d(φ) in the case of a negated formula, and
• d(φ ◦ ψ) = 1 + max(d(φ), d(ψ)), for any of the binary connectives
Furthermore, let’s take the following inductive definition of the set of subformulae sf (φ):
• sf(b)={b}, for b∈B
• sf (P) = {P}, for P ∈ τ
• sf(¬φ)={¬φ} ∪ sf(φ), for φ∈PF
• sf(φ◦ψ) = {φ◦ψ} ∪ sf(φ) ∪ sf(ψ), for φ,ψ∈PF.
For example, the formula φ := P∧ ¬(Q∨R) has depth d(φ) = 3, its subformulae are:
sf(φ):={P,Q,R,(Q∨R),¬(Q∨R), P ∧ ¬(Q∨R)}.
Observe that we only use parentheses for clarity, they are not part of the inductive definition.
Show through induction that:
a) Formulae of depth n ≥ 1 have at most 2^(n+1) − 1 subformulae.
b) For each n ∈ N, there exist formulae with exactly 2^(n+1) − 1 subformulae
For a) :
assume that all formulae with depth $n$ have at most $2^{(n+1)} − 1$ subformulae, and prove it for depth $n+1$.
We have two cases :
(i) $\varphi$ is $\lnot \psi$ with $d(\psi)=n$ and $\psi$ has $2^{(n+1)} − 1$ subformulae. $\varphi$ has depth $n+1$ and one more subformula : $\lnot \psi$ itself.
Thus, $\varphi$ has : $2^{(n+1)} − 1 + 1 = 2^{(n+1)} \le 2^{[(n+1)+1]}-1$ subformulae.
(ii) $\varphi$ is $\psi_1 \circ \psi_2$ with $d(\psi_i)=n$ and $\psi_i$ with $2^{(n+1)} − 1$ subformulae. $\varphi$ has depth $n+1$ and all the subformulae of $\psi_1$ and $\psi_2$ plus one.
Thus, $\varphi$ has : $2^{(n+1)} − 1 + 2^{(n+1)} -1 + 1 = 2 \times 2^{(n+1)} -1 = 2^{[(n+1)+1]}-1$ subformulae.
For b) :
we have only to use the inductive definition of $PF$ :
$n=0 : P \in PF$ has $2^{(0+1)} − 1 = 2-1=1$ subformula
$n=1 : P \land Q \in PF$ has $2^{(1+1)} − 1 = 4-1=3$ subformulae
Assume that $\psi_1, \psi_2 \in PF$ have $2^{(n+1)} − 1$ subformulae each.
Then $\psi_1 \land \psi_2 \in PF$ has $2^{(n+1)} − 1 + 2^{(n+1)} -1 + 1 = 2 \times 2^{(n+1)} -1 = 2^{[(n+1)+1]}-1$ subformulae.