Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.
BOOLEAN ALGEBRA AND ITS APPLICATIONS This book is in the ADDISON-WESLEY SERIES IN THE ENGINEERING SCIENCES Electrical and Control Systems BOOLEAN ALGEBRA AND ITS APPLICATIONS by J. ELDON WHITESITT Department of Mathematics Montana State College An ADDISON-WESLEY PUBLISHING COMPANY, INC. READING, MASSACHUSETTS, U.S.A. LONDON, ENGLAND Copyright © 1961 ADDISON-WESLEY PUBLISHING COMPANY, INC. Printed in the United States of America ALL RIGHTS RESERVED. THIS BOOK, OR PARTS THERE- OF, MAY NOT BE REPRODUCED IN ANY FORM WITH- OUT WRITTEN PERMISSION OF THE PUBLISHER. Library of Congress Catalog Card No. 61-50P27 Second printing-January, 1962 PREFACE George Boole (1815-1864) introduced in his book The Laws of Thought the first systematic treatment of logic and developed for this purpose the algebraic system now known by his name, Boolean algebra. Few mathe- matical works of the past 100 years have had a greater impact upon mathematics and philosophy than this famous book. The significance of the work has been well expressed by Augustus De llorgan: That the symbolic processes of algebra, invented as tools of numerical calculation, should be competent to express every act of thought, and to furnish the grammar and dictionary of an all-containing system of logic, would not have been believed until it was proved in Laws of Thought. In addition to its applications in the field of logic, Boolean algebra has two other important applications. The first of these arises from the fact that Boolean algebra is the natural algebra with which to treat the com- bination of sets of elements under the operations of intersection and union of sets. With the addition of the idea of "number of elements" in a set, Boolean algebra becomes the foundation for the theory of probability. The algebra of sets is also important in many other branches of mathe- matics. With the publication of two papers approximately 20 years ago, Claude E. Shannon introduced a new area of application of Boolean algebra when he showed that the basic properties of series and parallel combinations of bistable electrical devices such as relays could be adequately repre- sented by this algebra. Since this time, Boolean algebra has played a significant role in the important and complicated task of designing tele- phone switching circuits, automatic control devices, and electronic com- puters. At the present time, more interest is centered in this application than in either of the others. This book, designed to be used as a text in a one-semester or two- quarter course, has developed out of notes used in such a course at Mon- tana State College for the past two years. It is not possible, in a single book, to give an exhaustive account of Boolean algebra and all of its applications. The purpose of this book is to introduce the subject on a level which will make it available even to those with rather limited mathe- matical background, and to examine each of the applications in enough detail so that the student will gain an appreciation of the scope and use- fulness of the subject. This book could well serve as a background for specialized courses in any of the major areas of application. v vi PREFACE The first chapter deals with the algebra of sets from an intuitive point of view, since it is felt that this application is the most readily understood with little formal training. While this approach is less satisfying to the mathematically mature than an axiomatic treatment might be, it is hoped that this section will serve as motivation for the precise development of the subject which follows in Chapter 2. In Chapter 2, Boolean algebra is presented formally as an abstract algebraic system with no reference to applications. For many students this will be their first introduction to modern mathematics, and the training in the axiomatic method will be of value in any future work in mathematics. Chapter 3 introduces symbolic logic, with special emphasis on those portions of logic which depend heavily upon the algebra of propositions, a Boolean algebra. In addition to extending the area of application of Boolean algebra, this chapter emphasizes those topics of logic most often used in elementary mathematics. The concepts of valid argument and indirect proofs are discussed in some detail. Chapters 4, 5, and 6 are closely related and all deal with the third application of Boolean algebra mentioned, the algebra of circuits. Switch- ing circuits are discussed in Chapter 4 as the most easily understood of the many types of circuits which can be treated. In Chapter 5 the ideas are extended to relay circuits which, although similar in principle, are much more versatile in applications. Finally, Chapter 6 discusses briefly some of the arithmetic circuits used by modern computers. Here the emphasis is on logical design rather than on the physical properties of components. Chapter 7 is added for the benefit of those who would like to pursue the algebra of sets a little further, to an application in probability theory. While the treatment is brief, many fundamental concepts of probability are introduced and the basic dependence of probability upon the algebra of sets is clearly shown. Since no notation is standard throughout all three applications of Boolean algebra, the notation used in this book was chosen on the basis of simplicity and ease of manipulation. Skill in the correct algebraic manipu- lation of the symbols is essential for the applications, and it is hoped that the use throughout of a single notational system will speed the process of acquiring this skill. The notation used is that commonly used in treatises on logical design of circuits, but will serve equally well for the other applications. A short list of references is given at the end of each chapter. Students should be encouraged to do outside reading on topics of particular interest, either in these suggested texts or in current periodicals. I would like to express appreciation to John W. Hurst, Head of the Department of Mathematics, Montana State College, for his encourage- PREFACE vl; ment and for providing the opportunity to use this material in the class- room in its various stages of development. Thanks are due also to Mrs. Janet Bierrum for her skillful help with typing and the preparation of the manuscript. Finally, I dedicate this book to my wife, Doris Whitesitt, for her under- standing patience during the time of its preparation. Montana State College J. E. W. March 1960 CON TENTS CHAPTER 1. THE ALGEBRA OF SETS . . 1 1-1 Introduction . . . . . . . . . . . . . . . . 1 1-2 Element and set . . . . . . . . . . . . . . . 1 1-3 The combination of sets . . . . . . . . . . . . 3 1-4 Venn diagrams . . . . . . . . . . . . . . . 5 1-5 Fundamental laws . . . . . . . . . . . . . . 7 1-6 Expanding, factoring, and simplifying . . . . . . . . 9 1-7 Properties of set inclusion . . . . . . . . . . . . 12 1-8 Conditional equations . . . . . . . . . . . . . 15 1-9 Solution of equations . . . . . . . . . . . . . 19 1-10 The number of elements in a set . . . . . . . . . . 20 CHAPTER 2. BOOLEAN ALGEBRA . . . . . . . . . . . . 25 2-1 Introduction . . . . . . . . . . . . . . . . 25 2-2 Preliminary definitions . . . . . . . . . . . . . 25 2-3 Definition and properties of a Boolean algebra . . . . . . 27 2-4 Disjunctive normal form . . . . . . . . . . . . 33 2-5 Conjunctive normal form . . . . . . . . . . . . 38 2-6 Representation of a Boolean algebra . . . . . . . . . 41 CHAPTER 3. SYMBOLIC LOGIC AND THE ALGEBRA OF PROPOSITIONS . 43 3-1 Introduction . . . . . . . . . . . . . . . . 43 3-2 Propositions and definitions of symbols . . . . . . . . 43 3-3 Truth tables . . . . . . . . . . . . . . . . 47 3-4 Object logic and syntax logic . . . . . . . . . . . 52 3-5 Material implication . . . . . . . . . . . . . . 52 3-6 Truth sets for propositions . . . . . . . . . . . . 56 3-7 Quantifiers . . . . . . . . . . . . . . . . 59 3-8 Valid arguments . . . . . . . . . . . . . . . 61 3-9 Indirect proofs . . . . . . . . . . . . . . . 66 3-10 Functionally complete sets of operations . . . . . . . . 68 3-11 Special problems . . . . . . . . . . . . . . . 70 CHAPTER 4. SWITCHING ALGEBRA . . . . . . . . . . . 75 4-1 Introduction . . . . . . . . . . . . . . . . 75 4-2 Definition of the algebraic symbols . . . . . . . . . 75 4-3 Simplification of circuits . . . . . . . . . . . . 79 4-4 Non-series-parallel circuits . . . . . . . . . . . . 83 4-5 Design of circuits from given properties . . . . . . . . 90 4-6 Design of n-terminal circuits . . . . . . . . . . . 94 4-7 Symmetric functions and their circuits . . . . . . . . 99 ix X CONTENTS CHAPTER 5. RELAY CIRCUITS AND CONTROL PROBLEMS . . . . . 104 5-1 Introduction . . . . . . . . . . . . . . . 104 5-2 Basic relay control paths . . . . . . . . . . . . 106 5-3 n-terminal circuits and the uses of transfer contacts . . . . 110 5-4 Operate and hold paths . . . . . . . . . . . . 116 5-5 Sequential circuits and sequence diagrams . . . . . . . 119 5-6 Design of sequential relay circuits from given conditions . . . 124 5-7 Special problems involving the design of relay circuits . . . . 132 CHAPTER 6. CIRCUITS FOR ARITHMETIC COMPUTATION . . . . . 135 6-1 Introduction . . . . . . . . . . . . . . . . 135 6-2 The binary number system . . . . . . . . . . . 135 6-3 Logical circuit elements . . . . . . . . . . . . 138 6-4 Addition of binary numbers . . . . . . . . . . . 142 6-5 Subtraction of binary numbers. . . . . . . . . . . 145 6-6 Accumulation . . . . . . . . . . . . . . . 147 6-7 Binary multiplication . . . . . . . . . . . . . 150 CHAPTER 7. INTRODUCTION TO PROBABILITY IN FINITE SAMPLE SPACES 153 7-1 Introduction . . . . . . . . . . . . . . . . 153 7-2 Event, sample space, probability . . . . . . . . . . 153 7-3 Conditional probability . . . . . . . . . . . . . 157 7-4 Some aids to counting . . . . . . . . . . . . . 160 7-5 Bernoulli trials, binomial distribution . . . . . . . . 163 ANSWERS TO SELECTED PROBLEMS . . . . . . . . . . . 168 INDEX . . . . . . . . . . . . . . . . . . . . 179 CHAPTER 1 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 repre- sented 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 per- pendicular 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 1 2 THE ALGEBRA OF SETS [CHAP. 1 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, E, 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 E 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 E 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 Y and write X c 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 E 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 . 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 1-3] THE COMBINATION OF SETS 3 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, F = F and R e E. In fact, R is a proper subset of E. If a particular red book is denoted by m, we may write m E R and also in e E. Or we could write < m 19; R and < m >e 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 1. (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 univer- sal set of all books in the stack, and R + E is just B, 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 follow- ing theorem also comes directly from these definitions. 4 THE ALGEBRA OF SETS [CHAP. 1 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 X Y, 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 e X, then since m is an element of either Y or Y' but not both, m is a member of X Y or X1" 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 c 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 comple- mentation 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 Meaning Symbolic notation Union of set X and set Y X + Y, X U Y, X V Y Intersection of set X and set Y X Y, X fl Y, X A 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, Y, and Z. Do not give proofs. (a) X -- X Y = X (b) X (X -I- Y) = X (c) X (Y + Z) = X Y + XZ (d) X + YZ = (X + Y) (X + Z) 1-4] VENN DUGR NIS 5 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 .11 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. 11 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 if for the following sets: (a) 13, 6] (b) ]1, 3, 5] (c) All positive integers which are multiples of 6. (d) All even integers greater than 6. (e) 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 ob- tained 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