StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q30E

Expert-verifiedFound in: Page 784

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**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\}\)?**

**\({\bf{ \ast + + xyx}}\)****\( \circ {\bf{xy \ast xz}}\)****\({\bf{ \ast }} \circ {\bf{xz \ast \ast xy}}\)****\({\bf{ \ast + }} \circ {\bf{xx}} \circ {\bf{xxx}}\)**

** **

- Therefore, the given formula is not a well-formed formula.
- Therefore, the given formula is not a well-formed formula.
- Therefore, the given formula is not a well-formed formula.
- Therefore, the given formula is a well-formed formula.

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

** **

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

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.

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.

94% of StudySmarter users get better grades.

Sign up for free