%$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_bal0/c_bal0.tex,v 1.10 2003/11/03 02:14:24 dtashley Exp $
\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 $A**B$ or to $B**