The Logical Algebra
We come now to another most important reason for the effectiveness of the digital computer; the reason that makes it the “logical” choice for not only mathematics but thinking as well. For the digital computer and logic go hand in hand.
Logic, says Webster, is “the science that deals with canons and criteria of validity in thought and demonstration.” He admits to the ironic perversion of this basic definition; for example, “artillery has been called the ‘logic of kings,’” a kind of logic to make “argument useless.” Omar Khayyám had a similar thought in mind when he wrote in The Rubáiyát,
The grape that can with logic absolute,
The Two-and-Seventy Sects confute.
Other poets and writers have had much to say on the subject of logic through the years, words of tribute and words of warning. Some, like Lord Dunsany, counsel moderation even in our logic. “Logic, like whiskey,” he says, “loses its beneficial effect when taken in too large quantities.” And Oliver Wendell Holmes asks,
Have you heard of the wonderful one-hoss shay
That was built in such a logical way
It ran a hundred years to the day?
The words logic and logical are much used and abused in our language, and there are all sorts of logic, including that of women, which seems to be a special case. For our purposes here it is best to stick to the primary definition in the dictionary, that of validity in thought and demonstration.
Symbolic logic, a term that still has an esoteric and almost mystical connotation, is perhaps mysterious because of the strange symbology used. We are used to reasoning in words and phrases, and the notion that truth can be spelled out in algebraic or other notation is hard to accept unless we are mathematicians to begin with.
We must go far back in history for the beginnings of logic. Aristotelian logic is well known and of importance even though the old syllogisms have been found not as powerful as their inventors thought. Modern logicians have reduced the 256 possible permutations to a valid 15 and these are not as useful as the newer kind of logic that has since come into being.
Leibniz is conceded to be the father of modern symbolic logic, though he probably neither recognized what he had done nor used it effectively. He did come up with the idea of two-valued logic, and the cosmological notion of 1 and 0, or substance and nothingness. In his Characteristica Universalis he was groping for a universal language for science; a second work, Calculus Ratiocinator, was an attempt to implement this language. Incidentally, Leibnitz was not yet twenty years old when he formulated his logic system.
Unfortunately it was two centuries later before the importance of his findings was recognized and an explanation of their potential begun. In England, Sir William Hamilton began to refine the old syllogisms, and is known for his “quantification of the predicate.” Augustus De Morgan, also an Englishman, moved from the quantification of the predicate to the formation of thirty-two rules or propositions that result. The stage was set now for the man who has come to be known as the father of symbolic logic. His name was George Boole, inventor of Boolean algebra.
In 1854, Boole published “An Investigation of the Laws of Thought on which are Founded the Mathematical Theories of Logic and Probabilities.” In an earlier pamphlet, Boole had said, “The few who think that there is that in analysis which renders it deserving of attention for its own sake, may find it worth while to study it under a form in which every equation can be solved and every solution interpreted.” He was a mild, quiet man, though nonconformist religiously and socially, and his “Investigation” might as well have been dropped down a well for all the immediate splash it made in the scientific world. It was considered only academically interesting, and copies of it gathered dust for more than fifty years.
Only in 1910 was the true importance given to Boole’s logical calculus, or “algebra” as it came to be known. Then Alfred North Whitehead and Bertrand Russell made the belated acknowledgment in their Principia Mathematica, and Russell has said, “Pure mathematics was discovered by Boole, in a work he called ‘The Laws of Thought.’” While his praise is undoubtedly exaggerated, it is interesting to note the way in which mathematics and thought are considered inseparable. In 1928, the first text on the new algebra was published. The work of Hilbert and Ackermann, Mathematical Logic, was printed first in German and then in English.
What was the nature of this new tool for better thinking that Boole had created? Its purpose was to make possible not merely precise, but exact analytical thought. Historically we think in words, and these words have become fraught with semantic ditches, walls, and traps. Boole was thinking of thought and not mathematics or science principally when he developed his logic algebra, and it is indicative that symbolic logic today is often taught by the philosophy department in the university.
Russell had hinted at the direction in which symbolic logic would go, and it was not long before the scientist as well as the mathematician and logician did begin to make use of the new tool. One pioneer was Shannon, mentioned in the chapter on history. In 1938, Claude Shannon was a student at M.I.T. He would later make scientific history with his treatise on and establishment of a new field called information theory; his early work was titled “A Symbolic Analysis of Relay and Switching Circuits.” In it he showed that electrical and electronic circuitry could best be described by means of Boolean logic. Shannon’s work led to great strides in improving telephone switching circuits and it also was of much importance to the designer of digital computers. To see why this is so, we must now look into Boolean algebra itself. As we might guess, it is based on a two-valued logic, a true-false system that exactly parallels the on-off computer switches we are familiar with.
The Biblical promise “Ye shall know the truth, and the truth shall make you free” applies to our present situation. The best way to get our feet wet in the Boolean stream is to learn its so-called “truth tables.”
Conjunctive Boolean Operation
| A and B equal C | A B C |
| (A · B = C) | ——— |
| 0 0 0 | |
| 1 0 0 | |
| 0 1 0 | |
| 1 1 1 |
Disjunctive Boolean Operation
| A or B equals C | A B C |
| (Ā ∨ B = C) | ——— |
| 0 0 0 | |
| 1 0 1 | |
| 0 1 1 | |
| 1 1 1 |
In the truth tables, 1 symbolizes true, 0 is false. In the conjunctive AND operation, we see that only if both A and B are true is C true. In the disjunctive OR operation, if either A or B is true, then C is also true. From this seemingly naïve and obvious base, the entire Boolean system is built, and digital computers can perform not only complex mathematical operations, but logical ones as well, including the making of decisions on a purely logical basis.
Before going on to the few additional conditions and combinations that complete the algebra, let’s study some analogies that will make clear the AND/OR principles of operation. We can think of AND as two bridges in sequence over two rivers. We can reach our destination only if both bridges are working. However, suppose there are two parallel bridges and only one river. We can then cross if either or both of the bridges is working. A closer example is that of electrical switches. Current will flow through our AND circuit if—and only if—both switches are closed. When the switches are in parallel—an OR circuit—current will flow if either, or both, are closed.
The truth tables resemble the bridge or switch arrangements. We can proceed across the line of 1’s and 0’s in the first table only if both switches are closed. The symbol 1 means that the switch is closed, so we can cross only the bottom line. In the second table, we are told we can proceed across the line if either switch is closed. Thus we can cross lines 2, 3, and 4. We can use many symbols in our two-valued system.
Symbol
| Bridge | No Bridge |
| Power | No Power |
| 1 | 0 |
| True | False |
A little imagination suggests a logic computer of sorts with one switch, a battery, and a light bulb. Suppose we turn on the switch when we drive into our garage. A light in the hallway then indicates that the car is available. By using two switches we can indicate that a second car is also in the garage; or that either of them is, simply by choosing between AND logic and OR logic. Childish as this seems, it is the principle of even our most complex thinking processes. You will remember that the brain is considered a digital computer, since neurons can only be on or off. All it takes is 10 billion neuron switches!
In addition to the conjunctives AND and OR, Boolean algebra makes use of the principle of negation. This is graphically illustrated thus:
| Original | Negation |
| A | Ā |
| 1 | 0 |
| 0 | 1 |
The negation device used in computer circuitry is called an inverter, since it changes its input from a 1 to a 0, or vice versa. The usefulness of such an element is obvious when we remember the computer trick of subtracting by adding complements. The inverter circuit used with a code like the excess-3 readily forms these complements.
Further sophistication of the basic Boolean forms leads to units other than the AND and OR gates. Possible are NOT, NOR, and exclusive-OR forms. In the latter, there is an output if one and only one input is present. The NOR circuit is interesting in that it was made possible with the introduction of the transistor; the vacuum tube does not permit this configuration.
Present-day symbolic logic is not the pure Boolean as presented back in 1854. Boole’s OR was the exclusive, one and only one, type. Today the logician generally assumes the either-or connotation. The logic has also been amplified, using the commutative, associative, and distributive laws much like those of conventional algebra. We are indebted to De Morgan for most of this work, showing that A and B equals B and A; A and (A and B) equals (A and B) and A; and so on. While these seem intuitively true, the implications are nonetheless of great importance both in pure logic and its practical use in circuitry.
A graphic representation of the metamorphosis from symbolic to actual implementation of Boolean equations follows: The implication of importance is that logic applies equally well whether we are making a qualifying statement such as “A man must have strength and courage to win a barehanded fight with a lion,” or wiring a defensive missile so that it will fire only if a target is within range and is unfriendly.
In the early period of computer design the engineer was faced with the problem of building his own switches and gates. Today many companies offer complete “packaged” components—AND gates, OR gates, and the other configurations. This is the modular approach to building a computer and the advantages are obvious. The designer can treat the components simply as “black boxes” that will respond in a prescribed way to certain input conditions. If he wants, the engineer can go a step further and buy a ready-built logic panel consisting of many components of different types. All he need do to form various logic circuits is to interconnect the proper components with plug-in leads. This brings us to the point of learning what we can do with these clever gates and switches now that we have them available and know something about the way they work.
We talked about the computer adder circuit earlier in this chapter. It is made up of two half-adders, remember, with perhaps an additional OR gate, flip-flop, etc. Each half-adder is composed of two AND gates and an OR gate. So we have put together several basically simple parts and the result is a piece of equipment that will perform addition at a rate to make our heads swim.
There are other things we can do with Boolean logic besides arithmetic. A few gates will actuate a warning signal in a factory in case either of two ventilators is closed and the temperature goes up beyond a safe point; or in case both vents are closed at the same time. We can build a logic computer that will tell us when three of four assembly lines are shut down at the same time, and also which three they are.
Logic problems abound in puzzle books, and many of us spend sleepless nights trying to solve them in our heads. An example is the “Farnsworth Car Pool” problem. Rita Farnsworth asks her husband if someone in his car pool can drive for him tomorrow so that she may use the car. Joe Farnsworth replies, “Well, when I asked Pete if he would take my turn he said he was flying to Kansas City today, but he’d be glad to drive tomorrow if he didn’t have to stay over and that his wife has been staying home lately and he will drive her car if she doesn’t go to work. Oscar said that since his own car is due back from the garage tomorrow he can drive it even if his wife does use hers, provided the garage gets his back to him. But if this cold of mine gets any worse I’m going to stay home even if those fellows have to walk to work, so you can certainly have the car if I don’t go to work.” This dialogue of Joe’s confuses Rita and most of us are in the same state.
The instruction manual for BRAINIAC, a do-it-yourself computer that sells for a few dollars, gives a simple wiring diagram for solving Rita’s dilemma. Electrically the problem breaks down into three OR gates and one AND gate. All Mrs. Farnsworth has to do is set in the conditions and watch the indicator light. If it glows, she gets the car!
These are of course simple tasks and it might pay to hire a man to operate the vents, and ride to work on the bus when the car pool got complicated. But even with relatively few variables, decision-making can quickly become a task requiring a digital computer operating with Boolean logic principles.
The Smith-Jones-Robinson type of problem in which we must find who does what and lives where is tougher than the car pool—tough enough that it is sometimes used in aptitude tests. Lewis Carroll carried this form of logical puzzler to complicated extremes involving not just three variables but a dozen. To show how difficult such a problem is, an IBM 704 required four minutes to solve a Carroll puzzle as to whether any magistrates indulge in snuff-taking. The computer did it the easy way, without printing out a complete “truth table” for the problem—the method a man would have to use to investigate all the combinations of variables. This job would have taken 13 hours! While the question of the use of snuff is perhaps important only to tobacconists and puzzle-makers, our technical world today does encounter similar problems which are not practical of solution without a high-speed computer. A recent hypothetical case discussed in an electronics journal illustrates this well.
A missile system engineer has the problem of modifying a Nike-Ajax launching site so that it can be used by the new Nike-Hercules missile. He must put in switching equipment so that a remote control center can choose either an Ajax system, or one of six Hercules systems. To complicate things, the newer Hercules can be equipped with any of three different warheads and fly either of two different missions. When someone at the control center pushes a button, the computer must know immediately which if any of the missiles are in acceptable condition to be fired.
This doesn’t sound like too big a problem. However, since there are twelve on-off signals to be considered, and since each has two possible states, there are 4,096 possible missile combinations. Not all these are probable, of course, but there is still sufficient variation to make it humanly impossible to check all of them and close a firing switch in the split second the control center can allow.
The answer lies in putting Boolean algebra on the job, with a system of gates and inverters capable of juggling the multiplicity of combinations. Then when the word comes requesting a missile launch, the computer handles the job in microseconds without straining itself unduly.
Just as Shannon pointed out twenty-five years ago, switching philosophy can be explained best by Boolean logic, and the method can be used not only to implement a particular circuit, but also to actually design the circuit in the first place. A simple example of this can be shown with the easy-to-understand AND and OR gates. A technician experimenting with an AND gate finds that if he simply reverses the direction of current, he changes the gate into an OR gate. This might come as a surprise to him if he is unfamiliar with Boolean logic, but a logician with no understanding of electrical circuits could predict the result simply by studying the truth tables for AND and OR.
Reversing the polarity is equivalent to changing a 1 to a 0 and vice versa. If we do this in the AND gate table, we should not be surprised to find that the result looks exactly like the OR table! It acts like it too, as the technician found out.
Boolean logic techniques can be applied to existing circuits to improve and/or simplify them. Problems as simple as wiring a light so that it can be turned on and off from two or more locations, and those as complex as automating a factory, yield readily to the simple rules George Boole laid down more than a hundred years ago.
Watching a high-speed electronic digital computer solve mathematical problems, or operate an industrial control system with speed and accuracy impossible for human monitors, it is difficult to believe that the whole thing hinges on something as simple as switches that must be either open or closed. If Leibnitz were alive, he could well take this as proof of his contention that there was cosmological significance in the concept of 1 and 0. Maybe there is, after all!
“Whatever that be which thinks, understands, wills, and
acts, it is something celestial and divine.”
—Cicero