• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q30E

Expert-verified Found in: Page 784 ### Discrete Mathematics and its Applications

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}}$$

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.
See the step by step solution

## Step 1: 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.

## Step 2: 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.

## Step 3: 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. ### Want to see more solutions like these? 