Monday, December 7, 2009

Boolean Algebra - Computer Science Week

Ok, a brief respite from my usual blog topics for National Computer Science Education Week. Each day this week I'm going to blog about some topic in computer science. My goal is to make these topics introductory enough so that anyone can read them and learn something, and perhaps get an interest in learning more.

Today's topic is Boolean Algebra. I know the work "algebra" scares people off. Months of sitting in school trying to fathom what "x" was has left a bad taste in the mouths and minds of millions. But the word actually comes from the title of a book, עilm al-jabr wa'l-muḳābala ‘the science of restoring what is missing and equating like with like,’ by the mathematician al- K wārizmī. So let's restore what is missing in algebra - fun (well, maybe not, but we'll try).

You're familiar with arithmetic operators, + - x and /. George Bool came up with a system of operators on the values TRUE and FALSE. There are three basic operators (which can actually be reduced to 2), that describe all the things you can do. They are AND, OR and NOT, and they are pretty simple to understand.

"I'll eat chicken OR beef." Means I will eat chicken. I will eat beef. I will eat both. The only way this is FALSE is if I will eat neither chicken nor beef.

"I had bacon AND eggs for breakfast." Means I had both, I could not say this if I didn't have bacon or if I didn't have eggs.

"I did NOT eat the peas." This of course, would be false if I did eat the peas.

Pretty simple, and yet George made it complicated by adding formal equations and parentheses and varous properties. The nice thing that falls out of it are some general principles that let us simplify logic. For instance, the sentence:

"If it is NOT Tuesday OR it is NOT raining I will NOT have duck for dinner."

can be shown to be logically the same as

"If it is Tuesday AND it is raining I will have duck for dinner."

Of course, that sounds obvious, but just like numerical algebra, you can use boolean algebra to take some complicated logic problems and find a simpler form that is equivalent. For more information see Ones and Zeroes: Understanding Boolean Algebra, Digital Circuits and the Logic of Sets.


Post a Comment