Talk:Boolean algebra (logic)

Article has been replaced

[Added on 9/24/2007] The second replacement has now happened and seems to have generated no controversy after two months, except for the "brick wall of text" remark below, with which I fully agree and may try to do something about at some point by breaking up paragraphs and supplying lots of diagrams and pictures. The rest of this talk page deals with the first replacement---since it all refers to a now historic article it may as well be archived appropriately in its entirety. Since I'm likely to break something attempting that, would someone good at archiving who agrees with this please do the honors? Thanks. --Vaughan Pratt 21:11, 24 September 2007 (UTC)

The article originally here has been moved to Boole's syllogistic. If you would like that article restored to this name, please vote to do so here:

Oppose. StuRat 13:18, 18 September 2005 (UTC)

Oppose. (I never liked that name for it, anyway.) Arthur Rubin 20:46, 24 September 2005 (UTC)

I don't think this is currently a live issue. Wait till Charles gets around to fixing up Boole's syllogistic; then maybe it'll be clearer what it should be called. The current Boolean logic should certainly be moved at some point, but primarily because it's not a good name for the article, not to make space for the "syllogistic" article. --Trovatore 21:27, 24 September 2005 (UTC)

Intent of this article

This is written for those who use Boolean applications in electronics and computers, and those taking classes in Boolean logic in school. It is not intended for PhDs in mathematics. The article Boolean algebra is written with that audience in mind. StuRat 13:35, 18 September 2005 (UTC)

New article is under construction

I still want to work on the transitions between sections, which I expect to finish within a week. StuRat 13:18, 18 September 2005 (UTC)

Suggested changes

I will take any suggestions for changes to this article under advisement. I would prefer if you wait a week before making major changes yourself. If you find a spelling error, etc., please go ahead and fix it yourself, though. StuRat 13:19, 18 September 2005 (UTC)

  This article is a brick-wall of text, would be nice to see some more air and use of figures 148.122.181.240 02:52, 24 August 2007 (UTC)

To add

Here's a list of things I would like to add:

A) Applications:

1) Digital computers - bit and image manipulation using Boolean operations. Provide links for right shift, left shift, 1's complement, and 2's complement; but don't spend any time on them.

2) CAD - union / intersection / subtract /splits (performed using element of "n-1" dimensions) , etc.

a) 2D CAD/drafting/drawing/architecture software - such as patterns for wood paneling having the area inside a window frame subtracted.

b) 3D surfacing packages

c) 3D solid modeling packages

3) Database - discuss "UNION" and "UNION ALL" SQL statements

B) Transitions:

1)Transition into sets

2)Transition out of sets - talk about Boolean algebra of two elements/states to transition to truth tables.

C) Graphics

1) Provide links for each symbol to an image page (for use by those with browsers which don't support set notation symbols). Also add text explaining the links.

StuRat 19:23, 18 September 2005 (UTC)

Rename this article ?

I don't particularly mind the move of what used to be here to Boole's syllogistic, but I don't think "Boolean logic" is really going to work as a name for this article. For parts of the article, such as "Properties" and "Truth tables", it would be a good name if we were naming things ourselves, but we shouldn't be doing that. As far as I know there is no common usage of the phrase "Boolean logic" to represent these topics.

For the stuff about the algebra of sets, it's not even a good name. That isn't logic at all; it's baby set theory. Logic is about propositions and sets aren't propositions. --Trovatore 16:08, 18 September 2005 (UTC)

I think this is the best place for this content because:

1) The article that was here didn't seem to be about "Boolean logic".

2) This content needed a home, and the old name was clearly unsatisfactory.

3) I disagree with you that this content is not "Boolean logic". I believe that it is. It also includes material from related areas; however, I believe that is permissable. For example, in an article on DC power, I would expect to see some mention of AC, particularly the similarities and differences between the two, and perhaps Edison's pro-DC / anti-AC bias.

In short, while this may or may not be the ideal placement, I believe it is a substantial improvement over the previous situation. StuRat 17:13, 18 September 2005 (UTC)

BTW, just what type of things would you like to see in an article about "Boolean logic" ? Perhaps I can tweak the content of the current article to include that material. StuRat 17:17, 18 September 2005 (UTC)

It's not that there's stuff I call "Boolean logic" that's missing; it's that much of the material already here doesn't belong under that name (specifically, the algebra-of-sets material). But maybe even that's not the main issue.

