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 X AND NOT(X) = FALSE |
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 |