%$Header$ \chapter[\cbalzeroshorttitle{}]{\cbalzerolongtitle{}} \label{cbal0} \section{Introduction, Definition, And History Of Boolean Algebra} %Section tag: INT0 \label{cbal0:sint0} \index{Boolean algebra} In this chapter, we review methods of simplifying \index{Boolean function}Boolean functions, and show how such methods can be used to simplify software constructs or to construct software which is more compact (in ROM or RAM) or executes more quicky. Boolean algebra is named after \index{Boole, George}George Boole, a 19th-century British mathematician. A fairly concise biography of George Boole comes from \cite{bibref:w:georgeboolebio01}: \begin{quote} George Boole first attended a school in Lincoln, then a commerical school. His early instruction in mathematics, however, was from his father who also gave George a liking for constructing optical instruments. George's interests turned to languages and he received instruction in Latin from a local bookseller. By the age of 12 George had become so skilled in Latin that it provoked an argument. He translated an ode by the Latin poet Horace which his father was so proud of that he had it published. However the talent was such that a local schoolmaster disputed that any 12 year old could have written with such depth. Boole did not study for an academic degree, but from the age of 16 he was an assistant school teacher. He maintained his interest in languages and intended to enter the Church. From 1835, however, he seems to have changed his mind for he opened his own school and began to study mathematics on his own. He was later to realize that he had almost wasted five years in trying to teach himself the subject instead of having a skilled teacher. At this time Boole studied the works of Laplace and Lagrange, making notes which would later be the basis for his first mathematics paper. However he did receive encouragement from Duncan Gregory who at this time was in Cambridge and the editor of the recently founded \emph{Cambridge Mathematical Journal}. Boole was unable to take Duncan Gregory's advice and study courses at Cambridge as he required the income from his school to look after his parents. However he began publishing in the \emph{Cambridge Mathematical Journal} and his interests were also influenced by Duncan Gregory as he began to study algebra. An application of algebraic methods to the solution of differential equations was published by Boole in the \emph{Transactions of the Royal Society} and for this work he received the Society's Royal Medal. His mathematical work was beginning to bring him fame. Boole was appointed to the chair of mathematics at Queens College, Cork in 1849. He taught there for the rest of his life, gaining a reputation as an outstanding and dedicated teacher. In 1854 he published \emph{An investigation into the Laws of Thought, on Which are founded the Mathematical Theories of Logic and Probabilities}. Boole approached logic in a new way reducing it to a simple algebra, incorporating logic into mathematics. He pointed out the analogy between algebraic symbols and those that represent logical forms. It began the algebra of logic called Boolean algebra which now finds application in computer construction, switching circuits etc. Boole also worked on differential equations, the influential \emph{Treatise on Differential Equations} appeared in 1859, the calculus of finite differences, \emph{Treatise on the Calculus of Finite Differences} (1860), and general methods in probability. He published around 50 papers and was one of the first to investigate the basic properties of numbers, such as the distributive property, that underlie the subject of algebra. Many honours were given to Boole as the genius in his work was recognised. He received honorary degrees from the universities of Dublin and Oxford and was elected a Fellow of the Royal Society (1857). However his career, which was started rather late, came to an unfortunately early end when he died at the age of 49. The circumstances are described by Macfarlane in [17]\footnote{As reproduced from \cite{bibref:w:georgeboolebio01}---this is not a valid reference number in this work.} as follows: \begin{quote} One day in 1864 he walked from his residence to the College, a distance of two miles, in the drenching rain, and lectured in wet clothes. The result was a feverish cold which soon fell upon his lungs and terminated his career \ldots{} \end{quote} What Macfarlane fails to say is that Boole's wife (Mary---niece of Sir George Everest, after whom the mountain is named) believed that a remedy should resemble the cause. She put Boole to bed and threw buckets of water over the bed since his illness had been caused by getting wet. Hirst described Boole as: \begin{quote} \ldots{} evidently an earnest able and at the same time a genial man. \end{quote} His work was praised by \index{DeMorgan, Augustus}De Morgan who said: \begin{quote} Boole's system of logic is but one of many proofs of genius and patience combined. \ldots{} 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. When Hobbes \ldots{} published his Computation or Logique'' he had a remote glimpse of some of the points which are placed in the light of day by Mr Boole. \end{quote} Boolean algebra has wide applications in telephone switching and the design of modern computers. Boole's work has to be seen as a fundamental step in today's computer revolution. (Article by: J. J. O'Connor and E. F. Robertson.) \end{quote} In the preface of \cite{bibref:b:whitesittbooleanalgandapps}, Whitesitt explains the significance of Boole's work: \begin{quote} George Boole (1815-1864) introduced in his book \emph{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 last 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: \begin{quote} 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 \emph{Laws Of Thought}. \end{quote} 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,\footnote{Whitesitt's book was first published in 1961, so Whitesitt probably means \emph{20 years ago} with respect to 1961.} \index{Shannon, Claude E.}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. \end{quote} Claude E. Shannon's classic 1937 thesis is described separately in several places. From \cite{{bibref:w:boolealghist01}}: \begin{quote} Shannon, whose 1937 thesis centered on the improvement of the Differential Analyzer, a clunky mechanical gear and shaft addition machine, realized that Boolean algebraic principles governed its operation. He proposed that such a machine could be built with circuits using components that were governed by Boolean principles. Shannon's paper was regarded as genius and his ideas were almost immediately incorporated into the telephone system. Shannon took a position at Bell Labs. Later, of course, Shannon's thesis came to be seen as a focal point in the development of modern computers. \end{quote} In \cite{bibref:w:boolealghist02}, Shannon's thesis is described very favorably: \begin{quote} Around the 1850's, the British mathematician George Boole was busily inventing a new form of mathematics, in which he represented logical expressions in a mathematical form now known as Boolean Algebra. Unfortunately, with the exception of students of philosophy and symbolic logic, Boolean Algebra was destined to remain largely unknown and unused for the better part of a century. It fact it was not until 1938 that Claude E. Shannon published an article based on his master's thesis at MIT. (Shannon's thesis has since been described as: \emph{Possibly the most important master's thesis of the twentieth century.''}) In his paper, which was widely circulated, Shannon showed how Boole's concepts of TRUE and FALSE could be used to represent the functions of switches in electronic circuits. It is difficult to convey just how important this concept was; suffice it to say that Shannon had provided electronics engineers with the mathematical tool they needed to design digital electronic circuits, and these techniques remain the cornerstone of digital electronic design to this day. Apropos of nothing at all, Shannon is also credited with the invention of the rocket-powered Frisbee, and is famous for riding down the corridors of Bell Laboratories on a unicycle while simultaneously juggling four balls. \end{quote} In summary, in 1854 George Boole published his classic work \emph{An investigation into the Laws of Thought, on Which are founded the Mathematical Theories of Logic and Probabilities}, which laid the foundation of manipulation of logical ideas using algebraic mechanisms. Boole's ideas were revived in 1937 and 1938 by Claude E. Shannon in his master's thesis and a subsequent article, in which Shannon applied Boole's ideas to the design of electric switching circuits. Shannon's reapplication of Boole's work came to be seen as a focal point in the development of modern computers. \section[Simplification By Algebraic Manipulation] {Simplification Of Boolean Functions By Algebraic Manipulation} %Section Tag: SAM0 \label{cbal0:ssam0} We assume that the reader has had previous exposure to \index{Boolean function!simplification of}simplification of Boolean functions. For this reason, this section is a review (it is terse and moves quickly). (For readers without this background, we recommend \cite{bibref:b:manodigitaldesignseconded}.) The most direct way to simplify Boolean functions is \index{Boolean function!algebraic simplification}\emph{algebraic} transformation---to use transformation postulates and theorems to transform algebraic expressions to a more desirable equivalent form. \subsection{Nomenclature And Operators} %Subsection Tag: NOM0 \label{cbal0:ssam0:snom0} We define the set of two elements which we will use in two-valued Boolean algebra as 0' and '1' (or alternatively as FALSE' and TRUE', respectively). All functions which we will describe subsequently require inputs which are members of this set and will produce outputs which are also members of this set. The \emph{complement} or \emph{negation} operator (or function) maps from 0$\rightarrow$1 and from 1$\rightarrow$0 (see Table \ref{tbl:cbal0:ssam0:snom0:01}). We denote this operator by an apostrophe following the variable to be complemented (example: $x'$). Alternatively, in some circumstances, we may use the tilde ($\sim{}x$), the overbar ($\overline{x}$), or the negation symbol ($\neg{}x$). \begin{table} \caption{Definition Of Logical Complement, Logical And, Logical Or, And Logical Exclusive Or Operators} \label{tbl:cbal0:ssam0:snom0:01} \begin{center} \begin{tabular}{|c|c||c|c|c|c|} \hline $X$ & $Y$ & $X'$ & $XY$ & $X+Y$ & $X \oplus{} Y$ \\ \hline \hline 0 & 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 1 & 1 & 0 & 1 & 1 \\ \hline 1 & 0 & 0 & 0 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 & 1 & 0 \\ \hline \end{tabular} \end{center} \end{table} The \emph{logical AND} (or simply \index{AND}\index{Boolean algebra!AND}\emph{AND}) operator (or function) returns TRUE if both of its input arguments are TRUE (see Table \ref{tbl:cbal0:ssam0:snom0:01}). We denote this operator by the \emph{times} symbol (example: $x \times{} y$), by the keyword AND', or by placing the operands adjacent to each other (examples: $xy$, $x(y)$). The \emph{logical OR} (or simply \index{OR}\index{Boolean algebra!OR}\emph{OR}) operator (or function) returns TRUE if either of its input arguments are TRUE (see Table \ref{tbl:cbal0:ssam0:snom0:01}). We denote this operator by the \emph{plus} symbol (example: $x + y$) or by the keyword OR'. The \emph{logical exclusive-OR} (or simply \index{XOR}\index{Boolean algebra!XOR} \emph{XOR}) operator (or function) returns TRUE if either but not both of its input arguments are TRUE (see Table \ref{tbl:cbal0:ssam0:snom0:01}). We denote this operator by the \emph{circled plus} symbol (example: $x \oplus{} y$), by the \emph{caret} character (example: $x$\^{}$y$), or by the keyword XOR'. The exclusive-OR function is not a function traditionally considered in the canonical forms of Boolean algebra. However, we consider it here because our aims may in some cases be subtly different than the aims of classic two-valued Boolean algebra. The goal of classic Boolean algebra is to minimize the number of terms which appear in a canonical form. However, often our goal here is to rearrange Boolean functions into a form which is optimal for implementation on a computer. Since actual computers usually provide a bitwise exclusive-OR instruction, there are some applications where it may be useful to consider the underlying instruction set of the computer (for example, see \emph{Vertical Counters}, Section \ref{cbal0:svct0}). In general, there are $2^{2^N}$ different Boolean functions of $N$ input variables, so it isn't practical to name functions involving more than 2 input variables. There are 16 ($=2^{2^2}$) Boolean functions of 2 input variables, and these are enumerated in Table \ref{tbl:cbal0:ssam0:snom0:02}. \begin{table} \caption{Sixteen Possible Boolean Functions $f(A,B)$ Of Two Boolean Variables} \label{tbl:cbal0:ssam0:snom0:02} \begin{center} \begin{tabular}{|c||c|c|c|c||l|} \hline \small{Func.} & $\scriptstyle{f(1,1)}$ & $\scriptstyle{f(1,0)}$ & $\scriptstyle{f(0,1)}$ & $\scriptstyle{f(0,0)}$ & Function Description \\ \small{Num.} & & & & & \\ \hline \hline 0 & 0 & 0 & 0 & 0 & \small{Zero'' or clear'' function. Always} \\ & & & & & \small{returns zero regardless of $A$ and $B$ } \\ & & & & & \small{input values. } \\ \hline 1 & 0 & 0 & 0 & 1 & \small{Logical NOR = $(A+B)'$. } \\ \hline 2 & 0 & 0 & 1 & 0 & \small{Inhibition = $BA'$. So named because } \\ & & & & & \small{a TRUE value of $A$ inhibits $B$. Also } \\ & & & & & \small{equivalent to $B>A$ or to $AB$ or to \$B