《离散数学英文课件：DM_lecture1_6_7》由会员分享，可在线阅读，更多相关《离散数学英文课件：DM_lecture1_6_7（16页珍藏版）》请在金锄头文库上搜索。
1、Discrete Mathematics 1OverviewlIn section 1.5, we already saw:lSeveral types of proofs of implications pq:lVacuous, Trivial, Direct, IndirectlSome methods of proving general statements p:lproof by contradiction (reduction to absurdity).lIn this module, we will see examples of:lForward vs. backward r
2、easoning.lProof by cases.lTurning conjectures into proofs.Discrete Mathematics 2Forward ReasoninglHave premises p, and want to prove q.lFind a s1 such that ps1lThen, modus ponens gives you s1.lThen, find an s2 (such that) s1s2.lThen, modus ponens gives you s2.lAnd hope to eventually get to an sn snq
3、.lThe problem with this method islIt can be tough to see the path looking from p.Discrete Mathematics 3Backward ReasoninglIt can often be easier to see the very same path if you just start looking from the conclusion q insteadlThat is, first find an s1 such that s1q.lThen, find an s2 s2s1, and so on
4、lWorking back to an sn psn.lNote we still are using modus ponens to propagate truth forwards down the chain from p to sn to to s1 to q! lThough we are finding the chain backwardsDiscrete Mathematics 4Backward Reasoning ExamplelTheorem: a0,b0,ab: (a+b)/2 (ab)1/2.lProof:lNotice it is not obvious how t
5、o go from the premises a0, b0, ab directly forward to the conclusion (a+b)/2 (ab)1/2.lSo, lets work backwards from the conclusion, (a+b)/2 (ab)1/2 !Discrete Mathematics 5Steps of Examplel(a+b)/2 (ab)1/2 (squaring both sides)lThis preserves the “” since both sides are positive.l(a+b)2/4 ab (multiplyi
6、ng through by 4)l(a+b)2 4ab (squaring a+b)la2+2ab+b2 4ab (subtracting out 4ab)la22ab+b2 0 (factoring left side)l(ab)2 0lNow, since ab, (ab)0, thus (ab)20, and we can work our way back along the chain of stepsDiscrete Mathematics 6“Forwardized” version of ExamplelTheorem: a0,b0,ab: (a+b)/2 (ab)1/2.lP
7、roof. If Since ab, (ab)0. Thus, (ab)20, i.e., a22ab+b2 0. lAdding 4ab to both sides, a2+2ab+b2 4ab. Factoring the left side, we have (a+b)2 4ab, so (a+b)2/4 ab. lSince ab is positive, we can take the square root of both sides and get (a+b)/2 (ab)1/2. Discrete Mathematics 7Stone Game ExamplelGame rul
8、es: lThere are 15 stones in a pile. Two players take turns removing either 1, 2, or 3 stones. Whoever takes the last stone wins.lTheorem: There is a strategy for the first player that guarantees him a win.lHow do we prove this? lLooks complicated How do we pick out the winning strategy from among al
9、l possible strategies?lWork backwards from the endgame!Discrete Mathematics 8Working Backwards in the GamelPlayer 1 wins if it is player 2s turn and there are no stoneslP1 can arrange this ifit is his turn, and thereare 1, 2, or 3 stoneslThis will be true aslong as player 2 had4 stones on his turnlA
10、nd so onPlayer 1Player 201, 2, 345, 6, 789, 10, 111213, 14, 15Discrete Mathematics 9“Forwardized” versionlTheorem. Whoever moves first can always force a win.lProof. 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 these ca
11、ses, 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 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.Discrete Mathematics 10Proof by Examples (Cases)
12、 lA universal statement can never be proven by using examples, unless the universe can be validly reduced to only finitely many examples, and your proof covers all of them!lWe want to show p1 p2 pn q (p1 q) (p2 q) (pn q)Proof: p1 p2 pn q (p1 p2 pn) q (p1 p2 pn) q (p1 q) (p2 q) (pn q) (p1 q) (p2 q) (
13、pn q)Discrete Mathematics 11Proof by Examples (Cases) lTheorem: x,yZ: x2+3y2 = 8.lProof: If |x|3 or |y|2 then x2+3y2 8. This leaves x20,1,4 and 3y20,3. The largest pair sum to 4+3 = 7 1), there is some natural number larger than all x, y, z such that it is not divisible by x or y or z.Proof: Constru
14、ct xyz+1. we first assume xyz+1 can be evenly divided by x, i.e. (xyz+1)/x = yz + 1/x, where 1/x must be an integer. The only possible value for x must be 1. But this is in contradiction with the fact that x, y, z 1. Therefore, xyz+1 cannot be divided by x, and similarly, by y or z.Discrete Mathemat
15、ics 13Conjecture & CounterexampleslConjecture: integers n0, n2n+41 is prime.lHm, lets see if we can find any counter-examples: l121+41 = 41 (prime)l222+41 = 42+41 = 43 (prime)l323+41 = 93+41 = 47 (prime) Looking good so far!lCan we conclude after showing that it checks out in, say, 20 or 30 cases, t
16、hat the conjecture must be true?lNEVER!lOf course, 41241+41 is divisible by 41!Discrete Mathematics 14Even Great Mathematicians Can Propose False Conjectures!lEuler conjectured that for n2, the sum of n1 nth powers of positive integers is not an nth power.lRemained true for all cases checked for 200
17、 years, but no proof was found.lFinally, in 1966, someone noticed that275 + 845 + 1105 + 1335 = 1445.lLarger counter-examples have also been found for n=4, but none for n5 yet.Discrete Mathematics 15Fermats “Last Theorem”lTheorem: xn+yn=zn has no solutions in integers xyz 0 with integer n2.lIn the 1
18、600s, Fermat famously claimed in a marginal note that he had a “wondrous proof” of the theorem.lBut unfortunately, if he had one, he never published it!lThe theorem remained a publicly unproven conjecture for the next 400 years!lFinally, a proof that requires hundreds of pages of advanced mathematic
19、s was found by Wiles at Princeton in 1990.lIt took him 10 years of work to find it!lChallenge: Find a short, simple proof of Fermats last theorem, and you will become instantly famous!Discrete Mathematics 16Some Open ConjectureslConjecture: There are infinitely many primes of the form n2+1, where nZ
20、.lConjecture: (Twin Prime Conjecture) There are infinitely pairs of primes of the form (p, p+2).lConjecture: (The Hailstone Problem) If h(x) = x/2 when x is even, and 3x+1 when x is odd, then xN nN hn(x) = 1 (where the superscript denotes composition of h with itself n times).Prove any of these, and you can probably have a lifetimecareer sitting around doing pure mathematics
