Boolean Algebra and Its Applications

Read an Excerpt

Boolean Algebra and Its Applications

Dover Publications, Inc.

THE ALGEBRA OF SETS

1–1 Introduction. Boolean algebra, as the name suggests, is part of that branch of mathematics known as modern algebra, or abstract algebra. It is one of the most easily understood of the algebraic systems usually studied in a basic course in algebra because of its simplicity and because of the readily available applications to illustrate the theory. No particular subject matter is prerequisite to the study of this text, although any maturity gained in other mathematics courses will be helpful.

In order to present Boolean algebra in a way which can be readily followed by a beginner, this chapter deals only with one of the special examples of a Boolean algebra, the algebra of sets. This example was chosen because it is perhaps the most intuitive of all applications and because at the same time it is complex enough to reveal the essential nature of any Boolean algebra. The development is entirely intuitive, in that any proofs given are based on intuitive concepts rather than on formal axioms. The axiomatic approach is delayed until Chapter 2. While this order is perhaps less satisfying to a professional mathematician, it is hoped that a greater appreciation of the precise formulation will result because the reader is already familiar with the properties represented in the axioms.

1–2 Element and set. Throughout mathematics there are countless instances where the concepts of "element" and "set of elements" (or class) play a crucial role. Every freshman student in mathematics is familiar with the set of integers, the set of all right triangles, the set of lines perpendicular to a given plane, and the set of points on a line. The concept of set is not limited to mathematics, however. The totality of books in a library, of people in a room, and of fish in a given stream are examples of sets. The purpose of this chapter is to investigate the nature of sets and the ways in which they may be combined. That sets obey laws of algebra similar, although not identical, to the laws of algebra for real numbers may seem strange at first. However, it will be shown how this phenomenon is a natural and very useful one.

In any subject in mathematics there are certain terms so basic that definition is impossible. In plane geometry, the terms point and line are undefined, although a student of geometry is encouraged to form an intuitive notion of the meaning of these words. We will take as undefined terms for the algebra of sets the words element and set. Intuitively we think of elements as the basic objects which, in collections, constitute sets. As symbols we shall use the letters of the alphabet in lower case italics (a, b, c, x, y, etc.) to represent elements, and capital letters (A, B, X, etc.) to represent sets. A further symbol, [member of], will be used to denote an undefined relation which may or may not hold between a particular element and a particular set, in that order. We may write, for example, m [member of] X, and read this symbol "m is a member of the set X." It will be assumed that for each element m and each set X in any discussion it is possible to determine whether or not the relation m [member of] X is valid.

We will say that set X equals set Y, and write X = Y, if and only if the two sets are identical, that is, contain exactly the same elements. If a set X consists entirely of elements which are members of a second set Y, we say that X is a subset of F and write X [subset or equal to] Y. If, in addition, Y contains one or more elements not in X, we say X is a proper subset of Y.

It is convenient to introduce names for two special sets which will be important in any application. The first is called the universal set and is defined to be the set consisting of all elements under discussion. This set is also referred to as the domain of discourse, or the fundamental domain. The universal set will be denoted by the symbol 1. We note that every set is a subset of the universal set. The second special set, called the null set, is defined to be a set containing no elements at all. By definition, the null set is a subset of every other set. The notation for the null set will be the symbol 0. It is important to note that 0 and 1, as used here, are not numbers but the names of two special sets.

The algebra that will be developed is an algebra for sets, not for elements of sets. For example, the symbol m [member of] X cannot be introduced into the algebra. It is frequently important to work with individual elements of sets, and since we cannot handle elements as such in the algebra, it is convenient to introduce the concept of a unit set. A unit set is a set which consists of a single element, and if this element is, say, x, we denote the set by {x}. In other instances as well, if the set is specified by listing each of the elements in the set, the symbol { } will be used. For example, {a, b, c} is understood to be the set consisting of the elements a, b, and c only.

