Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Proof rules we’ve studied so far:(used to justify new steps in a proof)Identity Introduction: = IntroIdentity Elimination: = ElimReiteration: ReitConjunction Introduction: ᴧ Intro Conjunction Elimination: ᴧ Elim Disjunction Introduction: ᴠ Intro Disjunction Elimination: ᴠ Elim “proof by cases”A ᴠ B must have a disjunction to begin withA one disjunct becomes premise of a subproofC must prove this from Aᴠ ElimB other disjunct becomes premise of another subproofC must prove this from BC conclusion here must be same as conclusion of each subproof aboveNegation Introduction: ¬ Intro“proof by contradiction”• Our second major method of proof• Based on the remaining Boolean connective• Involves use of contradictionContradiction = “any claim that cannot possibly be true, or any set of claims which cannot all be true simultaneously” (p. 138)Contradiction symbol:Examples of contradictions … single statements: a ≠ aP ᴧ ¬Psets of statements:P and ¬PA ᴧ B and ¬(A ᴠ B)Larger(a,b) and Larger(b,a)Negation Introduction: ¬ Intro“proof by contradiction”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 (this opposite claim being the one you originally wanted to prove anyway).Grieving Tony?Queen ElizabethR.I.P.“Gone but not forgotten”Bo: “Tony called me this morning asking if I wanted to cut class and go shopping with him. I said I couldn’t because I was sick.”Sal: “I saw Tony and his girlfriend shopping at Target today during your logic class.” Flo: “When I asked Tony this afternoon on the phone how his fish were doing, he laughed and said they had never been better!”The evidence: Tony is not really grieving!Having first believed Tony (‘Fish dead’), with additional evidence we’ve run into a contradiction. So, we now reason that Tony must be lying and we end up believing the opposite of what led us into the contradiction (we’ve used a ‘proof by contradiction’ strategy).Negation Introduction (¬ Intro)<1 P assume as premise the opposite of what you want to prove2 then reach a contradiction ¬P ¬ Intro: 1-2 you can now negate the premise, back one level But now we need a formal mechanism for flagging a contradiction . . .Contradiction Introduction ( Intro)<You can assert a contradiction whenever you can cite two contradictory steps of the proof.P P¬P more¬Pcommonly ⊥ ⊥(p. 158)1. A2. ¬A3. ⊥ ⊥ Intro: 1,24. ¬¬A ¬ Intro: 2-31. Cube(b) (proof 6.9)2. ¬(Cube(c) ᴧ Cube(b))3. Cube(c)4. Cube(c) ᴧ Cube(b) ᴧ Intro: 1,35. ⊥ ⊥ Intro: 2,46. ¬ Cube(c) ¬ Intro: 3-51. A ᴠ B2. ¬A3. ¬B4. A5. ⊥ ⊥ Intro: 4,26. B7. ⊥ ⊥ Intro: 6,38. ⊥ ᴠ Elim: 1, 4-5, 6-7<Keep in mind that ⊥ Intro doesn’t always have to be used in combination with the ¬ Intro strategy. Here it’s used instead with ᴠ Elim . . .Negation Elimination (¬ Elim)<You can eliminate double negations.1 ¬¬PP ¬ Elim: 1Contradiction Elimination ( Elim)<The weirdest rule of the semester . . .Review of VALIDITY: An argument is valid if, when we assume the premises to be true, the 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.BUT . . . 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 . . .(i.e., if—relative to a particular world—you plug false premises into a valid argument structure, it may yield a false conclusion).For 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 OneThis is a valid argument, but it seems goofy because the first premise is false in the real world … but this simply means that though the argument is valid, it is unsound in the real world.BUT . . . What if a set of premises contains not merely a false premise, but an outright contradiction? If the premises are contradictory, then there is no situation in which they will ever all be true at the same time, so there is (obviously) no situation in which the premises will all be true but the conclusion false. But this overlaps our definition of a valid argument! (i.e., a valid argument is one in which it is impossible for the premises to all be true but the conclusion false).A ‘normal’ invalid argument:1 Cube(a) Counterexample world:2 Cube(b)3 Cube(c) a b cThe fact that we can create a counterexample world in which both premises are true but the conclusion is false proves the argument is invalid.Argument with contradictory premises:1 Cube(a) Impossible to make2 ¬Cube(a) counterexample world:3 Cube(c)a ? cBecause you cannot demonstrate that this argument is invalid (i.e., you can’t construct a counterexample world in which both premises are true), you must assume it is valid!As ridiculous as it may sound, this means that you can tack any sentence on as the ‘conclusion’ of a set of contradictory premises, and you will have a valid argument! An argument with a contradictory set of premisesis trivially or vacuously valid. Or, what amounts to the same thing,Any and every sentence is a logical consequence of a contradiction.Hence, our next rule . . .Contradiction Elimination (⊥ Elim)<If you can establish a contradiction on the basis of some set of sentences, you can then assert any sentence at all following—and at the same level as—the contradiction.1 P2 ¬P3 ⊥4 Q ⊥ Elim: 3Q here represents any sentence at all, asserted at the same proof level as the ⊥ immediately before
View Full Document
Unlocking...