Boolean Algebra

Boolean algebra is the mathematical method that governs much of modern computing. It was developed hundreds of years ago, yet still remains relevant today as a method for circuit and chip designers to build microprocessors and other logic chips that run the devices we depend on every day.

The main points of boolean algebra is that there are only two states, true or false, on or off, and in the case of binary number systems 0 and 1. For now we will use the 0 and 1 system because it is also the number system used in computers. There are several operations that can be done in a binary or boolean number system to reach desired results. Common operations are AND, OR, and NOT, with more complex operations being made from combinations of these three simple operations. For a short hand we will use * to represent AND (in most texts this will be a small filled in black circle instead of an asterisk), a + to represent OR, and a ' to represent NOT. For example, x * y is x AND y, x + y is x OR y, and x' is NOT x.

Now that we know the components of boolean algebra we can start to build methods to analyze these operations. The most basic method called a truth table. The truth table for the AND operation is given below. Truth tables are built by specifying every combination of variables in an expression, and then the result of the expression for each combination.

x y x*y
-------------
0 0 0
0 1 0
1 0 0
1 1 1

As you can see the result of a AND operation is only 1 if both inputs, which can themselves be expressions that need to be evaluated, are 1. Below are the truth tables for OR and NOT operations. OR evaluates to 1 if one of the two inputs is a 1, and NOT is simply the inversion of the input.

x y x+y
-------------
0 0 0
0 1 1
1 0 1
1 1 1

x x'
------
0 1
1 0

Now that we know what each operation does we can analyze expressions themselves, and ways to simplify them. For example, (x * y)' is the inversion of x AND y, which is sometimes called NAND, or negation of an AND operation. The way to evaluate this expression is to first evaluate x*y for the desired input combination, then apply the NOT operation. From this expression we are evaluating you can interpret that by adding parentheses you can change the order in which operations are executed. Normally NOT operations have the highest precedence, then AND, and then OR operations. And of course parentheses supersede any operations.

The properties you normally associate with regular algebra and math also hold true for boolean algebra. Operations can be distributed within parentheses. For example, x*(y+z) = x*y + x*z = xy + xz. I have also included another common notation in the third part of that expression by omitting the * when referring to an AND operation, the same way a multiplication sign can be omitted in everyday math. The distributive property holds true for OR as well, x+yz = (x+y)*(x+z).

These simple operations should serve as a small primer of boolean algebra and will enable you to get your feet wet should you choose to read more into this topic.