# Contents of /pubs/books/ucbka/trunk/c_bal0/c_bal0.tex

Mon Aug 12 00:47:10 2019 UTC (3 years, 7 months ago) by dashley
File MIME type: application/x-tex
File size: 51086 byte(s)
Change keyword substitution (migration from cvs to svn).

 1 %$Header$ 2 3 \chapter[\cbalzeroshorttitle{}]{\cbalzerolongtitle{}} 4 5 \label{cbal0} 6 7 \section{Introduction, Definition, And History Of Boolean Algebra} 8 %Section tag: INT0 9 \label{cbal0:sint0} 10 11 \index{Boolean algebra} 12 In this chapter, we review methods of 13 simplifying \index{Boolean function}Boolean functions, and 14 show how such methods can be used to simplify software constructs 15 or to construct software which is more compact (in ROM or RAM) 16 or executes more quicky. 17 18 Boolean algebra is named after \index{Boole, George}George Boole, 19 a 19th-century British mathematician. 20 A fairly concise biography of George Boole comes from 21 \cite{bibref:w:georgeboolebio01}: 22 23 \begin{quote} 24 George Boole first attended a school in Lincoln, then a commerical school. 25 His early instruction in mathematics, however, was from his father who 26 also gave George a liking for constructing optical instruments. George's 27 interests turned to languages and he received instruction in Latin from a 28 local bookseller. 29 30 By the age of 12 George had become so skilled in Latin that it provoked 31 an argument. He translated an ode by the Latin poet Horace which his 32 father was so proud of that he had it published. However the talent was 33 such that a local schoolmaster disputed that any 12 year old could 34 have written with such depth. 35 36 Boole did not study for an academic degree, but from the age of 16 he was an 37 assistant school teacher. He maintained his interest in languages 38 and intended to enter the Church. From 1835, however, he seems to have 39 changed his mind for he opened his own school and began to study mathematics 40 on his own. He was later to realize that he had almost wasted five years 41 in trying to teach himself the subject instead of having a skilled teacher. 42 43 At this time Boole studied the works of Laplace and Lagrange, making 44 notes which would later be the basis for his first mathematics paper. 45 However he did receive encouragement from Duncan Gregory who at this 46 time was in Cambridge and the editor of the recently founded 47 \emph{Cambridge Mathematical Journal}. 48 49 Boole was unable to take Duncan Gregory's advice and study courses at 50 Cambridge as he required the income from his school to look after 51 his parents. However he began publishing in the \emph{Cambridge 52 Mathematical Journal} and his interests were also influenced by Duncan Gregory 53 as he began to study algebra. An application of algebraic methods 54 to the solution of differential equations was published by Boole in the 55 \emph{Transactions of the Royal Society} and for this work he received 56 the Society's Royal Medal. His mathematical work was beginning to bring 57 him fame. 58 59 Boole was appointed to the chair of mathematics at Queens College, 60 Cork in 1849. He taught there for the rest of his life, gaining a reputation 61 as an outstanding and dedicated teacher. 62 63 In 1854 he published \emph{An investigation into the Laws of Thought, on 64 Which are founded the Mathematical Theories of Logic and Probabilities}. 65 Boole approached logic in a new way reducing it to a simple algebra, 66 incorporating logic into mathematics. He pointed out the analogy 67 between algebraic symbols and those that represent logical forms. 68 It began the algebra of logic called Boolean algebra which now finds 69 application in computer construction, switching circuits etc. 70 71 Boole also worked on differential equations, the influential 72 \emph{Treatise on Differential Equations} appeared in 1859, the calculus of finite 73 differences, \emph{Treatise on the Calculus of Finite Differences} (1860), 74 and general methods in probability. He published around 50 papers and 75 was one of the first to investigate the basic properties of numbers, such 76 as the distributive property, that underlie the subject of algebra. 77 78 Many honours were given to Boole as the genius in his work was recognised. 79 He received honorary degrees from the universities of Dublin 80 and Oxford and was elected a Fellow of the Royal Society (1857). 81 However his career, which was started rather late, came to an unfortunately 82 early end when he died at the age of 49. The circumstances are described 83 by Macfarlane in [17]\footnote{As reproduced from 84 \cite{bibref:w:georgeboolebio01}---this is not a valid reference 85 number in this work.} as follows: 86 87 \begin{quote} 88 One day in 1864 he walked from his residence to the College, 89 a distance of two miles, in the drenching rain, and lectured in wet 90 clothes. The result was a feverish cold which soon fell upon his 91 lungs and terminated his career \ldots{} 92 \end{quote} 93 94 What Macfarlane fails to say is that Boole's wife 95 (Mary---niece of Sir George Everest, after whom the mountain is named) believed that a 96 remedy should resemble the cause. She put Boole to bed and threw 97 buckets of water over the bed since his illness had been caused by getting 98 wet. 99 100 Hirst described Boole as: 101 102 \begin{quote} 103 \ldots{} evidently an earnest able and at the same time a genial man. 104 \end{quote} 105 106 His work was praised by \index{DeMorgan, Augustus}De Morgan who said: 107 108 \begin{quote} 109 Boole's system of logic is but one of many proofs of genius and patience combined. 110 \ldots{} That the symbolic processes of algebra, 111 invented as tools of numerical calculation, should be competent to 112 express every act of thought, and to furnish the grammar and 113 dictionary of an all-containing system of logic, would not have 114 been believed until it was proved. When Hobbes \ldots{} published his 115 Computation or Logique'' he had a remote glimpse of some of the points which 116 are placed in the light of day by Mr Boole. 117 \end{quote} 118 119 Boolean algebra has wide applications in telephone switching and the 120 design of modern computers. Boole's work has to be seen as a 121 fundamental step in today's computer revolution. 122 (Article by: J. J. O'Connor and E. F. Robertson.) 123 \end{quote} 124 125 In the preface of 126 \cite{bibref:b:whitesittbooleanalgandapps}, Whitesitt explains the 127 significance of Boole's work: 128 129 \begin{quote} 130 George Boole (1815-1864) introduced in his book \emph{The Laws Of Thought} 131 the first systematic treatment of logic and developed for this purpose 132 the algebraic system now known by his name, Boolean algebra. Few 133 mathematical works of the last 100 years have had a greater impact 134 upon mathematics and philosophy than this famous book. The significance 135 of the work has been well expressed by Augustus De Morgan: 136 137 \begin{quote} 138 That the symbolic processes of algebra, invented as tools of numerical 139 calculation, should be competent to express every act of thought, and to 140 furnish the grammar and dictionary of an all-containing system of 141 logic, would not have been believed until it was proved in 142 \emph{Laws Of Thought}. 143 \end{quote} 144 145 In addition to its applications in the field of logic, Boolean algebra 146 has two other important applications. The first of these arises from 147 the fact that Boolean algebra is the natural algebra with which to 148 treat the combination of sets of elements under the operations of 149 intersection and union of sets. With the addition of the idea of 150 number of elements'' in a set, Boolean algebra becomes the 151 foundation for the theory of probability. The algebra 152 of sets is also important in many other branches of mathematics. 153 154 With the publication of two papers approximately 20 years 155 ago,\footnote{Whitesitt's book was first published in 1961, 156 so Whitesitt probably means \emph{20 years ago} with 157 respect to 1961.} 158 \index{Shannon, Claude E.}Claude E. Shannon introduced a new 159 area of application of 160 Boolean algebra when he showed that the basic properties of 161 series and parallel combinations of bistable electrical 162 devices such as relays could be adequately represented 163 by this algebra. Since this time, Boolean algebra has 164 played a significant role in the important and complicated 165 task of designing telephone switching circuits, automatic 166 control devices, and electronic computers. At the present 167 time, more interest is centered in this application than 168 in either of the others. 169 \end{quote} 170 171 Claude E. Shannon's classic 1937 thesis is described separately 172 in several places. From \cite{{bibref:w:boolealghist01}}: 173 174 \begin{quote} 175 Shannon, whose 1937 thesis centered on the improvement of the 176 Differential Analyzer, a clunky mechanical gear and shaft addition 177 machine, realized that Boolean algebraic principles governed its operation. 178 He proposed that such a machine could be built with circuits using 179 components that were governed by Boolean principles. Shannon's paper 180 was regarded as genius and his ideas were almost immediately 181 incorporated into the telephone system. Shannon took a position at Bell 182 Labs. Later, of course, Shannon's thesis came to be seen as a focal point 183 in the development of modern computers. 184 \end{quote} 185 186 In \cite{bibref:w:boolealghist02}, Shannon's thesis is described 187 very favorably: 188 189 \begin{quote} 190 Around the 1850's, the British mathematician George Boole was 191 busily inventing a new form of mathematics, in which he represented 192 logical expressions in a mathematical form now known as 193 Boolean Algebra. 194 195 Unfortunately, with the exception of students of philosophy 196 and symbolic logic, Boolean Algebra was destined to remain 197 largely unknown and unused for the better part of a century. 198 It fact it was not until 1938 that Claude E. Shannon published 199 an article based on his master's thesis at MIT. (Shannon's 200 thesis has since been described as: \emph{Possibly the 201 most important master's thesis of the twentieth century.''}) 202 203 In his paper, which was widely circulated, Shannon showed how 204 Boole's concepts of TRUE and FALSE could be used to represent 205 the functions of switches in electronic circuits. It is difficult 206 to convey just how important this concept was; suffice it to say 207 that Shannon had provided electronics engineers with the mathematical 208 tool they needed to design digital electronic circuits, and these 209 techniques remain the cornerstone of digital electronic 210 design to this day. 211 212 Apropos of nothing at all, Shannon is also credited with the invention 213 of the rocket-powered Frisbee, and is famous for riding down the 214 corridors of Bell Laboratories on a unicycle while simultaneously 215 juggling four balls. 216 \end{quote} 217 218 In summary, in 1854 George Boole published his classic work 219 \emph{An investigation into the Laws of Thought, on 220 Which are founded the Mathematical Theories of Logic and Probabilities}, 221 which laid the foundation of manipulation of 222 logical ideas using algebraic mechanisms. Boole's ideas 223 were revived in 1937 and 1938 by Claude E. Shannon 224 in his master's thesis and a subsequent article, in which 225 Shannon applied Boole's ideas to the design of electric 226 switching circuits. Shannon's reapplication of Boole's work 227 came to be seen as a focal point in the development of modern 228 computers. 229 230 231 \section[Simplification By Algebraic Manipulation] 232 {Simplification Of Boolean Functions By Algebraic Manipulation} 233 %Section Tag: SAM0 234 \label{cbal0:ssam0} 235 236 We assume that the reader has had previous exposure to 237 \index{Boolean function!simplification of}simplification of 238 Boolean functions. For this reason, this section is a review (it is terse 239 and moves quickly). (For readers without this background, we 240 recommend \cite{bibref:b:manodigitaldesignseconded}.) 241 242 The most direct way to simplify Boolean functions is 243 \index{Boolean function!algebraic simplification}\emph{algebraic} 244 transformation---to use transformation postulates and 245 theorems to transform algebraic 246 expressions to a more desirable equivalent form. 247 248 249 \subsection{Nomenclature And Operators} 250 %Subsection Tag: NOM0 251 \label{cbal0:ssam0:snom0} 252 253 We define the set of two elements which we will use in 254 two-valued Boolean 255 algebra as 0' and '1' (or alternatively as 256 FALSE' and TRUE', respectively). 257 All functions which we will describe subsequently require 258 inputs which are members of this set and will produce outputs 259 which are also members of this set. 260 261 The \emph{complement} or \emph{negation} operator (or function) 262 maps from 0$\rightarrow$1 and from 1$\rightarrow$0 (see Table 263 \ref{tbl:cbal0:ssam0:snom0:01}). 264 We denote this operator 265 by an apostrophe 266 following the variable to be complemented (example: $x'$). 267 Alternatively, in some circumstances, we may use the 268 tilde ($\sim{}x$), the overbar ($\overline{x}$), or 269 the negation symbol ($\neg{}x$). 270 271 \begin{table} 272 \caption{Definition Of Logical Complement, Logical And, Logical Or, And Logical 273 Exclusive Or Operators} 274 \label{tbl:cbal0:ssam0:snom0:01} 275 \begin{center} 276 \begin{tabular}{|c|c||c|c|c|c|} 277 \hline 278 $X$ & $Y$ & $X'$ & $XY$ & $X+Y$ & $X \oplus{} Y$ \\ 279 \hline 280 \hline 281 0 & 0 & 1 & 0 & 0 & 0 \\ 282 \hline 283 0 & 1 & 1 & 0 & 1 & 1 \\ 284 \hline 285 1 & 0 & 0 & 0 & 1 & 1 \\ 286 \hline 287 1 & 1 & 0 & 1 & 1 & 0 \\ 288 \hline 289 \end{tabular} 290 \end{center} 291 \end{table} 292 293 The \emph{logical AND} (or simply \index{AND}\index{Boolean algebra!AND}\emph{AND}) 294 operator (or function) 295 returns TRUE if both of its input arguments are TRUE 296 (see Table 297 \ref{tbl:cbal0:ssam0:snom0:01}). 298 We denote this operator 299 by the \emph{times} symbol (example: $x \times{} y$), by 300 the keyword AND', or by placing the operands adjacent to 301 each other (examples: $xy$, $x(y)$). 302 303 The \emph{logical OR} 304 (or simply \index{OR}\index{Boolean algebra!OR}\emph{OR}) 305 operator (or function) 306 returns TRUE if either of its input arguments are TRUE 307 (see Table 308 \ref{tbl:cbal0:ssam0:snom0:01}). 309 We denote this operator 310 by the \emph{plus} symbol (example: $x + y$) or by 311 the keyword OR'. 312 313 The \emph{logical exclusive-OR} 314 (or simply \index{XOR}\index{Boolean algebra!XOR} \emph{XOR}) 315 operator (or function) 316 returns TRUE if either but not both of its input arguments are TRUE 317 (see Table 318 \ref{tbl:cbal0:ssam0:snom0:01}). 319 We denote this operator 320 by the \emph{circled plus} symbol (example: $x \oplus{} y$), 321 by the \emph{caret} character (example: $x$\^{}$y$), or by 322 the keyword XOR'. 323 324 The exclusive-OR function is not a 325 function traditionally considered in the canonical forms of Boolean 326 algebra. However, we consider it here because our aims may in 327 some cases be subtly 328 different than the aims of classic two-valued Boolean algebra. 329 The goal of classic Boolean algebra is to minimize the number of 330 terms which appear in a canonical form. 331 However, often our goal here is to rearrange Boolean functions into a form 332 which is optimal for implementation on a computer. Since actual 333 computers usually provide a bitwise exclusive-OR instruction, there 334 are some applications where it may be useful to consider the 335 underlying instruction set of the computer (for example, 336 see \emph{Vertical Counters}, 337 Section \ref{cbal0:svct0}). 338 339 In general, there are $2^{2^N}$ different Boolean functions of $N$ 340 input variables, so it isn't practical to name functions involving more 341 than 2 input variables. There are 16 ($=2^{2^2}$) Boolean functions of 342 2 input variables, and these are enumerated in 343 Table \ref{tbl:cbal0:ssam0:snom0:02}. 344 345 \begin{table} 346 \caption{Sixteen Possible Boolean Functions $f(A,B)$ Of Two Boolean Variables} 347 \label{tbl:cbal0:ssam0:snom0:02} 348 \begin{center} 349 \begin{tabular}{|c||c|c|c|c||l|} 350 \hline 351 \small{Func.} & $\scriptstyle{f(1,1)}$ & $\scriptstyle{f(1,0)}$ 352 & $\scriptstyle{f(0,1)}$ & $\scriptstyle{f(0,0)}$ 353 & Function Description \\ 354 \small{Num.} & & & & & \\ 355 \hline 356 \hline 357 0 & 0 & 0 & 0 & 0 & \small{Zero'' or clear'' function. Always} \\ 358 & & & & & \small{returns zero regardless of $A$ and $B$ } \\ 359 & & & & & \small{input values. } \\ 360 \hline 361 1 & 0 & 0 & 0 & 1 & \small{Logical NOR = $(A+B)'$. } \\ 362 \hline 363 2 & 0 & 0 & 1 & 0 & \small{Inhibition = $BA'$. So named because } \\ 364 & & & & & \small{a TRUE value of $A$ inhibits $B$. Also } \\ 365 & & & & & \small{equivalent to $B>A$ or to $AB$ or to \$B

## Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision URL Header