# Logic Elements of Boolean Algebra

## Logic Elements of Boolean Algebra

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.

### NOT (complement or inverter)

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

### AND (Boolean product)

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

### OR (Boolean sum)

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

### XOR (exclusive OR)

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

### NAND (inversed AND)

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).

### NOR (inversed OR)

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).

### Rules of precedence

Table L-11 shows the precedence rules of the Boolean algebra operators.

Table L-11: Boolean Algebra Operator Precedence

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.
Table L-12: Precedence Rules Illustration

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.

Table L-13: 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
X AND X = X

Identity laws

X OR FALSE = X
X AND TRUE = X

Dominance laws

X OR TRUE = TRUE
X AND FALSE = FALSE

Commutative laws

X OR Y = Y OR X
X AND Y = Y AND X

Associative laws

X OR (Y OR Z) = (X OR Y) OR Z
X AND (Y AND Z) = (X AND Y) AND Z

Distributive laws

X OR (Y AND Z) = (X OR Y) AND (X OR Z)
X AND (Y OR Z) = (X AND Y) OR (X AND Z)

DeMorgan's laws

NOT(X AND Y) = NOT(X) OR NOT(Y)
NOT(X OR Y) = NOT(X) AND NOT(Y)

Absorption law

X AND (X OR Y) = X

 Preface
 Part I: SQL Basic Concepts and Principles
 Part II: Creating and Modifying Database Objects
 Part III: Data Manipulation and Transaction Control
 Part IV: Retrieving and Transforming Data
 Part V: Implementing Security Using System Catalogs
 Part VI: Beyond SQL--Procedural Programming and Database Access Mechanisms
 List of Figures
 List of Tables
 List of Code Examples
 List of Sidebars