Theory and application of Boolean algebra.

摘要

The basic ideas of Boolean Algebra were introduced in 1847 in George Boole's book The Mathematical Analysis of Logic as a means of dealing with symbolic logic. In 1938 Claude Shannon used Boolean algebra to describe the logical relationships found between the elements of switching circuits. His goal here was to simplify these circuits. In our thesis we look at Boolean algebra from both a theoretical standpoint as well as from its utility in approaching the problem of simplifying switching circuits. We begin with the axiomatic description of Boolean algebra and go through the proofs of several of its basic and most useful properties. Next we introduce the notions of logic gates and switching circuits and their connection with Boolean functions. We particularly emphasize the representation of these functions in canonical forms involving components known as minterms and maxterms.; While these Boolean functions may sometimes be simplified using the basic axioms and properties of Boolean algebra, a more systematic approach is needed. One such approach is the Karnaugh Map Method. We illustrate its use in minimizing the number of terms in functions of 2, 3, 4, 5 and 6 variables. Next we consider the Variable Mapping Method for dealing with large numbers of variables. The last method we consider is the Quine-McCluskey method. We explain this in detail and elaborate with several examples. The goal of this thesis is to provide a document to which a reader of minimal background might turn in order to learn about Boolean algebra as applied to the problem of reducing circuit complexity.