Logic 15 Implication a - Grade A+ PDF

Preview

Summary

Grade A+...

Description

NATURAL DEDUCTION: THE RULES OF IMPLICATION 1 Natural deduction is a method for proving the validity of arguments in propositional logic. It has two major advantages over truth tables: 1. It is often much quicker and easier to use. An argument with three premises made up of five simple statements might take only 10 lines to prove using natural deduction (with each line being relatively short), while doing a truth table for this argument might require 32 (very long) lines. 2. Doing a proof in natural deduction helps us understand why an argument is valid. It does this by showing us how the validity of argument follows from the validity of simpler arguments, such as modus ponens, modus tollens, hypothetical syllogism, and so on. The system of natural deduction we are learning will eventually have 18 rules of inference, which are the simple arguments will we use as our “starting points.” These consist of both “rules of implication” and “rules of replacement.” HOW TO START A NATURAL DEDUCTIVE PROOF In order to start a natural deductive proof, you begin by putting each premise on a separate line, and numbering them sequentially. Then, to the right of the last premise, you should write a “/” followed by the conclusion. For example, consider the argument “If the apple was ripe, I ate it. I did not eat the apple. So, the apple was not ripe.” We could let R = “The apple is ripe” and E = “I ate the apple.” We would start our natural deductive proof as follows: 1. R ⊃ E (This is the first premise.) 2. ~E / ~R (~E is the second premise. ~R is the conclusion—this is what we are trying to “get to”) 3. (You’ll need to add more lines here!) 4. … 5. ~R (This is the last line, which should always be the conclusion. You’ve shown the argument is valid!) In the course of the natural deductive proof, we will add more lines (3, 4, 5, etc.). In order to add a line, however, we must cite a rule of inference. In this example, line 3, 4, and 5 would all need to have rules written on the right. The proof is finished when you have arrive at a line that exactly matches the conclusion. In this case, we want to get to a line that says “~R.” RULES OF IMPLIC ATION: THE FIRST FOUR A rule of implication is a simple, valid argument form. In order to use the rule, you must find lines that have the same form as the premises. This allows you to write down a line that has the same form as the conclusion. I’ve provided simple example proofs (each requires only one step) below. Name

Disjunctiv e Syllogism

Abbr eviati on DS

Hypotheti cal Syllogism

HS

Modus Ponens

MP

Modus Tollens

MT

Form

Sample Proof 1

p∨ q p ∴q p⊃ q q⊃r ∴ p⊃r p⊃ q p ∴q

1. ~A 2. A ∨ B / B 3. B 2,1 DS

p⊃ q q

1. ~C 2. (A ≡ B) ⊃ C B)

1. A ⊃ (B ∙ C) 2. (B ∙ C) ⊃ D 3. A ⊃ D

Sample Proof 2

1. ~(A ∨ B) 2. (A ∨ B) ∨ C 3. C /A⊃D 1,2 HS

1. A ≡ B 2. (A ≡ B) ⊃ C / C 3. C 2,1 MP

/ ~(A ≡

/C 1,2 DS

1. C ⊃ (D ∙ E) 2. (A ∙ B) ⊃ C /(A∙B) ⊃ (D∙E) 3. (A ∙ B) ⊃ (D ∙ E) 2,1 HS 1. (A ∙ D) 2. (A ∙ D) ⊃ (A ∨ D) /A ∨ D 3. A ∨ D 2,1 MP 1. ~(A ∨ D) 2. (A ∙ D) ⊃ (A ∨ D) D)

/~(A ∙

3. ~(A ≡ B)

∴ p

2,1 MT

3. ~(A ∙ D)

2,1 MT

Some basic rules to remember: 1. A premise that you are given does NOT need a rule. Every other line does. 2. Look for the form—the rules of inference apply to any lines that have the relevant form, no matter how complex they look. 3. Natural deductive proofs only work for valid arguments! If you try to prove the validity of invalid argument, the proof will never end (that’s what makes being a logician so tough!). STRATEGIES FOR MORE COMPLEX PROOFS Most of the proofs you will be doing require more than one line to complete. In order to successfully use the first four rules, it’s helpful to have a strategy (applying these strategies will become much easier with practice): 1. Start by looking at the conclusion and work backwards. Your goal is get to the conclusion. So, look to see what other lines contain the same letters as the conclusion, and try to think “What rules would allow me to get that letter by itself?” In longer proofs, it sometimes helps to think of your proof in terms of “stages,” each with its own “conclusion”—“first, I want to get to subconclusion 1. Next, I’ll try to get to subconclusion 2. Then, I’ll be able to prove the real conclusion.” 2. If the conclusion contains a letter that appears in the consequent of a conditional statement in the premises, see if you can use modus ponens. Modus ponens isolates the consequent (the second part) of conditional statements. See example 1. 3. If the conclusion contains a letter that appears in the antecedent of a conditional statement in the premises, see if you can use modus tollens. Modus tollens isolates the antecedent (the first part) of conditional statements. See example 1. Remember to add a “~” when using this rule! 4. If the conclusion is a conditional statement AND there are conditional statements in the premises, see if you can use hypothetical syllogism. Hypothetical syllogism allows you to create a new conditional statements from two other conditional statements. See example 2. 5. If the conclusion contains a letter that appears as a disjunct (part of an “or” statement) in the premises, consider using disjunctive syllogism. Disjunctive syllogism allows you to get out one of the disjunctions. See example 2. Example 1: Suppose we want to prove the validity of the argument ~A ⊃ B / ~B / ~~A ⊃ C // C. Here’s one way the proof might go: 1. 2. 3. 4.

~A ⊃ B ~B ~~A ⊃ C /C ~~A 1, 2 MT plus a “~”) 5. C 3, 4 MP

(Premise – No rule needed) (Premise – No rule needed) (Premise / Conclusion – No rule needed) (We can use MT to get the antecedent of the conditional on line 1, (We can use MP to get the consequent of the conditional on line 3)

Example 2: “Daniel is not at the party. Moreover, if Anne is not at the party, then Billy is, and if Cathy is not at the party, the neither is Annie. Finally, either Daniel is at the party or Cathy is not there. We can conclude Billy is at the party.” 1. 2. 3. 4.

~D Daniel is not at the party. (Premise) ~A ⊃ B If Annie is not at the party, then Billy is at the party. (Premise) ~C ⊃ ~A If Cathy is not at the party, then Annie is not at the party. (Premise) D ∨ ~C /B Either Daniel is at the party or Cathy isn’t (premise). So, Billy is at the party (conclusion). 5. ~C ⊃ B 2, 3 HS If Cathy is not at the party, then Billy is at the party. 6. ~C 1, 4 DS Cathy is not at the party. 7. B 5, 6 MP So, Billy is at the party. REVIEW QUESTIONS The following proofs have already been completed. Identify which rules (and line numbers) were used to produce each line.

Proof 1: 1. 2. 3. 4. 5. 6. 7. 8.

R ⊃ (G ∨ ~A) (G ∨ ~A) ⊃ ~S G⊃S R G ∨ ~A ~S ~G ~A

/~A

(Premise) (Premise) (Premise) (Premise/Conclusion) 1,4 MP (Sample—you do the rest!)

Proof 2: 1. N ⊃ (J ⊃ P) 2. (J ⊃ P) ⊃ (N ⊃ J) 3. N 4. 5. 6. 7.

J⊃P N⊃J N⊃P P

/P

(Premise) (Premise) (Premise/Conclusion) 1,3 MP (Sample—you do the rest!)...