Consider now two propositions p and q. If we know the truth value of p and the truth value of q, then we can determine the truth values of p&q, pvq, p⊃q, and p≡q—and also the truth value of ~p (as well as the truth value of ~q). It therefore follows that given any combination of p and q (that is, any proposition expressible in terms of p and q, using the logical connectives), we can determine the truth value of this combination once we are given the truth values of p and q. For example, suppose A is the proposition (p≡(q&p))⊃(~p⊃q). Given the truth values of p and q, we can successively find the values of q&p, p≡(q&p), ~p, (~p⊃q), and finally (p≡(q&p))⊃(~p⊃q). There are four possible distributions of truth values for p and q, and in each of the four cases we can determine the truth value of A. We can do this systematically by constructing the following table:
We see then that A is true in the first three cases and false in the fourth.
Let us consider another example: Let B = (p⊃q)⊃(~q⊃~p), and let us make a truth table for B.
We see that B is true in all four cases, and is hence an example of what is called a tautology.
We can also construct a truth table for a combination of three propositional unknowns—p, q, and r—but now there are eight cases to consider (because there are four distributions of T’s and F’s to p and q, and with each of these four distributions there are two possibilities for r). For example, suppose C is the expression (p&(q⊃r))⊃(r&~p). It would have the following truth table:
We will see that C is false in all eight cases; it is the very opposite of a tautology and is an example of what is called a contradiction. There are no propositions p, q, and r such that (p&(q⊃r))⊃(r&~p) is true. (We could have seen this without a truth table by using common sense. Suppose p&(q⊃r) is true. Then how could (r&~p) be true, since ~p is false?)
If we make a truth table for an expression in four unknowns—say, p, q, r, and s—there are sixteen cases to consider, and so the truth table will have sixteen lines. In general, for any positive whole number n, a truth table for an expression in n unknowns must have 2n lines (each time we add an unknown, the number of lines doubles).
TAUTOLOGIES
A proposition is called a tautology if it can be established purely on the basis of the truth table rules for the logical connectives. For example, suppose that one person says that it will rain tomorrow and a second person says that it won’t. We can hardly expect to tell which one is right by using a truth table. We must wait till tomorrow and then observe the weather. But suppose a third person says today: “Either it will rain tomorrow or it won’t.” Now, that’s what I would call a safe prediction! Without waiting for tomorrow, and making an observation, we know by pure reason that he must be right. His assertion is of the form pv~p (where p is the proposition that it will rain tomorrow), and for every proposition p, the proposition pv~p must be true (as a truth table will easily show).
The more usual definition of tautology involves the notion of a formula. By a formula is meant any expression built from the symbols ~, &, v, ⊃, ≡ and the propositional variables p, q, r,…parenthesized correctly. Here are the precise rules for constructing formulas:
(1) Any propositional variable standing alone is a formula.
(2) Given any formulas X and Y already constructed, the expressions (X&Y), (XvY), (X⊃Y), or (X≡Y) are again formulas, and so is the expression ~X.
It is to be understood that no expression is a formula unless it is constructed according to rules (1) and (2) above.
When displaying a formula standing alone, we can dispense with the outermost parentheses without incurring any ambiguity—for example, when we say “the formula p⊃q,” we mean “the formula (p⊃q).”
A formula in itself is neither true nor false, but only becomes true or false when we interpret the propositional variables as standing for definite propositions. For example, if I asked: “Is the formula (p&q) true?”, you would probably (and rightly) reply: “It depends on what propositions the letters ‘p’ and ‘q’ represent.” And so a formula such as “p&q” is sometimes true and sometimes false. On the other hand, a formula such as “pv~p” is always true (it is true whatever proposition is represented by the letter “p”) and is accordingly called a tautological formula. Thus a tautological formula is by definition a formula that is always true—or what is the same thing, a truth table for the formula will have only T’s in the last column. We can then define a proposition to be a tautology if it is expressed by some tautological formula under some interpretation of the propositional variables. (For example, the proposition that it is either raining or not raining is expressed by the formula pv~p, if we interpret “p” to be the proposition that it is raining.)
Logical Implication and Equivalence. Given any two propositions X and Y, we say that X logically implies Y, or that Y is a logical consequence of X if X⊃Y is a tautology. We say that X is logically equivalent to Y if X≡Y is a tautology; or, what is the same thing, if X logically implies Y and Y logically implies X.
SOME TAUTOLOGIES
The truth table is a systematic method of verifying tautologies, but many tautologies can be more quickly recognized by using a little common sense. Here are some examples:
(1) ((p⊃q)&(q⊃r))⊃(p⊃r).
This says that if p implies q, and if q implies r, then p implies r. This is surely self-evident (but can, of course, be verified by a truth table). This tautology has a name—it is called a syllogism.
(2) (p&(p⊃q))⊃q.
This says that if p is true, and if p implies q, then q is true. This is sometimes paraphrased: “Anything implied by a true proposition is true.”
(3) ((p⊃q)&~q)⊃~p.
This says that if p implies a false proposition, then p must be false.
(4) ((p⊃q)&(p⊃~q))⊃~p.
This says that if p implies q and also p implies not q, then p must be false.
(5) ((~p⊃q)&(~p⊃~q))⊃p.
This principle is known as reductio ad absurdum. To show that p is true, it suffices to show that ~p implies some proposition q as well as its negation ~q.
(6) ((pvq)&~p)⊃q.
This is a familiar principle of logic: If at least one of p or q is true, and if p is false, then it must be q that is true.
(7) ((pvq)&((p⊃r)&(q⊃r)))⊃r.
This is another familiar principle known as proof by cases. Suppose pvq is true. Suppose also that p implies r and that q implies r. Then r must be true (regardless of whether it is p or q that is true—or both).
The reader with little experience in propositional logic should benefit from the following exercise.
Exercise 1. State which of the following are tautologies.
(a) (p⊃q)⊃(q⊃p)
(b) (p⊃q)⊃(~p⊃~q)
(c) (p⊃q)⊃(~q⊃~p)
(d) (p≡q)⊃(~p≡~q)
(e) ~(p⊃~p)
(f) ~(p≡~p)
(g) ~(p&q)⊃(~p&~q)
(h) ~(pvq)⊃(~pv~q)
(i) (~pv~q)⊃~(pvq)
(j) ~(p&q)≡(~pv~q)
(k) ~(pvq)≡(~p&~q)
(l) (q≡r)⊃((p⊃q)≡(p⊃r))
(m) (p≡(p&q))≡(q≡(pvq))
Answers. (a) No, (b) No, (c) Yes, (d) Yes, (e) No! (f) Yes, (g) No, (h) Yes, (i) No, (j) Yes, (k) Yes, (l) Yes, (m) Yes (both p≡(p&q) and (q≡(pvq)) are equivalent to p⊃q).
Concerning (e), many beginners think that no proposition p can imply its negation. This is not so! If p happens to be false, then ~p is true, hence in that case, p⊃~p is true. However, no proposition can be equivalent to its own negation, and so (f) is indeed a tautology.
Discussion. The significance of tautologies is that they are not only true, but logically certain. No scientific experiments are necessary to establish their truth—they can be verified on the basis of pure reason.
One can alternatively characterize tautologies without appeal to the notion of formulas. Let us define a state of affairs as any classification of all propositions into two categories—true propositions and fa
lse propositions—subject to the restriction that the classification must obey the truth table conditions for the logical connectives (for example, we may not classify pvq as true if p and q are both classified as false). A tautology, then, is a proposition which is true in every possible state of affairs.
This is related to Leibniz’s notion of other possible worlds. Leibniz claimed that of all possible worlds, this one was the best. Frankly, I have no idea whether he was right or wrong in this, but the interesting thing is that he considered other possible worlds. Out of this, a whole branch of philosophical logic known as possible world semantics has developed in recent years—notably by the philosopher Saul Kripke—which we will discuss in a later chapter. Given any possible world, the set of all propositions that are true for that world, together with the set of all propositions that are false for that world, constitute the state of affairs holding for that world. A tautology, then, is true, not only for this world, but for all possible worlds. The physical sciences are interested in the state of affairs that holds for the actual world, whereas pure mathematics and logic study all possible states of affairs.
• 7 •
Knights, Knaves, and Propositional Logic
KNIGHTS AND KNAVES REVISITED
We can now introduce a simple but basic translation device whereby a host of problems about liars and truth tellers can be reduced to problems in propositional logic. This device will be crucial in several subsequent chapters.
Let us return to the Island of Knights and Knaves. Given a native P, let k be the proposition that P is a knight. Now, suppose that P asserts a proposition X. In general we do not know whether P is a knight or a knave, nor whether X is true or false. But this much we do know: If P is a knight, then X is true, and conversely, if X is true, then P is a knight (because knaves never make true statements). And so we know that P is a knight if and only if X is true; in other words, we know that the proposition k≡X is a true proposition. And so we translate “P asserts X” as “k≡X.”
Sometimes we have more than two natives involved—for example, suppose we have two natives P1 and P2. We let k1 be the proposition that P1 is a knight; we let k2 be the proposition that P2 is a knight. If a third native P3 is involved, we let k3 be the proposition that P3 is a knight, and so forth, for all natives involved. We then translate “P1 asserts X” as “k1≡X”; we translate “P2 asserts X” as “k2≡X”; and so on.
Let us now look at the first problem in Chapter 3 (this page). There are two natives P1 and P2 (the husband and the wife) involved. We are given that P1 asserts that P1 and P2 are both knaves; we are to determine the types of P1 and P2. Now, k1 is the proposition that P1 is a knight, hence ~k1 is equivalent to the proposition that P1 is a knave (since each inhabitant is a knight or a knave, but not both). Similarly, ~k2 is the proposition that P2 is a knave. Hence the proposition that P1 and P2 are both knaves is ~k1&~k2. P1 is asserting the proposition ~k1&~k2. Then, using our translation device, the reality of the situation is that k1≡(~k1&~k2) is true. So the problem can be posed in the following purely propositional terms: Given two propositions k1 and k2 such that k1≡(~k1&~k2) is true, what are the truth values of k1 and k2? If we make a truth table, we can see that the only case in which k1≡(~k1&~k2) comes out true is when k1 is false and k2 is true. (We also saw this by common-sense reasoning when we solved the problem in Chapter 3.) The upshot is that the proposition (k1≡(~k1&~k2))⊃~k1 is a tautology, and so is the proposition (k1≡(~k1&~k2))⊃k2.
The entire mathematical content of this problem is that for any propositions k1 and k2, the following proposition is a tautology: (k1≡(~k1&~k2))⊃(~k1&k2).
The reader might note as well that the converse proposition (~k1&k2)⊃(k1≡(~k1&~k2)) is also a tautology, hence the proposition k1≡(~k1&~k2) is logically equivalent to the proposition ~k1&k2.
Now let us look at the second problem in Chapter 3. Here P1 asserts that either P1 or P2 is a knave. We concluded that P1 is a knight and P2 is a knave. The mathematical content of this fact is that the proposition (k1≡(~k1v~k2))⊃(k1&~k2) is a tautology.
The reader might note in passing that the converse is also true, and hence that the proposition (k1≡(~k1v~k2))≡(k1&~k2) is a tautology.
The translation of Problem 3 is of particular theoretical significance; in fact, let us consider it in the more general form of Theorem I, Chapter 3 (this page). We have a native P claiming about a certain proposition q that if P is a knight, then q is true (q could be the proposition that P’s wife is a knight, or that there is gold on the island, or any proposition whatsoever). We let k be the proposition that P is a knight. Thus P is claiming the proposition k⊃q, and so the reality of the situation is that k≡(k⊃q) is true. From this we are to determine the truth value of k and q. As we have seen, k and q must both be true. Thus the mathematical content of Theorem I, Chapter 3, is that (k≡(k⊃q))⊃(k&q) is a tautology. Of course this fact is not really dependent on the particular nature of the proposition k; for any proposition p and q, the proposition (p≡(p⊃q))⊃(p&q) is a tautology. The converse proposition, (p&q)⊃(p≡(p⊃q)), is also a tautology, because if p&q is true, p and q are both true, then p⊃q must be true, hence p≡(p⊃q) must be true. And so the following is a tautology: (p≡(p⊃q))≡(p&q).
Let us now look at Problem 4, or rather Theorem II, in Chapter 3. Here we have P claiming that P is a knight if and only if q. Again we let k be the proposition that P is a knight, and so P is claiming the proposition k≡q. Therefore we know that k≡(k≡q) is true. From this we can determine that q must be true, and so the essential mathematical content of Theorem II, Chapter 3, is that the following is a tautology: (k≡(k≡q))⊃q.
This tautology is what I would call the Goodman tautology, since it arises from Nelson Goodman’s problem, which is discussed in Chapter 3.
Exercise 1. Let us consider three inhabitants P1, P2, and P3 of the knight-knave island. Suppose P1 and P2 make the following statements.
P1: P2 and P3 are both knights.
P2: P1 is a knave and P3 is a knight.
What types are P1, P2, and P3?
Exercise 2. (a) Is the following a tautology?
((k1≡(k2&k3))&(k2≡(~k1&k3)))⊃((~k1&~k2)&~k3
(b) How does this relate to Exercise 1?
Exercise 3. Show that the proposition p3 is a logical consequence of the following two propositions:
(1) p1≡~p2
(2) p2≡(p1≡~p3)
Exercise 4. Suppose P1, P2, and P3 are three inhabitants of the knight-knave island, and that P1 and P2 make the following statements:
P1: P2 is a knave.
P2: P1 and P3 are of different types.
(a) Is P3 a knight or a knave?
(b) How does this relate to Exercise 3?
THE OONA PROBLEMS
Many of the Oona problems of Chapter 4 can also be solved by truth tables. Consider, for example, the first one (this page): We have two natives P1 and P2; P1 asserts that if P1 and P2 are both knights, then Oona is on the island. P2 asserts the same thing. We let O be the proposition that Oona is on the island. Using our translation device, we know that the following two propositions are true.
(1) k1≡((k1&k2)⊃O)
(2) k2≡((k1&k2)⊃O)
We are to determine whether O is true or false. Well, if you make a truth table for the conjunction of (1) and (2)—i.e., for (k1≡((k1&k2)⊃O))&(k2≡(k1&k2)⊃O)), you will see that the last column contains T’s in those and only those places in which O has the value T. Therefore O must be true.
Exercise 5. Suppose the husband goes looking for Oona and meets two natives A and B on an island and they make the following statements:
A: If B is a knight, then Oona is not on this island.
B: If A is a knave, then Oona is not on this island.
Is Oona on this island?
Exercise 6. On another island, two natives A and B make the following statements:
A: If either of us is a knight, then Oona is on this island.
B:
If either of us is a knave, then Oona is on this island.
Is Oona on this island?
Exercise 7. On another island, two natives A and B make the following statements.
A: If I am a knight and B is a knave, then Oona is on this island.
B: That is not true!
Is Oona on this island?
MARTIANS AND VENUSIANS REVISITED
Many of the Mars–Venus–Female–Male puzzles of Chapter 5 can also be solved by truth tables, although the translation device needed is a bit more complex, and this type of problem is not considered further in the present book.
Let us number the club members in some order P1, P2, P3, etc., and for each number i, let Vi be the proposition that Pi is Venusian, and let Fi be the proposition that Pi is female. Then Pi is Martian can be written ~Vi, and Pi is male can be written ~Fi. Now, Pi tells the truth if and only if Pi is either a Venusian female or a Martian male, which can be symbolized (Vi&Fi)v(~Vi& ~Fi), or more simply, Vi≡Fi. And so now if Pi asserts a proposition X, the reality of the situation is the following proposition: (Vi≡Fi)≡X.
This then is our translation device. Whenever Pi asserts X, we write down: (Vi≡Fi)≡X.
Consider, for example, Problem 7 of Chapter 5 (this page)—the case of Ork and Bog. Let P1 be Ork and P2 be Bog. Then we are given the following four propositions (after we apply the translation device):
(1) (V1≡F1)≡V2
(2) (V2≡F2)≡~V1
(3) (V1≡F1)≡~F2
(4) (V2≡F2)≡F1
The truth values of V1, F1, V2, and F2 can then be found by a truth table. (There are four unknowns V1, F1, V2, and F2 involved, and so there are sixteen cases to consider!)
Forever Undecided Page 4