Today’s topicsForward ReasoningBackward ReasoningBackward Reasoning ExampleStone Game ExampleWorking Backwards in the Game“Forwardized” versionProof by Cases ExampleProof by Examples?A Constructive Existence ProofThe proof...Nonconstructive Existence ProofThe proof, using proof by cases...Adapting Existing ProofsConjecture and ProofConjecture & CounterexamplesCompSci 102 © Michael Frank 7.1Today’s topics•Integers & Number TheoryIntegers & Number Theory–Integers–Division, GCD–Euclidean Alg–Mod!•Reading: Sections 2.4-2.6Reading: Sections 2.4-2.6•UpcomingUpcoming–Sequences, Summations, & InductionSequences, Summations, & InductionCompSci 102 © Michael Frank 7.2Forward Reasoning•Have premises Have premises pp, and want to prove , and want to prove qq..–Find a Find a ss11 such that such that pp→→ss11•Then, modus ponens gives you Then, modus ponens gives you ss11..–Then, find an Then, find an ss22 (such that) (such that) ss11→→ss22..•Then, modus ponens gives you Then, modus ponens gives you ss22..–And hope to eventually get to an And hope to eventually get to an ssnn ssnn→→qq..•The problem with this method is…The problem with this method is…–It can be tough to see the path looking from It can be tough to see the path looking from pp..CompSci 102 © Michael Frank 7.3Backward Reasoning•It can often be easier to see the It can often be easier to see the very same pathvery same path if you just if you just start looking from the conclusion start looking from the conclusion qq instead… instead…–That is, That is, firstfirst find an find an ss−1−1 such that such that ss−1−1→→qq..–ThenThen, find an , find an ss−2 −2 ss−2−2→→ss−1−1, and so on…, and so on…–Working back to an Working back to an ss−−nn pp→→ss−−nn..•Note we Note we stillstill are using are using modus ponensmodus ponens to propagate truth to propagate truth forwardsforwards down the chain from down the chain from pp to to ss−−nn to … to to … to ss11 to to qq!!–We are We are findingfinding the chain the chain backwardsbackwards, but , but applyingapplying it it forwardsforwards..–This is not quite the same thing as an indirect proof…This is not quite the same thing as an indirect proof…•In that, we would use In that, we would use modus tollensmodus tollens and ¬ and ¬qq to prove ¬ to prove ¬ss−−11, , etc.etc.–However, it it similar.However, it it similar.CompSci 102 © Michael Frank 7.4Backward Reasoning Example•Theorem:Theorem: aa>0,>0,bb>0,>0,aa≠≠bb: (: (aa++bb)/2 > ()/2 > (abab))1/21/2..•Proof:Proof:–Notice it is not obvious how to go from the Notice it is not obvious how to go from the premises premises aa>>00, , bb>0>0, , aa≠≠bb directly forward to the directly forward to the conclusion conclusion ((aa++bb)/2 > ()/2 > (abab))1/21/2..–So, let’s work So, let’s work backwardsbackwards from the conclusion, from the conclusion, ((aa++bb)/2 > ()/2 > (abab))1/21/2 !!Example 1CompSci 102 © Michael Frank 7.5Stone Game Example•Game rules: Game rules: –There are 15 stones in a pile. Two players take turns There are 15 stones in a pile. Two players take turns removing either 1, 2, or 3 stones. Whoever takes the removing either 1, 2, or 3 stones. Whoever takes the last stone wins.last stone wins.•Theorem:Theorem: There is a strategy for the first player There is a strategy for the first player that guarantees him a win.that guarantees him a win.•How do we prove this? Constructive proof…How do we prove this? Constructive proof…–Looks complicated… How do we pick out the winning Looks complicated… How do we pick out the winning strategy from among all possible strategies?strategy from among all possible strategies?•Work backwards from the endgame!Work backwards from the endgame!Example 2CompSci 102 © Michael Frank 7.6Working Backwards in the Game•Player 1 wins if it is player 2’s turn and there are Player 1 wins if it is player 2’s turn and there are no stones…no stones…•P1 can arrange this ifP1 can arrange this ifit is his turn, and thereit is his turn, and thereare 1, 2, or 3 stones…are 1, 2, or 3 stones…•This will be true asThis will be true aslong as player 2 hadlong as player 2 had4 stones on his turn…4 stones on his turn…•And so on…And so on…Player 1Player 1Player 2Player 2001, 2, 31, 2, 3445, 6, 75, 6, 7889, 10, 119, 10, 11121213, 14, 1513, 14, 15CompSci 102 © Michael Frank 7.7“Forwardized” version•Theorem.Theorem. Whoever moves first can always force a win. Whoever moves first can always force a win.–Proof.Proof. Player 1 can remove 3 stones, leaving 12. After player 2 Player 1 can remove 3 stones, leaving 12. After player 2 moves, there will then be either 11, 10, or 9 stones left. In any of moves, there will then be either 11, 10, or 9 stones left. In any of these cases, player 1 can then reduce the number of stones to 8. these cases, player 1 can then reduce the number of stones to 8. Then, player 2 will reduce the number to 7, 6, or 5. Then, player 1 Then, player 2 will reduce the number to 7, 6, or 5. Then, player 1 can reduce the number to 4. Then, player 2 must reduce them to 3, can reduce the number to 4. Then, player 2 must reduce them to 3, 2, or 1. Player 1 then removes the remaining stones and wins.2, or 1. Player 1 then removes the remaining stones and wins.CompSci 102 © Michael Frank 7.8Proof by Cases Example•Theorem:Theorem: nnZZ ¬(¬(2|2|nn 3 3|n|n) ) → 24|(→ 24|(nn22−1)−1)–Proof:Proof: Since Since 2·3=62·3=6, the value of , the value of nn mod 6 mod 6 is sufficient is sufficient to tell us whether to tell us whether 2|2|nn or or 3|3|nn. If . If ((nn mod 6) mod 6){0,3}{0,3} then then 3|3|nn; if it is in ; if it is in {0,2,4}{0,2,4} then then 2|2|nn. Thus . Thus ((nn mod 6) mod 6){1,5}{1,5}..•Case #1: Case #1: If If nn mod 6 = 1 mod 6 = 1, then , then ((kk) ) nn=6=6kk+1+1. . nn22=36=36kk22+12+12kk+1+1, , so so nn22−1=36−1=36kk22+12+12kk = 12(3 = 12(3kk+1)+1)kk. Note . Note 2|(32|(3kk+1)+1)kk since either since either kk or or 33kk+1+1 is even. Thus is even. Thus 24|(24|(nn22−1)−1)..•Case #2:Case #2: If If nn mod 6 = 5 mod 6 = 5, then , then nn=6=6kk+5+5. . nn22−1 = (−1 = (nn−1)·(−1)·(nn+1) = +1) =
View Full Document
Unlocking...