0
$\begingroup$

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$
  • 1
    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.2012-11-04

2 Answers 2

2

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

  • 0
    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.2012-11-13
1

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.

  • 0
    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.2012-11-13