= Solution
Apply <structural induction> to the formation of a <propositional formula>. Let $L(\theta)$ and $R(\theta)$ count its opening and closing parentheses, and use the usual grammar generated by propositional variables, any allowed truth constants, <negation>, and parenthesized binary <logical connectives>.
An atomic variable or truth constant contains neither kind of parenthesis, so $L=R=0$. If $L(\alpha)=R(\alpha)$, prefixing <negation> leaves both counts unchanged. If the notation writes a negated formula with an extra pair of parentheses, it adds one to each and still preserves equality.
For a binary construction $(\alpha\circ\beta)$, where $\circ$ is an allowed binary <logical connective>,
$$
L((\alpha\circ\beta))=L(\alpha)+L(\beta)+1,
\qquad R((\alpha\circ\beta))=R(\alpha)+R(\beta)+1.
$$
The two induction hypotheses make these equal. Every grammar construction preserves the property, so \b[every <propositional formula> contains equally many left and right parentheses]. This is <balanced parentheses in propositional syntax>.
Back to article page
