Proofs In Propositional Logic

PHIL 100 Proofs (download) Page 1 of 11 PROOFS IN PROPOSITIONAL LOGIC In propositional logic, a proof system is a set of rules for constructing proofs. In our technical vocabulary, a proof is a series of sentences, each of which is a premise or is justified by applying one of the rules in the system to earlier sentences in the series. A sentence justified in this way is said to be derived from the premises. The rules are designed with a very important limitation: they will only allow you to derive a conclusion from a group of premises if the argument is deductively valid – that is, if it is not possible for there to be a situation where the premises would all true be true yet the conclusion would be false. It is this limitation that makes it legitimate for us to call the series of sentences a proof. Ordinarily, to convince someone of a conclusion, given certain premises, you would try to show in clear, simple steps how the premises lead to that conclusion. The most common types of proof systems, natural deduction systems, for the most part work in that way. Each rule lets you add a sentence that must be true, given that certain sentences earlier in the proof are true. We will use this kind of system. Its rules let us break apart sentences containing the propositional operators (connectives) we saw in truth tables, and use those operators to combine sentences to form more complex sentences. Rules of the first kind are Elim (short for ‘elimination’) rules; rules of the second kind are Intro (short for ‘introduction’) rules. We also have a special rule, Reit (short for ‘reiteration’, another word for ‘repetition’) because it is sometimes useful to repeat a sentence we already have. These basic rules are sufficient to let us build a proof for any argument that is truth-functionally valid – that is, any argument that is valid just because of how the premise and conclusion sentences are built up using the connectives for which we have truth-table rules. However, some arguments require very long proofs, and it is hard to figure out what steps some proofs need. So we will add a few other rules that make some proofs shorter and easier. The sentences in a formal proof are numbered consecutively. We list the premises first, and draw below the last premise. The sentences justified by earlier steps are conclusions (subsidiary or ultimate). Next to each we write the rule by which it is justified, along with the numbers of the earlier sentences in the proof to which the rule is applied. BASIC RULES (starting with the easiest) Reit: You may repeat any sentence you are already assuming or have already derived. & Elim This rule works as you would expect, based on what ‘&’ means. If sentence joining two simpler sentences with ‘and’ is true, you can conclude that each of those simpler sentences is true. So this rule lets you add one of them to your proof. (You may apply the rule more than once to add more than one of those simpler sentences.) & Intro If 2 separate sentences are true, then the sentence you get by joining them with ‘and” is true. So this rule lets you join any 2 sentences from earlier in the proof with ‘&’. Example 1: {b & c, j & k} /∴ c & k (Premises are listed in brackets. ‘/∴’ stands for ‘therefore’.) PHIL 100 Proofs (download) Page 2 of 11 1 2 3 4 5 → Elim b&c j& k c k c&k Premise Premise & Elim: 1 & Elim: 2 & Intro: 3,4 The point of a conditional (if-then) sentence is that, combined with its ‘if’ part (its antecedent), it guarantees the truth of its ‘then’ part (its consequent). So when your proof already contains a conditional and its antecedent as 2 earlier steps, this rule lets you add its consequent to the proof. Example 2: {g, h, (g & h) → (r & s)} /∴ s 1 2 3 4 5 6 g h (g & h) → (r & s) g&h r&s s Premise Premise Premise & Intro: 1,2 → Elim: 3,4 & Elim: 5 This → Elim rule allows us to use common valid argument form also known as ‘Modus Ponens’: p → q, p /∴ q. A common error is to use this similar but invalid pattern, Affirming the Consequent: p → q, q /∴ p. ∨ Intro All it takes to make a disjunction (‘or’ sentence) true is that at least one of its component sentences (its disjuncts) is true. As a result, the truth of a sentence guarantees the truth of any disjunction in which it is a disjunct. So this rule lets you add a disjunction formed by joining any sentence already in the proof with any sentence you choose, in either order. Example 3: {(a ∨ b) → c, b} /∴ c 1 2 3 4 (a ∨ b) → c b a∨b c Premise Premise ∨ Intro: 2 → Elim: 1,3 From ‘b’, this rule would let us build either ‘a ∨ b’ or ‘b ∨ a’ . We choose ‘a ∨ b’ because that is what we would need along with 1 to get ‘c’ by → Elim. EXERCISES, group 1 A. Identify the premises and conclusion of the argument. Translate the argument, using the letters given. Then build a proof deriving the conclusion from the premises. 1. The starter must be malfunctioning. The car won't start, but the lights are working. If the lights work, the battery must be charged. If the car won't start when the battery is charged, there must be a problem with the starter. (s = The starter is functioning properly; c = The car starts; w = The lights are working; b = The battery is charged) PHIL 100 Proofs (download) 2. Page 3 of 11 If Mia moved out of her parents' house, she must be able to afford to. She can afford it only if she found both a roommate and a job. Since she moved out, she must have found a job. (m = Mia moved out of her parents’ house; a = Mia can afford to move out of her parents’ house; r = Mia found a roommate; j = Mia found a job) B. Derive the conclusion from the premises. 1. a a→b (a & b) → c b&c 2. g&h g → (d → k) h→d d&k 3. a&b (b ∨ c) → (d & e) e → (b → s) s 4. (m ∨ o) → k k → (l & r) m k & (r ∨ s) MORE BASIC RULES To use any of the remaining Intro and Elim rules, we must temporarily assume or suppose something that was not given as one of the argument’s original premises. These assumptions are temporary in the sense that we will give them up by the time we reach the end of the proof. The part of a proof in which we are holding a temporary assumption is a subproof. We show how long we are in a subproof by putting its steps to the right of another vertical line. Once a subproof ends, we can no longer rely on sentences within it, since they may depend on an assumption we are no longer holding. The only way to use what is in a subproof once it ends is with one of the remaining rules. Each relies on a subproof as a whole, not single lines in it. ~Intro Any assumption that leads to a contradiction – that is, the same thing being both true and false – cannot possibly be true. So if a temporary assumption leads to some sentence and the denial of that same sentence, this rule lets us give up this assumption, and assert its negation. Example 4: It’s not the case that both Gary and Harvey will be promoted. Harvey is getting a promotion. So Gary won’t be promoted. {~(g & h), h} /∴ ~g 1 2 3 4 5 6 ~(g & h) h g g&h ~(g & h) ~g Premise Premise Premise & Intro: 2,3 Reit: 1 ~Intro: 3 – (4,5) After the original premises (sentences 1 and 2), we reason as follows: Suppose Gary will be promoted (sentence 3). Then it will be true both Gary and Harvey will be promoted (sentence 4). But, as we were already told, it is not true that they will both be promoted (sentence 5). So the assumption (sentence 3) that leads to this contradiction is false (sentence 6). The notation after the rule indicates the assumption through the contradictory pair derived from it as the steps the ~Intro rule is applied to. In this case, we didn’t really need to derive one of the conflicting sentences, since it was something we already had. But the rule requires a contradiction inside the subproof. This is the kind of situation where we need the Reit rule. PHIL 100 Proofs (download) ~ Elim Page 4 of 11 If the negation of a sentence leads to a contradiction, the negation of the sentence must be false, so the sentence itself must be true, This is what is behind the ~Elim rule: When a temporary assumption of a negation leads to a contradiction, you may end the subproof and write the sentence that had been negated. Example 5: If Alicia doesn’t get the job, Nina will. But there is no way Nina or Eloise will get the job. So Alicia will get it. {~a → n, ~(n ∨ e } /∴ a 1 2 3 4 5 6 7 → Intro ~a → n ~(n ∨ e) ~a n n∨e ~(n ∨ e) a Premise Premise Premise → Elim: 1,3 ∨ Intro: 4 Reit: 2 ~ Elim: 3-(5,6) Use this rule to prove a conditional. Assume its antecedent, and show that, on that assumption, you can derive its consequent. When you apply this rule, you stop assuming the antecedent and assert the conditional – that is, you say hypothetically that IF that assumption is true, then so is what you proved under the assumption. Example 6: If Alberto gets his way, the proposed policy will be approved. In that case, Marta and Roger will be angry. Marta will quit if she is angry. So if Albert gets his way, Marta will quit. {a → p, p → (m & r), m → q} /∴ a → q 1 2 3 4 5 6 7 8 9 a→p p → (m & r) m→q a p m&r m q a→q Premise Premise Premise Premise → Elim: 1,4 → Elim: 2,5 & Elim: 6 → Elim: 3,7 → Intro: 4-8 To use more than one rule requiring a subproof, you can start one subproof inside another. In that case, the inner subproof must end before the outer one. Example 7: 1 b → ~(c & d) Premise 2 a → (b → d) Premise 3 a&b Premise 4 a & Elim: 3 5 b→d → Elim: 2,4 6 b & Elim: 3 7 d → Elim: 5,6 8 c Premise 9 c&d & Intro: 7,8 10 ~(c & d) → Elim: 1, 6 11 ~c ~ Intro: 8 – (9,10) 12 (a & b) → ~c → Intro: 3-11 PHIL 100 Proofs (download) ∨ Elim Page 5 of 11 To make use of the information in a disjunction (an ‘or’ sentence), create 2 subproofs. In the first, suppose one of the disjuncts is true; then in the second, suppose the other is true instead. Anything that can be proven from both disjuncts separately, you can say outside these 2 subproofs. Example 8: Rosa will get a ride with either Don or Glenn. If Don gives May a ride, Rosa will be picked up late and she’ll arrive late. If Glenn gives her a ride, he’ll make a stop along the way and Rosa will arrive late. So Rosa will arrive late. 1 2 3 4 5 6 d∨g Premise d → (p & a) Premise g → (s & a) Premise d Premise p & a →Elim: 2,4 a & Elim: 5 7 g Premise 8 s & a → Elim: 3,7 9 a & Elim: 8 10 a ∨ Elim: 1,4-6,7-9 Rosa will ride with Don or Glenn. Suppose Rosa rides with Don. That leads to: Rosa will arrive late. Suppose Rosa rides with Glenn. That leads to: Rosa will arrive late So Rosa will arrive late. In Example 8, the first premise tells us one of two things is true. In the first subproof, we temporarily assume one of them, and show that in that case, Rosa will arrive late. Then we give up that assumption and suppose the other alternative line 1 instead in the second subproof. We see that it leads to the same thing. Since Rosa will be late either way, we don’t have to know which alternative in the first premise is true to be sure Rosa will be late. Example 9: If Luis is given the job, he’ll be happy but Igor will be upset. But if the job goes to Igor, Luis will be upset. Since one of them will get the job, one of them will be upset. {l → (h & u), i → s, l ∨ i} /∴ u ∨ s 1 2 3 4 5 6 7 l → (h & u) i→s l∨i l h&u u u∨s 8 i 9 s 10 u∨s 11 u ∨ s Premise Premise Premise Premise → Elim: 1,4 & Elim: 5 ∨ Intro: 6 Premise → Elim: 2,8 ∨ Intro: 9 ∨ Elim: 3,4-7, 8-10 PHIL 100 Proofs (download) Page 6 of 11 EXERCISES, group 2 Derive the conclusion from the premises. 1. ~b ~(~a & ~b) a 4. (m ∨ r) → s s → (p → q) (r & p) → q 7. a∨n n → (e & s) a→s s 2. j → (k & m) m → ~k ~j 5. (b & c) → d (d & g) → h b&g c→h 8. j → (k ∨ l) (j & k) → m j l → (m & o) m 3. c → (d & e) d → ~h c → ~h 6. r → ~(p & q) w → (r → q) w → ~(p & r) 9. a → (b ∨ c) d → ~b c → ~(a & d) a → ~d DERIVED RULES Derived rules express patterns of arguments that we could prove alone or as parts of longer proofs, using just the basic rules of our proof system. As a result, anything we prove with them, we could prove without them. They are helpful, then, not because of what they enable us to prove, but because they let us prove things more quickly and easily. Modus Tollens Suppose your proof contains both a conditional and the negation of its consequent. Then you may write the negation of its antecedent. That is, you may use this valid argument form: p → q, ~q /∴ ~p. Example 10: Raul would have picked up his newspaper if he were home. He must not be home, because he did not pick up his paper. {h → n, ~n} /∴ ~h 1 h→n Premise 2 ~n Premise 3 ~h Modus Tollens: 1,2 This might remind you of the similar but invalid form, affirming the consequent. The negations, though, make this different. PHIL 100 Proofs (download) Hypothetical syllogism Suppose your proof contains (in any order) a series of conditionals where the consequent in one conditional is the antecedent in the next. Then you may write a conditional with the antecedent of the first conditional in the series as its antecedent, and the consequent of the last conditional in the series as its consequent. Example 11: Disjunctive Syllogism Page 7 of 11 1 2 3 4 5 a→b b→c c→d d→e a→e Premise Premise Premise Premise Hypothetical Syl: 1-4 You may use either of these valid argument forms in proofs: p ∨ q, ~p /∴ q OR p ∨ q, ~q /∴ p Example 12: 1 2 3 4 5 6 7 8 (j & k) → m ~l k∨l j k j&k m j→m Premise Premise Premise Premise Disjunctive Syl: 2, 3 & Intro: 4,5 → Elim: 1,6 → Intro: 4 – 7 Example 13 1 2 3 4 5 6 7 8 9 10 (p & q) ∨ (r & s) p → ~(q ∨ u) p&q p q q∨u ~(q ∨ u) ~(p & q) r&s s Premise Premise Premise & Elim: 3 & Elim: 3 ∨ Intro: 5 → Elim: 2,4 ~Intro: 3-(6,7) Disjunctive Syl: 1,8 & Elim: 9 Double Negation (~ ~) You may drop or add ‘~ ~’. This is a substitution rule because you can substitute a sentence for double negation of the same sentence (or vice versa) within a longer sentence, as well as when one of these appears alone. Example 14: If Ned wasn’t sick or on vacation, he’d be at work. He’s not at work and not on vacation, so he must be sick. {~(s ∨ o) ⊃ w, ~w} /∴ s 1 2 3 4 5 6 7 ~(s ∨ o) → w Premise ~w & ~o Premise ~w & Elim: 2 ~~(s ∨ o) Modus Tollens:1,3 s∨o ~ ~: 4 ~o & Elim: 2 s Disjunctive syl: 5,6 PHIL 100 Proofs (download) DeMorgan’s Laws Page 8 of 11 DeMorgan’s Laws reflect these pairs of equivalent sentence forms: ~(p & q) is equivalent to ~p ∨ ~q ~(p ∨ q) is equivalent to ~p & ~q You may substitute a sentence of one form for that of its equivalent form, whether alone or in a longer sentence. What it means for two sentences to be equivalent is that they would true in the same situations. Here, what this amounts to is that they yield the same results on a truth table – that is, they come out true on exactly the same lines and false on exactly the same lines. Without DeMorgan’s Laws, Example 15 (a variation on the argument in Example 14) would be harder. After a substitution justified by DeMorgan’s Laws, we can proceed as we did in Example 14. Example 15: If Javier wasn’t sick or on vacation, he’d be at work. He’s neither at work nor on vacation, so he must be sick. 1 2 3 4 5 6 7 8 ~(s ∨ o) → w ~(w ∨ o) ~w & ~o ~w ~~(s ∨ o) s∨o ~o s Premise Premise DeMorgan: 2 & Elim: 2 Modus Tollens:1,4 ~~: 5 & Elim: 2 Disjunctive syl: 6,7 Example 16: Ed couldn’t have passed history. If he had passed history or sociology, he would have graduated. If he’d graduated, he would have gone to the ceremony, but he didn’t. {(h ∨ s) → g, (g → c) & ~c} /∴ ~h 1 2 3 4 5 6 7 8 (h ∨ s) → g (g → c) & ~c g→c (h ∨ s) → c ~c ~(h ∨ s) ~h & ~s ~h Premise Premise & Elim: 2 Hypothetical syl:1,3 & Elim: 2 Modus Tollens: 4.5 DeMorgan: 6 & Elim: 7 Example 17: 1 2 3 4 5 6 7 8 a →(b & c) c→d ~d ~c ~b ∨ ~c ~(b & c) ~a ~d → ~a Premise Premise Premise Modus Tollens: 2,3 ∨ Intro: 4 DeMorgan: 5 Modus Tollens: 1,6 →Intro: 3 - 7 PHIL 100 Proofs (download) Page 9 of 11 EXERCISES, group 3 Derive the conclusion from the premises. 1. (a & b) → c ~c & ~d ~a ∨ ~b 2. ~(j & k) → m j ~(l ∨ m) ~k 3. 4. 5. d→c c → ~g g∨h d→h j→k ~l → ~(k ∨ m) j→l ~b → ~c ~(a ∨ b) (~a & ~c) → d d 6. ~ g → (h ∨ e) ~h & ~e g∨m m 7. ~(a ∨ b) → c ~(b ∨ c) ~a 8. r→s g→h (s ∨ u) → g r→h 9. o→j j → (k ∨ m) ~(j & m) o→k SUMMARY OF RULES on next page PHIL 100 Proofs (download) Page 10 of 11 SUMMARY OF PROOF RULES General restrictions Sentences to which a rule applies must appear (1) earlier (that is, above where the rule is applied) and (2) outside any subproofs that have already ended BASIC RULES Reit You may repeat any sentence you already have. & Elim You may write either conjunct from a conjunction you already have. & Intro You may join any 2 sentences you already have with ‘&’. → Elim (Modus ponens) If you have a conditional and its antecedent, you may write its consequent. ∨ Intro You may use write any disjunction in which a sentence that you already have is one of the disjuncts. ~ Intro If you can get a sentence and its negation in a subproof, you may end the subproof and, immediately to its left, write the negation of the sentence that was on the first line of the subproof. ~ Elim Exactly like ~Intro, but where the first line of the subproof is a negation, you may write the sentence the first line negates. p → Intro ∨ Elim Premise ~p q q ~q ~q ~p ~Intro Immediately to the left of a subproof, you may write a conditional whose antecedent is the first sentence on the first line of the subproof, and whose consequent is any sentence on any line in the subproof. If you have a disjunction and separate subproofs (one below but outside the other) starting with its two disjuncts, any sentence that appears in those two subproofs may be written just to the left of them. Premise p ~ Elim p Premise q p→q → Intro p∨q p Premise r q Premise r r ∨ Elim PHIL 100 Proofs (download) Page 11 of 11 DERIVED RULES Modus Tollens From a conditional and the negation of its consequent, you may derive the negation of its antecedent. Hypothetical syllogism From a chain of conditionals where the consequent in one is the antecedent in the next, you may derive a conditional whose antecedent is the same as the antecedent of the first conditional in the chain, and whose consequent p→q is the same as the q→r consequent in the last conditional in the p → r Hypothetical syl. chain. Disjunctive syllogism From a disjunction and the negation of one of its disjuncts, you may derive the other disjunct. Double Negation (~~) You may drop or add ‘~~’. DeMorgan’s Laws You may substitute one sentence for the other in either of these equivalent pairs: ~(p & q) is equivalent to ~p ∨ ~q ~(p ∨ q) is equivalent to ~p & ~q (DeMorgan’s Laws may be applied to make a substitution for a component of a longer sentence.)