Talk:Boolean algebra (structure)/Archive 4
![]() | This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 | Archive 2 | Archive 3 | Archive 4 |
Execution time
(I moved the following paragraph down from the end of the (previously) second last section, where it might not have been so visible, and started a new section since the "French" section was getting long. Also probably time to archive some of the earlier sections if someone would like to volunteer to do that, this page is now up to 155 kilobytes. Vaughan Pratt 09:25, 9 July 2007 (UTC))
Meanwhile I've removed the material about Boolean algebras (plural) from Elementary Boolean algebra so as to make it purely about syntax, and added some figures. At this point I'll stop working on it. If someone sees fit to merge it and Boolean logic into a single suitably named article about the purely syntactic side of Boolean algebra I won't object. I don't mind doing it myself if no one else minds, just let me know. Vaughan Pratt 09:10, 8 July 2007 (UTC)
Now back to the present.
Having stopped work on Elementary Boolean algebra, I went back to Boolean algebras canonically defined and worked it up into an article (a) focusing just on Boolean algebras, little or no syntax, and (b) replacing the idiosyncratic bits by material reflecting the status quo as neutrally as possible. The original reason I wrote that article is that it really bugged me to see such basis-biased accounts of the subject, which reflect the cultural biases of the authors. Some of the Boolean algebra expositors in the literature, e.g. Halmos, come from quite a different background than those who grew up convinced a Boolean algebra could only be defined formally as a kind of lattice. The present write-up tries to express these different cultural backgrounds as neutrally as possible.
User: Trovatore is concerned that I'm writing too much about the subject. If that's a universally shared concern, I guess the message would have to be that Wikipedia is aiming to avoid encyclopedic articles (!). Is that in fact the case, or is the brevity of many articles more a reflection of the limited resources of their authors than of a deliberately imposed style?
If there's general support for incorporating some part of each of my two articles in the proposed split of Boolean algebra into an article on the elementary or symbolic aspects and a separate one on Boolean algebras as abstract structures, I'm happy to do what it takes to move that forwards. Meanwhile let me encourage those who'd like to see such a split take a look at each of Elementary Boolean algebra and Boolean algebras canonically defined (the latter name definitely needs to disappear one way or another) and comment on suitability for respectively the symbolic and abstract articles -- too fast, too slow, too long, too short, too many figures, too few figures, not enough references to Chad Boole, etc. etc. Vaughan Pratt 09:25, 9 July 2007 (UTC)
- So first of all, there's no proposal to split the existing Boolean algebra -- it was split quite some time ago, and now does not treat equational logic. The article that was supposed to treat the equational logic, or at least so I thought, was Boolean logic. But your elementary Boolean algebra does a better job of it. However Boolean logic has a long history with many authors, so for the sake of preserving the history, elementary Boolean algebra should be merged into Boolean logic.
- As for the "too much" thing: It's not that it's too much in quantity exactly. It's that it's too essay-like, too pedagogical, and also I was concerned that implementation code was being written before we'd agreed on the header files.
- The thing to keep in mind here is that Wikipedia is a reference work. It's certainly a learning tool, but only secondarily; primarily it's a place to look things up, and if you want to learn from it (just as if you want to learn from a print encyclopedia) you have to expect that things will be presented more synthetically than they would be in a textbook, in a more "just the facts" style, and that you have to find your own approach into the material rather than having one spelled out for you in easy lessons.
- As regards the "canonically defined" article -- I would add a section to the algebraic structure article, called "alternative characterizations" or some such, and mention there the definition with the XOR operator. I never completely digested the article (just got the general "too essay-like" impression), so I'm not sure what else from it ought to be merged. You do write well and include a lot of good information, so probably there is more material that should come over. --Trovatore 16:45, 9 July 2007 (UTC)
- Pragmatically there is no difference in the editing needed in either direction, whether Elementary Boolean algebra gets merged into Boolean logic or the other way around. Basically, create anywhere by any means a text that is the desired merged text (or a reasonable approximation). Then, if not already at Boolean logic, paste and copy the merged text there wholesale, superseding the old contents. As long as the Boolean logic page is not deleted (something only admins can do), its edit history will be preserved. See also Help:Merging and moving pages#Performing the merger. --LambiamTalk 20:26, 9 July 2007 (UTC)
- Even though Wikipedia is not a textbook, there are too many maths articles that are neither well written nor readily accessible even to mathematicians. I'd say, it is generally better to err on the side of too much well written and accessible material, than too little. --LambiamTalk 20:33, 9 July 2007 (UTC)
Thanks, User: Lambiam. I've started the merge process with a mergeto tag in Elementary Boolean algebra and a mating mergefrom in Boolean logic. I did that in preference to proposing to merge both to Boolean algebra (logic) (or whatever final name is agreed on) in order to separate the question of article name from the details of what to merge and what to displace, dealing with the latter first. Hopefully people running across the merge tags will notice User: Trovatore's pointer at the bottom of Talk:Boolean logic to this page. --Vaughan Pratt 19:36, 11 July 2007 (UTC)
The merge at Boolean logic is now completed. For the purposes of a dab page, is everyone in agreement that Boolean algebra and Boolean logic should be moved to Boolean algebra (structure) and Boolean algebra (logic) respectively? The above discussion suggests that this is the preferred choice, and it does have the advantage of being more or less self-explanatory. My own preference would be to track the standard distinction drawn in sections 2 and 3 of Algebra, between Elementary algebra and Abstract algebra, which for Boolean algebra would seem to indicate Boolean algebra (elementary) and Boolean algebra (abstract) as being more in line with standard usage. Are there strong feelings either way at this point? --Vaughan Pratt 21:36, 17 July 2007 (UTC)
- I definitely prefer the structure/logic distinction. The distinction should be based on the subject matter, not on the approach. Note that the abstract algebra article is about algebra treated abstractly, not about algebras in the sense of modules plus multiplication. The "structure" article should be analogous to the latter, not the former.
- A complicating factor: There's a current active discussion about "introduction to..."-type articles, triggered by the featured-article candidacy of Introduction to general relativity. I personally don't like them. However, if they do become standard, then it would be reasonable to have an Introduction to Boolean algebra article, while maintaining the content-based logic/structure distinction in the articles aimed at mathematicians. --Trovatore 21:47, 17 July 2007 (UTC)
- Actually, having allowed that possibility into my internal discussion, I find myself more and more drawn to the idea that it may be the only practical solution here, much as I would dislike to see it become commonplace. The structure-v-equational-logic distinction is, to me, extremely clear, and exemplifies two very distinct meanings of the phrase "Boolean algebra", so we pretty much have to have two articles. But the problem remains that neither of those articles, as written by mathematicians, is going to serve the needs of people wanting to understand how to do a Boolean search on an ORION database, or things like that.
- So I'm now leaning to a three-article-plus-dab-page model: The two articles based on the structure/logic distinction, the "Introduction to..." article, and Boolean algebra itself becomes a strict dab page, not "dab plus". Anything that might have gone in "dab plus" should be worked into one of the three real articles. The naming of the "Introduction" article addresses my concern about linking (it won't be accidentally linked to by authors intending the structure).
- Oh, I haven't addressed the "canonically defined" article. Vaughan, to be honest, I can't really understand why you think this issue is so important; to me it appears to be a detail of presentation. It's nice to know that you can characterize Boolean algebras in terms of AND and XOR instead of AND and OR, and that it forms a ring structure, and that whenever it's convenient to use this terminology, you just do it and don't need to say much about it. And that there are other possible choices. But is it worth a whole article? I'd just add an "alternative characterizations" section to the "structure" article, and write a paragraph or two. --Trovatore 22:40, 17 July 2007 (UTC)
- I don't have any strong disagreement with any of the above. So it sounds like whoever's offering to do the dab page should at that time move Boolean algebra to Boolean algebra (structure) and Boolean logic to Boolean algebra (logic).
- On the "canonically defined" article, the point was not that rings are an alternative to lattices in the definition of "Boolean algebra", nor that there are yet other choices of operations on which to base a definition such as NOR, but rather that there's a simple yet rigorous definition of the concept that does not depend on any explicitly given list of either operations or equations. A Boolean algebra is just any model of the equational theory of the algebra of finitary operations on {0,1}. The existing definitions create the incorrect impression that "Boolean algebra" can't be defined without first choosing suitable operations like and-or-not or plus-minus-times or NOR and equations like those for a complemented distributive lattice or a Boolean ring.
- But I agree in retrospect that that point alone doesn't justify a separate article. However most of what's in my article isn't in the existing Boolean algebra article. However as an attempt to improve overall on the status quo it didn't succeed the way I'd hoped it might. I'm happy to remove Boolean algebras canonically defined from Wikipedia altogether if people feel that the existing Boolean algebra (structure) article is fine as it stands. I do feel however that as a self-contained article it has a lot of useful material and insights about Boolean algebra that is hard to find elsewhere. Merging it in with Boolean algebra might make sense if it were clear how to do the merging without breaking up the continuity of the two articles. --Vaughan Pratt 19:40, 19 July 2007 (UTC)
- Your stuff is good and I don't want to see it lost either. I'd like to see it merged into the structure article (hopefully it'll pack down a bit in transition, though; there's lots of other stuff I'd like to see go into the structure article too, like atomicity, atomlessness, quotients by ideals, restrictions to a nonzero element, existence of nontrivial automorphisms, model-theoretic saturation, stuff like that. Getting everything in while keeping a tight narrative flow is going to be an extreme challenge. But as I say, let's first get the header files right. If there are no objections, I'll go ahead and do the move and dab page as outlined above, leaving "canonically defined" and "introduction" out of the picture for the moment. --Trovatore 20:01, 19 July 2007 (UTC)
- OK, couldn't anyone have dropped me a note on my talk page to tell me you were planning on undoing all my careful work (to make an accessible article on Boolean logic aimed at a general audience and with computer science and electronics applications) ? This article remains readable only by PhDs, and now that article is similarly readable only by PhDs. (The simple illustrations with Venn diagrams were stripped out, and mathematician-speak was put in, for example.) I have now put the general audience article back at "Boolean logic" and left the PhD level article at the new name of Boolean algebra (logic). I suggest you merge the two "Boolean algebra" articles together (or leave them separate, if you prefer) and leave "Boolean logic" alone. If you wish, I am willing to rename "Boolean logic" to Boolean logic (computer science), in order to make it perfectly clear that this is not an article for or by mathematicians. StuRat 03:23, 25 September 2007 (UTC)
Move completed; links need fixing
I've done the move and started the very tedious process of fixing all the links. I'll come back and do some more later; sooner or later we'll get them done. Anyone who wants to help out should note that some of the links should not be to either of the "Boolean algebra" articles, but to Boolean function or Boolean datatype. --Trovatore 20:04, 20 July 2007 (UTC)
Disambiguation
I have this nagging suspicion that the typical innocent reader wanting to read up on "Boolean algebra", having read the disambiguating definitions at Boolean algebra, will have no clue as to which of the two to navigate to. For reference, here is the current wording of the disambiguation:
- Boolean algebra may mean:
- Boolean algebra (logic), a logical calculus applying to truth values or sets
- Boolean algebra (structure), a type of algebraic structure modeling the aforementioned logical calculus
Should we, perhaps, expand the first definition by adding "used for describing logic circuits and formulating search engine queries"? --Lambiam 03:23, 23 July 2007 (UTC)
- Sure, that seems fine. --Trovatore 06:05, 23 July 2007 (UTC)
- Thus amended. --Lambiam 15:32, 23 July 2007 (UTC)
Image:Hasse diagram of powerset of 3.svg
Can someone please explain to me clearly why commons:Image:Hasse diagram of powerset of 3.svg has been replaced by an inferior png substitute image? KSmrq says "illegal image" and Cronholm144 says "not attributed" but to me it appears as properly licenced under GFDL and CC, attributed as "own work" by commons:User:Fibonacci. —David Eppstein 17:22, 24 July 2007 (UTC)
- It's a near-identical re-drawing of an image made by KSmrq, who was not credited (and the license is different from KSmrq's license). KSmrq objected. I don't really know whether this is the sort of thing actually covered by copyright, but given that KSmrq objects and the costs of meeting his conditions are small, I'd encourage Fibonacci to go ahead and do it. --Trovatore 17:27, 24 July 2007 (UTC)
- Superficially, the resemblance is much closer than one would expect from an independent re-drawing, but if you pay attention to KSMrq's drawing it says it was created by graphviz, and it's reasonable to believe that the same is true for Fibonacci. The node layout is an obvious choice for a Hasse diagram of this lattice, and the style of nodes with labels in ovals is I think the graphviz default. So really the only "artistic" choice made by KSmrq and copied by Fibonacci is to make the arrowheads hollow instead of solid. Is that all we're arguing about? All this is convincing me that I'm making the right choice by uploading my own diagrams PD and not having to worry about whether I'm being properly credited. —David Eppstein 17:48, 24 July 2007 (UTC)
- I decided rather than waiting to see if the attribution and licensing problems would be fixed, I would simply upload my own original SVG. So feel free now to use my SVG, which has no copyright problems.
- The SVG I replaced was nothing more than a copy of my PNG, and yet it did not comply with the generous license under which I contributed the PNG, which requires both attribution and use of the same license. Incidentally, I uploaded the PNG at very high resolution so it was not visibly inferior, and the unlicensed SVG was the substitute.
- At one time it was not possible to upload SVG files. Even today, perfectly correct SVG files may be improperly rendered by the defective SVG rasterizer (librsvg) Wikipedia has chosen to use. (Compare this SVG and this PNG.) I'm a big proponent of SVG, and use it as much as possible. --KSmrqT 17:59, 24 July 2007 (UTC)
- Your comparison example uses a nonstandard font which is not linked to nor defined within the svg (Nimbus-Roman). Perhaps that is related to some of the rendering difficulties. Though I don't understand some other issues (the huge curve width and missing axes). —David Eppstein 18:06, 24 July 2007 (UTC)
- The font is a standard font — for Wikipedia. (See here.) I wish that were the source of that problem, but it's not; the same thing happens with any font. I spent considerable time with a number of SVG implementations trying to understand exactly what caused each to fail. The one used by Wikipedia was, by far, the worst of them all. (That's well known. The rationale is that it's fast; but it's easy to be fast if you don't have to be correct!) The thing is, it's not a matter of understanding the SVG standard, but of teasing out exactly what combination of valid input features causes the renderer to misbehave. Not only is it tedious, it's really annoying! Eventually I decided it was not a good use of my time, so I uploaded a PNG. I shall continue to do so until the rendering software is fixed. --KSmrqT 19:56, 24 July 2007 (UTC)
- I've been using SVG as generated by a recent version of Adobe Illustrator, with only a few problems: (1) it defines and uses xml entities, which must be expanded before Wikipedia's renderer can handle it, and (2) it uses idiosyncratic font names which must be replaced by something more standard. Neither issue is hard to handle; I use a small script to do the replacements. But it was, I agree, very frustrating before I figured out what was causing the problems. —David Eppstein 19:15, 25 July 2007 (UTC)
- Most of my SVG images are created using a text editor. I use the standard in ways that should be unremarkable; yet CSS, nested transforms, length units, markers, and various other features cause renderers to misbehave. What works and what does not is bizarre. Since each renderer breaks in its own way, dodging the bugs is a very unpleasant exercise. (In sympathy for the implementors, I should say that the standard itself does not make their job easy.)
- I believe I abandoned XML entities early on, sadly. I had wanted to be able to name a color, for example, and an entity seemed a natural approach. I switched to CSS classes, which proved more robust, though still a little delicate. The automatically generated stuff (including output of dot, gnuplot, and so on) seems to mostly avoid all the features that lend convenience and economy, perhaps as a response to the broken renderers.
- Only one renderer supports declarative animation and most static features well, and that's the Adobe 6 beta, only available for Windows. (Grab it now while you can; it will soon disappear permanently.) Except for lacking animation (which is in beta), the Batik renderer seems far superior to everything except ASV6β. It's built on Java, which makes it cross-platform (good) and a bit slow (not so good). Rapidly improving for rendering, and already nicest for GUI editing, is Inkscape. The GLIPS Graffiti editor is based on Batik, but is somewhat disappointing. The browsers Firefox and Opera have some SVG support, but leave much to be desired. Signs are that Adobe itself is moving away from SVG, so we can only hope everyone else picks up the slack. --KSmrqT 21:43, 25 July 2007 (UTC)
- Support for SVG seems minimal everywhere. Given this, and given the huge support worldwide for the past 25 years for PostScript, both embedded and not, I find it extremely frustrating that Wikipedia claims to support SVG (which the above comments indicate it does badly) while offering no support at all for PostScript. I can readily crank out PostScript figures that don't seem to have SVG counterparts, and end up having to convert my nice resolution-independent PostScript files into bitmaps in order to turn them into figures for Wikipedia articles. There is no translator from PostScript to SVG. Why can't Wikipedia at least look into rendering PostScript? Ghostscript is readily available. SVG sucks. --Vaughan Pratt (talk) 09:03, 28 January 2008 (UTC)
- I've been using SVG as generated by a recent version of Adobe Illustrator, with only a few problems: (1) it defines and uses xml entities, which must be expanded before Wikipedia's renderer can handle it, and (2) it uses idiosyncratic font names which must be replaced by something more standard. Neither issue is hard to handle; I use a small script to do the replacements. But it was, I agree, very frustrating before I figured out what was causing the problems. —David Eppstein 19:15, 25 July 2007 (UTC)
- The font is a standard font — for Wikipedia. (See here.) I wish that were the source of that problem, but it's not; the same thing happens with any font. I spent considerable time with a number of SVG implementations trying to understand exactly what caused each to fail. The one used by Wikipedia was, by far, the worst of them all. (That's well known. The rationale is that it's fast; but it's easy to be fast if you don't have to be correct!) The thing is, it's not a matter of understanding the SVG standard, but of teasing out exactly what combination of valid input features causes the renderer to misbehave. Not only is it tedious, it's really annoying! Eventually I decided it was not a good use of my time, so I uploaded a PNG. I shall continue to do so until the rendering software is fixed. --KSmrqT 19:56, 24 July 2007 (UTC)
- Your comparison example uses a nonstandard font which is not linked to nor defined within the svg (Nimbus-Roman). Perhaps that is related to some of the rendering difficulties. Though I don't understand some other issues (the huge curve width and missing axes). —David Eppstein 18:06, 24 July 2007 (UTC)
Links (mostly) sorted
I have completed, for now, the task of sorting the mainspace links to Boolean algebra to one of the articles (or in a few cases to some different article, like Boolean function, Boolean datatype, or Boolean operator). Charles Peirce is currently protected so I couldn't get to that one, and I didn't know how to deal with relation algebra -- I think Vaughan may be looking into it.
However there are still about 140 links to the disambig page (from talk, wikipedia, and user pages). I don't think it's really policy to change most of those. This is a little unfortunate because http://en.wikipedia.org/wiki/Special:Whatlinkshere/Boolean_algebra is hard to interpret. Does anyone know whether there's any way to filter the "what links here" tool, so that only mainspace links show up? --Trovatore 18:59, 25 July 2007 (UTC)
- I handled the Peirce edit. —David Eppstein 19:06, 25 July 2007 (UTC)
- Thanks. --Trovatore 19:07, 25 July 2007 (UTC)
The relation algebra article is now revised. It makes use of a new article on residuated Boolean algebras based on work of Jónsson and Tsinakis, and also a complete rewrite of residuated lattices, which connects up also with a new article on action algebras aka residuated Kleene algebras. --Vaughan Pratt 23:58, 16 August 2007 (UTC)
- Vaughan, thanks for the rewrite at relation algebra; it looks much cleaner. Could possibly use a little more text on motivations -- that's always a delicate balance as it's tricky to avoid sliding into a textbook style, but as it stands I think even a lot of sophisticated readers are going to be scratching their heads about the why of the whole thing. --Trovatore 21:37, 17 August 2007 (UTC)
Lack of inline citations
I put a citation cleanup tag on this article and was immediately reverted. This is not an instance of inline-citation purity: I don't want a citation on every sentence. But this article, as it stands now, has zero inline citations. None. See Wikipedia:Scientific citation guidelines for situations in which no inline citations are necessary; I don't think this article is short enough to qualify. There are ten publications listed in the references, some of which I know to be relevant but some of which look dodgy, and I have no idea which, if any, of them, are relevant to which of the topics discussed here. There is a history section which names names of contributors to the topic, none of which match up to the actual references. I'm tempted to rip out the whole references section, except for the Halmos book, and add a note at the top of the article stating that the material here can be found discussed in greater depth in that book. Can someone dissuade me from this course of action? —David Eppstein 20:16, 5 August 2007 (UTC)
- Most of the citations seem to be for the section "Axiomatics for Boolean algebras" which does have inline citations (to Huntington (1933) and Dahn (1998)). Some of the references do seem to need further investigation, such as Brown and Vranesic (2002), Cori and Lascar (2000), Mendelson (1970), and
Stoll (1963). The Handbook of Boolean Algebras seems like a fine reference to include even if it is not directly cited. — Carl (CBM · talk) 20:27, 5 August 2007 (UTC)
Really my main objection was to the template on the article page, not to adding inline refs. I think such templates should go on article pages only when it's necessary to warn the reader that either (1) there are statements in the article that may not be accurate, or (2) there are problems that would bring Wikipedia into disrepute, such as bad grammar/spelling errors or unclear writing. When it's only editors that need to be informed, the tag ought to go on the talk page, so as not to uglify the article. --Trovatore 20:30, 5 August 2007 (UTC)
I'm familiar with the Stoll book. It has a nice chapter on Boolean algebras. It seems to be a perfectly reasonable reference to me. What seems to be the problem with it? Paul August ☎ 22:00, 5 August 2007 (UTC)
- The "investigation" I mentioned is just to make sure that the books discuss boolean algebras (qua lattices); the title of Stoll's book isn't a clear indication. I'll strike it out above since it does. — Carl (CBM · talk) 00:15, 6 August 2007 (UTC)
A comment on 'Principles of duality':
I have my doubts as to the duality of the connectives . For, while , i.e., is a tautology, the supposedly dual formula is not tautological (it is in fact a contradiction). The correct dual formula is .
It is my impression that the dual connectives are: , , , , and (NOR, NAND).
Shimon P. Vingron 81.217.16.172 07:52, 28 August 2007 (UTC)
Atomicity
It would be nice if possible (interesting) properties of boolean algebras such as atomicity are mentioned in the article, and what they mean of course. H. (talk) 12:36, 6 September 2007 (UTC)
About the math rendering of boolean algebra equations
My user preferences are set so to render math formulas as HTML as much as possible. This provides a nice HTML rendering for all equations of the article to the exception of the equation which is rendered as a PNG image. The reason is that the math environment does not recognize \varnothing as HTML interpretable.
To respect the editor choice of having \varnothing in the equation rather than, say \emptyset, I tried to replace \varnothing by \O (which is in LaTeX a slightly larger form of \varnothing). But it did not work because the <math> environment is bugged: it correctly interpret \O in HTML as a circle with a slash (i.e. ∅, i.e. ∅) but it interprets it for LaTeX rendering as an oval (i.e. , as if it actually were a \emptyset), so that \O as an alternative for \varnothing does not work as far as PNG is concerned.
But after all, is the intended meaning of the equation not to have \emptyset rather than \varnothing? If one would change \varnothing to \emptyset, then, for LaTeX typesetting, the difference would be to have an oval with a slash (instead of a circle), and, for HTML rendering, the gain would be that \emptyset has a rendering which is ∅. So would somebody oppose to a change of \varnothing to \emptyset so that the readers that use HTML as much as possible in rendering see the HTML formula A∩(AC) = ∅ instead of a PNG image, knowing that for readers that rely on PNG images it would be rendered with a slashed oval instead of a slashed circle.
PS: I already changed \lnot \to neg for the same purpose (to the exception that lnot and neg are LaTeX synonymous while \varnothing and \emptyset are not). Hugo Herbelin (talk) 12:14, 31 December 2007 (UTC)
- \emptyset is rather ugly. The best solution would be for the developers to fix the code so that \varnothing is converted to HTML in the same way as \emptyset. That way it would work for all articles. --Zundark (talk) 12:45, 31 December 2007 (UTC)
Reducing this article
As a first step in fighting the current proliferation of articles on Boolean algebra, I am going to remove some redundancy from this one. Vaughan Pratt has done an excellent job of writing an introduction (under the title Boolean algebra (introduction)) that is both accessible by a general audience and reasonable for mathematicians. Therefore it seems reasonable to cut off some of the more elementary material here that is also presented in the introductional article. I am also going to shift the focus slightly towards lattice theory, an aspect that is still a bit underdevelopped in all articles. --Hans Adler (talk) 22:04, 27 January 2008 (UTC)
Math notation
I've replaced a lot of the formulas with math notation, primarily because Firefox 3 (unfortunately) does not render the ∨ (logical and) character (I said IE in my edit summary by mistake; I was actually using Firefox at the time). It may also not be supported by IE6 but I haven't checked. All formulas should still render as text if you have the right option selected in your preferences. Dcoetzee 20:34, 7 December 2008 (UTC)
Possible move to Boolean lattice
Does anyone object to moving (renaming) this page to Boolean lattice, which currently redirects here? — Carl (CBM · talk) 19:08, 21 April 2009 (UTC)
- I would have done it boldly, but the redirect has a history and Carl (whom I asked) is a bit more cautious than I am. Here is the rationale:
- This article had 7686 hits in March, compared to 595 for modular lattice. To me this suggests that most of these hits are from readers looking for boolean algebra (logic) or boolean logic. Until I fixed this today, the article was the first on the disambiguation page boolean algebra; renaming makes it even clearer (especially to Google) that the article is not about elementary school material.
- We currently have no less than 3 articles named "boolean algebra (something or other)" and one article boolean algebras canonically defined.
- Boolean algebras are basically the same objects as boolean lattices, and the homomorphisms are also the same. By moving to the unique name we can avoid the unfortunate name clash. (This is recommended by WP:NCDAB.)
- --Hans Adler (talk) 19:40, 21 April 2009 (UTC)
I do object to this idea. Boolean algebra is the standard name. It would be more convenient for us if the standard name were Boolean lattice, but it isn't, and there's nothing we can do about it. --Trovatore (talk) 20:41, 21 April 2009 (UTC)
- I would also add that I'm less than convinced by the data from the comparison with the modular lattice article. Boolean algebras are a widely studied topic with a large diffusion in the literature; modular lattices I think I just heard of today. While it's certainly plausible that a certain number of readers aren't just sure of the distinction between "logic" and a "structure", and wind up at the wrong article, these data themselves don't appear to indicate that it's a huge problem. If there were no misnavigation at all, I would frankly expect the discrepancy between the two articles to be greater than this. --Trovatore (talk) 01:33, 22 April 2009 (UTC)
- I agree with Trovatore. Paul August ☎ 04:39, 26 April 2009 (UTC)
At least Semilattice has the sensible approach of not forking the article based on the approach (order vs algebra). That is lacking here. Tijfo098 (talk) 23:06, 24 March 2011 (UTC)
- The problem is not so much order vs algebra, it's more that (at least in US college curricula) boolean algebra (logic) or boolean logic are standard freshman-level computer science topics while the subject of this article is more something one would see in an upper-division modern algebra class for mathematics majors only. They have different audiences, neither of which would find what they are looking for in an article written for the other audience. Possibly boolean algebra (logic) and boolean logic could be merged, though, as they're on similar topics and the boolean logic article is a mess. —David Eppstein (talk) 01:13, 25 March 2011 (UTC)
- It was clear in 2006 that Boolean logic had too many problems to fix incrementally, and I rewrote it from scratch. The result was then subsequently moved to Boolean algebra (logic) so as to pair it more naturally with Boolean algebra (structure). The author of the original Boolean logic article, User:StuRat, then revived it in its original problematic form without bothering to address any of the many criticisms made of it (and apparently not understanding them either). Ideally Boolean logic would be merely a redirect to one of Boolean algebra, Boolean algebra (logic), or Introduction to Boolean algebra, but until the debate over the appropriate organization of the main article(s) is settled there isn't a good case for implementing the redirect, so in the meantime Boolean logic continues to exist as a blot on the landscape. --Vaughan Pratt (talk) 19:53, 25 March 2011 (UTC)
- There's a massive discussion on talk:Boolean algebra. If you have something new to add, would be better to comment there. If possible, contribute things that tend to reduce rather than increase the number of open issues. --Trovatore (talk) 01:21, 25 March 2011 (UTC)
- Excellent advice, Trovatore. I hope everyone involved follows it. --Vaughan Pratt (talk) 19:53, 25 March 2011 (UTC)
The lack of usefulness of this page in general
As usual, Wikipedia pages on mathematical topics are virtually useless to anyone who actually needs to use them. If you can understand this technical gobbledygook, then you already know mathematics well enough, probably, to have little need for a wikipedia page on this topic.
those of us who are just learning this stuff can't even decipher the page. I hope contributors to wikipedia pages do not actually teach students using the same way they write Wikipedia pages.
How about making a list that shows how to translate each of the operations into standard mathematical operations-- like multiplication or addition, without using technical mathematical jargon? —Preceding unsigned comment added by 72.234.37.70 (talk) 20:50, 3 October 2009 (UTC)
- Hi 72. Is it possible you're looking for Boolean logic or Boolean algebra (logic)?
- Perhaps not, since you talk about multiplication and addition, which are more appropriate to algebraic structures. I'm afraid the usual operations in a Boolean algebra do not directly translate into multiplication and addition, although you can recombine them into operations that do so correspond — see Boolean ring for more information.
- Regarding your remarks about teaching: Wikipedia's purpose is not in fact to teach. It's a reference work, not a textbook. It's a valuable resource for self-teaching; this is a subtle but important distinction.
- Constructive criticism as to how to make it more useful for self-teaching, while not detracting from its quality as a reference work, is always welcome, and I take the remarks about multiplication and addition in that spirit. I hope I've explained why I don't think talking about multiplication and addition would actually be all that helpful here. --Trovatore (talk) 21:35, 3 October 2009 (UTC)
- Indeed. I would be in favour of a "didactic" approach, starting with the simplistic notion of Boolean algebra as an algebra of elements that can only be TRUE or FALSE and involve operators like AND and OR, and then perhaps embark on the generalisations mathematicians are so fond of. I am aware that for a genuine mathematician, the only reposible route is the other way round, but, indeed, Wikipedia primarily targets non-experts. Rbakels (talk) 15:14, 8 June 2011 (UTC)
- I guess you are looking for the article Boolean algebra. This article is about something that is almost exclusively of interest to mathematicians, which is of course not true for Boolean algebra. The similar names (Boolean algebra the theory vs. Boolean algebras the structures) is no accident. You can think of the structures as the "advanced" concept behind the "simple" algebra. Hans Adler 15:29, 8 June 2011 (UTC)
- Right. I was mistaken. Would you agree that the title of the lemma is confusing? Adding the word "structure" in brackets is not very clarifying. Perhaps "advanced topics" is clearer. Rbakels (talk) 20:29, 8 June 2011 (UTC)
- No, it's not about "advanced topics in Boolean algebra" in general; that's a misunderstanding. (I don't think it's really what Hans meant either.) This article is about a particular sort of structure, in the mathematical sense of the word structure, which is itself not really understood by the general public. When we were originally debating it, other possibilities were Boolean algebra (algebraic structure), Boolean algebra (mathematical structure), and Boolean algebra (object).
- I don't exactly recall the arguments by which this one won out over those. I'm not enthusiastic about relitigating the issue, but I could live with any of those three titles if others preferred. --Trovatore (talk) 21:09, 8 June 2011 (UTC)
- Right. I was mistaken. Would you agree that the title of the lemma is confusing? Adding the word "structure" in brackets is not very clarifying. Perhaps "advanced topics" is clearer. Rbakels (talk) 20:29, 8 June 2011 (UTC)
1st axiomatization?
Ok, so who gave that? There are ton of engineering books saying that Boole discovered the Boolean algebras, but that is contradicted by [1]. There is also an monograph (ISBN 981-283-454-0) that has oodles of axiomatizations, but it's not organized historically, so it's hard to find the answer in there. Tijfo098 (talk) 12:15, 27 March 2011 (UTC)
- First comment from Vaughan Pratt in this section of the Boolean algebra talk page gives some answers. --Hugo Herbelin (talk) 12:42, 27 March 2011 (UTC)
- Thanks, that is quite in-depth. However, given the WP:OR rules here, perhaps this is all we can say given the proto-mathematical way (relative to today's standards) in which Boole wrote: "Boole's algebra was connected with the origins of both abstract algebra and symbolic logic." "Boolean algebra was perfected by Jevons, Schröder, Huntington, and others until it reached the modern conception." Tijfo098 (talk) 13:26, 27 March 2011 (UTC)
Contradiction in definition
In the Definition section: "A Boolean algebra is a six-tuple [...] and two elements 0 and 1 [...]"
Later: "A Boolean algebra with only one element is called [...]"
??? Gwideman (talk) 00:16, 27 August 2012 (UTC)
- As the article says, some authors require 0 and 1 to be distinct, others do not. Paul August ☎ 00:38, 27 August 2012 (UTC)
- The usual convention in mathematics is that, unless the text says that things have to be distinct, they might be identical. Thus "two elements" can be the same element twice; "two distinct elements" could not. — Carl (CBM · talk) 01:44, 27 August 2012 (UTC)
- Ah, the "one element" statement is really talking about the case where there are still two elements in the six-tuple, it's just that the two elements symbolized as 0 and 1 (⊥ and ⊤) are not distinct values. The point of confusion was that if there was literally "only one element" then the algebra would consist of only a five-tuple, and the identity and complements axioms would have to be written differently. Gwideman (talk) 23:35, 27 August 2012 (UTC)
- No, in that case it would be a six-tuple, two of whose entries are equal. The axioms would not change, but the symbols 0 and 1 would denote the same value. --JBL (talk) 03:30, 28 August 2012 (UTC)
- Do we really want to define a Boolean algebra as a "six-tuple" anyway? For my taste this is too "implementation-specific" and not very informative. Can't we say that a Boolean algebra is a set, equipped with two binary operations and one unary operation, and having two distinguished elements? It's not that much more intuitive, but it's at least a small improvement. --Trovatore (talk) 04:50, 28 August 2012 (UTC)
- No objection from me. Though it doesn't solve Gwideman's confusion, it seems like a completely sound idea. --JBL (talk) 13:41, 28 August 2012 (UTC)
- Fine with me. Paul August ☎ 21:36, 28 August 2012 (UTC)
- Do we really want to define a Boolean algebra as a "six-tuple" anyway? For my taste this is too "implementation-specific" and not very informative. Can't we say that a Boolean algebra is a set, equipped with two binary operations and one unary operation, and having two distinguished elements? It's not that much more intuitive, but it's at least a small improvement. --Trovatore (talk) 04:50, 28 August 2012 (UTC)
- No, in that case it would be a six-tuple, two of whose entries are equal. The axioms would not change, but the symbols 0 and 1 would denote the same value. --JBL (talk) 03:30, 28 August 2012 (UTC)
Thanks for your responses! At this point, I understand what this is trying to say. But the more I look at it, the more I think that the "is a six-tuple" is a red herring -- why not just say "A Boolean algebra has six features: a set A..." etc.
Also, would there anything wrong with specifically saying that the "two elements" are the values which the elements of A are allowed to take on, and which are allowed as the results of expressions?
Then instead of the obtuse statement "A Boolean algebra with only one element is called a trivial Boolean algebra", we could have something more concrete like "The most familiar Boolean algebra allows two distinct values for elements of A, and results. If instead the two values are the same, the axioms still hold in a trivial way, and this is termed a "trivial Boolean Algebra".
Finally, I note that this decription has variables (here a, b and c). These are not mentioned explicitly as a feature of Boolean algebra (ie: as part of the six-tuple), unless they are implied by "set A". Clearly it's intended that set A could contain 0 and 1, but what is it that lets us know that the set A can contain variables? If variables are a sort of metafeature of set description, and actually the set can contain only values, then how does a set with more than two members (0 and 1) arise to correspond to a, b and c? Gwideman (talk) 23:24, 31 August 2012 (UTC)
Finite/Cofinite subsets?
I noticed that the text claims that the finite or cofinite subsets of an arbitary set S is a Boolean algebra, but that it didn't define the operations. Obviously meet and join are union and intersection, but what is the negation operation? It certainly can't be set-theoretic complement. 67.79.154.194 (talk) 23:25, 27 December 2012 (UTC)
- the article (which could be clearer on this point) asserts that the collection of subsets that are finite or cofinite forms a Boolean algebra. That is, all of the finite subsets together with all of the cofinite subsets. So complementation is indeed the negation. --JBL (talk) 01:21, 28 December 2012 (UTC)
Synopsis of axiomatizations
I'm wondering about the different axiomatizations of Boolean algebras found in the literature and started the synopsis shown below (additional columns are welcome!). A "." in a cell means that the law of the row is not used by the axiomatiation of the column, all other entries mean it is used, and give some reference (rank of appearance for WP, SEP, page number:law name for DP and Bir) to ease verifying.
The article "Lattice_(order)" shows that Absorption implies Idempotency and states that Distributivity implies Modularity, using the lattice properties. Birkhoff proves that one Distributivity law implies the other, using Commmutativity, Associativity, and Absorption. However, some confusion seems to have happened in his book, as L6 is presented before L5 (which in turn would not be needed), while L7 is not defined at all. Absorption + Complement implies Identity (x∨0 = x∨(x∧¬x) = x).
I'm unable to see whether all axiomatizations are equivalent, but I'd like to know that. Maybe, at least the main variants could be mentioned in the article. In particular: isn't Absorption missing for sure?
WP | [SEP] | DP | Bir | |
Commutativity | ||||
x ∨ y = y ∨ x | 2 | 1 | 109:L2 | 8:L2 |
x ∧ y = y ∧ x | 2 | 2 | 109:L2 | 8:L2 |
Associativity | ||||
x ∨ (y ∨ z) = (x ∨ y) ∨ z | 1 | 3 | 109:L1 | 8:L3 |
x ∧ (y ∧ z) = (x ∧ y) ∧ z | 1 | 4 | 109:L1 | 8:L3 |
Distributivity | ||||
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) | 4 | 5 | 131 | 11:L6' |
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) | 4 | 6 | . | . |
Absorption | ||||
x ∨ (x ∧ y) = x | . | 7 | 109:L4 | 8:L4 |
x ∧ (x ∨ y) = x | . | 8 | 109:L4 | 8:L4 |
Complements | ||||
x ∨ ¬x = 1 | 5 | 9 | 144 | 17:L8 |
x ∧ ¬x = 0 | 5 | 10 | 144 | 17:L8 |
Identity | ||||
x ∨ 0 = x | 3 | . | 144 | . |
x ∧ 1 = x | 3 | . | 144 | . |
De Morgan | ||||
¬(x ∧ y) = ¬x ∨ ¬y | . | . | . | 17:L10 |
¬(x ∨ y) = ¬x ∧ ¬y | . | . | . | 17:L10 |
Double Negation | ||||
¬¬x = x | . | . | . | 17:L9 |
Modularity | ||||
x ≤ z ⇒ x ∨ (y ∧ z) = (x ∨ y) ∧ z | . | . | . | 12:L5 |
Idempotency | ||||
x ∧ x = x | . | . | 109:L3 | 8:L1 |
x ∨ x = x | . | . | 109:L3 | 8:L1 |
- DP: B.A. Davey, H.A. Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press.
- Bir: Garrett Birkhoff (1967). Lattice Theory. Colloquium Publications. Vol. 25. Am. Math. Soc.
Jochen Burghardt (talk) 20:41, 5 September 2013 (UTC)
- Hmm ... absorption was included in the definition until this edit. Paul August ☎ 21:10, 5 September 2013 (UTC)
- Thanks! I found the cited paper at http://www.ams.org/journals/tran/1933-035-01/S0002-9947-1933-1501684-X/S0002-9947-1933-1501684-X.pdf and start reading it. Jochen Burghardt (talk) 07:11, 6 September 2013 (UTC)
- It seems I'd better read "Edward V. Huntington (1904). "Sets of Independent Postulates for the Algebra of Logic" (PDF). These Transactions. 5: 288–309.", where Huntington presents his "First axiom set"; the latter seems to be identical with the WP axioms. Jochen Burghardt (talk) 08:15, 6 September 2013 (UTC)
- The definition we should be using here is the "standard" one (whatever that is). I suspect that such a definition probably includes Absorption. In any case whatever definition we use should cite a standard reference work not a research paper. Paul August ☎ 17:25, 6 September 2013 (UTC)
- Ok, I adapted the axiomatization to Davey.Priestley.1990, but added a remark (and 2 boxes) about Huntington. Jochen Burghardt (talk) 14:38, 7 September 2013 (UTC)
- Alternative axiomatizations for Boolean algebras, and their history, are an interesting topic. However, the current form of the section is confusing: it doesn't say what Whitehead's axioms were, it doesn't say where the current axiomatization (used in the Definition section) fits in (is it the same as Whitehead's?); it's not clear why it says "even proving the associativity laws"; etc. The "Proven properties" box seems unnecessary; showing the dual forms of every equation seems unnecessary; labelling the axioms with Idn/Cmm/etc. seems unnecessary; repeating the content of the Robbins algebra seems unnecessary. --Macrakis (talk) 17:50, 7 September 2013 (UTC)
- I'll try to find out what Whitehead's axioms were, and then supplement them, and relate them to the current axiomatization (by Davey+Priestley). Do you suggest to have a different axiomatization in the article?
- ((done: Whitehead.1898)) Jochen Burghardt (talk) 20:49, 7 September 2013 (UTC)
- The text says "even proving the associativity laws", because this is unusual, they are normally required as axioms. I was really impressed when I read Huntington's 1904 article. Maybe rephrasing as "which doesn't even require associativity axioms" is more clear?
- The "Proven properties" box is intended for readers (like me) who wish to see how certain properties are proved (click on "show" to look at a proof); axioms and properties are referred to by their labels ("Idn" etc.) in the proofs; this is the purpose of these labels. I think such proof-boxes could be an(other) advantage web-base encyclopedias have over paper based ones: they do not take considerable space when collapsed (by default), nor do they distract a reader who is not interested in them; but then can provide valuable information to an interested reader.
- I included all dual formulas as I found this in a similar way in section "Definition" of the article; they could be omitted in the boxes, adding an appropriate remark on dual forms (and their labels, as e.g. E2 is used in the proof of H1). On the other hand, they use space only if the box has been expanded.
- The text on the Robbins algebra has not been written by me; it is in fact a lot of repetition. Maybe, the "Robbins algebra" article should be merged and redirected into the section "Boolean_algebra_(structure)#Axiomatics", or even an own subsection "Boolean_algebra_(structure)#Robbins algebra" (to be created)? - Jochen Burghardt (talk) 19:21, 7 September 2013 (UTC)
- I'll try to find out what Whitehead's axioms were, and then supplement them, and relate them to the current axiomatization (by Davey+Priestley). Do you suggest to have a different axiomatization in the article?
- Alternative axiomatizations for Boolean algebras, and their history, are an interesting topic. However, the current form of the section is confusing: it doesn't say what Whitehead's axioms were, it doesn't say where the current axiomatization (used in the Definition section) fits in (is it the same as Whitehead's?); it's not clear why it says "even proving the associativity laws"; etc. The "Proven properties" box seems unnecessary; showing the dual forms of every equation seems unnecessary; labelling the axioms with Idn/Cmm/etc. seems unnecessary; repeating the content of the Robbins algebra seems unnecessary. --Macrakis (talk) 17:50, 7 September 2013 (UTC)
- Ok, I adapted the axiomatization to Davey.Priestley.1990, but added a remark (and 2 boxes) about Huntington. Jochen Burghardt (talk) 14:38, 7 September 2013 (UTC)
- The definition we should be using here is the "standard" one (whatever that is). I suspect that such a definition probably includes Absorption. In any case whatever definition we use should cite a standard reference work not a research paper. Paul August ☎ 17:25, 6 September 2013 (UTC)
- It seems I'd better read "Edward V. Huntington (1904). "Sets of Independent Postulates for the Algebra of Logic" (PDF). These Transactions. 5: 288–309.", where Huntington presents his "First axiom set"; the latter seems to be identical with the WP axioms. Jochen Burghardt (talk) 08:15, 6 September 2013 (UTC)
- Thanks! I found the cited paper at http://www.ams.org/journals/tran/1933-035-01/S0002-9947-1933-1501684-X/S0002-9947-1933-1501684-X.pdf and start reading it. Jochen Burghardt (talk) 07:11, 6 September 2013 (UTC)
- Although of course Huntington is an important figure in the axiomatization of Boolean algebra, I don't get the impression that the Huntington axiomatization is considered as a core part of the subject today. I am not an expert -- but for example, Paul Halmos's textbook relegates it to an exercise; see Gratzer's Lattice Theory for an example of how various axiomatizations are covered [2]. R. Padmanabhan and S. Rudeanu [http://www.amazon.com/Axioms-Lattices-Boolean-Algebras-Padmanabhan/dp/9812834540 Axioms For Lattices And Boolean Algebras] certainly discuss it, but that's a book-length treatment -- which also mentions that Huntington proposed multiple axiomatizations. --Macrakis (talk) 20:40, 7 September 2013 (UTC)
Derivation of the order
Currently, the definition section contains these lines:
- It follows from the last three pairs of axioms above (identity, distributivity and complements) that
- a = b ∧ a if and only if a ∨ b = b.
- It follows from the last three pairs of axioms above (identity, distributivity and complements) that
I wonder how that is. Even if it is indeed so, wouldn't it be simpler to attribute this corollary to commutativity and absorption instead? 2A02:8109:9340:42C:8410:961C:6FA1:7170 (talk) 01:05, 11 February 2014 (UTC)
Citation for the existence of an isomorphism between Boolean algebras and Boolean rings
It would be nice to simply state that Boolean algebras and Boolean rings are isomorphic in the lead section, if such an isomorphism exists. Does anyone have such a source for the footnote citation? User:David Eppstein, do you know of one? —wing gundam 01:45, 3 May 2015 (UTC)