Associated with each set X is another set X' called the complement of X and defined to be the set consisting of all elements of the universal set which are not elements of X. As special cases we note that the null set and the universal set are each complements of the other.

Example. Consider a stack of books of which some are bound in red, some in black, and the rest in yellow. Suppose that all red books and some of the black books are written in English. The remainder of the black books are in German, and the yellow books are written in French. Let the set of all books in the stack be the universal set and let other sets be denoted as follows:

R is the set of red books,

Y is the set of yellow books,

B is the set of black books,

E is the set of books written in English,

F is the set of books written in French,

G is the set of books written in German.

In this example, Y = F and R [subset or equal to] E. In fact, R is a proper subset of E. If a particular red book is denoted by m, we may write m [member of] R and also m [member of] E. Or we could write {m} [subset or equal to] R and {m} [subset or equal to] E. E' is the set consisting of all yellow books and those black books which are written in German.

Exercises

1. List all subsets of the set {a, b, c}. (There are eight subsets, of which seven are proper subsets, counting the null set.)

2. Use the definition of complement to prove that (X')' = X for any set X.

3. Describe the complement of each set of books given in the example of this section.

4. How many different subsets are there for a set containing a finite number n of elements? [Hint: Express the number of subsets with u elements, u ≤ n, as a combinatorial symbol and use the binomial theorem to sum from 0 to n.]

1–3 The combination of sets. In this section we will investigate the rules by which sets may be combined to form new sets. First, for arbitrary sets X and Y, the union of X and Y is defined to be the set consisting of all elements which are either in X or in Y or in both X and Y. This new set is denoted by X + Y. In the illustration of Section 1–2 for example, R + Y is the set of all red and all yellow books, Y + E + G is the universal set of all books in the stack, and R + E is just E, the set of all books written in English.

Next, the intersection of X and Y, for arbitrary sets X and Y, is defined to be the set consisting of those elements which are both in X and in Y. The intersection of X and Y will be denoted by XY, or by X · Y. We will refer to the centered dot (·) whenever it is desired to discuss the process of forming an intersection, just as the symbol (+) will refer to the process of forming the union of sets. For convenience the centered dot is usually omitted in algebraic expressions, as is common in the algebra of numbers. Again referring to the example of Section 1–2, we note that EB is the set of black books written in English, RY is the null set, and RE is R, the set of red books.

As immediate consequences of the definitions of (+), (·), and ('), we note that for an arbitrary set X, X + X' = 1 and XX' = 0. The following theorem also comes directly from these definitions.

Theorem. If m is any element in the universal set and X and Y are arbitrary sets, then m is a member of one and only one of the sets XY, XY', X'Y, and X'Y'.

Proof. By the definition of complement, m is an element of either X or X' but not both. If it happens that m [member of] X, then since m is an element of either Y or Y' but not both, m is a member of XY or XY' but not both, by definition of intersection. Similarly, if m is a member of X ', then m is a member of X 'Y or X 'Y ' but not both, which completes the proof.

The operations just defined are not independent of the symbols and relations defined in Section 1–2. A little reflection will reveal that the five conditions X [subset or equal to] Y, XY = X, X + Y = Y, XY' = 0, and X' + Y = 1 all represent the same condition on the sets X and Y, namely, that each element of the set X is a member of the set Y. Again, the set X + Y may be written {X'Y')'. These relationships simply illustrate the fact that we have introduced more symbols than are really necessary to treat the algebra of sets. The significance of this fact will be examined more closely in a later section. In the meantime, we will find it convenient to use all these symbols.

The symbols used in this chapter for intersection, union, and complementation are by no means standard. It was considered desirable to use a single notation throughout the text for the several applications of Boolean algebra. The set chosen is the one most commonly used in the application to circuit algebra. The notations most commonly used in other books are listed in the following table.

Symbols in Common Usage

MeaningSymbolic notation

Union of set X and set F
X + F, X [union] F, [disjunction] F

Intersection of set X and set F
XY, X [intersection] Y, [conjunction] Y

Complement of set X
X, X, ~X

Exercises

1. Refer to the Example in Section 1–2 and describe simply, in words, the following sets:

(a) Y + G

(b) RB'

(c) G (B + R)

(d) B + BR

2. Justify for the Example in Section 1–2 that

(a) (G + R)' = G'R'

(b) (GB)' = G' + B'

3. Decide intuitively which of the following are always true for arbitrary sets X, F, and Z. Do not give proofs.

(a) X + XY = X

(b) X (X + Y) = X

(c) X (F + Z) = XY + XZ

(d) X + YZ = (X + Y)(X + Z)

4. If it is known that an element m is neither a member of the set X nor of the set Y', then describe the set to which m must belong. Write the symbolic expression for this set.

5. Let the universal set be the set of all positive integers and define sets S, E, and M as follows:

S is the set of all positive integers less than or equal to 6.

E is the set of all positive integers which are even, 2, 4, 6, etc.

M is the set of all positive integers which are multiples of 3, that is, 3, 6, 9, etc.

Write simple algebraic expressions in terms of S, E, and M for the following sets:

(a) {3, 6}

(b) {1, 3, 5}

All positive integers which are multiples of 6.

All even integers greater than 6.

The set which contains all multiples of 3 and all odd integers.

1–4 Venn diagrams. A formal presentation of Boolean algebra, which will be given in Chapter 2, begins with a description of the symbols to be used and a statement of the axioms which it is assumed the symbols satisfy. Upon this foundation, a framework of theorems and definitions is constructed which becomes a mathematical model to be used in any application which the model seems to fit. The validity of the results obtained from the application depend upon the closeness with which the model fits the practical situation.

In Chapter 1, however, a different approach to Boolean algebra has been adopted. An application has been considered first, with the hope that the reading will be more pleasant and to provide a strong motivation for the axiomatic treatment to follow. This approach has its weaknesses, of course. The greatest is that we have no formal basis upon which to build precise proofs. Since there are no axioms to employ in writing proofs, we must rely upon an intuitive notion of the meanings of terms like "set" and "element." To strengthen this intuition and provide some justification for the basic laws which are valid in the algebra of sets, we shall introduce the concept of a Venn diagram. It should be remembered that such diagrams do not constitute proofs, but rather represent illustrations which make the laws seem plausible.

In a Venn diagram the set of points interior to a rectangle is taken as the universal set. Arbitrary sets within the universal set are represented by the sets of points interior to circles (or other closed regions) within the rectangle. If nothing specific is known about the sets involved, these circles are drawn so that all the possibilities of intersections among the sets are represented. By shading appropriate areas, all combinations of the sets can be represented graphically.

As an illustration of the usefulness of Venn diagrams, consider Fig. 1–1, representing two sets X and Y which have a nonzero intersection. In this figure X', the complement of set X, is shaded with horizontal lines, and Y' is shaded with vertical lines. The set X'Y' appears as the crosshatched area, which is clearly the complement of X + Y. Thus we have illustrated a basic law, that (X + Y)' = X'Y'. In the figure, the unshaded area represents XY, which is clearly the complement of X' + Y', the area shaded either with horizontal lines, or vertical lines, or both. This illustrates a second basic law, namely, that (XY)' = X' + Y'.

As another illustration, consider Fig. 1–2, which illustrates the law X + YZ = (X + Y)(X + Z). This diagram is constructed in steps to show more clearly how the required sets are determined. The diagrams are self-explanatory.

Exercises

1. Draw a Venn diagram showing three sets X, Y, and Z with the maximum number of nonzero intersections and label each of the areas representing the sets XYZ, XYZ', XY'Z, X'YZ, XY'Z', X'YZ', X'Y'Z, X'Y'Z'.

---

Excerpted from Boolean Algebra and Its Applications by J. Eldon Whitesitt. Copyright © 2010 Dover Publications, Inc.. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

---