Slashdot Mirror
Boolean Logic : George Boole's The Laws of Thought
Ian writes "The Globe and Mail has a piece about the man behind Boolean Logic - George Boole - The Isaac Newton of logic. 'It was 150 years ago that George Boole published his classic The Laws of Thought, in which he outlined concepts that form the underpinnings of the modern high-speed computer.'"
Also that year, Grace Hopper, an admiral in the U.S. Navy, recorded the first computer "bug" -- a moth stuck between the relays of a pre-digital computer.
The computer was digital, it just used relays instead of integrated circuits. It wasn't stuck between relays, it was stuck in a relay.
And while I'm at it, a nitpick. She wasn't an admiral until much later.
Infuriate left and right
Moderate this comment
Negative: Offtopic Flamebait Troll Redundant
Positive: Insightful Interesting Informative Funny
Nothing to see here
I'm a bit confused why you mention the BBC...
Let's not forget Lovelace, Ritchie, Knuth, von Neumann, Turing...
Moderate this comment
Negative: Offtopic Flamebait Troll Redundant
Positive: Insightful Interesting Informative Funny
Nothing to see here
...but it apparently made even less sense in Boolean if you can believe that's even possible. And if he wasn't a Unitarian this whole mess of ours would have been in base 3.
Grace Hopper Found a bug? Was it a Grasshopper?
Overuse of the Pumping Lemma causes blindness
Not in Project Guttenberg yet
There's nothing like reading the original works.
Offtopic: Why did it take me 15 seconds to realize the word "Google" was no where in the story title? Anyone else have that problem?
I think Turing and von Neumann had far more to do with the underpinnings of modern computers than Boole.
Boole's great acheivement was his attempt to formalize logic algebraically at a time when logic was informal and far too meta for even mathematicians to consider formally. While this is great and all, it doesn't result in a general purpose computer.
However, Turing machines and von Neumann machines are in everyway a general purpose computer.
Am I the only one who finds that name Grace Hopper and the expression "computer bug" go well together? :oP
DrkBr
To be pedantic, the title of Boole's book was "An Investigation of the Laws of Thought"
No electrons were harmed creating this post, though some may have been subjected to electrical and/or magnetic fields.
"Also that year, Grace Hopper, an admiral in the U.S. Navy, recorded the first computer "bug" -- a moth stuck between the relays of a pre-digital computer.)"
Ahh, but relays are digital.... They are either on or off. That was binary the last I looked.
Parent post is completely wrong. The complete title is actually "An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities".
The amount of information a yes/no answer conveys to someone with no prior knowledge. Or, if you want to get technical: an ln(2) reduction in entropy.
Be faithful to your obsessions. Identify them and be faithful to them, let them guide you like a sleepwalker. JG Ballard
While that's a pretty clumsy way of saying, it, Shakespeare was ahead of Boole.
I suggest we all add the following statement (or equivalent) to our code in honor of this great mind.
typedef bool shakespear;
DNA is the ultimate spaghetti code.
As wonderful as binary is, it falls utterly in capturing the fuzzy analog nature of life and the real world. Our recent debate on whether Sedna (or Pluto) is a planet is but one example of how the real world fails to fit into simple binary categories. Even at the subatomic level, the wave-particle duality gives lie to the fiction of discreteness.
I'm not saying that binary is not great for doing all manner of wonderfully powerful proofs, logic, and computation. I'm only saying that it is a mere approximation to the real world and can thus fail when the real world is does not dichotomize to fit into Boole's logic.
Boolean Logic illustrates both the tremendous power and weakness of mathematical systems. On the one hand the power of proof guarantees that man-made mathematical system with certain axioms will undeniably have certain properties. On the other hand, math gives one no guarantee that the real world obeys those axioms.
Two wrongs don't make a right, but three lefts do.
Set Theory is a Boolean Algebra. Odd there was no (explicit) mention of this. It is important to both mathematics in general, and Computer Science.
...
..
...
Just as an aside, a mathematical structure is a Boolean Algebra if, and only if, if it contains two operations (generally denoted +, and *), such that for all elements A, B and C in the structure
A + B = B + A
A * B = B * A
(A + B) + C = A + (B + C)
(A * B) * C = A * (B * C)
A + (B * C) = (A + B) * (A + C)
A * (B + C) = (A * B) + (A * C)
and there exists two elements 0 and 1 in the structure such that
A + 0 = A
A * A = A
and for each A an element exists that's the "negation" of A
A + ~A = 1
A * ~A = 0
In logic, + is equivilent to OR, * is equivilent to AND, a Tautology is equivilent to 1, and contradiction is equivilent to 0. ~ is NOT.
Similar comparisons can be made in Set Theory. In the same order of above: Union, Inclusion, Universal Set, Empty Set, and Set Complement.
So, if you prove one algebraic identity in Set Theory, you also proved the same exact identity in
Propositional Logic (and vice versa.)
(shrug)
#define bit 1
love slashdot. populate it. use it. abuse it. hate it. kill it. miss it. stop following links, they only kill servers.
One good boolean algebra is the logical algebra of probabilities. Every datum is a real between 0 and 1. x or y would be x + y - xy; x and y would be xy; not x would be 1 - x. (All of this is off the top of my head BTW). It's a perfectly valid boolean algebra.
To say that boolean algebra is about "true" or "false" is absolute rubbish. It's largely because binary computers have become so popular that people think that way.
Boole was born in Lincoln, England, in 1815, the eldest son of a poor shoemaker who also had a passion for mathematics. He was a precocious child. His mother boasted that young George, 18 months, wandered out of the house and was found in the centre of town, spelling words for money.
Spelling expert? He would have stood out as a slashdotter.
Table-ized A.I.
Reading the article, you'll see that Boole assigned algebraic operators to logic operators.
AND = x (multiply)
OR = + (add)
The order of operations states that we multiply before adding.
It's probably the same reason multiplication has a higher precedence than addition. Multiplication and AND are equivalents, and addition and OR are equivalents.
In fact, for most practical purposes, AND *is* multiplication and OR *is* addition. Just compare the truth tables with multiplication and addition tables (one minor technicality, of course, is that addition carries while OR does not; the carry bit is simply the result of A AND B).
It was a really good paper.
h96566k.jpg
Yes, I'm aware than an AC beat me to it, but he's at -1 right now, so I'm posting this because it's more visible.
Intuitively, checking if the elements of a set are all true should have presedens over checking if one of them is true.
- These characters were randomly selected.
She was also already a PhD when she was called up for active service in WW2, so the grandparent post is really highly inaccurate.
Grace Hopper - the third programmer in the United States, and a fitting successor to Ada Lovelace.
Panurge has posted for the last time. Thanks for the positive moderations.
Some complain that the intruduction of "null" into some systems (such as databases) ruins the simplicity of Boolean logic. It creates a "3-value logic" which can get messy to grok.
I generally agree. I think nulls are perhaps fine for numeric calculations in some cases, such as the average if there are zero records, but not Booleans and not strings. But sometimes it is hard to limit it to one but not the other. It is a controversial topic nevertheless. Chris Date has written some white papers on how to get rid of null.
Table-ized A.I.
The importance of Boole's ideas, therefore, was that they provided a grand unifying framework for computer design.
In fact Turing's ideas were more fertile for programming, and it's a pity that he lived in the UK after WW2 and was held back by the usual British official incompetence in technical and commercial matters. And Von Neumann- how important was he really for computer development? Not as important, I think, as Black, Eckert or Mauchly.
Panurge has posted for the last time. Thanks for the positive moderations.
I helped proofread this one recently at pgdp.net. It's in post-processing now, so it will be in Gutenberg soon!
It appears this "Computer History" attempt overlooks John Vincent Atanasoff, credited by most reliable sources (Smithsonian, etc.) as developer of the first electronic digital computer" years before the ENIAC. In fact, the ENIAC was derived from Atanosoffs's ABC Computer at Iowa State after an ENIAC developer visited Atanasoff (stayed several days in Atanasoff's home), and "stole" his ideas and proposed a larger verssion as the ENIAC to the army. Atanosoff's ABC computer was the first to solve Schroedinger's equation represented by the solution of a 39x39 system of matrix equations. However, time caught up with the ENIAC visitor, and the notebook he kept when he visited Atanasoff was his undoing when the U.S. Court in Minneapolis overturned previous patent rulings for computer developments and ruled they were all derived from Atanasoff's ABC computer. Hopefully, this attempt at a computer museum will soon be updated to accurately reflect the original development of the electronic computer by Atanasoff at Iowa State in 1942.
Boole undertook to rewrite the Bible in his mathematical logic.
And 101101 sayeth unto 111000, "Don't partake of thy apple, for it is full of 110101001010". But sayeth 111000 back to 101101, "11111111 That! I am hungry!". Behold he biteth into thy apple, and suddenly God made him naked, and his "1" showed, and 101101 laughed because she thoughteth it was a decimal. But her "00" also showed, and 111000 laughed because he though they were two decimals.
Table-ized A.I.
Plus they credit her with coining the term "bug". The squashed moth was a joke. "Bug" was slang for electronic glitches long before then.
But, maybe the real world fits into complex binary categories. For example, suppose I ask you to pick a real number between 0 and 1
Excellent point. But again, I'm not sure that the real world actually obeys the laws of real numbers either. Again, wave-particle duality makes a mess of mathematically notions of pure discrete and pure continuous. Some theories of physics suggest the existence of a quantum mechanical foam at dimensions of about 10^-33 meters. Perhaps the physical world is neither continuous (in the infinite-digit real number sense) nor discrete (in the exactly N-bits binary sense) Perhaps continuous real numbers are a good approximation, but whether real numbers are real (or just a very convenient mathematical construct) is debatable
Similarly, a question asking the color of something (which has finitely many answers) could be reformulated as a sequence of yes/no questions. For example, if the color is in 24-bit format, start with: Is the first bit a 1? and so on.
An interesting example. Yet real-world colors aren't 24-bit, although they can be approximated with a 24-bit color measuring systems. Its a crude approximation, unfortunately. I don't even know of a 24-bit system that has the color gamut of human vision, let alone one that properly measures the hyperspectral reflectance, transflectance, absorption, & flourescence properties of real-world materials. Yes, if you assume a 24-bit approximation, then binary yes/no questions suffice. My point is that one is forced to make a big (sometime right, sometime wrong) assumption in reducing the physical world to any N-bit approximation.
After all, everything you do on a computer, from playing video games to chatting via Instant messaging, ultimately gets reduced to binary form.
So very true.
To me, the deeper issue is whether the real world obeys the mathematicaly axioms of an algebra, Boolean or otherwise. The real world is nonlinear and that throws a wrench in the axioms right there. I also wonder about the axiom of closure -- that interactions of physical quantities in physical systems have consequences outside the algebraic variables of the system.
Again, I'm sure that algebras and real numbers or N-bit numbers are excellent approximations as long as we don't forget that they are only approxmations.
Two wrongs don't make a right, but three lefts do.
Again, I'm sure that algebras and real numbers or N-bit numbers are excellent approximations as long as we don't forget that they are only approxmations.
... the red on white was a different color than the red on black! So, what is our reference point? Is a certain shade of red a fixed frequency of visible radiation? Or is it entirely perceptual?
I believe that approximations are the best we can do. I've been trained as a mathematician. But, I don't believe in the square root of 2 in any physical sense. Some may argue, well construct a square 1 unit on a side, then the diagonal is square root of two. I argue, is it possible to construct a physical square 1 unit to a side? Each side would have to have the same number of atoms in a regular array, otherwise, it's not a square. But even if you accomplish this magnificent feat, the atoms in the lattice are vibrating, so the length isn't constant in time. So, I don't even believe in 1 as a physically measurable number!
Point being, what is our reference point? Color perception has the same problem. I saw an excellent program on PBS (maybe NOVA? it's been several years) on color vision. One experiment was to project a red (that is a fixed frequency of light) circle onto a black background. Then they repeated the experiment with a white background. And I'll be damned
I say again, every measurement is an approximation. Ergo, choose N large enough that no one can practically tell the difference. Then the approximation becomes reality.
I believe that approximations are the best we can do.
....
;)
So, I don't even believe in 1 as a physically measurable number!
Cool, I can tell that you and I are on a similar wavelength. Whether that wavelenth is representable as a real number or as a 24-bit color is another matter.
I say again, every measurement is an approximation. Ergo, choose N large enough that no one can practically tell the difference. Then the approximation becomes reality.
And I agree 100% that a large enough N creates a indistinguishably fine approximation with one important exception. If the physical system violates the axioms of the mathematical system used in measurement, then there will be physical states or dynamical behaviors that have no corresponding mathematical state or admissible mathematical transform. Thus, for example, there are physical and perceptual colors for which there are no 24-bit approximations (the gamut problem). Moreover, the inverse problem occurs too. A mathematical system can have states with no corresponding physical state (see the problem of illegal colors)
The extent that the physical and mathematical systems lack a bijective (1-to-1) mapping of both states and admissible transforms is the extent that mathematical reasoning has short-comings. Math is great. As an engineer who has studied math extensively, I can vouch for the power of math to construct axiomatic systems that represent novel physical systems. I can also vouch for the weakness of math in misconstructing those axiomatic analogs of physical systems.
Math is like a chainsaw -- very powerful at cutting into problems, but also very dangerous if one is not careful.
Two wrongs don't make a right, but three lefts do.
Well,Goerge Boole proposed the basic principles of Boolean Algebra in 1854 in his trearise "An investigation of the laws of thought on Which to Found the Mathematical Theories of Logic and Probablities". While admire Goerge Boole, and I certainly give hime credit for creating this branch of Algebra, it should be noted that Goerge Boole himself had nothing to do with computers or digital systems.In the middle of the 19th century, many mathematicians were working on something called "Principles of Logic". Their goal was to descibe the human thought, in pure mathematical format. They aimed to model the human logic, as a branch of science, and they wanted to formulate it and find the principles of human's way of thinking. If you have ever taken a Descrete Mathematic course, you certainly have seen nonsense statements that "If Today is Sunday" AND "if Betty is happy" THEN "The Sky is Red".
This was what those mathematicians were aiming for. Goerge Boole also proposed a set of principles, which at the time no one thought had any practical use. This branc of mathematics was a purely theoric one. Mathematicians mostly abondend this subject after it was proven by experience that the human thought can not be formulated in to some mathematical notations.
It wasn't untill in the 40s, when someone at the Bell Labs (forgot his name) suddenly found out that the Boolean Algebra can be used in digital systems, specifically in implementing digital circuits. Even the first computer built, the ENICA, used a decimal system, and didn't have anything to do with digital systems. It was only by an accident that it was found out that Boolean Algebra, which at the time was a completely useless and theoritic branch of math, found an application, and became a widely studied subject.
What I am trying to say, is that Goerge Boole himself, by no means had any interest in digital systems, in programming, in computers, or in anything even remotely related to electronics. While as I said, I we should all give him immense credit for his work on Boolean Algebra, it should be noted that many people, contributed much more to the computer and electrical science, than Goerge Boole. Charles Babage and Lady Ada were actually writing computer programs in the 19th century; their only problem was that they had no computer at that time! And certainly, the father of today's computer architecture, is von Neuman.
Give credit were credit is due, but over-crediting someone, like saying Goerge Boole invented the foundation of computers, is certainly not correct.
--
I found it very interesting at first, but the final parts where really annoying. But the important thing is that after finishing the semester I started that even I've being a programer since 95 and having experience with turbo pascal, javascript, lambdaMOO, php, c, c++ and object pascal, I've just get better at programking because of boole!
Boole is one of those things that looks simple and useless at first, but that is not the truth.
It's a sad day when the editors of Science feel they need to define what algebra is to their audience.
Long live the Speaker Bracelet
Rolo D. Monkey
Just to be a bit pedantic, according to Simon Singh's book "The Code Book", the first "computer" was the ENIGMA code breaker, the British Bletchley Park WWII invention , COLOSSUS (http://www.acsa.net/a_computer_saved_the_world.ht m). It never received as much publicity as the ENIAC because it was a war secret...
Cheers
If you are going to list "those who made all this possible" you cannot ignore Claude Shannon. Creating information theory was important, but what is equally remarkable was his master's thesis: "Symbolic Analysis of Relay and Switching Circuits" (1941) was what proved that Boole's logic could be implemented in digital hardware.
It was, by a long margin, the most important master's thesis in history.
IMHO, the discovery of a real-world application of the idempotent law that was Boole's greatest accomplishment. One could argue that Lebnitz and Boole had independently discovered this. This is not unlike Hamilton's discovery of an application for non-commutative algebra.
Boole's contribution to logic was profound. First, a real world model for any mathematical property ensures the consistency of that model. Boole's work provided an abstraction for elementary set theory. The key to this abstraction is idempotency. The aggregate of set A and itself is the set A (i.e. A+A=A). Thus, Boolean algebra formalizes the basic set theoretic operations of union and intersection, which in turn is almost trivially isomorphic to a Boolean ring. I could create all kinds of stupid rules [insert your favorite slam on mathematics here] that have no meaning in the real world. Most importantly, Boole seemed to be the first to attempt to bridge the gap between abstract thought and mathematics. Admittedly there was some previous work in attempting to formalize|classify all syllogistic reasoning. It was the first step towards a unified theory of logic and ultimately what is hope to be a universal theory of symbolism (see Chomsky's mathematical linguistics).
The irony about mathematics is that often the best ideas are childishly simple. It's not the proof of deep theorems (although that has it's place) that often has the greatest impact. It's the fresh applications of mathematical rigour to some real world scenario. Thus, mathematics is often at it's weakest when done in isolation. Incidentally, Knuth's work in algorithm analysis was revolutionary. In a world described by (K-Complexity (AIT)|cellular automata|simple computer programs) algorithm analysis and ultimately a proof of P not= NP may be to hold the key to the fundamental laws of nature (i.e. physics, biology, and chemistry).
Incidentally, the Martin Davis' The Universal Computer is a great popular science book on this topic. A free copy of the introduction is here. This book manages to introduce the ideas of Turing (Turing-Post?) Machines and the Diagonal Method to the lay reader. The author is a respected logician and computer scientist who studied under Church and Post.
What do you mean my sig is repetitive? What do you mean my sig is repetitive? What do you mean....