Mecatronica

Chapter 1.6 Boolean Algebra
Ki Hang Kim
Alabama State University, Montgomery, Alabama

6.1

INTRODUCTION

that is, a•0ˆa a”1ˆa

The theory of Boolean algebra is relatively simple but it is endowed with an elegant structure and rich in practical applications. Boolean algebra is named after the British mathematician George Boole (1815±1864). For Boole's pioneering work, see Refs 1 and 2.Boolean algebras have been extensively studied by Schroder [3], Huntington [4], Birkhoff [5], Stone [6], È Halmos [7], Sikorski [8], and Hohn [9]. In this chapter, we present a concise summary of Boolean algebra and its applications. A Boolean algebra is a mathematical system …; •; ”† consisting of a nonempty set  ˆ fa; b; c; F F Fg and two binary operations • (vee) and ” (wedge) de®ned on such that: b1 . Both operations are associative; that is …a • b† • c ˆ a • …b • c† …a ” b† ” c ˆ a ” …b ” c† b2 . b3 . Both operations are commutative; that is, a•bˆb•a a”bˆb”a Each operation is distributive with respect to the other; that is, a • …b • c† ˆ …a • b† ” …a • c† a ” …b • c† ˆ …a ” b† • …a ” c† b4 .  contains an identity element 0 with respect to • and an identity element 1 with respectto ”;
113

b5 .

The element 0 is called the zero element and the element 1 is called the unit (or universal) element, respectively, of . " For each a P , there exists an element a P  such that " a•aˆ1 " a”aˆ0

" The element a is called a complement of a. Notice that there exists a complete symmetry in the postulates b1Àb5 with respect to the operations • and ” and also in the identitiesof b4 . Therefore, we can state the following principle: Principle of Duality. If in any statement deduced from the ®ve postulates b1Àb5 we interchange • and ”, and 0 and 1, then we obtain a valid statement. Example 1. Let S ˆ fa; bg, a < b. We de®ne a • b ˆ supfa; bg and a ” b ˆ inffa; bg. (Accordingly, we can also de®ne the operations as a • b ˆ maxfa; bg and a ” b ˆ minfa; bg.) The tables forthese operations are as Tables 1 and 2 . Clearly …S; •; ”† is the simplest and most fundamental nontrivial Boolean algebra. Example 2. Let D be the set of positive integral divisors of 6: that is, D ˆ f1; 2; 3; 6g. For all a, b P D, we

Copyright © 2000 Marcel Dekker, Inc.

114 Table 1 Multiplication for • • a a a a b b b b

Kim

”† is a Boolean algebra. The veri®cation is left as anexercise.
Table 5 • a b c d Four-Element • Multiplication Table a a b c d b b b d d c c d c d d d d d d

Table 2 Multiplication for ” ” a b a a a b a b

Table 6 Four-Element ” Multiplication Table ” a b c d a a a a a b a b a b c a a c c d a b c d

de®ne a • b and a ” b to be respectively the least common multiple (lcm) and greatest common divisor (gcd) of a and b. In other words, a • b ˆ lcmfa; bg and a ” b ˆ gcd fa; bg. The tables for these operations are Tables 3 and 4.
Table 3 Lowest Common Multiple Multiplication Table • 1 2 3 6 1 1 2 3 6 2 2 2 6 6 3 3 6 3 6 6 6 6 6 6

Example 4. Let P…X† be the power set of a nonempty, ®nite set X. Then …P…X†; ‘; ’† is a Boolean algebra, taking • and ” as ‘ and ’, respectively. Take ``±'' as complementation relative to X, 0 ˆ Y, 1 ˆ X,respectively. Therefore, the operations • and ” may be denoted by ‘ and ’, respectively. In®nite Boolean algebras are not used much in the theory of switching circuits but do occur in other areas of mathematics such as measure theory, logic, probability, and topology. Since we are mainly interested in the applications of Boolean algebras, we will only concentrate on ®nite Boolean algebras. The simplestin®nite Boolean algebras are in®nite Cartesian products of f0; 1g. These act almost identically to ®nite Boolean algebras. Example 5. All measurable subsets of the real numbers form a Boolean algebra which allows not only ®nite union and intersection but also countable union and intersection. Example 6. All sets obtained from the open and closed sets of a topology by ®nite union and intersection...