Here's the thing: People were frustrated because they came to the Boolean algebra article expecting to be able to read it, because they'd studied "Boolean algebra" in school. The reason they couldn't read it wasn't that it was too technical, but rather that it was about a different topic entirely, but there was no easy way for them to figure that out. So we want a place to redirect them. Now, is it reasonable to call that place "Boolean logic" when it's (1) not primarily about logic and (2) not a name they've ever heard? --Trovatore 17:36, 18 September 2005 (UTC)

I believe that to the masses, Boolean logic and Boolean algebra are synonymous, much like speed and velocity. While there is a difference, they would likely figure out that if one article doesn't have the info they need, perhaps the other will. I've provided a "dab" to direct them here, with as descriptive language as I could come up with, for what they will find here. I can't come up with a better way to tell them "Hey buddy, you want this article !", at least nothing short of adding a disambiguation page. That, unfortunately, would upset many of the PhDs who don't want the current article under Boolean algebra moved, since they would argue "it's the only VALID article on Boolean algebra, the rest is just computer and electronics crap that doesn't count." StuRat 17:43, 18 September 2005 (UTC)

You may be assuming an attitude that doesn't exist. Personally I wouldn't be opposed to a solution that included moving the current Boolean algebra to something like Boolean algebra (mathematical structure) or Boolean algebra (algebraic structure). Of course that by itself doesn't solve the problem of what to call the current Boolean logic article. BTW this is also discussed on the Wikipedia talk:WikiProject Mathematics page.

I'd like to add that your dab notice at the top of Boolean algebra looks fine. Perhaps it could be adapted into the first sentence of the current Boolean logic article -- that sentence is neither accurate nor descriptive of the content of the article. --Trovatore 18:31, 18 September 2005 (UTC)

I wouldn't mind doing that, but Oleg added that part, and you two math PhDs do seem to disagree on everything. What do you think Oleg ? StuRat 19:40, 18 September 2005 (UTC)

StuRat: I don't think anyone is saying that the current article at Boolean algebra can't be moved. And I don't think anyone has said it is the only valid article on Boolean algebra. In fact there have been several suggestions in various places to name either or both of these articles Boolean Algebra (something), we just haven't yet come up with a consensus what that (those) something(s) should be. And it is certainly not the case that anyone thinks that the other Boolean algebra is "crap". I don't know where you are getting that from? The situation is that there are two different things that are unfortunately both called "Boolean algebra". Both are important. Please believe me when I say that I am very familiar with both of these concepts. I have a background in both computer science, and mathematics and I've been thinking and dealing with both concepts for over thirty years. I think I fully appreciate the importance and the significance of both. On a more personal note, It sounds like you are feeling a bit frustrated. I'm sorry if that is so. If you think that some of us are being unreasonable, then I apologize. But you might want to consider the possibility that you are misunderstanding things. Paul August ☎ 18:48, 18 September 2005 (UTC)

Wow, someone with experience in both areas ? Sounds like you might be able to help us out. I do feel a bit frustrated, in that most of the comments seem to be destructive ("this is no good as is") not constructive ("it could be improved by doing this..."). My own math experience doesn't go beyond basic calculus, so I'm looking at it primarily from the programmer's point of view. StuRat 19:34, 18 September 2005 (UTC)

Well I have been trying to help out. And again I'm very sorry you are feeling frustrated. But again I think you may be blowing things out of proportion, and some of the things you consider to be "not constructive" may come from your lack of knowledge about some of these things. Did someone actually say "this is no good as is"? Frustration can also come from differences in pace. You may think that all should be resolved in a day or two, when the rest of us are perhaps working with a different time frame in mind. If so I would suggest trying to be more patient and keep in mind there is no real hurry to any of this. Paul August ☎ 20:52, 19 September 2005 (UTC)

By the way I would like to point out that others here (e.g. Travatore) probably know as much about this stuff as I do, and I think they have also been trying to help out, and from what I've seen, their remarks have all been constructive. Paul August ☎ 21:04, 19 September 2005 (UTC)

So it is true that I have sometimes pointed out a problem without suggesting a solution. That's generally because I didn't have a solution, or at least not a clear preferred one.

StuRat, I'd like to assure you that your efforts are appreciated. The collaborative process is not always pleasant, but in the end we'll have improved the Wikipedia, and you can be proud of having provided an article that was clearly lacking. --Trovatore 21:14, 19 September 2005 (UTC)

Constructive comments

In case anyone has forgotten what I said in Talk:Boolean algebra (basic concepts):

It now seems to me that this article should be split up among

• algebra of sets
• Truth tables to somewhere in logic
• "Boolean terms" sections to elsewhere in logic, or a separate subject (they need to be defined, anyway).
• Applications to a separate article

With disambiguation pages from Boolean algebra and Boolean logic.

Arthur Rubin 00:14, 17 September 2005 (UTC)

