Structural Induction, Propostitonal formulae problem

Question

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

Answer 1

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.