# 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.

-

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.

-
I understand your recursions, but how can this be use in an inductive proof? I've never encountered 'structural induction' before... – Mathmo Oct 20 '13 at 22:07