Take the 2-minute tour ×
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.

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.

share|improve this question

1 Answer 1

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

 
discard

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.