0

Need some help getting in the right direction for answering the following question:

Prove the following property and interpret this in $\mathcal P \left ({V} \right)$:

if $x+ \bar y=$ 1, then $x+y=x$.

How can I best approach this?

Garth Marenghi
  • 1,115

1 Answers1

1

We start with $x$, then use the boolean axioms and the identity $x+\overline{y}=1$ to reach $x+y$. Here's a proof (I'll leave off the brackets, due to associativity): \begin{align*} x &= x+x & \text{idempotence of } + \\ &= x+x*1 & \text{identity of } * \\ &= x+x*(y+\overline{y}) & \text{complementation of } + \\ &= x+x*y+x*\overline{y} & \text{distributivity of } * \text{ over } + \\ &= x*x+x*y+x*\overline{y} & \text{idempotence of } * \\ &= x*x+x*y+x*\overline{y}+0 & \text{identity of } + \\ &= x*x+x*y+x*\overline{y}+y*\overline{y} & \text{complementation of } * \\ &= x*(x+y)+x*\overline{y}+y*\overline{y} & \text{distributivity of } * \text{ over } + \\ &= x*(x+y)+(x+y)*\overline{y} & \text{distributivity of } * \text{ over } + \\ &= x*(x+y)+\overline{y}*(x+y) & \text{commutativity of } * \\ &= (x+\overline{y})*(x+y) & \text{distributivity of } * \text{ over } + \\ &= 1*(x+y) & \text{by assumption } x+\overline{y}=1 \\ &= x+y & \text{identity of } *. \end{align*}

Rebecca J. Stones
  • 26,845
  • Thank you for your answer! I still have to put some things in place, but right now I'm here: Step 1, idempotence: $x=x+x$. Step 2, identity: $(x+x)+0$. Step 3: $x+x+y+ \bar y$. Step 4: commutativity: $x+y+x+ \bar y$. Step 5, by assumption: $(x+y)+1$. The only things that don't work out yet are $(x+x)+0$, because zero should (I think) expand to $y* \bar y$. And $(x+y)+1$, because that would lead to 1, and not to $x+y$. – Garth Marenghi Sep 09 '13 at 17:46
  • Yes, the (x+x)+0 is my mistake: I should have written "Annihilator for +", and it'll be (x+x)+1. (I fixed this in the answer now.) – Rebecca J. Stones Sep 09 '13 at 17:50
  • Annihilator? English is not my first language, I've never heard of this before! I have an English book in front of me, and there is this: $a * 1 = a$. Is it somehow comparable? – Garth Marenghi Sep 09 '13 at 17:57
  • I think so, although I don't know what $*$ means here. It should be equivalent to "$X \vee \mathrm{TRUE}=X$". (Or $x+1=x$.) – Rebecca J. Stones Sep 09 '13 at 17:59
  • If I would translate to set theory, then $+$ equals union, and $*$ equals intersection. – Garth Marenghi Sep 09 '13 at 18:01
  • It should be $X$ union $1$, not $X$ intersection $1$. – Rebecca J. Stones Sep 09 '13 at 18:07
  • Right. But that's what confuses me: $x=x+x+1$ would be in set theory X = X union X union Universe. Wouldn't the answer to that be Universe? In boolean algebra: $x=x+x+1=1$ but $x \neq 1$? And as well; thanks for answering my questions! – Garth Marenghi Sep 09 '13 at 18:13
  • Okay, I think it's alright now. My apologies for the errors. – Rebecca J. Stones Sep 09 '13 at 18:46
  • Wow, this is quite different than what you first put up. Thank you for your effort, that was quite some work! – Garth Marenghi Sep 09 '13 at 18:47
  • It looks a lot worse that it really is: basically it boils down to the line $(x+\overline{y})(x+y)$. We know $x+\overline{y}=1$, so we get this equaling $x+y$, and if we expand it out and cancel, we get $x\overline{y}+x*y$ which simplifies to $x$. – Rebecca J. Stones Sep 09 '13 at 18:51
  • I was working about with your solution, and I thought of this (maybe you can verify this also works?): We start with $x+y$. Step 1: $x+y=1x+y$. Step 2: we know that $x+ \bar y$ equals 1, so we can write $x+y=(x+ \bar y) (x+y)$. Step 3: we can then extract $x$: $x+(y* \bar y)$. Step 4: $x+0$, which equals $x$. – Garth Marenghi Sep 09 '13 at 19:31