LESSON #15: Negation rules (6.3) Read pp. 156-163. Homework: 6.7-6.14POWERPOINT SLIDE #1We have studied seven proof rules so far (and you will need to know how to use all of them in working actual proofs for the midterm exam). POWERPOINT SLIDE #2We’ve already discussed the first major proof ‘method’, proof by cases (formally: disjunction elimination). Recall that disjunction elimination is used to prove a conclusion that can be shown to follow separately (in separate subproofs) from each disjunct of a known disjunction. (See powerpoint slide 2 for details)POWERPOINT SLIDE #3Now we come to our second major method of proof (and another rule that requires subproofs): proof bycontradiction. This rule is based on the one remaining Boolean connective: negation. The rule’s formal name is Negation Introduction (¬ Intro)To understand proof by contradiction, however, you first need to know what a ‘contradiction’ is. The book gives this definition (p. 138): “a contradiction is any claim that cannot possibly be true, or any set of claims which cannot all be true simultaneously.” POWERPOINT SLIDE #4Contradiction symbol: ⊥The following are examples of single-sentence contradictions:a ≠ aP ᴧ ¬PPairs (or larger sets) of sentences can also be contradictions (i.e., they can’t both/all be true in the same world):P . . . . ¬PA ᴧ B . . . . ¬(A ᴠ B)Larger(a,b) . . . . Larger(b,a)POWERPOINT SLIDE #5Now, the basic idea of proof by contradiction (i.e., ¬ Intro) is to assume as a premise the opposite (i.e., the negation) of what you want to actually prove, and when that assumption leads to a contradiction (i.e., a result that can’t possibly be true), then you can safely conclude that its opposite must instead be true (i.e., this opposite claim being the one you originally wanted to prove anyway).POWERPOINT SLIDE #6We use this kind of reasoning all the time in everyday life.(Elaborate on the story of Tony and the goldfish …)POWERPOINT SLIDE #7Now, we are ready to formalize this method of reasoning: Negation Introduction (¬ Intro)1 P2 ⊥¬P ¬Intro: 1-2That is, to prove ¬P, first assume its opposite, P, as the premise of a subproof and show that within this subproof you (eventually) reach a contradiction (it may take any number of steps to actually reach the contradiction—I’ve left these intermediate steps out in the schema above). If you can prove that a contradiction follows from assuming P as the premise of the subproof in this way, then you are allowed to assert the negation (opposite) of P back one level within the main proof.POWERPOINT SLIDE #8This approach means that we also need some way of formally identifying and marking a contradiction, and we achieve this through a simple rule of Contradiction Introduction ( Intro), which allows you to assert (i.e., that a contradiction has been reached) anytime you can cite two contradictory steps of the proof in support of this assertion.P¬P⊥Actually, more commonly the contradiction will be part of a structure like this:P¬P⊥That is, you’ll most often use Contradiction Intro inside a subproof, often as part of a larger strategy of proof by contradiction. POWERPOINT SLIDE #9Page 158 of the textbook gives a very simple example of how this works—in this case to prove that ¬¬A is a logical consequence of A. Notice how the two rules ¬ Intro and Contradiction Intro are used together in the the proof by contradiction:1. A2. ¬A3. ⊥ ⊥ Intro: 1,24. ¬¬A ¬ Intro: 2-3Proof 6.9 from your homework offers another good example of how ⊥ Intro is used as part of a ¬ Intro strategy:POWERPOINT SLIDE #101 Cube(b)2 ¬(Cube(c) ᴧ Cube(b))3 Cube(c)4 Cube(c) ᴧ Cube(b) ᴧ Intro: 1,35 ⊥ ⊥ Intro: 2,46 ¬Cube(c) ¬ Intro: 3-5POWERPOINT SLIDE #11Keep in mind that ⊥ Intro doesn’t always have to be used in combination with the ¬ Intro strategy. Another possible combination of strategies is to use ⊥ Intro in combination with ᴠ Elim, as in the following example from p. 159 of the textbook, which shows that the three premises taken together are contradictory:1. A ᴠ B2. ¬A3. ¬BRemember how ᴠ Elim works: You must have a disjunction to work from (in this case, at step 1) and then you must open subproofs corresponding to each of the disjuncts, where each subproof’s premise is one of the disjuncts of the original disjunction (notice that the premise at step 4 is the first disjunct from step 1, and the premise at step 6 is the other disjunct from step 1). Then, if you can prove the same conclusion in both of the subproofs, you can assert that conclusion one level back in the main proof. In this case, both subproofs lead to a contradiction (steps 5 and 7), so you can assert a contradiction back at the main level (step 8).4. A5. ⊥ ⊥ Intro: 4,26. B7. ⊥ ⊥ Intro: 6,38. ⊥ ᴠ Elim: 1, 4-5, 6-7As I’ve mentioned before, proof rules always come in pairs, an intro and and elimination rule. As you would expect, then, there is also a ¬ Elim and a ⊥ Elim rule. POWERPOINT SLIDE #12The ¬ Elim rule is simple:¬¬PPThis is just the basic procedure dealing with double negation that we discussed before but now formalized as a proof rule. Now, let’s consider the other contradiction rule, Contradiction EliminationPOWERPOINT SLIDE #13⊥ Elim is the weirdest rule we will encounter all semester …But first, some background review.POWERPOINT SLIDE #14Remember when we first discussed logical consequence and validity that we said that an argument is valid if when we assume the premises to be true, then conclusion necessarily follows. Put differently, we said that a conclusion is a logical consequence of a set of premises if it would be impossible for the premises to be true but the conclusion false. POWERPOINT SLIDE #15Of course, we also said that there is no guarantee, logically speaking, that any or all of the premises are actually true in a given world. An argument can be valid but unsound (meaning that false premises in a valid argument can lead to a valid but nonetheless false conclusion in some world).POWERPOINT SLIDE #16For example:P1: Jimmy Fallon is president of the U.S.P2: The president of the U.S. often rides on Air Force OneC: Jimmy Fallon often rides on Air Force One The above argument is valid, but unsound in our present world.POWERPOINT SLIDE #17What about when a set of premises contains not merely a false premise, but an outright contradiction? If the premises
View Full Document
Unlocking...