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
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
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
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)
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.
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.
Not to mention that it is unlikely that Hopper ever claimed to find the first "bug".
The comment next to the moth taped in the logbook seems to indicate that the word had been in use for some time, and Hopper was making a bit of a joke.
-- clvrmnky
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.
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.
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....