# 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  BackCover  SQL Bible  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  Part VII: Appendix  Appendix A: What's on the CD-ROM  Appendix B: The ACME Sample Database  Appendix C: Basics of Relational Database Design  Appendix D: Installing RDBMS Software  Appendix E: Accessing RDBMS  Appendix F: Installing the ACME Database  Appendix G: SQL Functions  Appendix H: SQL Syntax Reference  Appendix I: SQL-Reserved Keywords  Appendix J: SQL99 Major Features Compliance Across Different RDBMS  Appendix K: The Other RDBMS  Appendix L: A Brief Introduction to the Number Systems, Boolean Algebra, and Set Theory  The Number Systems  Logic Elements of Boolean Algebra  Set Theory  List of Figures  List of Tables  List of Code Examples  List of Sidebars  CD Content