|
|
Boolean algebra is a system named after George Boole, a mid-nineteenth-century English mathematician. It is based on the binary number system described earlier in this chapter. In addition to the binary elements (0 and 1) it also includes a number of operators. The four fundamental Boolean operators are:
NOT
AND
OR
XOR
There are two other operators derived from the three basic ones:
NAND
NOR
Note | As you know from Chapter 11, operators can be unary and binary (in this case the word "binary" is by no means related to binary numbers; it only means that the operator requires two operands). NOT is a unary operator; all other operators covered in this appendix are binary. |
The NOT operator accepts the value of one Boolean variable as input and outputs the opposite of this value. See Table L-5.
VALUE | 0 | 1 |
NOT (VALUE) | 1 | 0 |
The AND operator accepts two Boolean variables as input and outputs their Boolean product. See Table L-6.
VALUE1 | 0 | 0 | 1 | 1 |
VALUE2 | 0 | 1 | 0 | 1 |
VALUE1 AND VALUE2 | 0 | 0 | 0 | 1 |
The OR operator accepts two Boolean variables as input and outputs their Boolean sum. See Table L-7.
VALUE1 | 0 | 0 | 1 | 1 |
VALUE2 | 0 | 1 | 0 | 1 |
VALUE1 OR VALUE2 | 0 | 1 | 1 | 1 |
The XOR operator accepts two Boolean variables as input and outputs their exclusive Boolean sum (exactly one of the variables must be 1 for XOR output to be 1). See Table L-8.
VALUE1 | 0 | 0 | 1 | 1 |
VALUE2 | 0 | 1 | 0 | 1 |
VALUE1 XOR VALUE2 | 0 | 1 | 1 | 0 |
The NAND operator accepts two Boolean variables as input and outputs the opposite of their Boolean product. See Table L-9.
VALUE1 | 0 | 0 | 1 | 1 |
VALUE2 | 0 | 1 | 0 | 1 |
VALUE1 NAND VALUE2 | 1 | 1 | 1 | 0 |
Note | NOT(A AND B) is not the same as NOT(A) AND NOT(B). |
The NOR operator accepts two or more Boolean variables as input and outputs the complement of their Boolean sum. See Table L-10.
VALUE1 | 0 | 0 | 1 | 1 |
VALUE2 | 0 | 1 | 0 | 1 |
VALUE1 NOR VALUE2 | 1 | 0 | 0 | 0 |
Note | NOT(A OR B) is not the same as NOT(A) + NOT(B). |
Table L-11 shows the precedence rules of the Boolean algebra operators.
Precedence level | Operator |
---|---|
1 | brackets ( ) |
2 | Boolean complement NOT |
3 | Boolean product AND |
4 | Boolean sum OR |
Note | Brackets have the highest precedence, i.e., everything inside brackets is evaluated first. |
Table L-12 illustrates how the precedence rules are used when evaluating the expression: NOT (TRUE OR FALSE) OR TRUE AND FALSE.
Note | Remember, 1 in Boolean algebra means TRUE and 0 means FALSE. |
Step | Expression | Explanation |
---|---|---|
1 | NOT(1 OR 0) OR 1 AND 0 | 1 OR 0 is inside the brackets, so evaluate it first. The result is 1, so replace (1 OR 0) with 1. |
2 | = NOT(1) OR 1 AND 0 | Evaluate the complement next. NOT(1) = 0. Replace NOT(1) with 0. |
3 | = 0 OR 1 AND 0 | Evaluate the product next. 1 AND 0 = 0. Replace 1 AND 0 with 0. |
4 | = 0 OR 0 | Now, evaluate the sum. 0 OR 0 = 0, so the result of the expression is 0. |
5 | = 0 | We are done. |
Table L-13 contains the main identities of Boolean algebra.
Name | Corresponding Notation |
---|---|
Complement laws | X OR NOT(X) = TRUE |
Law of the double complement | NOT(NOT(X)) = X |
Idempotent laws | X OR X = X |
Identity laws | X OR FALSE = X |
Dominance laws | X OR TRUE = TRUE |
Commutative laws | X OR Y = Y OR X |
Associative laws | X OR (Y OR Z) = (X OR Y) OR Z |
Distributive laws | X OR (Y AND Z) = (X OR Y) AND (X OR Z) |
DeMorgan's laws | NOT(X AND Y) = NOT(X) OR NOT(Y) |
Absorption law | X AND (X OR Y) = X |
|
|