C H A P T E R S E V E N THE METHOD OF DEDUCTION 7.1 NATURAL DEDUCTION VERSUS TRUTH TABLES In the previous chapter we introduced symbolic logic. There we used truth tables to define the five truth-functional connectives, showed how to use truth tables to test individual sentences for various properties, and demonstrated how to use truth tables to test arguments for validity. In this chapter, we develop an alternative system of proof—the method of deduction. The method of deduction is a proof system logicians call natural deduction because the kinds of reasoning employed are close to natural language reasoning. This is in contrast to the truth table method which, though reliable and perfectly adequate as a system of proof, is not a very natural way to reason. If you’re trying to convince a friend to accept your conclusion, natural deduction follows the step-by-step method you’d use to demonstrate that, given your premises, your friend must accept your conclusion. Because natural deduction follows the ways in which we ordinarily argue, many students claim doing deductive proofs improves their argumentative skills. Some have claimed doing proofs improves their general organizational abilities. The method of deduction, however, differs from truth tables in two important ways. First, if you’re constructing a complete truth table, the procedure is virtually mechanical: You use the guide columns to fill in the columns for all the compound propositions according to the definitions of the connectives. When constructing a deductive proof, however, you’ll need to recognize argument forms, and you’ll often have to think carefully to figure out how to link the premises to the conclusion by means of a chain of valid argument forms. Second, truth tables can demonstrate invalidity as well as validity. The method of deduction can only be used to show that a conclusion follows by a series of valid inferences from a given set of premises. It cannot be used to demonstrate invalidity—but that’s easily done with a reverse truth table, so there is no problem. 244 Formal Proofs of Validity 7.2 FORMAL PROOFS OF VALIDITY Consider the following argument: A)B B)C ‘C A ¡ D ‹ D To establish the validity of this argument with a truth table would require a table of 16 rows. But we can establish its validity by a sequence of elementary arguments, each of which is known to be valid. Such a step-by-step procedure is called a formal proof. In general, we can define a formal proof as follows: A formal proof of an argument is a sequence of statements, each of which is either a premise of that argument or follows as an elementary valid argument from preceding statements in the sequence, such that the last statement in the sequence is the conclusion of the argument whose validity is being proved. An elementary valid argument is any argument that is a substitution instance of an elementary valid argument form. A proof consists of two columns. In one column you have the premises and all the conclusions that follow from them. In the other column, you cite the rule and the lines of the proof that justify the conclusion reached in that line. A formal proof of the argument above would look like this: 1. A ) B 2. B ) C 3. ‘ C 4. A ¡ D ‹ D 5. A ) C 6. ‘ A 7. D 1,2 H.S. 3,5 M.T. 4,6 D.S. The first four numbered propositions are the premises of the original argument. The premises are followed by a statement of the conclusion that is to be derived. Notice that the statement of the conclusion is not a part of the formal proof. Only the numbered steps or lines are part of the proof. Lines five through seven follow from preceding lines by elementary valid arguments. The notation to the right of each numbered line constitutes its justification. Thus Step 5, A ) C, is a valid conclusion from premises 1 and 2 by an elementary valid argument that is a substitution instance of the form called hypothetical syllogism (abbreviated H.S.). 245 246 Chapter 7 The Method of Deduction FORMAL PROOF: FIRST INFERENCE 1. A ) B 2. B ) C 3. ‘ C 4. A ¡ D ‹ D 5. A ) C Hypothetical Syllogism p)q q)r ‹ p)r 1. A ) B 2. B ) C 1,2 H.S. 5. A ) C Step 6, ‘ A, is a valid conclusion from premise 3 and step 5 by an elementary valid argument that is a substitution instance of the form called modus tollens (M.T.). FORMAL PROOF: SECOND INFERENCE 1. A ) B 2. B ) C 3. ‘ C 4. A ¡ D ‹ D 5. A ) C 6. ‘ A Modus Tollens p)q ‘q ‹ ‘p 1,2 H.S. 5,3 M.T. 5. A ) C 3. ‘ C 6. ‘ A And finally, Step 7, D, which is the conclusion of the argument, is a valid conclusion from premise 4 and step 6 by an elementary valid argument that is a substitution instance of the form called the disjunctive syllogism (D.S.). Step 7, in other words, shows that D follows from the original premises, and that the argument is valid. FORMAL PROOF: THIRD INFERENCE 1. A ) B 2. B ) C 3. ‘ C 4. A ¡ D ‹ D 5. A ) C 6. ‘ A 7. D Disjunctive Syllogism p ¡ q ‘p ‹ q 1,2 H.S. 5,3 M.T. 4,6 D.S. 4. A ¡ D 6. ‘ A 7. D Elementary valid argument forms like modus tollens (M.T.), Hypothetical Syllogism (H.S.), and Disjunctive Syllogism (D.S.) constitute rules of inference. Rules of Inference allow you to validly infer conclusions from premises. There Formal Proofs of Validity are nine such rules—summarized in the following table—corresponding to elementary argument forms whose validity is easily established by truth tables. With their aid, formal proofs of validity can be constructed for a wide range of more complicated arguments. R U L E S O F I N F E R E N C E : E L E M E N TA R Y VA L I D A R G U M E N T F O R M S NAME ABBREVIATION FORM Modus Ponens M.P. p)q p ‹ q Modus Tollens M.T. p)q ‘q ‹ ‘p Hypothetical Syllogism H.S. p)q q)r ‹ p)r Disjunctive Syllogism D.S. p ¡ q ‘p ‹ q Constructive Dilemma C.D. Absorption Abs. Simplification Simp. Conjunction Conj. Addition Add. 1p ) q2 • 1r ) s2 p ¡ r ‹ q ¡ s p)q ‹ p ) 1p • q2 p•q ‹ p p q ‹ p•q p ‹ p ¡ q It is important to remember that the variables, p, q, r, and s can be replaced by statements of any degree of complexity. So, although A•B ‹ A is an instance of Simplification, so is 31A ) B2 ¡ ‘ C4 • 53C K 1D ¡ ‘ E24 ) ‘ 1A K ‘ C26 ‹ 1A ) B2 ¡ ‘ C 247 248 Chapter 7 The Method of Deduction The other point to stress is that the rules apply to an entire line or lines of a proof, depending upon the rule. So, you must pay attention to what the principal connective in a line of the proof is. Your application of the rules must be mechanical: There must be a perfect match between the principal connectives in the rules and those in the lines to which the rules are applied. The general idea of the method of deduction is to move, by small inferences that are known to be valid, from the premises of an argument to its conclusion. When you can do this, you have proven that the original argument itself is valid. This works because validity is truth-preserving. Each of the rules is a valid deductive inference, as can be shown by truth tables.1 So, if a valid argument has true premises, its conclusion will be true. Notice what you’re doing when you do a proof. (1) Sometimes you’re using the rules to eliminate those simple statements that are in the premises but not in the conclusion. (2) In some cases, you’re making bigger statements. (3) Sometimes you’ll introduce a simple statement that is in the conclusion but not in the premises: That’s always done by addition. (4) Sometimes you move things around and change the appearance of statements in the premises so they’ll look like the conclusion—this is primarily done by the equivalences falling under the rule of replacement, which we’ll examine beginning in the next two sections. Keeping this in mind, the rules of inference can be divided into two classes. The first group might be called elimination rules. When you use those rules, you reach a conclusion that contains fewer simple statements than are found in the premises. Modus ponens, modus tollens, hypothetical syllogism, disjunctive syllogism, simplification, and constructive dilemma are elimination rules. The second group of rules might be called augmentation rules. When you use those rules, you reach a conclusion that either contains more simple statements than either of the premises contains or, in the case of absorption, a statement that has more instances of simple statements than are found in the premise. Addition, conjunction, and absorption are augmentation rules. So, let’s see how these work by considering a couple of examples. You’re given the argument form: p ) 1 ‘ q • r2 p q ¡ ‘s ‹ ‘s ¡ t You begin by noticing what is in the conclusion. The conclusion contains ‘ s and t. t is not found in the premises. The only rule that allows you to introduce something not found in the premises is addition. So, you’re going to use addition at the end of the proof. You need to isolate ‘ s so you can add. ‘ s is in 1We discussed some of these inferences in the last chapter. If you did all the exercises in the last chapter, you constructed truth tables that show the remaining inferences are valid. Formal Proofs of Validity premise 3. To isolate ‘ s, you’ll need ‘ q: Then you could reach ‘ s by disjunctive syllogism. The only place you find ‘ q is in premise 1. If you could isolate ‘ q • r, you could get ‘ q by simplification. To get ‘ q • r, you’d need p. Then you could reach ‘ q • r by modus ponens. You have p in premise 2. We have reasoned backward from the conclusion through the premises. Now we only need to state it forwardly: 1. p ) 1 ‘ q • r2 2. p 3. q ¡ ‘ s ‹ ‘s ¡ t ‘ 4. q • r 5. ‘ q 6. ‘ s 7. ‘ s ¡ t 1,2 M.P. 4 Simp. 3,5 D.S. 6. Add. Although it is sometimes possible to argue backwards from the conclusion through the premises, you might reason in the following way instead. p, q, and r are in the premises, but they are not in the conclusion. I can eliminate p by modus ponens from 1 and 2. That gives me ‘ q • r. Simplification will give me ‘ q, eliminating r. Using disjunctive syllogism with premise 3 will give me ‘ s, thereby eliminating q. But the conclusion is ‘ s ¡ t. So, I need to augment what I’ve concluded. The only rule that allows me to add a new simple statement into a proof is addition. So, I add t to ‘ s to get ‘ s ¡ t. You have written out the proof just as it is above, and with a certain panache you write Q.E.D. (quod erat demonstrandum, which was to be proved) at the end of the proof.2 It doesn’t make any difference whether you work backward from the conclusion or forward from the premises. Often you’ll do some of each. It’s always important to begin by noticing what is in the conclusion. By noticing what is in the conclusion, you will know which simple statements in the premises you want to eliminate. Consider another one: p•q 1p ) q2 • 1r ) s2 ‹ p • 1q ¡ s2 The conclusion is a conjunction. When the conclusion is a conjunction, you usually will reach the conclusion by the rule of conjunction.3 So, you’ll probably want to isolate p and q ¡ s. How do you do that? You’ll probably do 2The Q.E.D. is strictly a matter of flamboyance: It’s not part of the proof; it’s just a decoration. 3The exception is when you find the conjunction as a component of the premises. 249 250 Chapter 7 The Method of Deduction what most students do: You’ll stare at the rules (and, perhaps, mumble various words to yourself). If it’s productive staring, you’ll compare the premises and conclusion of the argument you wish to prove with the premises and conclusions in the rules. The first premise is a conjunction with p as the first conjunct. So, you’ll simplify. But how do you get q ¡ s ? You might think it through this way: The first conjunct of the second premise is p ) q. Since I have p, I could simplify the second premise to get p ) q, and use modus ponens to get q. Then it’s just a matter of adding and conjoining. Your proof would look like this: 1. p • q 2. 1p ) q2 • 1r ) s2 ‹ p • 1q ¡ s2 3. p 4. p ) q 5. q 6. q ¡ s 7. p • 1q ¡ s2 Q.E.D. 1 Simp. 2 Simp. 4,3 M.P. 5 Add. 3,6 Conj. On the other hand, once you’ve isolated p you might think it through this way: The second premise is a conjunction of conditionals, and I want to reach a conclusion that contains a disjunction. One of the premises for constructive dilemma is a conjunction of conditionals, and the conclusion of constructive dilemma is a disjunction. Further, the q and s are the consequents of both conditionals, just as they would be if I did a constructive dilemma. But I don’t have the other premise, namely, p ¡ r. Can I get that? Well, yes. I have p, and if you have p you can add anything. So, I can reach an intermediate conclusion p ¡ r and construct my proof as follows: 1. p • q 2. 1p ) q2 • 1r ) s2 ‹ p • 1q ¡ s2 3. p 4. p ¡ r 5. q ¡ s 6. p • 1q ¡ s2 Q.E.D. 1 Simp. 3 Add. 2,4 C.D. 3,5 Conj. Formal Proofs of Validity Of course, now you’re asking, “Yeah, but which one’s right???” They’re both right. Both proofs show that the conclusion follows validly from the premises, which is what a proof is supposed to do. The only difference is the second proof is more elegant. Elegance in logic is a matter of length: The shorter the proof, the more elegant it is. Elegance makes no logical difference. So, in constructing a proof, you’ll want to do the following: ESSENTIAL HINTS You should look at proofs as games or puzzles. As with many games or puzzles, the longer you play with them, the more fun they become. This doesn’t mean you’ll immediately applaud the joys of proofs. Students have been known to say words their grandmothers didn’t teach them when doing proofs. But if you work at them for an hour or so a day—every day— they become fun. This doesn’t mean you should sit down and say, “Now I’m going to do proofs for an hour.” Proofs can be fatiguing. Initially, proofs can be frustrating. You might do well to begin with several ten or fifteen minute sessions every day. If you become stumped, go on to another problem or stop and return to them later. Sometimes just by being away from a proof for a little while you’ll “see” things you didn’t see before. 1. Find the components of the conclusion in the premises. 2. Determine which rules you can use to eliminate simple statements in the premises that are not in the conclusion (modus ponens, modus tollens, disjunctive syllogism, hypothetical syllogism, simplification, constructive dilemma). 3. Determine whether you’ll need to use a rule to augment a premise or an intermediate conclusion to reach the final conclusion (addition, absorption, conjunction). 4. Construct the proof applying the rules of inference to an entire line of the proof (simplification, absorption, addition) or to two entire lines of the proof (modus ponens, modus tollens, disjunctive syllogism, hypothetical syllogism, constructive dilemma, conjunction). EXERCISES I. For each of the following elementary valid arguments, state the rule of inference by which its conclusion follows from its premise or premises. 1. 1E ) F2 • 1G ) H2 E ¡ G ‹ F ¡ H 3. H ) I ‹ 1H ) I2 ¡ 1H ) ‘ I2 2. 1D ¡ E2 • 1F ¡ G2 ‹ D ¡ E 4. ‘ 1J • K2 • 1L ) ‘ M2 ‹ ‘ 1J • K2 251 252 Chapter 7 The Method of Deduction 5. 1X ¡ Y2 ) ‘ 1Z • ‘ A2 ‘ ‘ 1Z • ‘ A2 ‹ ‘ 1X ¡ Y2 7. ‘ 1B • C2 ) 1D ¡ E2 ‘ 1B • C2 ‹ D)E 6. 1S K T2 ¡ 31U • V2 ¡ 1U • W24 ‘ 1S K T2 ‹ 1U • V2 ¡ 1U • W2 8. 1F K G2 ) ‘ 1G • ‘ F2 ‘ 1G • ‘ F2 ) 1G ) F2 ‹ 1F K G2 ) 1G ) F2 9. 1A ) B2 ) 1C ¡ D2 10. 3E ) 1F K ‘ G24 ¡ 1C ¡ D2 ‘ 3E ) 1F K ‘ G24 A)B ‹ C ¡ D ‹ C ¡ D 11. 1C ¡ D2 ) 31J ¡ K2 ) 1J • K24 12. ‘ 3L ) 1M ) N24 ) ‘ 1C ¡ D2 ‘ 31J ¡ K2 ) 1J • K24 ‘ 3L ) 1M ) N24 ‘ ‹ 1C ¡ D2 ‹ ‘ 1C ¡ D2 13. N ) 1O ¡ P2 Q ) 1O ¡ R2 ‹ 3Q ) 1O ¡ R24 • 3N ) 1O ¡ P24 14. 1W • ‘ X2 K 1Y ) Z2 ‹ 31W • ‘ X2 K 1Y ) Z24 ¡ 1X K ‘ Z2 15. 31H • ‘ I2 ) C4 • 31I • ‘ H2 ) D4 1H • ‘ I2 ¡ 1I • ‘ H2 ‹ C ¡ D II. Each of the following is a formal proof of validity for the indicated argument. State the “justification” for each numbered line that is not a premise. 16. 1. 1E ¡ F2 • 1G ¡ H2 17. 1. I ) J 2. 1E ) G2 • 1F ) H2 2. J ) K 3. ‘ G 3. L ) M 4. I ¡ L ‹ H 4. E ¡ F ‹ K ¡ M 5. G ¡ H 5. I ) K 6. H 6. 1I ) K2 • 1L ) M2 7. K ¡ M 18. 1. W ) X 2. 1W ) Y2 ) 1Z ¡ X2 3. 1W • X2 ) Y 4. ‘ Z ‹ X 5. W ) 1W • X2 6. W ) Y 7. Z ¡ X 8. X 19. 1. 1A ¡ B2 ) C 2. 1C ¡ B2 ) 3A ) 1D K E24 3. A • D ‹ D K E 4. A 5. A ¡ B 6. C 7. C ¡ B 8. A ) 1D ) E2 9. D K E Formal Proofs of Validity 20. 1. I ) J 2. I ¡ 1 ‘ ‘ K • ‘ ‘ J2 3. L ) ‘ K 4. ‘ 1I • J2 ‹ ‘L ¡ ‘J 5. I ) 1I • J2 6. ‘ I 7. ‘ ‘ K • ‘ ‘ J 8. ‘ ‘ K 9. ‘ L 10. ‘ L ¡ ‘ J III. For each of the following, adding just two statements to the premises will produce a formal proof of validity. Construct a formal proof of validity for each of the following arguments. 21. D ) E 22. J ) K J D•F ‹ E ‹ K ¡ L 23. P • Q R ‹ P•R 25. Y ) Z Y ‹ Y•Z 27. ‘ 1K • L2 K)L ‹ ‘K 29. 1Z • A2 ) 1B • C2 Z)A ‹ Z ) 1B • C2 31. 1K ) L2 ) M ‘ M • ‘ 1L ) K2 ‹ ‘ 1K ) L2 33. A ) B A ¡ C C)D ‹ B ¡ D 35. 1M ) N2 • 1O ) P2 N)P 1N ) P2 ) 1M ¡ O2 ‹ N ¡ P 24. V ¡ W ‘V ‹ W ¡ X 26. D ) E 1E ) F2 • 1F ) D2 ‹ D)F 28. 1T ) U2 • 1T ) V2 T ‹ U ¡ V 30. D ) E 3D ) 1D • E24 ) 1F ) ‘ G2 ‹ F ) ‘G 32. 3T ) 1U ¡ V24 • 3U ) 1T ¡ V24 1T ¡ U2 • 1U ¡ V2 ‹ 1U ¡ V2 ¡ 1T ¡ V2 34. J ¡ ‘ K K ¡ 1L ) J2 ‘J ‹ L)J 253 254 Chapter 7 The Method of Deduction IV. For each of the following, adding just three statements to the premises will produce a formal proof of validity. Construct a formal proof of validity for each of the following arguments. 36. 1D ¡ E2 ) 1F • G2 37. 1H ) I2 • 1H ) J2 D H • 1I ¡ J2 ‹ F ‹ I ¡ J 38. 1K • L2 ) M K)L ‹ K ) 31K • L2 • M4 40. T ) U V ¡ ‘U ‘V• ‘W ‹ ‘T 42. 1A ¡ B2 ) ‘ C C ¡ D A ‹ D 39. Q ) R R)S ‘S ‹ ‘Q• ‘R 41. ‘ X ) Y Z)X ‘X ‹ Y• ‘Z 43. 1H ) I2 • 1J ) K2 K ¡ H ‘K ‹ I 44. 1P ) Q2 • 1Q ) P2 R)S P ¡ R ‹ Q ¡ S 45. 1T ) U2 • 1V ) W2 1U ) X2 • 1W ) Y2 T ‹ X ¡ Y 48. W ) X 1W • X2 ) Y 1W • Y2 ) Z ‹ W)Z 49. A ) B C)D A ¡ C ‹ 1A • B2 ¡ 1C • D2 V. Construct a formal proof of validity for each of the following arguments. 46. 1F ) G2 • 1H ) I2 47. 1K ¡ L2 ) 1M ¡ N2 J)K 1M ¡ N2 ) 1O • P2 K 1F ¡ J2 • 1H ¡ L2 ‹ G ¡ K ‹ O 50. J ) K K ¡ L 1L • ‘ J2 ) 1M • ‘ J2 ‘K ‹ M 51. 31A ¡ B2 ) C4 • 31X • Y2 ) Z4 ‘C 1A ¡ B2 ¡ 1Y ) X2 ‘X ‹ ‘ Y ¡ 1X K Y2 VI. Construct a formal proof of validity for each of the following arguments. Translate using the abbreviations suggested. 52. If Adams joins, then the club’s social prestige will rise; and if Baker joins, then the club’s financial position will be more secure. Formal Proofs of Validity Either Adams or Baker will join. If the club’s social prestige rises, then Baker will join; and if the club’s financial position becomes more secure, then Wilson will join. Therefore, either Baker or Wilson will join. (A—Adams joins; S—The club’s social prestige rises; B—Baker joins; F—The club’s financial position is more secure; W—Wilson joins.) 53. If Brown received the wire, then she took the plane; and if she took the plane, then she will not be late for the meeting. If the telegram was incorrectly addressed, then Brown will be late for the meeting. Either Brown received the wire, or the telegram was incorrectly addressed. Therefore, either Brown took the plane, or she will be late for the meeting. (R—Brown received the wire; P—Brown took the plane; L—Brown will be late for the meeting; T—The telegram was incorrectly addressed.) 54. If Neville buys the lot, then an office building will be constructed; whereas if Payton buys the lot, then it quickly will be sold again. If Rivers buys the lot, then a store will be constructed; and if a store is constructed, then Thompson will offer to lease it. Either Neville or Rivers will buy the lot. Therefore either an office building or a store will be constructed. (N—Neville buys the lot; O—An office building will be constructed; P—Payton buys the lot; Q—The lot quickly will be sold again; R—Rivers buys the lot; S—A store will be constructed; T—Thompson will offer to lease it.) 55. If Ann is present, then Bill is present. If Ann and Bill are both present, then either Charles or Doris will be elected. If either Charles or Doris is elected, then Elmer does not really dominate the club. If Ann’s presence implies that Elmer does not really dominate the club, then Florence will be the new president. So, Florence will be the new president. (A—Ann is present; B—Bill is present; C—Charles will be elected; D—Doris will be elected; E—Elmer really dominates the club; F—Florence will be the new president.) 56. If either Alejandro or Julio went to the dance, then Belinda went to the dance; and if both Ivan and Dmitri went to the game, then Katrina went to the game. Belinda did not go to the dance. Either Alejandro or Julio went to the dance; unless the fact that Dmitri went to the game implies that Ivan went to the game. Ivan did not go to the game. Therefore, either Dmitri did not go to the game, or Ivan went to the game if and only if Dmitri went to the game. (A—Alejandro went to the dance; J—Julio went to the dance; B—Belinda went to the dance; I—Ivan went to the game; D—Dmitri went to the game; K—Katrina went to the game.) 255 256 Chapter 7 The Method of Deduction 57. If Giovanni plays chess, then Lucia plays chess; and if Tex does not play checkers, then Jen plays checkers. Giovanni plays chess, and Tex plays checkers. Lucia does not play chess. So, either Jen plays checkers and Giovanni plays chess, or if Lucia does not play chess, then Tex plays checkers. (G—Giovanni plays chess; L— Lucia plays chess; T—Tex plays checkers; J—Jen plays checkers.) 58. If either Rolf or Solvig plays polo, then Daphne writes poetry. Rolf plays polo. If Daphne writes poetry, then Chris sings ballads. Either Rolf or Solvig plays polo, and Chris sings ballads; only if Theo plays trumpet. Hence, Theo plays trumpet unless Rolf does not play polo. (R—Rolf plays polo; S—Solvig plays polo; D—Daphne writes poetry; C—Chris sings ballads; T—Theo plays trumpet.) 59. If Lucia writes music, then Gabriella writes novels; and if Horace writes poetry, then Xaneta writes cookbooks. If Pete shoots pool, then Saundra shoots skeet; and if Mei-Mei plays mah-jongg, then Danielle dances. Lucia writes music. If either Gabriella writes novels or Saundra shoots skeet, then Bart is clueless only if Callie catches crows. Callie does not catch crows. So, Bart is not clueless. (L—Lucia writes music; G—Gabriella writes novels; H—Horace writes poetry; X—Xaneta writes cookbooks; P—Pete shoots pool; S—Saundra shoots skeet; M—Mei-Mei plays mah-jongg; D— Danielle dances; B—Bart is clueless; C—Callie catches crows.) 60. If Mr. Smith is the brakeman’s next-door neighbor, then Mr. Smith lives halfway between Detroit and Chicago. If Mr. Smith lives halfway between Detroit and Chicago, then he does not live in Chicago. Mr. Smith is the brakeman’s next-door neighbor. If Mr. Robinson lives in Detroit, then he does not live in Chicago. Mr. Robinson lives in Detroit. Mr. Smith lives in Chicago or else either Mr. Robinson or Mr. Jones lives in Chicago. If Mr. Jones lives in Chicago, then the brakeman is Jones. Therefore, the brakeman is Jones. (S—Mr. Smith is the brakeman’s next-door neighbor; W—Mr. Smith lives halfway between Detroit and Chicago; L—Mr. Smith lives in Chicago; D—Mr. Robinson lives in Detroit; I—Mr. Robinson lives in Chicago; C—Mr. Jones lives in Chicago; B—The brakeman is Jones.) 61. Ms. Hernandez programs computers. If Ms. Hernandez programs computers, then Mr. Mendez is an accountant and Mr. Sanchez is president of the bank. If Ms. Hernandez programs computers, then Ms. Chang runs a computer firm and Mr. Kim writes software. If Mr. Mendez is an accountant and Ms. Chang runs a computer firm, then Ms. Lewinski keeps the mainframe working. If Ms. Lewinski keeps the mainframe working, then either Mr. Popov has a virus in his computer or Dr. Rasmussen runs the The Rule of Replacement (1) clinic. Mr. Popov does not have a virus in his computer. If Dr. Rasmussen runs the clinic, then Ms. DiToro is a nurse. Therefore, Ms. DiToro is a nurse. (H— Ms. Hernandez programs computers; M— Mr. Mendez is an accountant; S—Mr. Sanchez is president of the bank; C—Ms. Chang runs a computer firm; K—Mr. Kim writes software; L— Ms. Lewinski keeps the mainframe working; P— Mr. Popov has a virus in his computer; R— Dr. Rasmussen runs the clinic; D—Ms. DiToro is a nurse.) 7.3 THE RULE OF REPLACEMENT (1) There are many valid arguments whose validity cannot be proved using only the nine rules of inference. For example, A•B ‹ B is valid, since a conjunction is true if and only if both conjuncts are true. But the rule for simplification allows you only to conclude the truth of the left conjunct. B • A is logically equivalent to A • B If we could replace A • B with B • A, we could simplify and conclude B. So, we’re going to expand our system of propositional logic by introducing one more rule of inference and a number of logically equivalent statements that fall under that rule. The rule is the rule of replacement. The rule of replacement allows us to replace logically equivalent statements that fall under the rule wherever they occur in a proof. While the first nine rules apply only to a whole line or two lines of a proof, the equivalences falling under the rule of replacement allow you to modify compound statements within a line of a proof. For example, since A • B is logically equivalent to B • A, you could transform the statement 1A • B2 ) C to 1B • A2 ) C by commutation. Look at it this way. The nine rules of inference allow you to eliminate and augment statements as a whole. They allow you to “cut up” statements, to remove or add parts, in much the same way that a surgeon might remove something from your body when performing surgery or an auto mechanic might add a new part to your car. The rule of replacement allows you to change the appearance of statements in the same way that a plastic surgeon changes the appearance of a person—sometimes significantly—without changing the person: The fundamental parts are all still there. We introduce the equivalences falling under the rule of replacement in this section and the next. Once all the equivalences falling under the rule of replacement are introduced, you will be able to demonstrate the validity of any valid argument in propositional logic. 257 258 Chapter 7 The Method of Deduction R U L E O F R E P L A C E M E N T : A N Y O F T H E F O L L O W I N G L O G I C A L LY E Q U I VA L E N T E X P R E S S I O N S C A N R E P L A C E E A C H O T H E R WHEREVER THEY OCCUR IN A PROOF: NAME ABBREVIATION De Morgan’s Theorems De M. Commutation Association Distribution Double Negation Com. Assoc. FORM T ‘ ‘ 1p ¡ q2 K 1 p • ‘ q2 T ‘ ‘ 1p • q2 K 1 p ¡ ‘ q2 T 1p ¡ q2 K 1q ¡ p2 T 1p • q2 K 1q • p2 T 3p ¡ 1q ¡ r24 K 31p ¡ q2 ¡ r4 Dist. T 3p • 1q • r24 K 31p • q2 • r4 D.N. T 3p ¡ 1q • r24 K 31p ¡ q2 • 1p ¡ r24 T 3p • 1q ¡ r24 K 31p • q2 ¡ 1p • r24 T ” p K p De Morgan’s theorems tell you how to move a tilde into or out of parentheses when dealing with conjunction or disjunction. If you’re given a statement of the form ‘ 1p ¡ q2, you can replace it with the logically equivalent statement ‘ p • ‘ q. You could then simplify to ‘ p. Or if you’re given ‘ p ¡ ‘ q you can replace it with ‘ 1p • q2 and use that statement with another statement in the argument. Commutation allows you to reverse the positions of conjuncts or disjuncts. So, looking again at the example with which we began the section, given A • B, you can commute to B • A and simplify to conclude B. If you consider the truth values for conjunction and disjunction, you’ll conclude that the order in which the conjuncts or disjuncts are given does not affect the truth value. Notice, commutation applies only to conjunction and disjunction. Association allows you to move parentheses in conjunctions in which one conjunct is itself a conjunction and in disjunctions in which one of the disjuncts is itself a disjunction. If you consider the truth values for conjunction and disjunction, you’ll conclude that if you have a conjunction of three statements or a disjunction of three statements, the grouping does not affect the truth value. Notice, association applies only to conjunctions and disjunctions. Distribution deals with complex statements that include both a conjunction and a disjunction. The English sentence, “Alejandro won the election or both Dmitri and Lucia lost,” is logically equivalent to, “Either Alejandro won the election and Dmitri lost, or Alejandro won the election and Lucia lost.” The Rule of Replacement (1) Notice that distribution requires both a disjunction and a conjunction, and you can distribute only when you have both a disjunction and a conjunction. Double negation reflects what your English teachers have been telling you for years, namely, two negatives make a positive. Indeed, this is so deeply engrained, that of all the equivalences, double negation is the one you’re most likely to forget to include as a justification in a proof. ESSENTIAL HINTS Commutation, association, and distribution are probably familiar to you from your math classes. Commutation and association are properties of addition and multiplication. Addition and multiplication taken together allow you to distribute. D O U B L E N E G AT I O N : T W O P R O O F S Consider this argument: 1A ¡ B2 ) 1 ‘ ‘ D • C2 A ‹ D ONE FORMAL PROOF OF THIS ARGUMENT IS THE FOLLOWING: 1. 1A ¡ B2 ) 1 ‘ ‘ D • C2 2. A ‹ D 3. A ¡ B 2. Add 4. ‘ ‘ D • C 1,3 M.P. 5. ‘ ‘ D 4 Simp. 6. D 5 D.N. ANOTHER VALID PROOF OF THE ARGUMENT IS THIS: 1. 1A ¡ B2 ) 1 ‘ ‘ D • C2 2. A ‹ D 3. 1A ¡ B2 ) 1D • C2 1 D.N. 4. A ¡ B 2 Add. 5. D • C 3,4 M.P. 6. D 5 Simp. In both cases we replaced the expression ‘ ‘ D with the logically equivalent expression D. So, let’s look at a few examples to see how these equivalences fit together with the nine rules of inference. Consider the argument: ‘ A ¡ 1 ‘ B • C2 ‘ D ) 1B • A2 ‹ D Before we write anything down, we should look at the argument and think. C is in premise 1, but it’s not in the conclusion. You can’t simplify, since the dot (•) is not the principle connective in the premise. If you distribute, you’ll be able to simplify. You’ll have to get ‘ ‘ D by modus tollens and then double 259 260 Chapter 7 The Method of Deduction negate. So, you’ll need to conclude ‘ 1B • A2 to reach the conclusion. So the proof will look like this: 1. ‘ A ¡ 1 ‘ B • C2 2. ‘ D ) 1B • A2 ‹ D 3. 1 ‘ A ¡ ‘ B2 • 1 ‘ A ¡ C2 4. 1 ‘ A ¡ ‘ B2 5. ‘ 1A • B2 6. ‘ 1B • A2 7. ‘ ‘ D 8. D 1 Dist. 3 Simp. 4 De M. 5 Com. 2,6 M.T. 7 D.N. Now consider this one: 1A • ‘ B2 • C C ) 1D ) B2 ‹ ‘D ¡ E You’ll have to do some commutation and association so you can use the rules of inference. One way to do the proof is as follows: Consider one more: 1. 1A • ‘ B2 • C 2. C ) 1D ) B2 ‹ ‘D ¡ E 3. C • 1A • ‘ B2 4. C 5. D ) B 6. 1 ‘ B • A2 • C 7. ‘ B • 1A • C2 8. ‘ B 9. ‘ D 10. ‘ D ¡ E 1 Com. 3 Simp. 2,4 M.P. 1 Com. 6 Assoc. 7 Simp. 5,8 M.T. 9 Add. U•Q Q ) ‘ 1 ‘ S ¡ R2 S ) 3P ¡ 1T • R24 ‹ P ¡ T The Rule of Replacement (1) Now you do the proof before looking at the way we do it. Did your proof look like this? 1. U • Q 2. Q ) ‘ 1 ‘ S ¡ R2 S ) 3P ¡ 1T • R24 ‹ P ¡ T 4. Q • U 5. Q 6. ‘ 1 ‘ S ¡ R2 7. ‘ ‘ S • ‘ R 8. ‘ ‘ S 9. S 10. P ¡ 1T • R2 11. 1P ¡ T2 • 1P ¡ R2 12. P ¡ T 1 Com. 4 Simp. 2,5 M.P. 6 De M. 7 Simp. 8 D.N. 3,9 M.P. 10 Dist. 11. Simp. If your proof didn’t look like this, did you do the same things but in a different order? You’ll need to commute so that you can simplify and use modus ponens. You’ll need to use De Morgan’s theorem, but you could do that before you do anything else to premise 2. You’ll need to distribute the consequent of premise 3, although you could do that before you do anything else to premise 3. EXERCISES I. Name the equivalence falling under the rule of replacement that allows you to move from the premise to the conclusion. 1. ‘ 3A ¡ 1B • C24 2. A • ‘ 1C ¡ B2 ‘ ‘ ‹ A • 1B • C2 ‹ A • ‘ 1B ¡ C2 3. A • 1 ‘ B ¡ C2 4. 1A • B2 ¡ 1S • P2 ‹ 1A • ‘ B2 ¡ 1A • C2 ‹ 31A • B2 ¡ S4 • 31A • B2 ¡ P4 ‘ ‘ 5. 6. C • ‘ ‘ B 1C • B2 ‹ ‘ 1 ‘ C ¡ ‘ B2 ‹ ‘ ‘B•C 7. C ¡ 3B ) 1 ‘ B K ‘ ‘ G24 8. P • 31Q ¡ R2 • G4 ‹ C ¡ 3B ) 1 ‘ B K G24 ‹ 3P • 1Q ¡ R24 • G 9. P ¡ 51Q ¡ R2 • 31Q • S2 ) ‘ 1 ‘ W ) ‘ ‘ S246 ‹ 3P ¡ 1Q ¡ R24 • 5P ¡ 31Q • S2 ) ‘ 1 ‘ W ) ‘ ‘ S246 10. 3P • 1Q ) S24 ¡ 5Q • 31S ¡ G2 ¡ ‘ S46 ‹ 3P • 1Q ) S24 ¡ 5Q • 3S ¡ 1G ¡ ‘ S246 261 262 Chapter 7 The Method of Deduction II. Each of the following is a formal proof of validity for the indicated argument. State the justification for each numbered line that is not a premise. 11. 1. 1p • q2 ¡ 1r • s2 12. 1. ‘ p ¡ 1q ¡ ‘ r2 2. 31p • q2 ) t4 • 1s ) w2 2. ‘ q ‹ t ¡ w ‹ ‘ 1p • r2 3. 31p • q2 ¡ r4 • 31p • q2 ¡ s4 3. 1 ‘ p ¡ q2 ¡ ‘ r 4. 31p • q2 ¡ s4 • 31p • q2 ¡ r4 4. 1q ¡ ‘ p2 ¡ ‘ r 5. 1p • q2 ¡ s 5. q ¡ 1 ‘ p ¡ ‘ r2 6. t ¡ w 6. ‘ p ¡ ‘ r 7. ‘ 1p • r2 13. 1. ‘ p ¡ 1q ¡ ‘ r2 14. 1. 1r ) s2 • 1p ) q2 2. ‘ ‘ 1p • r2 2. ‘ 1 ‘ p • ‘ r2 ‘ ‘ 3. ‘ q ‹ q ¡ 1t • s2 ‘ ‘ 3. p ¡ 1 r ¡ q2 ‹ s 4. 1 ‘ p ¡ ‘ r2 ¡ q 4. ‘ ‘ 1p ¡ r2 5. ‘ 1p • r2 ¡ q 5. p ¡ r 6. q 6. 1p ) q2 • 1r ) s2 7. q ¡ ‘ 1t • ‘ s2 7. q ¡ s 8. s 15. 1. p ¡ 1q • s2 2. ‘ q 3. p ) s ‹ ‘ ‘s 4. 1p ¡ q2 • 1p ¡ s2 5. p ¡ q 6. q ¡ p 7. p 8. s 9. ‘ ‘ s 17. 1. p ) q 2. 1q • p2 ) 1r ¡ s2 3. ‘ r 4. s ) r ‹ ‘p 5. ‘ s 6. ‘ r • ‘ s 7. ‘ 1r ¡ s2 8. ‘ 1q • p2 9. ‘ 1p • q2 10. p ) 1p • q2 11. ‘ p 16. 1. p ) 1q ¡ r2 2. q ) s 3. ‘ r • ‘ s ‹ ‘p 4. ‘ s • ‘ r 5. ‘ s 6. ‘ q 7. ‘ r 8. ‘ q • ‘ r 9. ‘ 1q ¡ r2 10. ‘ p 18. 1. p ¡ 1q ¡ r2 2. ‘ q 3. ‘ 1 ‘ p • ‘ r2 ) 31s • q2 ¡ 1s • t24 ‹ s • 1q ¡ t2 4. 1p ¡ q2 ¡ r 5. 1q ¡ p2 ¡ r 6. q ¡ 1p ¡ r2 7. p ¡ r 8. ‘ ‘ 1p ¡ r2 9. ‘ 1 ‘ p • ‘ r2 10. 1s • q2 ¡ 1s • t2 11. s • 1q ¡ t2 The Rule of Replacement (1) 19. 1. ‘ p ¡ 1q • ‘ r2 20. 1. ‘ 1p ¡ ‘ q2 ‘ ‘ 2. 1p • r2 ) 3r • 1s ¡ t24 2. q ) 1s ¡ ‘ t2 ‘ 3. ‘ 1 ‘ s • t2 ) 3w ¡ 1y • z24 ‹ 1r • t2 3. 1 ‘ p ¡ q2 • 1 ‘ p ¡ ‘ r2 ‹ w ¡ z 4. 1 ‘ p ¡ ‘ r2 • 1 ‘ p ¡ q2 4. ‘ p • ‘ ‘ q 5. ‘ p ¡ ‘ r 5. ‘ p • q ‘ 6. 1p • r2 6. q • ‘ p ‘ 7. 3r • 1s ¡ t24 7. q 8. ‘ r ¡ ‘ 1s ¡ t2 8. s ¡ ‘ t ‘ ‘ ‘ 9. r ¡ 1 s • t2 9. ‘ ‘ s ¡ ‘ t ‘ ‘ ‘ ‘ 10. 1 r ¡ s2 • 1 r ¡ t2 10. ‘ 1 ‘ s • t2 11. 1 ‘ r ¡ ‘ t2 • 1 ‘ r ¡ ‘ s2 11. w ¡ 1y • z2 12. 1 ‘ r ¡ ‘ t2 12. 1w ¡ y2 • 1w ¡ z2 13. ‘ 1r • t2 13. 1w ¡ z2 • 1w ¡ y2 14. w ¡ z III. For each of the following, adding just two statements to the premises will produce a formal proof of validity. Construct a formal proof of validity for each of the following arguments. 21. A • ‘ B 22. A ) ‘ B B ‹ ‘B ‹ ‘A 23. A ¡ 1B • C2 ‹ A ¡ B 25. E ) 1G ¡ H2 1 ‘ G • ‘ H2 ‹ ‘E 27. 1A ) B2 • 1C ) D2 C ¡ A ‹ B ¡ D 24. A • 1B ¡ C2 ‘ 1A • B2 ‹ A ¡ C 26. 1 ‘ A • ‘ B2 ) ‘ C ‘C ) D ‹ ‘ 1A • B2 ) D 28. A ¡ 1B ¡ C2 ‘ 1A ¡ B2 ‹ C 29. 1A • B2 ) C 30. 3P K 1Q ¡ R24 ‘ 3P K 1Q ¡ R24 ¡ T ‹ 1A • B2 ) 3C • 1A • B24 ‹ T 31. B • 1C • D2 ‹ C • 1D • B2 33. 1E • F2 ) 1G • H2 F•E ‹ G•H 35. 31A ¡ B2 • 1A ¡ C24 ) D A ¡ 1B • C2 ‹ D 32. E ‹ 1E ¡ F2 • 1E ¡ G2 34. 1N • O2 ) P ‹ 1N • O2 ) 3N • 1O • P24 263 264 Chapter 7 The Method of Deduction IV. For each of the following, adding just three statements to the premises will produce a formal proof of validity. Construct a formal proof of validity for each of the following arguments. 36. ‘ 3A ¡ 1B ¡ C24 37. A ¡ ‘ 1B ¡ C2 ‘ ‹ 1B ¡ C2 ‹ A ¡ ‘B 38. M ) 1N • O2 39. 1P ¡ Q2 ¡ R ‘N ‘Q ‘ ‹ M ‹ P ¡ R 40. 1N • O2 ¡ 1N • P2 41. 1N ¡ O2 • 1N ¡ P2 ‘N N)S ‹ S ‹ O ‘ ‘ ‘ ‘ 42. 1 U ¡ P2 43. 1 ‘ U • ‘ P2 ‘U 1U • P2 ) R ‹ R ‹ P ‘ ‘ 44. P ) 1 Q • R2 45. E ¡ 1F • G2 Q ¡ R ‹ E ¡ G ‹ ‘P V. Construct a formal proof of validity for each of the following argument forms. 46. ‘ 1p ¡ q2 47. p • 1q • r2 ‹ ‘q ‹ r 48. p 49. ‘ p ) ‘ q ‘ 1p • q2 q ‘ ‹ q ‹ p 50. p • s ‹ 1s ¡ q2 • 1s ¡ ‘ r2 52. p • 1q • r2 ‹ p•r 54. ‘ p • 3q ¡ 1r • s24 ‹ 1 ‘ p • q2 ¡ 1 ‘ p • s2 56. p ¡ 1q ¡ r2 ‘p• ‘q ‹ r ‘ 58. 3p • 1q ¡ r24 q ‹ ‘p 60. 1p • q2 ¡ 1p • r2 ‘r q)t ‹ 1t ¡ s2 • 1t ¡ w2 51. p ¡ 1q ¡ r2 ‘q ‹ p ¡ r 53. 1p ) q2 • 1r ) s2 p ¡ 1q • r2 ‹ q ¡ s ‘ 55. 31p ¡ q2 ¡ r4 ‹ ‘q 57. 1p ) q2 • 1q ) p2 ‹ 1p ) p2 • 1q ) q2 59. ‘ 3p ¡ 1q • r24 r ‹ ‘q 61. p ¡ ‘ 1q ¡ r2 ‘ 1 ‘ p • q2 ) s s)w ‹ 1s • w2 ¡ 1t • z2 The Rule of Replacement (2) 63. 1p • q2 ¡ 1 ‘ p • ‘ q2 ‹ 1 ‘ p ¡ q2 • 1 ‘ q ¡ p2 62. 1p • q2 ¡ 1p • s2 1s ) w2 • 1q ) m2 a ) ‘ 1m ¡ w2 ‹ ‘a•p 64. 1p • q2 ¡ 1r • s2 s ) 1w • z2 ‘q ‹ z 7.4 65. 1p • q2 ¡ 1p • r2 ‘ 1 ‘ q • ‘ r2 ) t ‘ t ¡ 1x • z2 ‹ 1x ¡ a2 • 1x ¡ z2 THE RULE OF REPLACEMENT (2) To complete our system of propositional logic, we introduce several more equivalences falling under the rule of replacement. R U L E O F R E P L A C E M E N T : A N Y O F T H E F O L L O W I N G L O G I C A L LY E Q U I VA L E N T E X P R E S S I O N S C A N R E P L A C E E A C H O T H E R WHEREVER THEY OCCUR IN A PROOF: NAME ABBREVIATION Transposition Trans. Material Implication Impl. Material Equivalence Equiv. Exportation Exp. Tautology Taut. FORM ‘ 1p ) q2 K 1 q ) ‘ p2 T T ‘ 1p ) q2 K 1 p ¡ q2 T 1p K q2 K 31p ) q2 • 1q ) p24 T 1p K q2 K 31p • q2 ¡ 1 ‘ p • ‘ q24 T 31p • q2 ) r4 K 3p ) 1q ) r24 T p K 1p ¡ p2 T p K 1p • p2 Transposition is for horseshoes what commutation is for dots and wedges, but notice that when statements are flipped around the horseshoe, both statements are negated. Material implication allows you to remove or introduce horseshoes. Material equivalence provides equivalent forms of biconditionals. Since there are no rules of inference that deal directly with biconditionals, these equivalences are needed to work with biconditionals. Exportation is a useful equivalence. Tautology allows you introduce or remove the disjunction or conjunction of a term with itself. This is particularly useful regarding propositions embedded in more complex propositions. We now have a complete system of propositional logic. You can prove the validity of any valid propositional argument. Indeed you can even prove the validity of some of the first nine rules using the other rules and equivalences: 265 266 Chapter 7 The Method of Deduction 1. p ) q 2. p ‹ q 3. ‘ p ¡ q 4. ‘ ‘ p 5. q 1 Impl. 2 D.N. 3,4 D.S. So let’s look at a couple of proofs that involve some of the new equivalences. Consider the argument form: p p K q ‘q ¡ r 1r • s2 ) 1t ¡ t2 ‹ s)t An initial survey of the argument form should convince you that you’ll need to use material equivalence, since it’s the only way to do anything with a biconditional. You’ll probably use tautology, since there is one t in the conclusion, and there is the disjunction t ¡ t in the fourth premise. A conditional with a conjunction as an antecedent suggests that you might use exportation, especially given that s is a conjunct in the antecedent of the fourth premise and s is the antecedent of the conclusion. One way to do the proof is as follows: 1. p 2. p K q 3. ‘ q ¡ r 4. 1r • s2 ) 1t ¡ t2 ‹ s)t 5. 1p ) q2 • 1q ) p2 6. p ) q 7. q 8. q ) r 9. r 10. 1r • s2 ) t 11. r ) 1s ) t2 12. s ) t 2 Equiv. 5 Simp. 6,1 M.P. 3 Impl. 8,7 M.P. 4 Taut 10 Exp. 11,9 M.P. Could you have gotten away without using some of the new equivalences? Yes. You could have avoided using exportation, but it would have been far less convenient. You couldn’t have avoided material equivalence, since it’s the only The Rule of Replacement (2) 267 way to use a biconditional. You couldn’t have avoided tautology. You could have introduced the double negation of q in line 8 and reached r in line 9 by disjunctive syllogism. But, to avoid exportation, you would have had to use implication in line 10. Let’s pick up the proof at line 11 and see what would have been involved in avoiding exportation. 11. ‘ 1r • s2 ¡ t 12. 1 ‘ r ¡ ‘ s2 ¡ t 13. ‘ r ¡ 1 ‘ s ¡ t2 14. ‘ ‘ r 15. ‘ s ¡ t 16. s ) t 4 Impl. 11 De M. 12 Assoc. 9 D.N. 13,14 D.S. 15 Impl. Some of the new equivalences are essential. Others are at least convenient: They provide for more elegant proofs. In section 7.2, we said that elegance makes no logical difference, so why bring it up again? There’s an old saying about not being able to see the forest for the trees. When doing proofs, it works the other way around. You might look at a proof as building a forest one tree (line) at a time. As the forest gets larger, it’s harder to see the individual trees. So, with nine rules of inference plus fifteen distinct equivalences (with ten names) falling under the rule of replacement, it becomes important to think several lines ahead before using one of the equivalences. When there were only the nine rules of inference, you could apply most of them with little thought: There were relatively few patterns. Even after adding De Morgan’s theorems, commutation, association, distribution, and double negation, things were relatively easy. With the equivalences added in this section, the appearance of statements can be far different from what you might expect. For example, p ) q could be “hidden” as ‘ 1p • ‘ q2: 1. p ) q 2. ‘ p ¡ q 3. ‘ p ¡ ‘ ‘ q 4. ‘ 1p • ‘ q2 1 Impl. 2 D.N. 3 De M. So, ask whether using one of the equivalences will either allow you to use one of the nine rules of inference or to change the appearance of a statement to correspond to the form in the conclusion. Think a few lines ahead. If you use the equivalences willy-nilly, there is a good chance that you’ll build a large forest and not be able to see the individual “trees” you might need for your proof. ESSENTIAL HINTS We could construct a complete system of propositional logic using only the tilde and the wedge or the tilde and the dot. The horseshoe is expendable, but it’s terribly convenient. Should you question that, prove hypothetical syllogism without using the rule of hypothetical syllogism. 268 Chapter 7 The Method of Deduction Let’s consider a couple more proofs. You’re given what is sometimes called a destructive dilemma: 1p ) q2 • 1r ) s2 ‘q ¡ ‘s ‹ ‘p ¡ ‘r You can’t prove the conclusion without using at least one of the equivalences we introduced in this section. If you think things through carefully, it’s a fairly short proof. If you don’t, it’s relatively long. 1. 1p ) q2•1r ) s2 2. ‘ q ¡ ‘ s ‹ ‘p ¡ ‘r 3. 1 ‘ q ) ‘ p2•1r ) s2 4. 1 ‘ q ) ‘ p2•1 ‘ s ) ‘ r2 5. ‘ p ¡ ‘ r 1. 1p ) q2•1r ) s2 2. ‘ q ¡ ‘ s ‹ ‘p ¡ ‘r 1 Trans. 3. 1 ‘ p ¡ q2•1r ) s2 1 Impl. 3 Trans. 4. 1q ¡ ‘ p2•1r ) s2 3 Com. ‘ ‘ ‘ 4,2 C.D. 5. 1 q ¡ p2•1r ) s2 4 D.N. ‘ ‘ 6. 1 q ) p2•1r ) s2 5 Impl. 7. 1 ‘ q ) ‘ p2•1 ‘ r ¡ s2 6 Impl. ‘ ‘ ‘ 8. 1 q ) p2•1s ¡ r2 6 Com. ‘ ‘ ‘ ‘ ‘ 9. 1 q ) p2•1 s ¡ r2 8 D.N. 10. 1 ‘ q ) ‘ p2•1 ‘ s ) ‘ r2 9 Impl. ‘ ‘ 11. p ¡ r 10,2 C.D. Or you might have gone about it without using constructive dilemma: 1. 1p ) q2 • 1r ) s2 2. ‘ q ¡ ‘ s ‹ ‘p ¡ ‘r 3. q ) ‘ s 4. p ) q 5. 1r ) s2 • 1p ) q2 6. r ) s 7. p ) ‘ s 8. ‘ s ) ‘ r 9. p ) ‘ r 10. ‘ p ¡ ‘ r 2 Impl. 1 Simp. 1 Com. 5 Simp. 4,3 H.S. 6 Trans. 7,8 H.S. 9 Impl. Each of these proofs is logically valid. The first is more elegant than either of the other two. Does elegance make a difference? Would it make a difference if doing a destructive dilemma were part of a more elaborate argument? The Rule of Replacement (2) Consider the following argument form: ‘ 1p K r2 1p ) q) • 1r ) s2 ‹ ‘q ) s In section 7.1, we mentioned that it is often useful to work backwards from the conclusion for a few lines. Now that we have the equivalences falling under the rule of replacement, “working backwards” often involves looking at logically equivalent forms of the conclusion. If you do so, you’ll notice that the conclusion is logically equivalent to q ¡ s by implication and double negation. Given that the second premise is a conjunction of conditionals in which q is the consequent of one and s is the consequent of the other, you might reasonably guess that you’re going to reach the conclusion by constructive dilemma followed by double negation and implication. The first premise, however, might cause you to take pause. There are two statement forms that are logically equivalent to a biconditional. What do you use? You can use either one, but after you’ve had a bit of experience, you might choose one over the other. 1. ‘ 1p K r2 2. 1p ) q2 • 1r ) s2 ‹ ‘q ) s ‘ 3. 31p ) r2 • 1r ) p24 4. ‘ 1p ) r2 ¡ ‘ 1r ) p2 5. ‘ 1p ) r2 ¡ ‘ 1 ‘ r ¡ p2 6. ‘ 1p ) r2 ¡ 1 ‘ ‘ r • ‘ p2 7. ‘ 1p ) r2 ¡ 1r • ‘ p2 8. 3 ‘ 1p ) r2 ¡ r4 • 3 ‘ 1p ) r2 ¡ p4 9. ‘ 1p ) r2 ¡ r 10. ‘ 1 ‘ p ¡ r2 ¡ r 11. 1 ‘ ‘ p • r2 ¡ r 12. 1p • r2 ¡ r 13. r ¡ 1p • r2 14. 1r ¡ p2 • 1r ¡ r2 15. r ¡ p 16. p ¡ r 17. q ¡ s 18. ‘ ‘ q ¡ s 19. ‘ q ) s 1 Equiv. 4 De M. 4 Imp. 5 De M. 6 D.N. 7 Dist. 8 Simp. 9 Impl. 10 De M. 11 D.N. 12 Com. 13 Dist. 14 Simp. 15 Com. 16 Com. 17 D.N. 18 Impl. 269 270 Chapter 7 The Method of Deduction 1. ‘ 1p K r2 2. 1p ) q2 • 1r ) s2 ‹ ‘q ) s 3. ‘ 31p • r2 ¡ 1 ‘ p • ‘ r24 4. ‘ 1p • r2 • ‘ 1 ‘ p • ‘ r2 5. ‘ 1 ‘ p • ‘ r2 • ‘ 1p • r2 6. ‘ 1 ‘ p • ‘ r2 7. ‘ ‘ 1p ¡ r2 8. p ¡ r 9. q ¡ s 10. ‘ ‘ q ¡ s 11. ‘ q ) s 1 Equiv. 3 De M. 4 Com. 5 Simp. 6 De M. 7 D.N. 2,8 C.D. 9 D.N. 10 Impl. Let’s consider one more: p ) 1q • r2 p• ‘r ‹ s There is something odd here! The conclusion is a simple statement that is not found in the premises! “Surely,” you say, “this argument cannot be valid!” Here it is important to remember the distinction between validity and soundness. Recall that a sound argument is a valid argument with all true premises. Any substitution instance of an argument of the form above will be unsound, for, as we shall see, the premises entail an inconsistent pair of conclusions—a statement and its denial—in this case r and ‘ r. If the premises of a valid deductive argument are inconsistent, any statement follows from the premises. So, s follows. Here’s the proof: 1. p ) 1q • r2 2. p • ‘ r ‹ s 3. p 4. q • r 5. r • p 6. r 7. ‘ r • p 8. ‘ r 9. r ¡ s 10. s 2 Simp. 1,3 M.P. 4 Com. 5 Simp. 2 Com. 7 Simp. 6 Add. 9,8 D.S. The Rule of Replacement (2) If you are given a valid argument with a conclusion consisting of a simple statement that is not found in the premises, the argument form must entail inconsistent conclusions. Your task, then, is to find the inconsistency (both p and ‘ p). Once you’ve done so, you may add the conclusion to one statement (add x to p to obtain p ¡ x) and use the other statement 1 ‘ p2 with the disjunction to reach the conclusion by disjunctive syllogism. Ultimately, you’ll need to do many proofs to master the use of the rules and the equivalences. The following rules of thumb should prove helpful in working though many proofs. Rules of Thumb: Strategies for Doing Deductive Proofs 1. Determine where the simple statements in the conclusion are found in the premises. a. If there is a simple statement in the conclusion that is not found in the premises, you will need to use addition. b. If the conclusion is a simple statement not found in the premises, the premises are inconsistent; that is, both a statement and its denial follow from the premises. In such a case, you’ll need to use a combination of addition and disjunctive syllogism to reach the conclusion. For example, if the conclusion is r and you derive some pair of statements p and ‘ p from the premises, you then add r to p 1p ¡ r2 and use that statement and disjunctive syllogism with ‘ p to reach r.4 c. Look at equivalent forms of the conclusion. 2. Work backwards from the conclusion. a. If you can “see” what steps led to the conclusion, jot them down. If there are alternative routes, you might jot them down, too. b. It is often helpful to work backwards as many steps as you can. 3. If you can use any of the nine rules of inference to break down a compound statement into its simple components, do so. (This is generally helpful, but it is not always necessary.) 4. If you can use any of the nine rules of inference to eliminate a simple statement that is not in the conclusion, use it. 5. If there is a tribar (≡), use the rule of material equivalence; it’s usually the only way you can do anything with the statement. a. If a premise is an affirmative biconditional, you’ll probably want to use the first version of the rule so you can then simplify or commute and simplify to use one of the conditionals. 4If a collection of premises entails both a statement and its denial, the argument is unsound. Reaching inconsistent conclusions by deductions from the premises does not show that the argument is invalid. 271 272 Chapter 7 The Method of Deduction b. If a premise is the denial of a biconditional, you’ll probably want to use the second version of the rule so you can use De Morgan’s theorem and then simplify or commute and simplify. c. If the conclusion is a biconditional of the form p K q, and if you can establish either p • q or ‘ p • ‘ q, you can add the other one and use the second version of the rule to reach the conclusion. 6. If there is a tilde (∼) outside a set of grouping indicators, use De Morgan’s theorem to move the tilde inside, unless you can see how the negated statement can be used with modus tollens or disjunctive syllogism. Sometimes you will have to use other equivalences to change the statement in the parentheses into a conjunction or a disjunction before you can use De Morgan’s theorem. 7. If the premises contain both conditionals and disjunctions, you might consider constructive dilemma. 8. If you find a proposition of the form p ) 1q ) r2, you’ll probably use exportation. If you have both statements of the form p ) 1q ) r2 and p ) q, using exportation on the first and absorption on the second will allow you to conclude a statement of the form p ) r by hypothetical syllogism. 9. Plan ahead before using the equivalences falling under the rule of replacement to avoid extra lines in your proof. 10. Most important: If you believe you can solve all the problems in this book by following these rules of thumb as if there were no exceptions, you will be disappointed. R U L E S O F I N F E R E N C E A N D E Q U I VA L E N C E S The rules of inference and equivalences falling under the rule of replacement are as follows: ELEMENTARY VALID ARGUMENT FORMS: LOGICALLY EQUIVALENT EXPRESSIONS: 1. Modus Ponens (M.P.): p ) q, p, ‹ q 10. De Morgan’s Theorems (De M.): T ‘ ‘ 1p • q2 K 1 p ¡ ‘ q2 T ‘ ‘ 1p ¡ q2 K 1 p • ‘ q2 2. Modus Tollens (M.T.): p ) q, ‘ q, ‹ ‘ p 3. Hypothetical Syllogism (H.S.): p ) q, q ) r, ‹ p ) r 4. Disjunctive Syllogism (D.S.): p ¡ q, ‘ p, ‹ q 11. Commutation (Com.): T 1p ¡ q2 K 1q ¡ p2 T 1p • q2 K 1q • p2 12. Association (Assoc.): T 3p ¡ 1q ¡ r24 K 31p ¡ q2 ¡ r4 T 3p • 1q • r24 K 31p • q2 • r4 13. Distribution (Dist.): T 3p • 1q ¡ r24 K 31p • q2 ¡ 1p • r24 T 3p ¡ 1q • r24 K 31p ¡ q2 • 1p ¡ r24 The Rule of Replacement (2) 5. Constructive Dilemma (C.D.): 1p ) q2 • 1r ) s2, p ¡ r, ‹ q ¡ s 14. Double Negation (D.N.): T ” p K p 7. Simplification (Simp.): p • q, ‹ p 16. Material Implication (Impl.): T ‘ 1p ) q2 K 1 p ¡ q2 6. Absorption (Abs.): p ) q, ‹ p ) 1p • q2 8. Conjunction (Conj.): p, q, ‹ p • q 9. Addition (Add.): p, ‹ p ¡ q 15. Transposition (Trans.): T ‘ 1p ) q2 K 1 q ) ‘ p2 17. Material Equivalence (Equiv.): T 1p K q2 K 31p ) q2 • 1q ) p24 T 1p K q2 K 31p • q2 ¡ 1 ‘ p • ‘ q24 18. Exportation (Exp.): T 3p ) 1q ) r24 K 31p • q2 ) r4 19. Tautology (Taut.): T p K 1p ¡ p2 T p K 1p • p2 EXERCISES I. Which equivalence falling under the rule of replacement justifies the move from the premise to the conclusion in each of the following? 1. p K 1r ¡ s2 ‹ 3p ) 1r ¡ s24 • 31r ¡ s2 ) p4 2. p • 1q ¡ q2 ‹ p•q 3. 1p • q2 ) 1r ¡ s2 ‹ p ) 3q ) 1r ¡ s24 ‘ 4. p ) q ‹ ‘q ) ‘ ‘p 5. 31p • ‘ q2 • 1r ¡ s24 ¡ 3 ‘ 1p • ‘ q2 • ‘ 1r ¡ s24 ‹ 1p • ‘ q2 K 1r ¡ s2 6. ‘ 1p K q2 ) 1r K s2 ‹ ‘ ‘ 1p K q2 ¡ 1r K s2 7. 1p • q2 ) 1r ) s2 ‹ 31p • q2 • r4 ) s 8. p ¡ 1q ¡ r2 ‹ p ¡ 3q ¡ 1r • r24 ‘ 9. 51q • r2 ¡ 3p K 1s K ‘ r246 ) 1z ¡ w2 ‹ ‘ ‘ 51q • r2 ¡ 3p K 1s K ‘ r246 ¡ 1z ¡ w2 273 274 Chapter 7 The Method of Deduction 10. 51q • r2 ¡ 3p K 1s K ‘ r246 ) 1z ¡ w2 ‹ ‘ 1z ¡ w2 ) ‘ 51q • r2 ¡ 3p K 1s K ‘ r246 11. 31 ‘ O ¡ P2 ¡ ‘ Q4 • 3 ‘ O ¡ 1P ¡ ‘ Q24 ‹ 3 ‘ O ¡ 1P ¡ ‘ Q24 • 3 ‘ O ¡ 1P ¡ ‘ Q24 12. 3V ) ‘ 1W ¡ X24 ) 1Y ¡ Z2 ‹ 53V ) ‘ 1W ¡ X24 • 3V ) ‘ 1W ¡ X246 ) 1Y ¡ Z2 13. 31 ‘ A • B2 • 1C ¡ D24 ¡ 3 ‘ 1 ‘ A • B2 • ‘ 1C ¡ D24 ‹ 1 ‘ A • B2 K 1C ¡ D2 14. 3 ‘ E ¡ 1 ‘ ‘ F ) G24 • 3 ‘ E ¡ 1F ) G24 ‹ 3 ‘ E ¡ 1F ) G24 • 3 ‘ E ¡ 1F ) G24 15. 3H • 1I ¡ J24 ¡ 3H • 1K ) ‘ L24 ‹ H • 31I ¡ J2 ¡ 1K ) ‘ L24 II. Each of the following is a formal proof of validity for the indicated argument. State the “justification” for each numbered line that is not a premise. 16. 1. 1D • E2 ) F 17. 1. 1M ¡ N2 ) 1O • P2 2. (D ) F) ) G 2. ‘ O ‹ E)G ‹ ‘M 3. (E • D) ) F 3. ‘ O ¡ ‘ P 4. E ) (D ) F) 4. ‘ 1O • P2 5. E ) G 5. ‘ 1M ¡ N2 6. ‘ M • ‘ N 7. ‘ M 18. 1. T • 1U ¡ V2 19. 1. A ) B 2. T ) 3U ) 1W • X24 2. B ) C 3. 1T • V2 ) ‘ 1W ¡ X2 3. C ) A 4. A ) ‘ C ‹ W K X 4. 1T • U2 ) 1W • X2 ‹ ‘A• ‘C 5. 1T • V2 ) 1 ‘ W • ‘ X2 5. A ) C 6. 31T • U2 ) 1W • X24 • 6. (A ) C) • (C ) A) 7. A K C 31T • V2 ) 1 ‘ W • ‘ X24 7. 1T • U2 ¡ 1T • V2 8. (A • C) ¡ ( ‘ A • ‘ C) 8. 1W • X2 ¡ 1 ‘ W • ‘ X2 9. ‘ A ¡ ‘ C 9. W K X 10. ‘ (A • C) 11. ‘ A • ‘ C ‘ 20. 1. 1D • E2 ) F 2. F ¡ 1G • H2 3. D K E ‹ D)G 4. 1D ) E2 • 1E ) D2 5. D ) E 6. D ) 1D • E2 7. D ) ‘ F 8. 1F ¡ G2 • 1F ¡ H2 The Rule of Replacement (2) 9. F ¡ G 10. ‘ ‘ F ¡ G 11. ‘ F ) G 12. D ) G III. For each of the following, adding just two statements to the premises will produce a formal proof of validity. Construct a formal proof of validity for each of the following arguments. 21. A ‘B ) ‘A ‹ B 23. C 1C • D2 ) E ‹ D)E 25. Q ) 3R ) 1S ) T24 Q ) 1Q • R2 ‹ Q ) 1S ) T2 27. W ) X ‘Y ) ‘X ‹ W)Y 29. F K G ‘ 1F • G2 ‹ ‘F• ‘G 31. 1S • T2 ¡ 1U • V2 ‘S ¡ ‘T ‹ U•V 33. 1A ¡ B2 ) 1C ¡ D2 ‘C• ‘D ‹ ‘ 1A ¡ B2 35. 1M ) N2 • 1 ‘ O ¡ P2 M ¡ O ‹ N ¡ P 37. 1Y ) Z2 • 1Z ) Y2 ‹ 1Y • Z2 ¡ 1 ‘ Y • ‘ Z2 22. B K C ‹ B)C 24. E ) F ‘F ¡ G ‹ E)G 26. 1U • U2 ) ‘ V U ‹ ‘V 28. C ) ‘ D ‘E ) D ‹ C ) ‘ ‘E 30. 1L ) M2 • 1N ) M2 L ¡ N ‹ M 32. 1W • X2 ) Y 1X ) Y2 ) Z ‹ W)Z 34. 3E • 1F • G24 ) H D)E ‹ D ) 31F • G2 ) H4 36. ‘ 31U ) V2 • 1V ) U24 1W K X2 ) 1U K V2 ‹ ‘ 1W K X2 38. 31E ¡ F2 • 1G ¡ H24 ) 1F • I2 1G ¡ H2 • 1E ¡ F2 ‹ F•I 39. 1J • K2 ) 31L • M2 ¡ 1N • O24 40. 3V • 1W ¡ X24 ) 1Y ) Z2 ‘ 1L • M2 • ‘ 1N • O2 ‘ 1Y ) Z2 ¡ 1 ‘ W K A2 ‹ 3V • 1W ¡ X24 ) 1 ‘ W K A2 ‹ ‘ 1J • K2 IV. For each of the following, adding just three statements to the premises will produce a formal proof of validity. Construct a formal proof of validity for each of the following arguments. 41. ‘ B ¡ 1C • D2 ‹ B)C 42. E ¡ 1F • G2 ‹ E ¡ G 275 276 Chapter 7 The Method of Deduction 43. H • 1I • J2 ‹ J • 1I • H2 45. Q ) 1R ) S2 Q)R ‹ Q)S 47. W • 1X ¡ Y2 ‘W ¡ ‘X ‹ W•Y 49. G ) H H)G ‹ 1G • H2 ¡ 1 ‘ G • ‘ H2 44. O ) P P ) ‘P ‹ ‘O 46. T ) U ‘ 1U ¡ V2 ‹ ‘T 48. 1C ¡ D2 ) 1E • F2 D ¡ C ‹ E 50. 1N • O2 ) P 1 ‘ P ) ‘ O2 ) Q ‹ N)Q V. The exercises in this set represent frequently recurring patterns of inference found in longer formal proofs of validity. Familiarity with them will be useful in subsequent work. Construct a formal proof of validity for each of the following arguments. 51. ‘ A 52. C ‹ A)B ‹ D)C 53. E ) 1F ) G2 54. H ) 1I • J2 ‹ F ) 1E ) G2 ‹ H)I 55. K ) L 56. N ) O ‹ 1N • P2 ) O ‹ K ) 1L ¡ M2 57. 1Q ¡ R2 ) S 58. T ) U ‹ Q)S T)V ‹ T ) 1U • V2 59. W ) X 60. Z ) A Y)X Z ¡ A ‹ 1W ¡ Y2 ) X ‹ A VI. To give you more practice with the equivalent statements introduced in this section, construct a proof of validity for each of the following argument forms using only the nine rules of inference plus transposition, material implication, material equivalence, exportation, and tautology. 61. p 62. ‘ p ¡ q ‘p ¡ q ‘q ‹ q ‹ ‘p 63. p K q 64. p K q ‘ 1p • q2 ‘q ‘ ‘ ‹ ‘p• ‘q ‹ p• q 65. 1p ) q2 • 1r ) s2 66. 1p ) q2 • 1r ) q2 ‘q ¡ ‘s p ¡ r ‹ ‘p ¡ ‘r ‹ q ‘ 67. p ) q 68. q ) p ‘ ‘p ‘p ¡ ‘q ‹ 1p • ‘ q2 ¡ 1 ‘ p • ‘ ‘ q2 ‹ ‘ ‘q The Rule of Replacement (2) 69. p ) 1q ¡ ‘ s2 ‹ p ) 3p ) 1 ‘ s ¡ ‘ ‘ q24 71. p K q ‘p ) r ‹ ‘q ) r ‘ p 73. ‘p ) ‘s ‹ ‘ 1 ‘ r ) ‘ q2 ) ‘ s 75. q ) ‘ p p K q ‘ ‘ p ) 1 ‘ q ) r2 ‹ ‘ ‘p ) r 70. p ) 1 ‘ q ) r2 ‘ ‘q ¡ p ‹ ‘r ) ‘ ‘q 72. p ) q p ) 3q ) 1 ‘ r ¡ s24 ‹ 1p • r2 ) s 74. p K q q ) 1r ) s2 ‘s ‹ 1p • r2 ) t VII. Construct a formal proof of validity for each of the following arguments. 76. 1D • ‘ E2 ) F 77. 1G ) ‘ H2 ) I ‘ 1G • H2 ‘ 1E ¡ F2 ‘ ‹ D ‹ I ¡ ‘H 78. R ¡ 1S • ‘ T2 79. 31Y • Z2 ) A4 • 31Y • B2 ) C4 1B ¡ Z2 • Y 1R ¡ S2 ) 1U ¡ ‘ T2 ‹ T)U ‹ A ¡ C ‘ ‘ ‘ 80. 81. M ) N D ) 1 E ) F2 ‘ 1F • ‘ D2 ) ‘ G M ) 1N ) O2 ‹ G)E ‹ M)O 82. T ) 1U • V2 83. ‘ B ¡ 31C ) D2 • 1E ) D24 B • 1C ¡ E2 1U ¡ V2 ) W ‹ T)W ‹ D 84. J ¡ 1 ‘ J • K2 85. 1M ) N2 • 1O ) P2 ‘N ¡ ‘P J)L ‘ 1M • O2 ) Q ‹ 1L • J2 K J ‹ Q VIII. Construct a formal proof of validity for each of the following arguments, in each case using the suggested notation. 86. The oxygen in the tube either combined with the filament to form an oxide or else it vanished completely. The oxygen in the tube could not have vanished completely. Therefore the oxygen in the tube combined with the filament to form an oxide. (C, V) 87. It is not the case that she either forgot or wasn’t able to finish. Therefore she was able to finish. (F, A) 88. She has many friends only if she respects them as individuals. If she respects them as individuals, then she cannot expect them all to behave alike. She has many friends. Therefore she cannot expect them all to behave alike. (F, R, E) 277 278 Chapter 7 The Method of Deduction 89. Napoleon is to be condemned if he usurped power that was not rightfully his own. Either Napoleon was a legitimate monarch or else he usurped power that was not rightfully his own. Napoleon was not a legitimate monarch. So Napoleon is to be condemned. (C, U, L) 90. Had Roman citizenship guaranteed civil liberties, then Roman citizens would have enjoyed religious freedom. Had Roman citizens enjoyed religious freedom, there would have been no persecution of the early Christians. But the early Christians were persecuted. Hence Roman citizenship could not have guaranteed civil liberties. (G, F, P) 91. If the first disjunct of a disjunction is true, the disjunction as a whole is true. Therefore, if both the first and second disjuncts of the disjunction are true, then the disjunction as a whole is true. (F, W, S) 92. Jones will come if she gets the message, provided that she is still interested. Although she didn’t come, she is still interested. Therefore she didn’t get the message. (C, M, I) 93. If the teller or the cashier had pushed the alarm button, the vault would have locked automatically and the police would have arrived within three minutes. Had the police arrived within three minutes, the robbers’ car would have been overtaken. But the robbers’ car was not overtaken. Therefore, the teller did not push the alarm button. (T, C, V, P, O) 94. Although world population is increasing, agricultural production is declining, and manufacturing output remains constant. If agricultural production declines and world population increases, then either new food sources will become available or else there will be a radical redistribution of food resources in the world unless human nutritional requirements diminish. No new food sources will become available, yet neither will family planning be encouraged nor will human nutritional requirements diminish. Therefore there will be a radical redistribution of food resources in the world. (W, A, M, N, R, H, P) 95. Either the robber came in the door, or else the crime was an inside one and one of the servants is implicated. The robber could come in the door only if the latch had been raised from the inside; but one of the servants is surely implicated if the latch was raised from the inside. Therefore one of the servants is implicated. (D, I, S, L) IX. Construct a proof for each of the following arguments. Some of the following arguments might be a bit more challenging than those you’ve constructed above. Generally, they’re at least a bit longer. 96. 1. E ¡ 1B • R2 97. 1. 1M ) T2 • 1 ‘ M ) H2 ‘ 2. 1E ) R2 • 1B ) W2 2. M ¡ 1H K A2 3. W ) ‘ B 3. ‘ T ‘ ‹ A • 1T ) H2 ‹ E ¡ R The Rule of Replacement (2) 98. 1. S K 1T ¡ ‘ B2 2. ‘ 1T • P2 ) 1B ¡ T2 3. ‘ P ‹ S)T 99. 1. 2. 3. 4. 100. 1. 1Q ¡ ‘ P2 ) 1 ‘ P • S2 2. P K ‘ 1R • ‘ S2 ‹ P 101. 1. 2. 3. 102. 1. A ) (G • L) 2. L ) ‘ W 3. W ¡ ( ‘ A • G) ‹ ‘ A • (G ¡ ‘ L) 103. 1. 2. 3. 4. 5. 104. 1. T ¡ (R • K) 2. K ) C 3. (R ¡ K) ) (T ¡ ‘ C) ‹ T ¡ ‘K 105. 1. 2. 3. 1H ¡ C2 • 31R ¡ ‘ D2 ) V4 R ) 1C ) D2 V ) 1H ) T2 ‘T ‹ D ¡ C P ) 3Q ) (R ) S)4 R•P (S ) T) • (T ) ‘ S) ‹ ‘Q A)C (A • C) ) (G ¡ J) (E ¡ D) ) H A ¡ M M)E ‹ J ¡ (G ¡ H) (A ) B) • (C ) D) (A • C) ) (D ) E) ‘E•C ‹ ‘ A • (B ¡ D) X. The five arguments that follow are also valid, and a proof of the validity of each of them is called for. But these proofs will be somewhat more difficult to construct than those in earlier exercises, and students who find themselves stymied from time to time ought not become discouraged. What may appear difficult on first appraisal may come to seem much less difficult with continuing efforts. Familiarity with the rules of inference and the equivalences falling under the rule of replacement, and repeated practice in applying those rules, are the keys to the construction of these proofs. 106. If you study the humanities then you will develop an understanding of people, and if you study the sciences then you will develop an understanding of the world about you. So, if you study either the humanities or the sciences then you will develop an understanding either of people or of the world about you. (H, P, S, W) 107. If you study the humanities then you will develop an understanding of people, and if you study the sciences then you will develop an understanding of the world about you. So, if you study both the humanities and the sciences then you will develop an understanding both of people and of the world about you. (H, P, S, W) 108. If you have free will then your actions are not determined by any antecedent events. If you have free will then, if your actions are not determined by any antecedent events, then your actions 279 280 Chapter 7 The Method of Deduction cannot be predicted. If your actions are not determined by any antecedent events then, if your actions cannot be predicted, then the consequences of your actions cannot be predicted. Therefore, if you have free will then the consequences of your actions cannot be predicted. (F, A, P, C) 109. Socrates was a great philosopher. Therefore, either Socrates was happily married or else he wasn’t. (G, H) 110. If either Socrates was happily married or he wasn’t, then Socrates was a great philosopher. Therefore, Socrates was a great philosopher. (H, G) 7.5 CONDITIONAL PROOF Given the nine rules of inference and the equivalences falling under the rule of replacement, you can construct a proof for any valid argument in propositional logic. Some proofs are long. Sometimes figuring out how the rules and equivalences allow you to justify a claim is anything but obvious—at least one of the authors would claim that even if you wouldn’t. In this section and the next we introduce two additional techniques for constructing proofs. Each involves the assumption of an additional premise. In each, the assumption must be discharged before you can reach the conclusion of the proof. Look at these as additional arrows in your proof quiver. They’re deadly arrows. They’ll allow you to construct proofs that you might find elusive when using only the nine rules and equivalences. Consider a conditional statement. If a statement of the form p ) q is true, what do you know? You know that if the antecedent is true, then the consequent is true. You don’t know that either the antecedent or the consequent is true. This fact about conditional statements is the basis for conditional proofs. To construct a conditional proof, introduce an additional statement as an assumption for conditional proof (A.C.P.), proceed with the proof, and discharge the assumption with a conditional statement in which the assumed statement is the antecedent and the previous line of the proof is the consequent. “Okay,” you say, “so what does that mean?” Consider the following argument: p ) 1q • r2 1r ¡ s2 ) 1s ¡ t2 ‘s ‹ p)t You have constructed proofs for argument forms like this one. There would be a number of implications—De Morgan’s theorem, distributions, simplifications, Conditional Proof and so forth—to reach the conclusion. If you did it by conditional proof, you’d proceed as follows: 1. p ) 1q • r2 2. 1r ¡ s2 ) 1s ¡ t2 3. ‘ s ‹ p)t ƒ 4. p ƒ 5. q • r ƒ 6. r • q ƒ 7. r ƒ 8. r ¡ s ƒ 9. s ¡ t ƒ 10. t 11. p ) t A.C.P. 1,4 M.P. 5 Com. 6 Simp. 7 Add. 2,8 M.P. 9,3 D.S. 4-10 C.P. Here’s the procedure. Introduce an assumption for conditional proof, marking it A.C.P. Indent the line in which you introduce the assumption and show the scope of the assumption by drawing a vertical line along the lines in which the assumption is in force. Use the assumption as an additional premise together with premises that are not under the scope of an assumption that has been discharged. You must discharge the assumption with a conditional statement consisting of the assumption as the antecedent and previous line of proof as the consequent, marking the justification as the lines in which the assumption was in force by conditional proof (C.P.). Notice, this is what was done in the proof above. There are a couple of additional points to notice. (1) You can introduce assumptions within assumptions. We’ll consider such a case below. (2) When there are multiple assumptions, they must be discharged in the reverse of the order in which they were introduced: The last assumption made must be the first assumption that is discharged. (3) Once you have discharged an assumption, no line within the scope of the discharged assumption can be used to justify further lines of the proof. Let’s look at another one: ‘p ¡ s s K 1 ‘ q ¡ r2 ‹ p ) 1q ) r2 This time we’re going to introduce two assumptions and discharge them in the appropriate order. Remember, once you’ve introduced an assumption you can 281 282 Chapter 7 The Method of Deduction use it as an additional premise so long, and only so long, as the assumption is in effect. 1. ‘ p ¡ s 2. s K 1 ‘ q ¡ r2 ‹ p ) 1q ) r2 ƒ 3. p ƒ 4. ‘ ‘ p ƒ 5. s ƒ ƒ 6. q ƒ ƒ 7. 3s ) 1 ‘ q ¡ r24 • 31 ‘ q ¡ r2 ) s4 ƒ ƒ 8. s ) 1 ‘ q ¡ r2 ƒ ƒ 9. ‘ q ¡ r ƒ ƒ 10. ‘ ‘ q ƒ ƒ 11. r ƒ 12. q ) r 13. p ) 1q ) r2 A.C.P. 3 D.N. 1,4 D.S. A.C.P. 2 Equiv. 7 Simp. 8,5 M.P. 6 D.N. 9,10 D.S. 6-11 C.P. 3-12 C.P. Notice that although we played with p and premise 1 before we introduced q as an assumption for conditional proof, we could have just as easily assumed q in line 4. Notice also that although we didn’t deal with premise 2 until after we had introduced the second assumption for conditional proof, we could as easily have included what are lines 7–9 in the argument above before we introduced the second assumption for conditional proof. The argument forms we have looked at so far have both had conditional statements in the conclusion, and we assumed the antecedent and looked for the consequent. The times you’ll be most inclined to do conditional proofs are probably when the conclusion is a conditional. But given the equivalences falling under the rule of replacement, some conditional statement is logically equivalent to any statement. So, you can construct a conditional proof for any argument. Consider the following: p)q q)r p ‹ r Although it’s unlikely that any of you would construct a conditional proof for this argument (you can get the conclusion by two instances of modus ponens, right?), you could do it by conditional proof. What would you want to assume? The conclusion is r. r is logically equivalent to r ¡ r by tautology, which is logically equivalent to ‘ r ) r by material implication. So, assume ‘ r. Conditional Proof 1. p ) q 2. q ) r 3. p ‹ r ƒ 4. ‘ r A.C.P. ‘ ƒ 5. q 2,4 M.T. ƒ 6. q 1,3 M.P. ƒ 7. q ¡ r 6 Add. ƒ 8. r 7,5 D.S. 9. ‘ r ) r 4-8 C.P. 10. r ¡ r 9 Impl. 11. r 10 Taut. In the arguments we have considered so far, we have had no cases of multiple assumptions that did not overlap. Sometimes you’ll discharge one assumption before you introduce another. For example, if the conclusion is a biconditional, you might do two successive conditional proofs. 1. p K q 2. ‘ q ¡ r 3. ‘ 1r • ‘ q2 ‹ r K p ƒ 4. p ƒ 5. 1p ) q2 • 1q ) p2 ƒ 6. p ) q ƒ 7. q ƒ 8. ‘ ‘ q ƒ 9. r 10. p ) r ƒ 11. r ƒ 12. ‘ r ¡ ‘ ‘ q ƒ 13. ‘ r ¡ q ƒ 14. r ) q ƒ 15. q ƒ 16. 1p ) q2 • 1q ) p2 ƒ 17. 1q ) p2 • 1p ) q2 ƒ 18. q ) p ƒ 19. p 20. r ) p 21. 1r ) p2 • 1p ) r2 22. r K p A.C.P. 1 Equiv. 5 Simp. 6,4 M.P. 7 D.N. 2,8 D.S. 4-9 C.P. A.C.P. 3 De M. 12 D.N. 13 Impl. 14,11 M.P. 1 Equiv. 16 Com. 17 Simp. 18,15 M.P. 11-19 C.P. 20,10 Conj. 21 Equiv. 283 284 Chapter 7 The Method of Deduction Notice that lines 5 and 16 are identical. “Couldn’t you just commute line 5 to get what is now line 17?” you ask. No. Once the assumption is discharged, you are not allowed to do anything with the lines governed by the assumption. So, in this problem, if you had used material equivalence on line 1 before you introduced any assumptions for conditional proof, you could have used it anywhere later in the proof. A couple points should be noted before we conclude. First, conditional proofs are sometimes easier than nonconditional proofs, since you devote more energy to breaking down compound statements than you usually do when constructing a regular proof. Second, some people consider conditional proofs easier because you can avoid absorption and often some of the more unusual equivalences. Finally, conditional proofs are often longer than regular proofs. SUMMARY OF CONDITIONAL PROOF 1. Assume a proposition for conditional proof (A.C.P.). 2. Beginning with the line containing the assumption, indent and draw a vertical line to the left of each line in the scope of your assumption. 3. Use the assumption with the earlier lines to draw conclusions. 4. Discharge the assumption by constructing a conditional statement of the form p ) q, where p is the assumption for conditional proof and q is the conclusion reached in the previous line. 5. Assumptions can be made within the scope of other assumptions for conditional proof, but the assumptions must be discharged in the reverse of the order in which they were introduced (last-in-first-out). 6. Remember, conclusions reached within the scope of the assumption for conditional proofs cannot be used to justify conclusions after the assumption has been discharged. EXERCISES Construct a conditional proof for each of the following argument forms. 1. p ¡ q ‘p ‹ r)q 3. p 1p • q2 ) r ‹ ‘r ) ‘q 2. p ) q r•s ‹ p ) 1q • r2 4. p ) 1q • ‘ r2 r ¡ s ‹ p)s Indirect Proof 5. 1p • q2 ) r p)q ‹ 1s • p2 ) r 7. p ) q ‘r ) ‘q ‹ p ) 1p ) r2 9. 3p • 1q ¡ r24 ) s ‘q ) r ‘p ) r ‹ ‘ r ) 1q • s2 11. 1p ) q2 • 1r ) s2 ‹ 1p ¡ r2 ) 1q ¡ s2 13. ‘ 1p • q2 ‘q ) r ‘r ¡ p ‹ r K p 15. p ) 1q • s2 ‘q ¡ s 1q • s2 ) 1r ) t2 ‘t ‹ ‘ p ¡ 1t K r2 17. p ) 31q • r2 ) s4 ‘s p•q ‹ ‘r 19. p K 1q ¡ r2 r 1p • r2 ) 1s ¡ t2 ‘t ‹ s 7.6 6. 1p • q2 ) r ‘r•p ‹ s ) ‘q 8. p • q q ) 1r ¡ s2 ‹ ‘ s ) 1 ‘ s • r2 10. p ) ‘ q q ‘ p ) 1r ) s2 ‹ r ) 1r • s2 12. 1p ) q2 • 1r ) s2 ‹ 1p • r2 ) 1q • s2 14. p ¡ 1 ‘ q • r2 ‘ 3 ‘ p ) 1 ‘ q • s24 ‹ q ) 1 ‘ s ¡ r2 16. 1p ) q2 • r 1p • r2 ) s ‘s ‹ p ) 1q • r2 18. q K 1t ¡ p2 p 1q • p2 ) 1r ¡ s2 ‘s ‹ r 20. q ) 1p • r2 1 ‘ p • ‘ r2 ¡ 1s • t2 s ) ‘t ‹ q ) 1w K x2 INDIRECT PROOF What is known as indirect proof or proof by reductio ad absurdum is a variation on conditional proof. In the last section we noticed that if the conclusion is a simple statement, you could assume the negation of the conclusion as an additional premise. For example, for the argument form 285 286 Chapter 7 The Method of Deduction p)q q)r p ‹ r we assumed ‘ r for conditional proof, proceeded to conclude r from the premises, discharged our assumption for conditional proof as ‘ r ) r, asserted r ¡ r by material implication, and reached r by tautology. Whenever you have a valid argument form, if you assume the denial of the conclusion as an additional premise, you generate an inconsistent set of premises. This fact is the basis for constructing an indirect proof. The rationale is the same as it was for constructing reverse truth tables in 6.6. The procedure for constructing an indirect proof is similar to that for constructing a conditional proof. Introduce the denial of the statement you are attempting to prove as an assumption for indirect proof (A.I.P.). Mark the scope of your assumption by a vertical line, with the lines governed by the assumption indented. Continue until you have shown that a statement and its denial—any statement and its denial—follow from the original premises plus the assumption. Conjoin the statement and its denial and discharge your assumption, stating the denial of your assumption, and justifying it by the lines governed by your assumption and indirect proof (I.P.). For example, if you had assumed ‘ p for indirect proof, you would state the contradiction and discharge the assumption, indicating that p follows by indirect proof and by the lines within the scope of the assumption. The proof would look like this: 1. p ) q 2. q ) r 3. p ‹ r 3. ‘ r ƒ ƒ 4. ‘ q 5. ‘ p ƒ ƒ 6. p • ‘ p 7. r A.I.P. 2,3 M.T. 1,4 M.T. 3,5 Conj. 3-6 I.P. As in the case of conditional proof, there can be an indirect proof within the scope of another indirect proof, and the assumptions must be discharged in the reverse order of their introduction: last-in-first-out. Further, indirect proofs can be used in conjunction with conditional proofs, but the last-in-first-out principle continues to hold: It is permissible to construct an indirect or conditional proof within the scope of another, but they must not overlap. Indirect Proof Consider the following argument form: p ¡ 1q • r2 p)r ‹ r If you construct an indirect proof, you assume ‘ r as an additional premise and proceed until you reach a contradiction. Then you discharge the assumption. Either of the following would be correct. Notice: it makes no difference which statement and its denial you use to generate the contradiction. 1. p ¡ 1q • r2 2. p ) r ‹ r ƒ 3. ‘ r ƒ 4. ‘ p ƒ 5. q • r ƒ 6. r • q ƒ 7. r ƒ 8. r • ‘ r 9. r A.I.P. 2,3 M.T. 1,4 D.S. 5 Com. 6 Simp. 7,3 Conj. 3-8 I.P. 1. p ¡ 1q • r2 2. p ) r ‹ r ƒ 3. ‘ r ƒ 4. ‘ p ƒ 5. ‘ ‘ p ¡ 1q • r2 ƒ 6. ‘ p ) 1q • r2 ƒ 7. ‘ r ¡ ‘ q ƒ 8. ‘ q ¡ ‘ r ƒ 9. ‘ 1q • r2 ƒ 10. ‘ ‘ p ƒ 11. ‘ p • ‘ ‘ p 12. r A.I.P. 2,3 M.T. 1 D.N. 5 Impl. 3 Add. 6 Com. 7 De M. 6,9 M.T. 4,10 Conj. 3-11 I.P. Notice what you’re doing. You assume the denial of the conclusion as an additional premise. Then you use modus ponens, modus tollens, hypothetical syllogism, disjunctive syllogism, constructive dilemma, and simplification to break compound statements down into their simple components. Once you find a statement and its denial, you conjoin them and discharge the assumption. Although you can always break compound statements down to their simpler components when searching for a contradiction, it is equally acceptable to find a compound statement and its denial. If you have a conclusion that is a conditional statement, you can use conditional and indirect proof in tandem. Assume the antecedent of the conclusion for conditional proof. Next, assume the denial of the consequent for indirect proof. Proceed until you reach a contradiction. Discharge the assumption 287 288 Chapter 7 The Method of Deduction for indirect proof, and, in the next line, discharge the assumption for conditional proof. Applying this to hypothetical syllogism would look like this: 1. p ) q 2. q ) r ‹ p)r ƒ 3. p ƒ ƒ 4. ‘ r ƒ ƒ 5. q ƒ ƒ 6. ‘ q ƒ ƒ 7. q • ‘ q ƒ 8. r 9. p ) r A.C.P. A.I.P. 1,3 M.P. 2,4 M.T. 5,6 Conj. 4-7 I.P. 3-8 C.P. As with conditional proof, once you have discharged an assumption, you cannot use any of the lines governed by the assumption in subsequent lines of the proof. So, it is often wise to think a few lines ahead to avoid the need to duplicate lines that would be used in more than one assumption. While you will most often use indirect or conditional proof with respect to the conclusion of an argument, you can use it regarding any statement. Remember, however, you will be able to draw conclusions that follow with validity from the augmented set of premises. So, if you assume ‘ p for indirect proof with an eye to conclude p, you will be able to conclude p only if the set of premises augmented by ‘ p is inconsistent. A practical consequence of this is that if the conclusion of an argument is a disjunction, for example, p ¡ q, you should assume the denial of the disjunction for indirect proof. Why? You know that either p or q is entailed by the premises, but you don’t know which is entailed. If you assumed only ‘ p for indirect proof, you might never reach a contradiction. Sometimes indirect or conditional proofs are shorter than their direct counterparts. Usually they’re longer, but many students find them easier since more effort is used in breaking compound statements into their simpler components than in using the various equivalences. SUMMARY OF INDIRECT PROOF 1. Assume the denial of the proposition you wish to prove (A.I.P.). 2. Beginning with the line containing the assumption, indent and draw a vertical line to the left of each line in the scope of your assumption. 3. Use the assumption with earlier lines in the proof to draw conclusions. 4. When you have derived some statement p and its denial, ‘ p, conjoin them and discharge your assumption by stating the proposition you wish to prove (the denial of your assumption for indirect proof). Indirect Proof 5. Assumptions for indirect proof may be made within the scope of other assumptions for indirect or conditional proof, but the assumptions must be discharged in the reverse of the order in which they were made (lastin-first-out). 6. Remember: Conclusions reached within the scope of an assumption for indirect proof cannot be used to justify conclusions after the assumption has been discharged. A FEW MORE RULES OF THUMB 1. If the conclusion is a conditional, start by assuming the antecedent of the conclusion for conditional proof (A.C.P.) and then assume the denial of the consequent for indirect proof (A.I.P.). This will allow you to establish the consequent by indirect proof and then obtain the conclusion a line later by conditional proof. 2. Use M.P., M.T., D.S., H.S., and Simp. to break down complex statements as far as possible. 3. Since it is generally helpful to break complex statements down into simpler components, if the conclusion is a disjunction, try proceeding by indirect proof. 4. Since it is generally helpful to break complex statements down into simpler components when using either conditional or indirect proof, it is wise to break premises down as far as possible before making any assumptions for conditional or indirect proof. EXERCISES I. Construct an indirect proof for each of the following argument forms. 1. p 2. h ‹ q ¡ ‘q h ) 1m ¡ a2 a ) ‘p p ‹ m 3. m ) g 4. p ) q g)a q ¡ r a)p p ¡ ‘r p)i ‹ q m ‹ i 5. ‘ p ) 1o • g2 6. p ¡ f g K p p ) 1n ¡ b2 ‹ o)p f)a ‘a• ‘b ‹ n 289 290 Chapter 7 The Method of Deduction 7. p ) 3 ‘ q ¡ 1r • s24 ‘s•q ‹ ‘p 8. a ) b ‘ 1d • ‘ c2 a ¡ 1 ‘ c • e2 ‹ b ¡ ‘d 10. s ) w s K 1b • y2 ‘w ) b ‹ w ¡ ‘y 9. m ) g g ) 1c ¡ h2 h)d ‘d c)a ‹ ‘m ¡ a II. Construct an indirect or conditional proof for each of the following. You may use both, if you wish. 11. 1m • f2 ) 1a ¡ ‘ c2 12. ‘ f ) 1j ) p2 g)c p ) 1 ‘ a ¡ m2 ‘f ) j ‹ 1 ‘ f • j2 ) 1a ) m2 ‘a•g ‹ ‘m ¡ j 13. p ) 1 ‘ q • r2 14. 1s • w2 ¡ 1b • ‘ y2 1s ) b2 • 1w ) ‘ y2 1q ¡ ‘ r2 ) s ‘s ¡ p ‹ ‘y ‘ ‹ q 15. n K 1h ¡ s2 16. p ) 1q ¡ r2 ‘r ) s h ) 1b • m2 ‘s ¡ p s)e ‘e•n ‹ q ¡ r ‹ b•m 17. a ¡ 3g • 1 ‘ d • ‘ e24 18. 1p • ‘ q2 ) 1r ) s2 p• ‘s g K e ‹ ‘ a ) ‘ 1d • ‘ e2 ‹ ‘q ) ‘r 19. 1h • m2 ) 1k • b2 20. p • 1q ¡ ‘ r2 1p • ‘ r2 ) s 1k ¡ b2 ) 1f ¡ s2 ‘ h• s 1 ‘ s ¡ ‘ q2 ) r ‹ m)f ‹ q ¡ 1t • ‘ s2 ‘ 21. a ) 1b • c2 22. p ) q ‘a K b 1p • q2 ) r 1p • r2 ) s ‹ a)d ‹ p)s 23. 3w • 1c ¡ g24 ) 3g K 1o ) r24 24. p K 1q ¡ ‘ r2 ‘p• ‘s g g ) 1 ‘ r • w2 ‹ q K s ‹ ‘g ¡ ‘o 25. ‘ 3p K 1q ¡ ‘ r24 p• ‘s ‹ q K s Indirect Proof III. Construct an indirect or conditional proof for each of the following. 26. If Iowa Smith is the state’s chief barber shop investigator and the Temple of Groom is the largest barber shop in the state, then either Smith is investigating illegal sales to a hair shirt company or he is investigating the use of illegal hair tonics. If Smith is investigating illegal sales to a hair shirt company, then the boys at St. Mort’s Monastery will lose their shirts. If Smith is investigating the use of illegal hair tonics, then Baldilocks McCann has a hand in the affair. The boys at St. Mort’s Monastery will not lose their shirts, and although Smith will find tainted moustache wax, Baldilocks McCann does not have a hand in the affair. Iowa Smith is the state’s chief barber shop investigator. Therefore, the Temple of Groom is not the largest barber shop in the state. (I, T, S, H, M, B, W) 27. If Iowa Smith is investigating the Temple of Groom, then Baldilocks McCann has been spiking the hair tonic and Four Fingers O’Brien has his fingers in the till. If Four Fingers O’Brien has his fingers in the till, then he might lose another finger; and either Hannibal the cat has been drinking hair tonic or Milo the Kidder has not been telling bad jokes. If the fact that Milo the Kidder has been telling bad jokes implies that Four Fingers O’Brien has his fingers in the till, then Smith is in for the greatest adventure of his life. Iowa Smith is investigating the Temple of Groom. So, Smith is in for the greatest adventure of his life. (I, B, F, L, H, M, S) 28. Either the Temple of Groom is a front for hair smugglers, or business is going along at a good clip. If business is going along at a good clip, then Baldilocks McCann is a master barber. If Baldilocks McCann is a master barber, then Four Fingers O’Brien keeps a chair at St. Mort’s and Milo the Kidder has lost his joke book even though Iowa Smith will not investigate the joint. But Iowa Smith will investigate the joint. So the Temple of Groom is a front for hair smugglers. (T, B, M, O, K, I) 29. Either Iowa Smith will investigate the Temple of Groom or Baldilocks McCann has developed a new hair grower, just in case Hannibal the cat has been used as a guinea pig. If Hannibal the cat has been used as a guinea pig, then the Society for the Prevention of Cruelty to Animals will be called in and Feline Alcoholics Anonymous will be concerned. If Feline Alcoholics Anonymous is concerned, then Four Fingers O’Brien has spiked the catnip. Iowa Smith will investigate the Temple of Groom. So Four Fingers O’Brien has spiked the catnip. (I, B, H, S, F, O) 30. If the Temple of Groom is a front for a smuggling operation, then Baldilocks McCann is the ringleader. If the Temple of Groom is the front for a smuggling operation and Baldilocks McCann is the 291 292 Chapter 7 The Method of Deduction ringleader, then Four Fingers O’Brien will be implicated and Daphne Divine will need to find a different place to have her legs shaved. If Four Fingers O’Brien is implicated, then the boys at St. Mort’s Monastery will need to find a new barber; and if the boys at St. Mort’s Monastery will need to find a new barber, then Brother Boris will go to barber school. So if the Temple of Groom is the front for a smuggling operation, then Brother Boris will go to barber school unless Iowa Smith investigates. (T, M, O, D, S, B, I) 31. If Iowa Smith investigates the Temple of Groom but Virginia Johnson does not join in the investigation, then Baldilocks McCann will not be implicated or Milo the Kidder is calling the shots. If Milo the Kidder is calling the shots, then Virginia Johnson joins in the investigation. If Virginia Johnson joins in the investigation, then Lefty McLane is cutting more than hair and Hannibal the cat is going bald. So, if Lefty McLane is cutting more than hair and Milo the Kidder is calling the shots, then Virginia Johnson joins in the investigation. (I, V, B, M, L, H) 32. If Iowa Smith investigates the Temple of Groom and Virginia Johnson joins in the investigation, then if Four Fingers O’Brien is making moonshine in the back room, then Hannibal the cat has discovered the still. If Feline Alcoholics Anonymous enters the case, then Hannibal the cat has discovered the still. If Feline Alcoholics Anonymous enters the case, then either Lefty McLane is an undercover investigator or Milo the Kidder considers the whole affair a big joke. Milo the Kidder does not consider the whole affair a big joke, and both Iowa Smith investigates the Temple of Groom and Feline Alcholics Anonymous enters the case. So either Hannibal the cat has discovered the still or Lefty McLane is not an undercover investigator. (I, V, O, H, F, L, M) 33. If Baldilocks McCann is running a numbers racket, or Four Fingers O’Brien is making moonshine in the back room or Lefty McLane is bribing a judge, then the Temple of Groom is the front for illegal activities. Lefty McLane is not bribing a judge, just in case the Temple of Groom is a front for illegal activities and Iowa Smith investigates the joint. If Iowa Smith investigates the joint, then it is not the case that both Baldilocks McCann is running a numbers racket and Lefty McLane is bribing a judge. The Temple of Groom is not a front for illegal activities. So Iowa Smith investigates the joint and Virginia Johnson finds the entire case puzzling. (B, F, L, T, I, V) 34. If Lefty McLane is making moonshine and either Baldilocks McCann or Four Fingers O’Brien is a Treasury agent, then Smith’s investigation will be foiled. If Smith’s investigation is foiled, then Virginia Johnson will have the last laugh; and if Virginia Johnson Essentials of Chapter 7 has the last laugh then the Governor will stop all investigations of barber shops. Lefty McLane is making moonshine and either Iowa Smith investigates the Temple of Groom or the Governor will not stop all investigations of barber shops. So if Baldilocks McCann is a Treasury agent, Iowa Smith will investigate the Temple of Groom. (L, B, F, S, V, G, I) 35. If both Baldilocks McCann and Four Fingers O’Brien are Treasury agents, then Iowa Smith will be convicted of tax evasion and Virginia Johnson will visit Smith in prison. Four Fingers O’Brien is not a Treasury agent, just in case either the Temple of Groom is a front for a federal investigation or Iowa Smith will be convicted of tax evasion. Baldilocks McCann is a Treasury agent. If Baldilocks McCann is a Treasury agent, then Milo the Kidder is a federal agent; and if Milo the Kidder is a federal agent, then Virginia Johnson will visit Smith in prison. If Iowa Smith will not be convicted of tax evasion, then Lefty McLane is not a federal agent; and if the Temple of Groom is the front for a federal investigation, then Lefty McLane is a federal agent. So Iowa Smith will be convicted of tax evasion. (B, F, I, V, T, M, L) ESSENTIALS OF CHAPTER 7 In this chapter we introduced and explained the method of deduction. In section 7.2, we defined a formal proof of validity for any given argument as: a sequence of statements each of which is either a premise of that argument or follows from preceding statements of the sequence by an elementary valid argument, where the last statement of the sequence is the conclusion of the argument whose validity is being proved. We defined an elementary valid argument to be any argument that is a substitution instance of an elementary valid argument form. We listed nine elementary valid argument forms to be used in constructing formal proofs of validity. The nine rules of inference can be used only on a whole line or two lines of a proof. In sections 7.3 and 7.4, we strengthened the machinery for constructing formal proofs of validity by introducing the Rule of Replacement, which permits us to infer from any statement the result of replacing any component of that statement by any other statement logically equivalent to the component replaced. We introduced fifteen logically equivalent forms (under ten names) that can be substituted for each other wherever they occur in a proof. In section 7.5 we introduced the method of conditional proof. When constructing a conditional proof, you assume a statement as an additional premise, use that statement with the other premises, and discharge the assumption by a conditional statement in which the assumption is the antecedent and the previous line of the proof is the consequent. 293 294 Chapter 7 The Method of Deduction In section 7.6 we introduced indirect proof. Indirect proof is a variation on conditional proof. When constructing an indirect proof, you assume the denial of what you want to establish as an additional premise, use that statement with the other premises until you conclude both a statement and its denial— any statement and its denial. You conjoin the statement and its denial and discharge your assumption by stating the denial of the statement you assumed, that is, the statement you originally wished to prove. C H A P T E R S I X SYMBOLIC LOGIC 6.1 THE SYMBOLIC LANGUAGE OF MODERN LOGIC The theory of deduction provides techniques for the analysis and appraisal of deductive arguments. We have already looked at classical or Aristotelian logic in the previous three chapters. Now, in Chapter 6 through 8, we turn to modern symbolic logic. Developed primarily within the past century, symbolic logic rests upon an artificial language that was developed to represent statement forms and argument forms. Why should we develop a symbolic language? It is extremely convenient for our purposes. When focusing on deduction, the issue with which we are concerned is validity. Validity is a property of the form of an argument. The content makes no difference. The artificial language we develop does nothing but represent statement forms and argument forms. Hence, it is useful for examining deductive arguments. It allows us “see” relationships that are concealed by the words. As one of the greatest modern logicians noted, “By the aid of symbols we can make transitions in reasoning almost mechanically by the eye, which otherwise would call into play the higher faculties of the brain.”1 The arguments with which we are concerned in this chapter and the next are based on the relations among propositions. We’ll be concerned with what is known as propositional logic or sentential logic. The propositions with which we are concerned are known as truth-functional propositions. Every proposition is either true or false. The truth or falsity of a proposition is called its truth-value. A proposition such as “Jamal plays football” may be called a simple proposition or a simple statement. Any statement that contains a simple statement as a proper part is a compound statement. So, the statements, “Jamal plays football and Solvig plays harp,” and, “Dana believes that Tristan’s favorite musical group is U2,” are compound statements. Some compound statements are truthfunctional compound statements. A statement is a truth-functional compound statement if and only if the truth of the compound statement is determined solely by the truth-values of its component propositions. The statement, “Jamal 1Alfred North Whitehead, An Introduction to Mathematics, 1911. 191 192 Chapter 6 Symbolic Logic plays football and Solvig plays harp,” is truth-functionally compound. As we’ll see in the next section, the statement is true if and only if it is true that Jamal plays football and it is true that Solvig plays harp. The statement, “Dana believes that Tristan’s favorite musical group is U2,” contains the statement, “Tristan’s favorite musical group is U2,” but it is not a truth-functionally compound statement. The truth value of the component statement is irrelevant to the truth value of the whole. It might be true that Dana believes Tristan’s favorite group is U2 even if his favorite group is Chicago. In a non-truthfunctional compound statement, the truth of the statement does not depend upon the truth of the component propositions. The propositional arguments we examine in this chapter and the next are arguments composed solely on truth-functional compound propositions. Such arguments are far more common in everyday life than categorical syllogisms. In later sections we examine techniques for determining whether an argument composed solely of truth-functional compound propositions is valid. 6.2 SYMBOLESE 101: THE LANGUAGE OF PROPOSITIONAL LOGIC Artificial languages are developed with particular purposes in mind. In our case, we want to represent arguments in propositional logic and their forms. If you think about ordinary compound declarative sentences that express propositions, you’ll notice that they have three elements. (1) There are the individual simple statements of which they are composed. (2) There are the words that hook those simple sentences together, words such as and, or, although, if . . . then, and so forth. (3) There are punctuation marks that allow us to group sentences together and thereby understand what is being said. So, we need each of these in our artificial language. When dealing with categorical syllogisms we abbreviated terms to a single letter. So, the categorical proposition, “All aardvarks are beautiful animals,” might have been represented by “All A are B.” Let’s do something similar here and abbreviate specific statements to single uppercase letters. “Jamal plays football” might be abbreviated J. “Solvig plays harp” might be abbreviated S. “Tristan’s favorite musical group is Chicago” might be abbreviated T. We’ll use the uppercase letters A, B, C, Á Z as abbreviations for statements. When dealing with categorical syllogisms, we used the letters S, P, and M to represent the three terms of a syllogism. This allowed us to provide a schematic representation of a categorical syllogism of any form. S, P, and M were variables. Replacing them by actual terms resulted in a determinate categorical syllogism. We want to do something similar regarding arguments in propositional logic since we want to be able to represent the form of a statement or argument independent of any content. So, let’s let the lowercase letters p, q, r, Á z be variables that can be replaced by statements of any degree Symbolese 101: The Language of Propositional Logic of complexity. So, “If p, then q” represents a statement form. By replacing the variables with statements, you obtain statements of that form. So, “If Tristan drives a bus, then Angela is an artist” is an instance of “If p, then q.” “If the economy booms and the stock market rises rapidly, then either I’ll be able to retire early or I’ll be able to buy a bigger house” is also an instance of “If p, then q.” We introduce symbols to represent linguistic particles, those pieces of linguistic glue that hold two or more simple statements together to form compound statements—words such as not, and, or, if . . . then . . . , and if and only if. We do this by way of truth tables. A truth table shows all possible combinations of truth values for a simple statement or statements. Since any proposition is either true or false, the truth table for one simple statement will have two rows. Let’s abbreviate the statement “Today it is sunny” as S. The truth table for S would be: S T F We can also construct truth tables for variables. The truth tables for one variable, p, and for two variables, p and q, are as follows: p T F p q T T T F F T F F We use these combinations of truth values to define our propositional connectives. The connectives mean exactly what the truth tables for them say they mean; that is, they are true or false only under the conditions stated in the truth tables. This means the correlation between the symbols and the English words that are translated as the symbols is sometimes imperfect. A. Negation Every proposition is true or false. Any proposition that is not true is false, and vice versa. The negation or denial of a true statement is a false statement. 193 194 Chapter 6 Symbolic Logic The negation or denial of a false statement is a true statement. Let us represent negation by the tilde (∼).2 So, the truth table defining the tilde is as follows: p ‘p T F F T The proper reading of “ ‘ p” is “tilde p.” The tilde is a symbolic translation of the English expressions not and it is not the case that. So, some people tend to read “ ‘ p” as “not p,” even though that’s like reading, “Der Vogelfänger bin ich ja,” as “I am the bird catcher”: it’s a case of reading the translation into the symbol. B. Conjunction A conjunction of two state…
Purchase answer to see full attachment