1
$\begingroup$

Given the boolean expression given in reverse Polish notation $$x\ y\ +\ x\ z\ +\ *\ y\ z\ *\ +$$ recover the tree, write it in usual notation and simplify.

The usual notation is

$$\begin{array}{ll} &x\ y\ +\ x\ z\ +\ *\ y\ z\ *\ +\\ \iff&(x+y)\ x\ z\ +\ *\ y\ z\ *\ +\\ \iff&((x+y)+x)\ z\ *\ y\ z\ *\ +\\ \iff&(((x+y)+x)*z)\ y\ z\ *\ +\\ \iff&(((x+y)+x)*z)\ (y*z)\ +\\ \iff&(((x+y)+x)*z)+(y*z)\\ \end{array}$$

The recovery tree is

Recovery tree

Finally, the simplification is

$$\begin{array}{ll} &(((x+y)+x)*z)+(y*z)\\ \iff&(2*x+y)*z+y*z\\ \iff&2*x*z+y*z+y*z\\ \iff&2*z*(x+y) \end{array}$$

Is that correct? Is it possible to write $2*x\equiv2x$ and so on?

Thanks!

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Your third line is incorrect: $x~z~+$ translates to $(x+z)$ before it is multiplied by $(x+y)$. $\endgroup$ – Fabio Somenzi Nov 3 '18 at 6:11
  • $\begingroup$ @FabioSomenzi oh, thanks! So it would be $(x+y)*(x+y)+(y*z)$? $\endgroup$ – manooooh Nov 3 '18 at 6:18
  • 1
    $\begingroup$ The second $x+y$ is actually $x+z$, and then you can simplify a bit. $\endgroup$ – Fabio Somenzi Nov 3 '18 at 6:24
  • 1
    $\begingroup$ It's a Boolean expression, isn't it? So, $+$ is OR and $*$ is AND. $\endgroup$ – Fabio Somenzi Nov 3 '18 at 6:35
  • 1
    $\begingroup$ Right. You should post the answer, because it's your solution. I just gave a little nudge. $\endgroup$ – Fabio Somenzi Nov 3 '18 at 17:35
1
$\begingroup$

No, it is not correct. As @FabioSomenzi said in comments, the expression must be $(x+y)*(x+z)+(y*z)$, which has as a tree

Tree

and after applying some properties ends up with $x\vee(y\wedge z)$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.