2

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.

Mathmo
  • 4,883

2 Answers2

2

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.

Hagen von Eitzen
  • 374,180
  • 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
0

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!

Juergen Franz
  • 1
  • 1