Question

Which of these are well-formed formulae over the symbols \(\left\{ {{\bf{x,y,z}}} \right\}\) and the set of binary operators \(\left\{ {{\bf{ \ast , + ,}} \circ } \right\}\)?

1. \({\bf{ \ast + + xyx}}\)
2. \( \circ {\bf{xy \ast xz}}\)
3. \({\bf{ \ast }} \circ {\bf{xz \ast \ast xy}}\)
4. \({\bf{ \ast + }} \circ {\bf{xx}} \circ {\bf{xxx}}\)

Short answer

1. Therefore, the given formula is not a well-formed formula.
2. Therefore, the given formula is not a well-formed formula.
3. Therefore, the given formula is not a well-formed formula.
4. Therefore, the given formula is a well-formed formula.

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.

Evaluate the given expressions are well-formed formulae or not.

Given that, the symbols \(\left\{ {{\bf{x,y,z}}} \right\}\) and the set of binary operators \(\left\{ {{\bf{ \ast , + ,}} \circ } \right\}\).

Let us check the given expressions are well-formed formulae or not.

Given that, \({\bf{ \ast + + xyx}}\).

Now, x and y are each a well-formed formula, because the formula contains a single symbol.

Since x and y are well-formed formula, \({\bf{ + xy}}\) is a well-formed formula.

Let us name it as X.Then, \({\bf{ \ast + Xx}}\).

Since X and x are well-formed formula, \({\bf{ + Xx}}\) is a well-formed formula.

Let us name it as Y. Then, \({\bf{ \ast Y}}\).

So, we obtain binary operator with only 1 well-formed formula following it and then the given formula is not a well-formed formula.

Given that,\( \circ {\bf{xy \ast xz}}\).

Now, x, y and z are each a well-formed formula, because the formula contains a single symbol.

Since x and y are well-formed formula, \( \circ {\bf{xy}}\) is a well-formed formula.

Let us name it as X. Then, \({\bf{X \ast xz}}\).

Since x and z are well-formed formula, \({\bf{ \ast xz}}\) is a well-formed formula.

Let us name it as Y. Then, \({\bf{XY}}\).

So, one obtainstwo well-formed formulae without a binary operator and then the given formula is not a well-formed formula.

Evaluate the given expressions are well-formed formulae or not.

Given that,\({\bf{ \ast }} \circ {\bf{xz \ast \ast xy}}\).

Now, x, y and z are each a well-formed formula, because the formula contains a single symbol.

Since x and y are well-formed formula, \({\bf{ \ast xy}}\) is a well-formed formula.

Let us name it as X. Then, \({\bf{ \ast }} \circ {\bf{xz \ast X}}\).

Since we obtain a binary operator followed by 1 well-formed formulae\({\bf{ \ast X}}\) and thus the given formula is not a well-formed formula. Because the binary operator should always be followed by two well-formed formulas.

Given that,\({\bf{ \ast + }} \circ {\bf{xx}} \circ {\bf{xxx}}\).

Now, x is a well-formed formula, because the formula contains a single symbol.

Since x is a well-formed formula, \( \circ {\bf{xx}}\) is a well-formed formula.

Let us name it as X. Then, \({\bf{ \ast + XXx}}\).

Since X is a well-formed formula, \({\bf{ + XX}}\) is a well-formed formula.

Let us name it as Y. Then, \({\bf{ \ast Yx}}\).

So, one obtains two well-formed formulae with a binary operator and then the given formula is a well-formed formula.