Length of a formula in propositional logic I've seen the following problem on a past exam question:
Show that the length of a formula in $\mathscr{L}$ is equal to $4m+n+1$, where $m$ is the number of binary connectives and $n$ is the number of negation symbols in the formula
Thoughts
There are quite a few cases to consider, but the $n=m=0$ and $m=0\neq n$ cases are simple. So we are left to deal with the $n,m \neq 0$ case.
I think the key thing is realise that formulas are composed of strings of the type 
$$(p \star q)$$ for a binary connective $\star$ and formulas $p$ and $q$. We can of course throw a negation sign in front of this, but these 'substrings' of the formula seem to be key to cracking this to me, for each gives rise to $5$ symbols, although potentially $p$ or $q$ will itself by a $5$-long string embedded in the formula.
I really can't see how this general rule can be proved though. Perhaps an inductive approach is best? A solution to this problem would be very interesting to me.
 A: Use structural induction.
Use that a formula $\alpha$ is either of the form 


*

*$p$ or any other (atomic) variable

*$\neg \beta$ where $\alpha$ is a formula or

*$(\gamma\star \beta)$ where $\gamma,\beta$ are formulas and $\star$ is a binary connective.


The numbers $n(\alpha)$, $m(\alpha)$ and length $L(\alpha)$ obey the recursions


*

*$n(\alpha)=m(\alpha)=0$, $L(\alpha)=1$ if $\alpha=p$

*$n(\alpha)=n(\beta)+1$, $m(\alpha)=m(\beta)$, $L(\alpha)=L(\beta)+1$

*$n(\alpha)=n(\beta)+n(\gamma)$, $m(\alpha)=m(\beta)+m(\gamma)+1$, $L(\alpha)=L(\beta)+L(\gamma)+4$


in the respective cases.
A: I think this solution is not by the means of structural induction. I would love to learn about structural induction, please comment!
I can't think of a way to develop a complete proof of the proposition in a single step, so I would divide the question in two.
(I) Let $\alpha = \neg\gamma$, so $L(\alpha)= L(\gamma)+1$. This is part of the definition of the "length" of a logical proposition. For every negation in $\alpha$, we shall add 1 to $L(\alpha)$. So we say $L(\beta)$ is $L(\alpha) - n_\alpha$ where $n_\alpha$ is number of negation operators in $\alpha$. $L(\alpha)$ is thus $L(\beta) + n_\alpha$.
We now have this first part of the proposition. For every formula $\alpha$: $L(\alpha) = L(\beta) + n_\alpha$
(II) $L(\beta) = 4m+1$
To prove this: let $\beta_m $ be a proposition with $m$ binary connectives and no negations. $L(\beta_m) = 4m+1$ is quickly proved for $m \in \{0,1\}$. We assume this to be true for all $m \in \mathbb{N}$, our induction hypothesis.
$L(\beta_{m+1}) = L(\beta_m) + L(\beta_1) - L(\beta_0)$
I assume one can use this because the length of a proposition is defined as a series of additions. If we want to add a binary connective to $\gamma$, we have $\gamma * \alpha$ where alpha must be of the form $\neg\beta$ or must be an atom. We don't have negations in this case, so it must be an atom. Otherwise, we would need to add another binary connective to turn $\alpha$ into a formula.
So, we know that $L(\beta_m)$ may be an atom or a formula. To get to $L(\beta_{m+1})$, we need to add 3 for the binary connective and 1 for the atom. This is the difference from the length of $\beta_1$ to $\beta_0$, which is 4.
$L(\beta_{m+1}) = L(\beta_m) + 4$
With our induction hypothesis, we get:
$L(\beta_{m+1}) = 4m+1 + 4= 4m + 4 +1 = 4(m+1) +1$ q.e.d.
To wrap it up, (II) gives us the length of $\alpha$ without the negations, (I) gives us the length of the negations. To have $L(\alpha)$ including both, we need to add them up:
$L(\alpha) = 4m_\alpha + n_\alpha +1$
Hope this helps!
