CALCULATION OF LOGICAL TRUTH
Now what can we find out about the logical truth of statements 3 to 10? If we know something about the truth or falsity of statements 1 and 2, what will logically follow about the truth or falsity of statements 3 to 10? In other words, how can we calculate the logical truth of statements 3 to 10, given the truth or falsity of statements 1 and 2?
For example, 3 is not-1; that is, statement 3 is the negative or the denial of statement 1. It follows logically that, if 1 is true, 3 is false; if 1 is false, 3 is true. Suppose that we use T for logically true and F for logically false. Then we can show our calculation of the logical truth of statement 3 in Table 1.
| Table 1 | Table 2 | |||
| 1 | not-1 = 3 | 2 | not-2 = 4 | |
| T | F | T | F | |
| F | T | F | T | |
Our rule for calculation is: For T put F; for F put T. Of course, exactly the same rule applies to statements 2 and 4 ([see Table 2]). The T and F are called truth values. Any meaningful statement can have truth values. This type of table is called a truth table. For any logical pattern, we can make up a truth table.
Let us take another example, “and.” Statement 5 is the same as statement 1 and statement 2. How can we calculate the logical truth of statement 5? We can make up the same sort of a table as before. On the left-hand side of this table, there will be 4 cases:
- 1. Statement 1 true, statement 2 true.
- 2. Statement 1 false, statement 2 true.
- 3. Statement 1 true, statement 2 false.
- 4. Statement 1 false, statement 2 false.
On the right-hand side of this table, we shall put down the truth value of statement 5. Statement 5 is true if both statements 1 and 2 are true; statement 5 is false in the other cases. We know this from our common everyday experience with the meaning of “and” between statements. So we can set up the truth table, and our rule for calculation of logical truth, in the case of and, is shown on [Table 3].
Table 3
| 1 | 2 | 1 and 2 = 5 |
| T | T | T |
| F | T | F |
| T | F | F |
| F | F | F |
“and” and the other words and phrases joining together the original two statements to make new statements are called connectives, or logical connectives. The connectives that we have illustrated in statements 7 to 10 are: or, if ··· then, if and only if, or else.
[Table 4] shows the truth table that applies to statements 7, 8, 9, and 10. This truth table expresses the calculation of the logical truth or falsity of these statements.
Table 4
| 1 or 2 | if 1, then 2 | 1 if and only if 2 | 1 or else 2 | ||
| 1 | 2 | = 7 | = 8 | = 9 | = 10 |
| T | T | T | T | T | F |
| F | T | T | T | F | T |
| T | F | T | F | F | T |
| F | F | F | T | T | F |
The “or” (as in statement 7) that is defined in the truth table is often called the inclusive “or” and means “and/or.” Statement 7, “1 or 2,” is considered to be the same as “1 or 2 or both.” There is another “or” in common use, often called the exclusive “or,” meaning “or else” (as in statement 10). Statement 10, “1 or else 2,” is the same as “1 or 2 but not both” or “either 1 or 2.” In ordinary English, there is some confusion over these two “or’s.” Usually we rely on the context to tell which one is intended. Of course, such reliance is not safe. Sometimes we rely on a necessary conflict between the two statements connected by “or” which prevents the “both” case from being possible. In Latin the two kinds of “or” were distinguished by different words, vel meaning “and/or,” and aut meaning “or else.”
The “if ··· then” that is defined in the truth table agrees with our usual understanding that (1) when the “if clause” is true, the “then clause” must be true; and (2) when the “if clause” is false, the “then clause” may be either true or false. The “if and only if” that is defined in the truth table agrees with our usual understanding that (1) if either clause is true, the other is true; and (2) if either clause is false, the other is false.
In statement 6, there are only two possible cases, and the truth table is shown in [Table 5].
Table 5
| 1 | 1 and 1 = 6 |
| T | T |
| F | F |
We know that 6 is true if and only if 1 is true. In other words, the statement “1 and 1 if and only if 1” is true, no matter what statement 1 may refer to. It is because of this fact that we never use a statement in the form “1 and 1”: it can always be replaced by the plain statement “1.”
LOGICAL-TRUTH CALCULATION BY
EXAMINING CASES AND REASONING
Now you may say that this is all very well, but what good is it? Almost anybody can use these connectives correctly and certainly has had a great deal of practice using them. Why do we need to go into truth values and truth tables?
When we draft a contract or a set of rules, we often have to consider several conditions that give rise to a number of cases. We must avoid:
1. All conflicts, in which two statements that disagree apply to the same case.
2. All loopholes, in which there is a case not covered by any statement.
If we have one statement or condition only, we have to consider 2 possible cases: the condition satisfied or the statement true; the condition not satisfied or the statement false. If we have 2 conditions, we have to consider 4 possible cases: true, true; false, true; true, false; false, false. If we have 3 conditions, we have to consider 8 possible cases one after the other ([see Table 6]).
Table 6
| Case | 1st Condition | 2nd Condition | 3rd Condition |
| 1 | T | T | T |
| 2 | F | T | T |
| 3 | T | F | T |
| 4 | F | F | T |
| 5 | T | T | F |
| 6 | F | T | F |
| 7 | T | F | F |
| 8 | F | F | F |
Instead of T’s and F’s, we would ordinarily use check-marks (✓) and crosses (✕), which, of course, have the same meaning. We may consider and study each case individually. In any event, we must make sure that the proposed contract or set of rules covers all the cases without conflicts or loopholes.
The number of possible cases that we have to consider doubles whenever one more condition is added. Clearly, it soon becomes too much work to consider each case individually, and so we must turn to a second method, thoughtful classifying and reasoning about classes of cases.
Now suppose that the number of conditions increases: 4 conditions give rise to 16 possible cases; 5, 6, 7, 8, 9, 10, ··· conditions give rise to 32, 64, 128, 256, 512, 1024, ··· cases respectively. Because of the large number of cases, we soon begin to make mistakes while reasoning about classes of cases. We need a more efficient way of knowing whether all cases are covered properly.
LOGICAL-TRUTH CALCULATION
BY ALGEBRA
One of the more efficient ways of reasoning is often called the algebra of logic. This algebra is a part of a new science called mathematical logic. Mathematical logic is a science that has the following characteristics:
- It studies chiefly nonnumerical reasoning.
- It seeks accurate meanings and necessary consequences.
- Its chief instruments are efficient symbols.
Mathematical logic studies especially the logical relations expressed in such words as “or,” “and,” “not,” “else,” “if,” “then,” “only,” “the,” “of,” “is,” “every,” “all,” “none,” “some,” “same,” “different,” etc. The algebra of logic studies especially only the first seven of these words.
The great thinkers of ancient Greece first studied the problems of logical reasoning as these problems turned up in philosophy, psychology, and debate. Aristotle originated what was called formal logic. This was devoted mainly to variations of the logical pattern shown above called the syllogism. In the last 150 years, the fine symbolic techniques developed by mathematicians were applied to the problems of the calculation of logical truth, and the result was mathematical logic, much broader and much more powerful than formal logic. A milestone in the development of mathematical logic was The Laws of Thought, written by George Boole, a great English mathematician, and published in 1854. Boole introduced the branch of mathematical logic called the algebra of logic, also called Boolean algebra. In late years, all the branches of mathematical logic have been improved and made easier to use.
We can give a simple numerical example of Boolean algebra and how it can calculate logical truth. Suppose that we take the truth value of a statement as 1 if it is true and 0 if it is false. Now we have numbers 1 and 0 instead of letters T and F. Since they are numbers, we can add them, subtract them, and multiply them. We can also make up simple numerical formulas that will let us calculate logical truth. If P and Q are statements, and if p and q are their truth values, respectively, we have [Table 7].
Table 7
| Statement | Truth Value |
|---|---|
| not-P | 1 - p |
| P and Q | pq |
| P or Q | p + q - pq |
| if P, then Q | 1 - p + pq |
| P if and only if Q | 1 - p - q + 2pq |
| P or else Q | p + q - 2pq |
For example, suppose that we have two statements P and Q:
- P: John Doe is eligible for insurance.
- Q: John Doe requires a medical examination.
To test that the truth value of “P or Q” is p + q-pq, let us put down the four cases, and calculate the result ([see Table 8]).
Table 8
| p | q | p + q - pq |
| 1 | 1 | 1 + 1 - 1 = 1 |
| 0 | 1 | 0 + 1 - 0 = 1 |
| 1 | 0 | 1 + 0 - 0 = 1 |
| 0 | 0 | 0 + 0 - 0 = 0 |
Now we know that P or Q is true if and only if either one or both of P and Q are true, and thus we see that the calculation is correct.
The algebra of logic ([see also Supplement 2]) is a more efficient way of calculating logical truth. But it is still a good deal of work to use the algebra. For example, if we have 10 conditions, we shall have 10 letters like p, q to handle in calculations. Thus we need a still more efficient way.
CALCULATION OF CIRCUITS BY
THE ALGEBRA OF LOGIC
In 1937 a research assistant at Massachusetts Institute of Technology, Claude E. Shannon, was studying for his degree of master of science. He was enrolled in the Department of Electrical Engineering. He was interested in automatic switching circuits and wondered why an algebra should not apply to them. He wrote his thesis on the answer to this question and showed that:
- (1) There is an algebra that applies to switching circuits.
- (2) It is the algebra of logic.
A paper, based on his thesis, was published in 1938 in the Transactions of the American Institute of Electrical Engineers with the title “A Symbolic Analysis of Relay and Switching Circuits.”
Fig. 1. Switches in series.
For a simple example of what Shannon found out, suppose that we have two switches, 1, 2, in series ([see Fig. 1]). When do we get current flowing from the source to the sink? There are 4 possible cases and results ([see Table 9]).
Table 9
| Switch 1 is closed | Switch 2 is closed | Current flows |
|---|---|---|
| Yes | Yes | Yes |
| No | Yes | No |
| Yes | No | No |
| No | No | No |
Now what does this table remind us of? It is precisely the truth table for “and.” It is just what we would have if we wrote down the truth table of the statement “Switch 1 is closed and switch 2 is closed.”
Fig. 2. Switches in parallel.
Fig. 3. Switch open—current flowing.
Suppose that we have two switches 1, 2 in parallel ([see Fig. 2]). When do we get current flowing from the source to the sink? Answer: when either one or both of the switches are closed. Therefore, this circuit is an exact representation of the statement “Switch 1 is closed or switch 2 is closed.”
Suppose that we have a switch that has two positions, and at any time must be at one and only one of these two positions ([see Fig. 3]). Suppose that current flows only when the switch is open. There are two possible cases and results ([see Table 10]).
Table 10
| Switch 1 is closed | Current flows |
|---|---|
| Yes | No |
| No | Yes |
This is like the truth table for “not”; and this circuit is an exact representation of the statement “Switch 1 is not closed.” (Note: These examples are in substantial agreement with Shannon’s paper, although Shannon uses different conventions.)
We see, therefore, that there is a very neat correspondence between the algebra of logic and automatic switching circuits. Thus it happens that:
1. The algebra of logic can be used in the calculation of some electrical circuits.
2. Some electrical circuits can be used in the calculations of the algebra of logic.
This fact is what led to the next step.
LOGICAL-TRUTH CALCULATION
BY MACHINE
In 1946 two undergraduates at Harvard University, Theodore A. Kalin and William Burkhart, were taking a course in mathematical logic. They noticed that there were a large number of truth tables to be worked out. To work them out took time and effort and yet was a rather tiresome automatic process not requiring much thinking. They had had some experience with electrical circuits. Knowing of Shannon’s work, they said to each other, “Why not build an electrical machine to calculate truth tables?”
They took about two months to decide on the essential design of the machine:
1. The machine would have dial switches in which logical connectives would be entered.
2. It would have dial switches in which the numbers of statements like 1, 2, 3 ··· would be entered.
3. It would scan the proper truth table line by line by sending electrical pulses through the dial switches.
4. It would compute the truth or falsehood of the whole expression.
CONSTRUCTION AND COMPLETION OF THE
KALIN-BURKHART LOGICAL-TRUTH CALCULATOR
With the designs in mind, Kalin and Burkhart bought some war surplus materials, including relays, switches, wires, lights, and a metal box about 30 inches long by 16 inches tall, and 13 inches deep. From March to June, 1947, they constructed a machine in their spare time, assembling and mounting the parts inside the box. The total cost of materials was about $150. In June the machine was demonstrated in Cambridge, Mass., before several logicians and engineers, and in August it was moved for some months to the office of a life insurance company. There some study was made of the possible application of the machine in drafting contracts and rules.
GENERAL ORGANIZATION
OF THE MACHINE
The logical-truth calculator built by Kalin and Burkhart is not giant in size, although giant in capacity. Like other mechanical brains, the machine is made up of many pieces of a rather small number of different kinds of parts. The machine contains about 45 dial switches, 23 snap switches (or two-position switches), 85 relays, 6 push buttons, less than a mile of wire, etc. The lid of the metal box is the front, vertical panel of the machine.