I would like to make more detailed constructive comments, now.

The Terms section should be greatly simplified, and amplified by links to algebra of sets and the analogous algebra of propositions (approximately the same degree of formality as algebra of sets). I'll have to defer to StuRat about whether "sets" or "propositions" are more commonly used in the applications he's familiar with -- I would have thought it would be "propositions".

Simplified how ? I've never heard the term "propositions" used in programming. "Sets" is used rarely. More often, a specific application term is used. For example, database programmers refer to "joining tables", rather than "joining sets", although tables can certainly be viewed as sets of records. StuRat 19:05, 21 September 2005 (UTC)

Specific suggestions:

Remove "Subset/Superset" relationships, unless you're going to use them in this article.

Wikilink binary operator to binary operation, and unary operator to unary operation. (I'd do it myself, except I'm not sure that your meaning exactly matches "ours".)

Add a link from that section to algebra of sets

Conditions, assumptions, or assertions are the appropriate terms using in programming -- or at least, the sort of programming I do. I suggested propositions or predicates because they are closer to being technically correct. Sets are only used in alternative formulations of database programming. However, what I had in mind is an alternative formulation of your terms section (which could have been included in algebra of sets, whether or not it was) by referring to possible characterizations of the universe, such as (English) "The sun is shining", (Computer programming) "The input quantity street_number is odd", (mathematics) $b^{2}-4ac=0$, or (digital circuit design), a (specified) switch is "on".

Arthur Rubin 20:43, 24 September 2005 (UTC)

The use of Boolean terms sections need to be prefaced by a definition of Boolean terms.

It was my intent to define Boolean terms within the general Terms section. AND and OR were described under binary operator, I've now added XOR there, as well. The pic and caption on the right illustrates each of those terms. StuRat 19:49, 21 September 2005 (UTC)

I meant a definition of the term "Boolean terms". Sorry not to be more clear. -- Arthur Rubin 20:43, 24 September 2005 (UTC)

And you're wrong about the mathematical use of XOR in this context. The quadratic formula,

$x={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}$,

is perfectly valid even if

$b^{2}-4ac=0$.

What I was trying to say is that the answer is usually the positive OR the negative, but NOT BOTH simulaneously. If the quadratic formula is used to find an object's width, for example, the width can be one value or the other, but the obect can't have two widths simultaneously (unless we go into the theory of parallel universes collectively containing every possibility simultaneously). I added an exception for the case of $\pm$0. StuRat 19:20, 21 September 2005 (UTC)

I find that misleading. I wish you'd drop it. I'm not saying I'd necessarily insist on its removal in the final version, but consider expressions with more than one $\pm$: you not be able to pull up equal alternatives merely by looking at whether the argument of $\pm$ is 0. -- Arthur Rubin 20:43, 24 September 2005 (UTC)

(As an aside -- why is my second formula so much smaller than the first?)

Because the software was able to render it as HTML--Trovatore 18:30, 21 September 2005 (UTC)

