2
$\begingroup$

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?

  • 0
    Th$a$nk 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.2011-09-07

2 Answers 2

4

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$.

  • 0
    You made it clear as day. Thank you :)2011-09-08
2

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

  • 0
    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 ok2011-09-07