Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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.

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.