Boolean algebra is a system named after George Boole, a midnineteenthcentury 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 L5.
VALUE 
0 
1 
NOT (VALUE) 
1 
0 
The AND operator accepts two Boolean variables as input and outputs their Boolean product. See Table L6.
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 L7.
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 L8.
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 L9.
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 L10.
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 L11 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 L12 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 L13 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 