Boolean Algebra

All decisions in computer programs boil down to appropriate Boolean expressions. The ability to formulate, manipulate and reason with these expressions is an important skill for programmers and computer scientists. Boolean expressions obey certain algebraic laws similar to those that apply to numeric operations. These laws are called Boolean logic or Boolean algebra.

Let's look at a few examples. The following table shows some rules of algebra with their correlates in Boolean algebra.

Algebra Boolean algebra a* 0 = 0 a and false == false a* 1 = a a and true == a a 0 a a or false == a

From these examples, you can see that and has similarities to multiplication, and or has similarities to addition; while 0 and 1 correspond to false and true.

Here are some other interesting properties of Boolean operations. Anything ored with true is just true.

Both and and or distribute over each other.

a or (b and c) == (a or b) and (a or c) a and (b or c) == (a and b) or (a and c)

A double negative cancels out.

The next two identities are known as DeMorgan's laws.

not(a or b) == (not a) and (not b) not(a and b) == (not a) or (not b)

Notice how the operator changes between and and or when the not is pushed into an expression.

One application of Boolean algebra is the analysis and simplification of Boolean expressions inside of programs. For example, let's go back to the racquetball game one more time. Above, we developed a loop condition for continuing the game that looked like this:

while not (scoreA == l5 or scoreB == l5): # continue playing

You can read this condition as something like: While it is not the case that player A has 15 or player B has 15, continue playing. We're pretty sure that's correct, but negating complex conditions like this can be somewhat awkward, to say the least. Using a little Boolean algebra, we can transform this result. Applying DeMorgan's law, we know that the expression is equivalent to this.

Remember, we have to change the or to and when "distributing" the not. This condition is no better than the first, but we can go one step farther by pushing the nots into the conditions themselves.

while scoreA != l5 and scoreB != l5: # continue playing

Now we have a version that is much easier to understand. This reads simply as while player A has not reached 15 and player B has not reached 15, continue playing.

This particular example illustrates a generally useful approach to loop conditions. Sometimes it's easier to figure out when a loop should stop, rather than when the loop should continue. In that case, simply write the loop termination condition and then put a not in front of it. An application or two of DeMorgan's laws can then get you to a simpler but equivalent version suitable for use in a while statement.

0 0

Post a comment