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.

Table L-5: NOT Truth Table

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.

Table L-6: AND Truth table

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.

Table L-7: OR Truth table

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.

Table L-8: XOR Truth table

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.

Table L-9: NAND Truth table

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.

Table L-10: NOR Truth table

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




SQL Bible
Microsoft SQL Server 2008 Bible
ISBN: 0470257040
EAN: 2147483647
Year: 2005
Pages: 208

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net