# Is this boolean algebra problem solvable?

My professor is of no help at all. He's foreign and is giving assignments that are written poorly, and is teaching stuff far beyond what he's supposed to be teaching at this level.

Nonetheless, he's given this as a problem on an assignment and I'm inclined to believe that it's not solvable based on how it's written.

Prove from the axioms of Boolean algebra that $x\cdot (\overline{y\cdot \overline{x}+\overline{y}}))=(x+x)\cdot (y+0)$

Notice how first off, there's no opening bracket in front of the x. I'm assuming it's meant to be there, by the fact that there's an extra closing bracket.

Now. I've gotten so far as to expand it as follows:

$$(x+x)\cdot ((\overline{y\cdot \overline{x}})\cdot y)$$ $$(x+x)\cdot ((\bar{y}+x)\cdot y)$$ $$(x+x)\cdot ((y\cdot \bar{y})+(x\cdot y))$$ $$(x+x)\cdot (0+(x\cdot y))$$

But I cannot figure out how $x\cdot y$ can possibly simplify to $y$. Therefore I ask, is this even doable? or am I doing something wrong?

Edit: Just in case it's relevant (and I honestly cant' say I know if it is), here's the list of axioms he gave at the start of the problem. I had just assumed that they were a hint, and not actually required for the problem.

1. $x+y=y+x$, $x\cdot y=y\cdot x$
2. $(x+y)+z=x+(y+z)$, $(x\cdot y)\cdot z=x\cdot (y\cdot z)$
3. $x\cdot (y+z)=x\cdot y+x\cdot z$, $x+y\cdot z=(x+y)\cdot (x+z)$
4. $x+0=x$, $x\cdot 1=x$
5. $x+\bar{x}=1$, $x\cdot \bar{x}=0$
6. $0\neq 1$
-
You can't simplify $x\cdot y$ to $y$... but you can simplify $x\cdot(x\cdot y)$ to $x\cdot y$, which is what you actually need, right? –  mjqxxxx Nov 4 '12 at 20:41
I suppose that works. I was looking for a way to get to the intermediate step though of $(x+x)\cdot (y+0)$... I guess I'll have to get to the end and then step backward. –  agent154 Nov 4 '12 at 20:45
Each side can be reduced to $x\cdot y$, so they are indeed equivalent. By the way, I slightly edited your post; check that my edits maintain the sense of what you intended. –  Rick Decker Nov 4 '12 at 20:47

I’m assuming that you have associativity, distributivity, de Morgan’s laws, and $x+x=x$. It’s usually best to start by expanding the more complicated-looking side, which in this case is the left side, though in this case the righthand side is so simple that you can immediately reduce it to $x\cdot y$ as a nice target for the lefthand side.

\begin{align*} x\cdot \overline{\left(y\cdot \overline{x}+\overline{y}\right)}&=x\cdot\left(\overline{y\cdot\overline x}\cdot\overline{\overline{y}}\right)\\ &=x\cdot\overline{\left(y\cdot\overline x\right)}\cdot y\\ &=x\cdot\left(\overline y+\overline{\overline x}\right)\cdot y\\ &=x\cdot\left(\overline y+x\right)\cdot y\\ &=\left(\left(x\cdot\overline y\right)+(x\cdot x)\right)\cdot y\\ &=\left(x\cdot\overline y\right)\cdot y+(x\cdot x)\cdot y\\ &=x\cdot\left(\overline y\cdot y\right)+x\cdot y\\ &=x\cdot 0+x\cdot y\\ &=0+x\cdot y\\ &=x\cdot y\\ &=(x+x)\cdot y\\ &=(x+x)\cdot(y+0) \end{align*}

-
I had to clarify with the prof, but he said we could use any axioms we wanted that were well known... I wasn't limited to using the ones he gave. –  agent154 Nov 13 '12 at 2:29

If x=0, then we have 0*(a)=(0+0)(b), since 0+0=0, and 0*x=0 it follows that the equality holds in this case.

If x=1, then (1*(y*1'+y')')=(y*0+y')'=(0+y')'=y''=y and (1+1)(y+0)=1(y+0)=1y=y. So, the equality holds in this case.

Consequently, it follows that (x*(y*x'+y'))=((x+x)(y+0)) is a theorem of 2, and thus holds for all Boolean Algebras.

For a proof from your axiom set, we would require to know which axiom set you have at hand.

-
I had to clarify with the prof, but he said we could use any axioms we wanted that were well known... I wasn't limited to using the ones he gave. Thanks for the help though. –  agent154 Nov 13 '12 at 2:28