Question

Show that any well-formed formula in prefix notation over a set of symbols and a set of binary operators contains exactly one more symbol than the number of operators.

Short answer

Therefore, the given statement is true. We proved that any well-formed formula in prefix notation over a set of symbols and a set of binary operators contains exactly one more symbol than the number of operators is true.

Step-by-step solution

General form

Well-formed formulaein prefix notation over a set of symbols and a set of binary operators are defined recursively by these rules:

1. If x is a symbol, then x is a well-formed formula in prefix notation;
2. If X and Y are well-formed formulae and \( * \) is an operator, then \( * {\bf{XY}}\) is a well-formed formula.

Proof

To prove: any well-formed formula in prefix notation over a set of symbols and a set of binary operators contains exactly one more symbol than the number of operators.

Proof by mathematical induction.

Let S(X) and O(x) represent the number of symbols and the number of operators in the well-formed formula X, respectively.

Basis step:

Put n = 1.

Then the statement is true for well-formed formulae of length 1, because they have 1 symbol and 0 operators.

Let us assume that the statement is true for all well-formed formulae of length less than n.

Then, a well-formed formula of length n must be of the form \( * {\bf{XY}}\). Where \( * \) is an operator and X and Y are well-formed formulae of length less than n.

Let us use the inductive hypothesis.

\(\begin{array}{c}{\bf{S}}\left( { * {\bf{XY}}} \right){\bf{ = S}}\left( {\bf{X}} \right){\bf{ + S}}\left( {\bf{Y}} \right)\\{\bf{ = }}\left( {{\bf{O}}\left( {\bf{X}} \right){\bf{ + 1}}} \right){\bf{ + }}\left( {{\bf{O}}\left( {\bf{Y}} \right){\bf{ + 1}}} \right)\\{\bf{ = O}}\left( {\bf{X}} \right){\bf{ + O}}\left( {\bf{Y}} \right){\bf{ + 2}}\end{array}\)

Because \({\bf{O}}\left( { * {\bf{XY}}} \right){\bf{ = 1 + O}}\left( {\bf{X}} \right){\bf{ + O}}\left( {\bf{Y}} \right)\), it follows that \({\bf{S}}\left( { * {\bf{XY}}} \right){\bf{ = O}}\left( { * {\bf{XY}}} \right){\bf{ + 1}}\).

Hence proved.