Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

When asked to prove a specific equation for a boolean algebra by using the "Algebraic Foundation of Algebra Boole" (I don't know how accurate that translation is. In greek I found it as "αλγεβρική θεμελίωση της άλγεβρας Boole") i.e. prove the following:

$$x\cdot (y+x) = x$$

how should I proceed? What exactly is this "Algebraic Foundation" thing?

share|improve this question
3  
There are many different (but ultimately equivalent) ways to axiomatize Boolean algebras, and your property looks simple enough that a proof will depend significantly on which axioms you have. You may need to include them in your question in order to ensure a useful answer. (It may also help if you quote the bolded phrase in its original language). –  Henning Makholm Sep 7 '11 at 15:40
    
Thank you for your helpful comment. I edited my question and added the phrase the way I know it. I cannot answer to the first part of your request though because I think that the bolded phrase defines which axioms can be used... Sadly google wasn't any help at all. –  Eternal_Light Sep 7 '11 at 15:48

2 Answers 2

up vote 4 down vote accepted

There are two ways to describe boolean algebras axiomatically. One of them is the algebraic way (through the operations) in which the axioms talk about the three operations $+,\cdot, -,0,1$ (the constants can be seen as operations). The other is the relational way (through a partial order relation) in which the axiom talk about the relation $\leq$. When the author says "Αλγεβρική Θεμελίωση της Άλγεβρας Boole", he means the first way, rather than the second. My guess is that he specifies it, because the question is trivial in the second way.

A formulation of the axioms of the algebraic way is the following:

  1. $u+v=v+u$
  2. $u\cdot v=v\cdot u$
  3. $u+(v+w)=(u+v)+w$
  4. $u\cdot(v\cdot w)=(u\cdot v)\cdot w$
  5. $u\cdot(v+w)=u\cdot v+u\cdot w$
  6. $u+(v\cdot w)=(u+v)\cdot(u+w)$
  7. $u\cdot1=u$
  8. $u+0=u$
  9. $u+(-u)=1$
  10. $u\cdot(-u)=0$

What the question asks you is to use these axioms (or some other formulation that is presented in the source of the question) to prove that $x\cdot(y+x)=x$. Using the aforementioned axioms you can proceed as follows: First observe that $x\cdot x=x$. This is because (I use the axioms 7,9,5,10 and 8): $$x=x\cdot1=x\cdot(x+(-x))=x\cdot x+ x\cdot(-x)=x\cdot x +0=x\cdot x$$

Using the fifth axiom you get $x\cdot(y+x)=x\cdot y+ x\cdot x$. Now since we have $x\cdot x=x$ we get (using axioms 7 and 5): $$x\cdot(y+x)=x\cdot y+x=x\cdot y+x\cdot1=x\cdot(y+1)$$

If I show that $y+1=1$ I will be done. First show that $y+y=y$. This is analogue to $x\cdot x=x$, you can try it if you don't believe me. So we have $$y+1=y+(y+(-y))=(y+y)+(-y)=y+(-y)=1$$


In the formulation using the order relation $x\cdot y$ is the greatest lower bound of $x$ and $y$ and $x+y$ is the least upper bound of $x$ and $y$. Thus the question becomes trivial. We have $(x+y)\geq x$ by definition, thus $x$ is a lower bound of $x$ and $(x+y)$ and since every lower bound is smaller than or equal to $x$, we have that $x$ is the greatest lower bound, or using symbols $x\cdot(x+y)=x$.

share|improve this answer
    
You made it clear as day. Thank you :) –  Eternal_Light Sep 8 '11 at 11:52

hey i think i can help you with my view, actually those are basic postulates ,

let me prove $x*(y+x)=x$,but one needs the truth table construction and show that both of them come the same,but by a simple proof

$x(y+x)=x.y+x.x$ then it implies by idempotent law that

$x.x=x$, and so

$x(y+x)=x.y+x$ (as $x.x=1$) so by absorption law we can say that $x+x.y=x$

so hence proved

share|improve this answer
    
see this for more help and emphasis on laws :eecs.berkeley.edu/~newton/Classes/CS150sp98/lectures/week4_1/… –  Iyengar Sep 7 '11 at 16:11
    
thank you very much for your answer. That's exactly what I would do and it is obviously correct but it wouldn't be accepted as an answer because it "isn't making use of the algebraic foundation". I asked this question mostly in hope of finding out the meaning of that term. –  Eternal_Light Sep 7 '11 at 16:38
    
ha,its my pleasure ,thank you too,for giving me opportunity –  Iyengar Sep 7 '11 at 16:53
    
but even though i know the algebraic proofs ,they are very large,i read them somewhere in a library far away from our place,but i surely write them as soon as i find them ok –  Iyengar Sep 7 '11 at 16:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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