WFF of PropLog is Balanced

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathbf A$ be a WFF of propositional logic.


Then $\mathbf A$ is a balanced string.


Proof

We will prove by strong induction on $n$ that:

All WFFs of length $n$ are balanced.


Let $l \left({\mathbf A}\right)$ denote the number of left brackets in a string $\mathbf A$.

Let $r \left({\mathbf A}\right)$ denote the number of right brackets in a string $\mathbf A$.


Induction Basis

The only WFFs of PropLog of Length 1‎ are letters of the alphabet and the symbols $\bot$ and $\top$.

By definition, none of these consist of brackets.


So every WFF $\mathbf A$ of length $1$ has $l \left({\mathbf A}\right) = r \left({\mathbf A}\right) = 0$.

So every WFF of length $1$ is balanced.

This provides the induction basis.


Induction Hypothesis

Now, suppose all WFFs of propositional logic of length at most $n$ are balanced.

This provides the induction hypothesis.


Induction Step

Let $\mathbf A$ be a WFF of propositional logic of length $n + 1$.


The following cases are to be considered (with $\mathbf B$ and $\mathbf C$ WFFs):

$\mathbf A = \neg \mathbf B$
$\mathbf A = \left({\mathbf B \circ \mathbf C}\right)$, where $\circ$ is one of the binary connectives


Suppose $\mathbf A = \neg \mathbf B$.

Then $\mathbf B$ is a WFF of length $n$.

By the induction hypothesis, it is hence balanced.

Since $\mathbf A$ contains the same brackets as $\mathbf B$, it must also be balanced.


Suppose now $\mathbf A = \left({\mathbf B \circ \mathbf C}\right)$, where $\circ$ is one of the binary connectives.

Then:

$l \left({\mathbf A}\right) = l \left({\mathbf B}\right) + l \left({\mathbf C}\right) + 1$
$r \left({\mathbf A}\right) = r \left({\mathbf B}\right) + r \left({\mathbf C}\right) + 1$.

Now, $\mathbf B$ and $\mathbf C$ are both of length strictly less than $n + 1$, and thus balanced, by the induction hypothesis.

That is:

$l \left({\mathbf B}\right) = r \left({\mathbf B}\right)$
$l \left({\mathbf C}\right) = r \left({\mathbf C}\right)$.

It follows that also:

$l \left({\mathbf A}\right) = r \left({\mathbf A}\right)$

which precisely states that $\mathbf A$ is balanced.


We assumed that all WFFs of length $n$ and less are balanced, and demonstrated that as a consequence all WFFs of length $n+1$ are balanced.

$\Box$


The result now follows by strong induction.

$\blacksquare$


Sources