2.2 Boolean Algebra
Boolean algebra was developed in the 1800's by James Bool, an Irish mathematician. It was found to be extremely useful for designing digital circuits, and it is still heavily used by electrical engineers and computer scientists. The techniques can model a logical system with a single equation. The equation can then be simplified and/or manipulated into new forms. The same techniques developed for circuit designers adapt very well to circuit and program.
Boolean equations consist of variables and operations and look very similar to normal algebraic equations. The three basic operators are AND, OR and NOT; more complex operators include exclusive or (EOR), not and (NAND), not or (NOR). Small truth tables for these functions are shown in Figure 2.1. Each operator is shown in a simple equation with the variables A and B being used to calculate a value for X. Truth tables are a simple (but bulky) method for showing all of the possible combinations that will turn an output on or off.
Figure 2.1 Boolean Operations with Truth Tables and Gates
In a Boolean equation the operators will be put in a more complex form as shown in Figure 2.2. The variable for these equations can only have a value of 0 for false, or 1 for true. The solution of the equation follows rules similar to normal algebra. Parts of the equation inside parenthesis are to be solved first. Operations are to be done in the sequence NOT, AND, OR. In the example the NOT function for C is done first, but the NOT over the first set of parentheses must wait until a single value is available. When there is a choice the AND operations are done before the OR operations. For the given set of variable values the result of the calculation is false.
Figure 2.2 A Boolean Equation
The equations can be manipulated using the basic axioms of Boolean shown in Figure 2.3. A few of the axioms (associative, distributive, commutative) behave like normal algebra, but the other axioms have subtle differences that must not be ignored.
Figure 2.3 The Basic Axioms of Boolean Algebra
An example of equation manipulation is shown in Figure 2.4. The distributive axiom is applied to get equation (1). The idempotent axiom is used to get equation (2). Equation (3) is obtained by using the distributive axiom to move C outside the parentheses, but the identity axiom is used to deal with the lone C. The identity axiom is then used to simplify the contents of the parentheses to get equation (4). Finally the Identity axiom is used to get the final, simplified equation. Notice that using Boolean algebra has shown that 3 of the variables are entirely unneeded.
Figure 2.4 Simplification of a Boolean Equation
