# Given $x\ y\ +\ x\ z\ +\ *\ y\ z\ *\ +$ recover the tree, write it in usual notation and simplify

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

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!

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

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
and after applying some properties ends up with $$x\vee(y\wedge z)$$.