Wikipedia:Reference desk/Archives/Mathematics/2006 November 26

From Wikipedia, the free encyclopedia

Mathematics desk
< November 25 << Oct | November | Dec >> November 27 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


Contents


[edit] November 26

[edit] Confused about Boole algebra axiomas

I readBoolean_algebra#Formal_definition but now I am confused.

My professor only gave us four axioms for a Boole algebra : commutativity, distributivity, neutral elements (0 and 1, for join and wedge respectively), and complementarity (is this a correct word?)

He claims that associativity can be deduced from these four (well, there are eight of them actually,they come in pairs) axioms. And he also claims, that all others properties can be deduced from this (idempotence, absorption, involutive property, Morgan's laws, antitonity,...)

Now I don't want to ask too much of the fine people here :) so I won't ask for a proof of all of them, but I would definitely like to know how to prove

  • idempotence : a\land a = a and a\lor a=a
  • associativity : a\land (b\land c)=(a\land b) \land c and a\lor(b\lor c)=(a\lor b)\lor c
  • absorption : a\land (a\lor b) =a and a\lor(a\land b)=a

because then I would at least be able to prove each Boole algebra is also a lattice

Thank you,Evilbu 21:25, 26 November 2006 (UTC)

Using neutral elements and complements a=a\lor 0=a\lor(a\land \lnot a) and expand rhs using distributivity. --Salix alba (talk) 23:30, 26 November 2006 (UTC)
(after edit conflict) Be glad you don't have to show that every Robbins algebra is a Boolean algebra. Here is the proof of idempotence:
a\land a = (a\land a)\lor 0 = (a\land a)\lor(a\land\lnot a) = a\land(a\lor\lnot a) = a\land 1 = a.\,
(The dual idempotent property is proved dually.)  --LambiamTalk 23:33, 26 November 2006 (UTC)
Alternatively using the truth tables for AND and OR it should be easy to demonstrate all these for yourself. And proof by exhaustion is easy in this case since there are only 4 different options A true/false and B true/false.87.102.36.159 23:35, 26 November 2006 (UTC)
No, that doesn't work in general; it works only for the case of the simplest Boolean algebra, the one with only two elements. --Trovatore 23:42, 26 November 2006 (UTC)
Dear 83.100.138.7/83.100.174.103/83.100.250.33/83.100.250.53/83.100.253.24/87.102.12.129/87.102.16.174/87.102.36.82/87.102.36.159, perhaps you should verify (1) that you know what you are talking about, and (2) that your contribution adds value, before you react to the attempts of other editors to answer the questions posed here. Thus far your contributions have succeeded in creating more confusion than enlightenment.  --LambiamTalk 09:04, 27 November 2006 (UTC)
ok I'll fuck off then. 87.102.20.219 16:28, 27 November 2006 (UTC)
Nice proof, you just have to think of it. Can you help me with idempotence and associativity as well? If it makes you feel better, it's not homework, our professor just skipped it. But I'll feel bad about myself if I can't even prove that a Boole algebra is a lattice! :)Evilbu 00:18, 27 November 2006 (UTC)
(Fixed some typos in your formulae. And the correct term is "Boolean algebra", not "Boole algebra".) --KSmrqT 07:32, 27 November 2006 (UTC)
I thought surely someone would offer another proof. Alright, then here's a proof of absorption:
\begin{align} a\land (a\lor b) &{}= (a \lor 0) \land (a \lor b) && \qquad \text{neutral}\\ &{}= a \lor (0 \land b ) && \qquad \text{distributive}\\ &{}= a \lor 0 && \qquad \text{neutral}\\ &{}= a && \qquad \text{neutral} \end{align}
Enjoy. --KSmrqT 07:35, 29 November 2006 (UTC)