Show that every formula of Propositional Logic has the same number of left and right parentheses

Question

Show that every formula of Propositional Logic has the same number of left parentheses as it has of right parentheses. I have the answer, but I have failed to understand it.

Answer 1

First you need to have the definition of "formula of Propositional Logic". Without that, you can't prove anything about formulas of propositional logic. I'll suppose that the definition looks like this:

1. Atoms are formulas of propositional logic.
2. If $\Phi$ is a formula of propositional logic, then so is the formula you get by putting ‘$\lnot$’ in front of $\Phi$.
3. If $\Phi$ and $\Psi$ are formulas of propositional logic, then so is the formula you get by assembling ‘$($’, then $\Phi$, then ‘$\lor$’, then $\Psi$, and finally ‘$)$’
4. Nothing else is a formula of propositional logic

I left out the $\land$ and $\to$ operators, but the idea is the same with or without them.

Now consider the thing you want to prove: Every formula has the same number of ‘$($’ and ‘$)$’ signs. Just to save space and words, let's say that a formula that has the same number of left as right parentheses is “good” and a formula with different numbers of left than right parentheses is “bad”. We want to prove that all formulas are “good”.

Let's suppose there are bad formulas, and see where this leads us.

Among the bad formulas, there would have to be a shortest one, or at least one that is no longer than any other. This is the crucial point: if there are any counterexamples to the theorem we want to prove, then there must be one that is the shortest. Let's call this shortest bad formula $S$, for ‘shortest’. Then $S$ has two properties:

1. $S$ is a bad formula.
2. Any formula that is shorter than $S$ is good.

Point 2 there is very important, and you should pause to make sure you understand why it is true.

Since $S$ is a formula of propositional logic, it must fall under clause 1, 2, or 3 of the definition above. Let's look at clause 1. Is $S$ an atom? Certainly not, because atoms have no parentheses at all, so they have an equal number of left and right parentheses, namely zero of each. Every atomic formula is good. So $S$, which is bad, can't possibly be an atom.

Is $S$ produced according to clause 2, by putting ‘$\lnot$’ in front of some other formula? No, it can't be. Why not? What would that other formula be? Suppose it was $\Phi$. Since $S$ is just $\Phi$ with $\lnot$ in front, $\Phi$ is shorter than $S$, and so $\Phi$ is good. But putting $\lnot$ in front of $\Phi$ doesn't change the number of parentheses, so if $\Phi$ is good then $S$ would be good also. If $S$ is the shortest bad formula, it can't have the form $\lnot\Phi$.

Is $S$, the shortest bad formula, produced by clause 3? If so, it must be constructed from two formulas $\Phi$ and $\Psi$, by putting them together with ‘$($’, ‘$\lor$’, and ‘$)$’. $S$ is the shortest bad formula, and $\Phi$ and $\Psi$ are each certainly shorter than $S$, so both of them are good. $\Phi$ has some number of left parentheses, and some number of right parentheses, and these are equal, so let's call that number $m$. Similarly $\Psi$ has some number of left parentheses, and some number of right parentheses, and these are equal, so let's call that number $n$. But then $S$ has $m+n+1$ left parentheses—$m$ from $\Phi$, $n$ from $\Psi$, plus the extra one on the front—and similarly $m+n+1$ right parentheses—$m$ from $\Phi$, $n$ from $\Psi$, plus the extra one on the back—so if $S$ is constructed according to clause 3, it must be good. But $S$ is the shortest bad formula. But there is no way to make a bad formula from two good ones by clause 3. So $S$ was not made by clause 3.

We started this whole line of thought with “Let's suppose there are bad formulas, and see where this leads us”, and this supposition seems to be in trouble. If there are bad formulas, there must be a shortest bad formula, $S$, but we have seen there is no way that $S$ could have been made from shorter good formulas. But clause 4 says that every formula is made by clause 1, 2, or 3. So the supposition is wrong, and there are no bad formulas. This was what we were trying to prove.

I hope this helps you understand how the proof works.

Answer 2

The basic idea for the proof (for a richer language language) is also given at http://plato.stanford.edu/entries/logic-classical/ [See under "Compound Formulas"]

However, the OP writes "I have the answer, but I have failed to understand it." Which suggests that what is really needed here is a tutorial on proofs by induction. [After all, it isn't much help being told that the proof is by induction if you don't understand induction! While if you do know about induction, then you need to say why you don't understand this very easy inductive proof!]

For for more on induction (both induction in general and induction over the complexity of formulas in particular) see

• the first two pages of http://www.math.utah.edu/mathcircle/notes/induction.pdf
• then the very clear http://ruccs.rutgers.edu/~logic/mathInduction.pdf

You could also look at the set of exercises on induction and the answers to them, covering this very question, which you can find here: http://www.logicmatters.net/igt/exercises/

Answer 3

By induction; but of course you need to follow exactly the formal specifications contained in the rules for formulas' building.

Assuming that your language is the "usual" one, you will have that formulas are :

$(\lnot p)$ or $(p \land q)$, etc.

The rules will be applied adding a couple left-right each time (and always with the left parentheses to the left of the right one !); so, you will never found a "lost" one.

For an exhaustive treatment, see Herbert Enderton, A Mathematical Introduction to Logic (2nd ed Harcourt - 2001), Section 1.1: The Language of Sentential Logic.

There you can find [page 16] the definition of well-formed formula and the useful notions of formation tree and construction sequence [page 17].

Then follows the proof [page 18] of the

Induction Principle. If $S$ is a set of wffs [well-formed formulas] containing all the sentence symbols and closed under all five formula-building operations [the connectives], then $S$ is the set of all wffs.

This principle is used in the following example :

Any expression with more left parentheses than right parentheses is not a wff.

This is the proof [page 19] :

The idea is that we start with sentence symbols (having zero left parentheses and zero right parentheses), and then apply formula-building operations which add parentheses only in matched pairs.

We can rephrase this argument as follows: the set of "balanced" wffs (having equal numbers of left and right parentheses) contains all sentence symbols and is closed under the formula-building operations. The induction principle then assures us that all wffs are balanced.