J. Eldon Whitesitt [Whitesitt - Boolean Algebra and Its Applications (Dover Books on Computer Science)

AND ITS APPLICATIONS

by

J. ELDON WHITESITT

DOVER PUBLICATIONS, INC.

MINEOLA, NEW YORK

Bibliographical Note

This Dover edition, first published in 2010, is an unabridged republication of the 1995 Dover edition of the work originally published in 1961 by the Addison-Wesley Publishing Company, Reading, Massachusetts.

Library of Congress Cataloging-in-Publication Data

Whitsitt, J. Eldon (John Eldon), 1922

Boolean algebra and its applications / J. Eldon Whitesitt. Dover ed.

p. cm.

Originally published: Reading, Mass. : Addison-Wesley, 1961.

Includes bibliographical references and index.

eISBN-13: 978-0-486-15816-7

1. Algebra, Boolean. I. Title.

QA10.3.W48 2010

511.3'24dc22

2009042829

Manufactured in the United States by Courier Corporation

47767301

www.doverpublications.com

George Boole (18151864) 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 mathematical 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 Morgan :

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 combination 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 mathematics.

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 represented by this algebra. Since this time, Boolean algebra has played a significant role in the important and complicated task of designing telephone switching circuits, automatic control devices, and electronic computers. 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 Montana 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 mathematical background, and to examine each of the applications in enough detail so that the student will gain an appreciation of the scope and usefulness of the subject. This book could well serve as a background for specialized courses in any of the major areas of application.

, 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.

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.

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.

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 manipulation 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 encouragement and for providing the opportunity to use this material in the classroom 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 understanding patience during the time of its preparation.

J. E. W.

Montana State College

March 1960

11 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 . 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.

12 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.