Sometimes, the "alternative or" (neologism -- I've never taken a course in the grammar of mathematics) is used in mathematics -- the meaning is "inclusive or", with the side assertion that both expressions cannot both occur.

Arthur Rubin 18:28, 21 September 2005 (UTC)

---

So I see Arthur's points; his proposal splits up an agglomeration of related, but not unified, things, into logically distinct topics. But I don't really agree. In common usage "Boolean algebra" seems in fact to be a collection of topics, rather than a single one, much as "algebra" is a collection of topics. We do need an article on that collection of topics, because so many people are looking for it.

The intro needs to explain that it's a collection of topics, and the relationships among them need to be better explored.

Like Arthur, I'm a bit surprised that StuRat emphasizes the algebra-of-sets material, especially given that he says he's coming at it from a programmer's point of view. Programmers, as far as I know (and I have been one, from time to time) have relatively little use for sets, but a lot of use for the true-false semantics. --Trovatore 18:38, 21 September 2005 (UTC)

But maybe I misunderstood--I thought Arthur meant to split the material up into separate articles. Maybe he was talking about the organization of a single article. --Trovatore 18:41, 21 September 2005 (UTC)

I take his comments to mean my article should be scrapped and pieces put in other places. I strongly disagree, and think an "introduction" to all these related concepts is needed in one place, for novices. Links can certainly be provided for more detail in each area, however, as I've attempted to do. StuRat 18:59, 21 September 2005 (UTC)

You've interpreted my comments correctly, although I'm willing to withdraw the suggestion provided that you only include the minimal amount in each section for understanding, and provide appropriate links (which you haven't yet completed). -- Arthur Rubin 20:43, 24 September 2005 (UTC)

Please list those links which you would like to see included. StuRat 15:39, 5 October 2005 (UTC)

Temporary pause

I'm going on vacation this week, so won't have much opportunity to do editing. In the meantime, I would like to know what everyone thinks about the links I added for some of the symbols, so readers on browsers which don't support those characters can pick the link to view the image. I'd have preferred to put the pics directly in the text, to avoid the problem in the first place, but Wiki doesn't seem to do pics as part of text very well. StuRat 02:31, 25 September 2005 (UTC)

$\pm$ and XOR

I still do not concur $\pm$ is always OR, and sometimes XOR. Discussion? Arthur Rubin | (talk) 00:16, 30 November 2005 (UTC)

AfD discussion

Perhaps someone didn't understand how to do a merjer. Here's the process:

1. Pick whichever article has the better name. In this case, I would say it's the

  article specifying "elementary".

2. Ensure that this is the superior article in content, too. 3. Replace the inferior article with a redirection to the superior article.

  (The redirection might work if you simply insert it, but I've never tried that).

Brewhaha@edmc.net 03:19, 14 July 2007 (UTC)

Sixteen functions?

I was reading a book about electronic logic design, and it stated without giving any examples that: "in fact there are 16 possible boolean functions of two variables (2 input gates), but in practice only six are commonly used, AND, OR, NOT, NAND, NOR and XOR". I can find no further information about this - what on earth are the other ten? Try as I might I can't really imagine them, unless they are trivial ones such as always 1 or always 0... anyone got any insight into this, or were the book authors wrong? Graham 23:33, 5 January 2006 (UTC)

Ah, I found this: [1], which sheds some light. Graham 23:37, 5 January 2006 (UTC)

Logical XOR in English

In the text of this article I noticed it said

[QUOTE] Also note that the word OR in English may correspond with either logical OR or logical XOR, depending on the context:

"I start to sweat when the humidity OR the temperature is high." (logical OR) "I'm planning to have chicken OR beef for dinner." (logical XOR) [END QUOTE]

But their is a problem with the second example, I possible could have beef and chicken for dinner, many dishes have both. While I understand what the author is saying (and I realize this is quite stupid) I think this article deserves a better example (even if most people will only have one OR the other.) If everyone else agrees, I propose the author change example 2 too something along the lines of:
"Now turn right OR left." Or some other statement that can only take the XOR operator.

That does seem rather picky, but I'll go ahead and change the example as you suggest. StuRat 02:27, 19 February 2006 (UTC)

I don't think that helps. If I say "turn right or left", I'm not really forbidding you to do both; it might be impossible for you to do both, but that's not my fault. So this "or" can just as well be read as inclusive. Really I think the original version is better. A still better example might be a parent saying to a child "you can have ice cream or candy", the clear implication being that "both" is not an option. --Trovatore 02:34, 19 February 2006 (UTC)

No, that is not clearer. A situation where it is clearly impossible to choose both is much more suitable than a situation that depends on external factors irrelevant to the math.  freshofftheufoΓΛĿЌ  02:16, 15 September 2006 (UTC)

I completely disagree. If it's impossible to choose both, then there's no distinction between inclusive and exclusive "or", so the "or" might just as well be understood to be inclusive. --Trovatore 02:18, 15 September 2006 (UTC)

Here's more of a situational example. If two people are making a decision on whether or not to do something, there is no need for discussion if they already agree (both say yes or both say no), but discussion will take place if there is disagreement (if one says yes and the other says no). In this case, the yes or no is the true or false input, with whether discussion will take place being the XOR output. I don't know if it's any clearer, but it's coming at it from a different perspective. --Carl ^{(talk|contribs)} 03:39, 15 September 2006 (UTC)

I think both you and Freshgavin may be forgetting the context a bit. The discussion is not about what XOR means. It's about under what circumstances the English word "or" means XOR. Carl, your example just doesn't work in that context. "John and Mary will argue if John or Mary wants to go." It sounds like gibberish; it's not a case where the "or" is naturally read as XOR. --Trovatore 03:44, 15 September 2006 (UTC)

In my mind, XOR is more of an "or...but" statement instead of just an "or" statement. For example, John and Mary will argue if John or Mary wants to go but the other one does not. As far as the use of mutually exclusive options, I think the only way you can logically translate a statement as XOR where "or" is the only conjunction is when mutually exclusive options exist. Otherwise, there would need to be something specified (generally via another conjunction) that would indicate this. As XOR means "exclusive or," I do not see why mutually exclusive options would not be a good example. The options are either mutually exclusive by nature (e.g., you may turn left or right at this intersection) or by implication (you must take chemistry or physics but not both) That is by definition. --Carl ^{(talk|contribs)} 04:08, 15 September 2006 (UTC)

Clarifying a bit (after re-reading the previous posts), whether the mutual exclusivity exists because of it being impossible to perform both actions or because of an implied prohibition restricting the performance of both actions, the fact is that a person can only choose one of the two actions. I don't think it makes a difference for the purpose of an example of exclusive or. So yes, it is about what XOR means, because we are trying to give an example of its use "by definition" in everyday English. Saying "left or right" has or implying XOR because of impossibility. Saying "ice cream or candy" has or implying XOR because of prohibition. I personally prefer the absolute exclusivity of left or right because it depends not on language nuance (and an understanding of context), but on the fact that left and right are understood to be exclusive of each other. --Carl ^{(talk|contribs)} 04:17, 15 September 2006 (UTC)

You're doing it the wrong way around. There's no problem about what XOR means; it's a truth function and we all know precisely what its values are. The problem is to find an English sentence where "or" means XOR. That is, we're talking about the meaning of the word "or" (in that particular context), not about the meaning of XOR.

So now we have to get into something much trickier, which is natural-language semantics. In almost all contexts, I think, the natural-language meaning of "or" is not a truth function at all; it takes into account the meanings of the clauses it joins, not just their truth values.

Still, we can come up with examples where the closest truth-functional equivalent to the meaning of "or" is XOR. But in doing so, it's useless to give examples where the two possibilities are, by nature as opposed to by the meaning of the sentence, mutually exclusive. How then are you going to determine that the meaning of the sentence excludes the possibility that they're both true? --Trovatore 04:21, 15 September 2006 (UTC)

The above was edit-conflicted -- let me now respond to the "left or right" thing. The problem is, if I say "he turned left or right", but I intended inclusive or, I have still made a true statement, even though it was impossible that he turned both left and right. --Trovatore 04:24, 15 September 2006 (UTC)

OK, is this example clearer ?

"For gender, the user must select male or female." (logical XOR)

I suppose we could have both, or neither, allowed for transsexuals and such, but most computer forms would require that male XOR female be selected. StuRat 12:37, 15 September 2006 (UTC)

No, because when you select exactly one of "male" or "female", you have still selected male-inclusive-or-female. Note that pXORq implies p ∨ q, no matter what p and q happen to be.

In order for it to be an example where the English word "or" means specifically exclusive-or, we have to use an example where it is inherently possible for both conditions to be true at once, and where that possibility is being excluded by the meaning of the sentence, not by outside factors. The candy/ice cream example is, I think, a fairly clear one, but I'm open to others. But the male/female one is not such an example. --Trovatore 14:44, 15 September 2006 (UTC)

Although I suppose perhaps you meant that the instruction was intended to convey to the user not to mark both "male" and "female", even if he/she had a good reason to do so. That would be an example. The problem is that it's not clear that that's what's intended. In the candy/ice cream case, I think it is clear. --Trovatore 14:53, 15 September 2006 (UTC)

I think you're getting into level of detail which is more appropriate for the Boolean algebra article. For the Boolean logic article, there really isn't any need to distinguish between the case of two things which can't possibly both be true and two things which could both be true, but are not permitted to be so. But, I'm OK with the old example, too, so will leave it alone. StuRat 09:41, 16 September 2006 (UTC)

Revisiting naming

Please see talk:Boolean algebra#Revisiting naming (my proposal there affects this article also). --Trovatore 23:36, 13 June 2007 (UTC)

Now please see talk:Boolean algebra#naming -- trying again. --Trovatore 08:16, 20 June 2007 (UTC)

Merge complete

The promised merge has happened. Feedback from "those who use Boolean applications in electronics and computers, and those taking classes in Boolean logic in school" (the target audience of the old version as per User:StuRat) would be helpful both to make sure the merge wasn't a step backwards and to make whatever improvements those audiences might benefit from. For example are there clear boundaries between parts that could usefully be spun off as separate articles serving different audiences, or are the different audiences served by the article happy to browse around to find the bits most relevant to them? --Vaughan Pratt 06:35, 17 July 2007 (UTC)

You might have tried contacting me on my talk page. This merge completely destroyed the original intent of creating an article about Boolean Logic, as taught in middle and high school, and used extensively in computer science and electronics. This article was meant to be accessible to a general audience, but has now been changed back into a PhD-only article, much like the original Boolean algebra. We now have two PhD-only articles and nothing aimed at anyone else. I will recreate the original article under the name Boolean logic. StuRat 21:26, 24 September 2007 (UTC)