LOGIC MACHINES AND TRUTH TABLES
The secret of all reasoning machines is after all very simple.
It is that whatever relation among the objects reasoned
about is destined to be the hinge of a ratiocination, that
same general relation must be capable of being introduced
between certain parts of the machine.
CHARLES SANDERS PEIRCE
As logic enjoyed a rebirth through the work of George Boole, there were several notable attempts to mechanize the tedious work of analyzing long syllogisms. One of Professor Augustus De Morgan’s many devoted students, William Stanley Jevons, the British logician, philosopher, and economist, caught the attention of the logicians of the time when in 1869 he produced a rather famous Logic Machine.1
Jevons was actually preceded in this ambitious endeavor by the British statesman and inventor Earl Stanhope, some 50 years earlier. Stanhope’s device—the Stanhope Demonstrator—employed colored sliding panels that one maneuvered into slots according to the premises of the syllogism. The rather simple device could handle only three terms but allowed quantification of the predicate and even numerically definite syllogisms.2 Jevons could not possibly have known of Stanhope’s work as the Earl was known to be extremely secretive, obsessed with the notion that “some bastard imitation” might precede his intended publication. Sadly, Stanhope died before he could publish news of the Demonstrator. Through accounts garnered from letters, the Stanhope Demonstrator was brought to light later, in 1879, 63 years after his death.3
Jevons’s Logic Machine, or “analytical engine” as he called it, was the first working model able to solve a complicated syllogism faster than a proficient human being could. Like De Morgan, Jevons was one of the few British logicians to recognize the pioneering aspects of Boole’s accomplishments in algebraic logic. Jevons considered his machine to be a purely mechanistic embodiment of Boole’s Laws of Thought; moreover, his well-known mechanical device established a prototype for those that were to follow.4 The logic machine was about a meter in height and was sometimes referred to as the “logical piano,” resembling as it did, an upright piano. Modern historians have described it as resembling a cash register and indeed it does.5 The pianolike “keyboard” had 21 “keys” that provided a means for entering the premises as equations. The logic machine was based on Jevons’s method of combining terms and could handle syllogisms involving four terms and their negatives, as well as all the logical combinations among the terms. Rather than outputting a conclusion once the premises were input, the mechanism displayed a list of all possible conclusions to be drawn from the premises after having eliminated all contradictory propositions. The user had to inspect the possible conclusions and eliminate those that were not applicable; those remaining (if any remained) were the appropriate conclusions. In 1870, Jevons demonstrated the logical piano at a meeting of the Royal Society of London where the machine brought attention to the value of Boole’s symbolic system and to the possibility of “mechanistic thinking.”
Jevons called his system of combining terms to represent premises combinational logic, and he dubbed an exhaustive index of combinations of a logical alphabet a Logical Abecedarium.6 Jevons went so far as to calculate the amount of space necessary to house a complete index for five terms. With each page displaying 64 entries and each volume containing 1,024 pages, the index would require 65,536 such volumes. His calculations are reminiscent of the enumerations made by Chrysippus and Hipparchus, thousands of years earlier. At the time, these amounts must have seemed overwhelming, but modern computer storage devices can handle them easily.
As early as 1863, Jevons had invented a Logical Slate, which consisted of a complete abecedarium that was permanently engraved upon a common writing slate. Jevons also suggested several labor-saving devices such as the creation of a rubber stamp of the logic alphabet, thus eliminating the tedium of having to write down all of the combinations every time. For classroom instruction, Jevons favored a device he created called a Logical Abacus in which the combinations of the abecedarium were written on movable strips of wood, and a syllogism was analyzed by the user manually performing procedures similar to the ones his machine performed.7
Jevons’s method was actually worked out before John Venn’s method of diagrams, but Venn considered his diagrammatic analysis to be much easier than organizing premises into the form appropriate for Jevons’s machine. In 1880, Venn proposed a jigsaw puzzle version of his five-term diagram with each of the 32 compartments represented by a puzzle piece that would be removed as possibilities were eliminated. In addition, he designed what he termed a “logical-diagram machine,” which was a three-dimensional version of the jigsaw puzzle with four overlapping elliptical cylinders.8 Although they argued over the rival notions of whether diagrams or machines were more straightforward, Jevons and Venn clearly intended their contributions to elucidate the genius of Boole’s system. Their contributions were merely the icing on the cake; the cake itself was created by George Boole in the two books he wrote in 1847 and 1854.
In 1881, the American Allan Marquand constructed a logical-diagram machine, an improved version of the Jevons machine. The Marquand Logic Machine was smaller, the number of keys reduced, and its system of rods, springs, and levers proved far more sophisticated than previous mechanisms.9 The control panel of the instrument resembled Marquand’s logic diagram of overlapping rectangles.
Although it performed the same operations as the Jevons-type machine, Marquand felt that his device could be easily adapted to solve much larger problems.10 Both Jevons and Marquand had used De Morgan’s negative terms (represented by lowercase letters) as inputs to their machines. One interesting aspect of Marquand’s machine is that entire premises of the syllogism had to be input in the negative. His machine then eliminated any conclusions that agreed with the negative of the premises, as those would contradict the premises. In an 1885 article for the Proceedings of the American Academy of Sciences, Marquand described his machine and included pictures of it. He used Boole’s notion of disjunction as logical addition and conjunction as logical multiplication and Peirce’s symbolic notation for the conditional.11 A 
B means “If A, then B” (or “Every A is B” or “Class A is included in class B”). To input this premise, Marquand explained that we input its negative, Ab 0—meaning “As that are b (not-B) do not exist.”
Charles Sanders Peirce described the logic machines built by Jevons and Marquand as mills into which the premises were fed and conclusions turned out by the revolution of a crank.12 Peirce commented:
Precisely how much of the business of thinking a machine could possibly be made to perform, and what part of it must be left for the living mind, is a question not without conceivable practical importance; the study of it can at any rate not fail to throw needed light on the nature of the reasoning.13
The machines of Jevons and Marquand, while utilized to solve problems of a fairly elementary nature, afforded the world evidence of the possibilities of a reasoning machine that employed the rules of logic.
In the 1950s, a wiring diagram for a four-term electrical logic machine was found among Marquand’s manuscripts. Believed to be prepared in 1885, it is probably the first circuit diagram of an electric logical machine. Marquand had been a student of philosopher and Harvard professor Charles Sanders Peirce, and in the early 1970s an extremely interesting letter came to light that Peirce had sent to Marquand in 1886. In the letter, Peirce suggested a method in which Marquand’s machine might be improved by using electricity. Peirce even produced a sketch detailing how circuits for logical conjunction and disjunction would perform in series and parallel. Prolific author of books in recreational mathematics, Martin Gardner says that this is “the first known effort to apply Boolean algebra to the design of switching circuits!” in the same way that modern computer designers do today.
Gardner has written a delightful book, Logic Machines and Diagrams, which chronicles the progress of syllogism machines. He points out that ironically none of the syllogism machines of the time actually used logic to solve syllogisms. Even when electrical connections were introduced into the instruments, the electrical connections were not controlled through logical translations as they are today. The syllogism machines merely used electricity to reveal or cover up a preset arrangement of valid or contradictory statements rather like the windows and levers of the original mechanical devices. The link between Boolean algebra and switching circuits had yet to be made, except perhaps by Marquand and Peirce.
By the 1930s the link was indeed made, and since then hundreds of papers applying logic to switching circuits have been written. One other logic machine built by two Harvard undergraduates in 1947 is rather interesting. William Burkhart and Theodore A. Kalin, who were taking a course in symbolic logic from renowned logician Willard V. Quine, constructed the first electrical machine designed exclusively for propositional logic for the sole purpose of doing their homework problems. The Kalin-Burkhart “logical truth calculator” could handle up to 12 terms by isolating lines in a truth table.
The “truth table method” was introduced in 1920 in the Ph.D. dissertation of Emil Leon Post, a young Polish, Jewish emigrant student at the College of the City of New York. Used extensively to this day in the study of logic, a truth table is a table of all possible combinations of true/false (or 1s and 0s) for the propositions involved in an argument, using the rules set down by Boole.14 Earlier, we constructed a truth table for disjunctive, conjunctive, and conditional statements involving two propositions. Using a truth table, we can answer a problem adapted from Allan Marquand:
Suppose, regarding three girls, Anna, Bertha, and Cora, we observe the following rule:
Whenever either Anna or Bertha (or both) remained at home, Cora was at home; and
When Bertha was out, Anna was out; and
Whenever Cora was at home, Anna was at home.
What can we determine about the habits of the girls individually or as a group?15
Letting A, B, and C stand for “Anna is at home,” “Bertha is at home,” and “Cora is at home,” respectively, we must judge the truth of propositions A, B, and C given the truth of the rule “If A or B then C, and if not-B then not-A, and if C then A.” A truth table consists of an exhaustive list of possible truth values. In our example, there are three simple propositions, A, B, and C, each with two possible truth values (true or false). A truth table to analyze the rule involving all three propositions would require 2 × 2 × 2, or 8, lines in the table to reflect all true/false combinations of A, B, and C. The rule is a conjunction of three compound propositions, which must each be true for the whole rule to be true, since they are connected by “and.” Working with the first of the three conjoined propositions, “If A or B then C,” we get:
“A or B” is true any time either A is true or B is true and false only when both are false. “If A or B then C” is always true except when the consequent (C) is false and the antecedent (A or B) is true. Those have been highlighted in the table. Now since “If A or B then C” must be true for the entire rule to be true, we can eliminate any line in which “If A or B then C” is false (has an F). We will therefore eliminate those three lines from the table.
Let’s add the second part of the rule, “if not-B then not-A.” Before we do, however, let’s add a column for not-B and not-A, so the analysis will be easier. Not-B receives a value “F” whenever B has a “T” and a value “T” whenever B has an “F.” The same holds for not-A with respect to A. “If not-B then not-A” is false whenever not-B is true and not-A is false.
Let’s eliminate the line where “if not-B then not-A” is false (highlighted) and add the last portion of the three-part rule, “if C then A.”
If we eliminate the lines where “if C then A” is false, we are left with only two lines in the truth table where all three parts of the rule are true. What does the truth of the rule indicate about the truth of A, B, and C individually or as a group? Looking back to the first three columns and the truth values of A, B, and C, we are able to see that all must be true or all must be false. We can conclude that if the rule is true, then either all three girls are at home at the same time or all three are away at the same time. The fact that Marquand’s machine required the premises to be input in the negative is interesting because it is so similar to looking at a truth table and eliminating the false scenarios.
In our analysis of Marquand’s problem about Anna, Bertha, and Cora, each statement, simple or compound, was either true or false—the traditional system of logic. The law of the excluded middle guarantees us that a proposition is always either one or the other, and the law of noncontradiction guarantees us that a proposition is never both. In the language of the logician, the logic is bivalued, meaning that each proposition has one of two truth values. Logics other than the classical logic have been developed that do not restrict the number of truth values to two; in fact they may allow for a much larger set of truth values.
In 1917, Jan Łukasiewicz, co-founder of the Warsaw School of Logic and on whose work the great mathematical logician Alfred Tarski based his own, advocated a system with a third truth value, “possible.” Aristotle himself had acknowledged that inferences are often drawn from premises such as “It may be that all are . . .” or “Some possibly are. . . .” In a theory of what is called modal logic, Aristotle attempted to develop the same systematic treatment of syllogisms involving statements of necessity, statements of actuality, and statements of possibility, but he was never able to devise an organized and satisfactory system for modal propositions in the way that he had for categorical propositions. Prompted by the idea of understanding the modal notion of possibility in a three-valued way, Łukasiewicz suggested a three-valued logic with propositions categorized as “true,” “false,” or “possible.”
Figure 39. Truth values for the conditional and negation under Łukasiewicz’s three-valued logic.
Łukasiewicz proposed that if the certainty of a premise could not (yet) be established, that is, assigned a truth value of 1 (it is necessary) or assigned a truth value of 0 (it is impossible), we may indicate “the possible” by a truth value of ½. See his truth values for the conditional and for negation in Figure 39.16
The truth values for the conditional and the negation of true (1) and false (0) statements are the ones used in standard logic. Clearly the negation of “possible” is not “impossible” but “possibly not.” Take, for example, the proposition “You will win the lottery”—a proposition whose certainty will only be known in the future. Right at this moment, it is possibly true. Its negation is “You will not win the lottery” and it is also possibly true. Under a system of three-valued logic, both propositions will receive a truth “value” of ½. It may seem strange that both propositions receive a value of ½, since the chances of your not winning the lottery are greater than the chances of your winning, but we will return to that issue later. In classical logic no formula can be equivalent to its own negation; but in a three-valued logic if A has a value of ½, so does not-A. Therefore, A and not-A can be considered equivalent. The introduction of three truth values produces some surprisingly counterintuitive results. Our most basic laws of logic, the law of the excluded middle and the law of noncontradiction, are violated in a three-valued logic system.
Some modern linguists and philosophers have preferred three truth values for different reasons.17 A statement can be true, false, or neither true nor false; a statement is assigned the third truth value in cases where an existential presupposition is violated. How does one assign a truth value to a statement like “The present king of France is bald”? If we presuppose that the proposition actually speaks of something, we are mistaken. Our supposition is violated; there is no king of France. France no longer has a monarchy. Perhaps we should declare the proposition to be false. If there is no king of France then he can’t possibly be bald. However, if the proposition is false then its negation must be true. We would be forced to accept the truth of “The present king of France is not bald,” but once again we find ourselves in a quandary.18 Some have preferred to assign a third truth value to propositions of this sort (those that are neither true nor false). Statements that violate our existential presupposition do not fit neatly into Aristotle’s framework, and it is not clear how to treat them in logic. Forming the negations and understanding the truth rules of conditionals formed from such statements prove to be even more problematic.
According to the Stanford Encyclopedia of Philosophy, around 1910, Charles Sanders Peirce had developed, but not published, what amounts to a three-valued logic. Peirce used three symbols V, L, and F; V was associated with true (1), F was associated with false (0), and L was associated with an intermediate or unknown value (½).19 Peirce defined the rules for operating with three truth values: negation, disjunction, and conjunction, as well as inventing some operators of his own. Other philosophers, mathematicians, linguists, and psychologists have made forays into the usefulness of a three-valued logic. The third truth value has been given various interpretations, such as “undefined,” “senseless,” “undetermined,” or “paradoxical.”
Four-valued systems have been developed that have applications in computer science20 and in 1921, Emil Leon Post published “A General Theory of Elementary Propositions” in The American Journal of Mathematics, wherein he proposed many-valued systems of logic. Generalizing his Ph.D. thesis, Post produced a framework for a system of logic based on an arbitrary but finite number of truth values, rather than the two truth values of true and false.
Attempts to merge modal logic and many-valued logic have applications to problems dealing with artificial intelligence, a field in which scientists are trying to model human thinking. Many-valued logics have applications in linguistics, applications to philosophy in resolving certain paradoxes, applications in mathematics, and applications in hardware design. In the same way that classical logic is used as a technical tool for the analysis of electrical circuits built from switches with two states—“on” and “off”—a many-valued logic may be used to analyze circuits built from switches with many states.
Today machines can perform many amazing tasks; they can apply the rules of a two-valued logic or a many-valued logic unfailingly and mechanically. However, Charles Sanders Peirce’s words written over a hundred years ago still ring true:
Every reasoning machine, that is to say, every machine, has two inherent impotencies. In the first place, it is destitute of all originality, of all initiative. It cannot find its own problems; it cannot feed itself. . . . This, however, is not a defect in a machine; we do not want it to do its own business, but ours. . . . In the second place, the capacity of a machine has absolute limitations; it has been contrived to do a certain thing, and it can do nothing else. . . . But the mind working with a pencil and plenty of paper has no such limitations.21
Mr. Peirce is right. Humans are superior to machines in their creative abilities and initiative. They are superior in their inherent wherewithal to manipulate concepts that are not quite black and white. And most concepts are not black and white; most concepts (as we’ll see next) are fuzzy.