Bài giảng Chiến lược chứng minh

University of FloridaDept. of Computer & Information Science & EngineeringCOT 3100Applications of Discrete StructuresDr. Michael P. Frank Slides for a Course Based on the TextDiscrete Mathematics & Its Applications (5th Edition)by Kenneth H. Rosen Module #11:Chiến lược chứng minhProof Strategies Rosen 5th ed., §3.1 ~21 slides, ~1 lecture Tổng quan Bài #11 Trong bài #2, ta đã thấy: Một số kiểu chứng minh của phép kéo theo p→q: Ngây thơ, Hiển nhiên, Trực tiếp, Gián tiếp Các kiểu chứng minh tồn tại: Xây dựng và không xây dựng. Một số phương pháp chứng minh mệnh đề tổng quan: Chứng minh phân trường hợp, chứng minh phản chứng. Trong bài này, chúng ta xét các ví dụ về: Suy luận tới và lui. Chứng minh phân trường hợp. Chứng minh tồn tại thích hợp. Qui giả thuyết về các chứng minh. Suy luận tới Ta có giả thiết p, và muốn chứng minh q. Tìm s1 sao cho p→s1 Khi đó, luật suy diễn modus ponens sẽ cho s1. Tiếp tục tìm s2  (sao cho) s1→s2. Khi đó, luật suy diễn modus ponens sẽ cho s2. Và hy vọng sẽ nhận được sn  sn→q. Vấn đề với phương pháp này là… Phải bền bỉ để nhìn thấy đường đi từ p. Suy luận luiBackward Reasoning Thông thường dễ dàng hơn để thấy con đường tương tự nếu bạn bắt đầu từ kết luận q … Như vậy, đầu tiên tìm s−1 sao cho s−1→q. Sau đó, tìm s−2  s−2→s−1, và tiếp tục… Cho đến khi s−n  p→s−n. Lưu ý ta cũng sử dụng luật suy diễn modus ponens để triển khai tính đúng đắn từ p đến s−n đến … s-1 đến q! Chúng ta tìm được dãy lui nhưng áp dụng tiến tới. Đây không phải hoàn toàn như chứng minh gián tiếp… Ở đó ta dùng modus tollens và ¬q để chứng minh ¬s−1, …. Tuy nhiên, nó cũng gần tương tự. Ví dụ suy luận luiBackward Reasoning Example Theorem:  a>0,b>0,a≠b: (a+b)/2 > (ab)1/2. Proof: Notice it is not obvious how to go from the premises a>0, b>0, a≠b directly forward to the conclusion (a+b)/2 > (ab)1/2. So, let’s work backwards from the conclusion, (a+b)/2 > (ab)1/2 ! Example 1 Steps of Example (a+b)/2 > (ab)1/2  (squaring both sides) This preserves the “>” since both sides are positive. (a+b)2/4 > ab  (multiplying through by 4) (a+b)2 > 4ab  (squaring a+b) a2+2ab+b2 > 4ab  (subtracting out 4ab) a2−2ab+b2 > 0  (factoring left side) (a−b)2 > 0 Now, since a≠b, (a−b)≠0, thus (a−b)2>0, and we can work our way back along the chain of steps… Phương án chuyển thành tiến “Forwardized” version of Example Theorem: a>0,b>0,a≠b: (a+b)/2 > (ab)1/2. Proof. If Since a≠b, (a−b)≠0. Thus, (a−b)2>0, i.e., a2−2ab+b2 > 0. Adding 4ab to both sides, a2+2ab+b2 > 4ab. Factoring the left side, we have (a+b)2 > 4ab, so (a+b)2/4 > ab. Since ab is positive, we can take the square root of both sides and get (a+b)/2 > (ab)1/2. ■ Đây chỉ là ví dụ đơn giản để đi từ giả thiết đến kết luận, nhưng bạn không thể tưởng tượng nó được nhậnnhư thế nào, nó trông có vẻ “thần bí.” Phản ứng chung của sinh viên: “Nhưng làm sao bạn nghĩ ra việc bổ sung 4ab vào hai vế?” Trả lời: Bằng cách suy luận lui từ kết luận! Ví dụ trò chơi sỏiStone Game Example Game rules: Có 15 hòn sỏi trong 1 đống. Hai người chơi lần lượt lấy ra khỏi đống 1, 2, hoặc 3 hòn. Ai lấy hòn sỏi cuối cùng người đó thắng. Định lý: Có một chiến lược để đảm bảo rằng người đi đâu luôn thắng. Nó được chứng minh như thế nào? Chứng minh có xây dựng không… Nhìn có vẻ phức tạp… Chúng ta có thể chọn chiến lược chiến thắng nào trong số các chiến lược có thể? Suy luận quay lui từ cuối trò chơi! Example 2 Working Backwards in the Game Player 1 wins if it is player 2’s turn and there are no stones… P1 can arrange this ifit is his turn, and thereare 1, 2, or 3 stones… This will be true aslong as player 2 had4 stones on his turn… And so on… Phương án chuyển thành tới “Forwardized” version Theorem. Người nào đi trước người đó luôn có cách để thắng. Proof. 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 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 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. Chứng minh phân trường hợpProof by Cases Example Định lý: nZ ¬(2|n  3|n) → 24|(n2−1) Proof: Since 2·3=6, the value of n mod 6 is sufficient to tell us whether 2|n or 3|n. If (n mod 6){0,3} then 3|n; if it is in {0,2,4} then 2|n. Thus (n mod 6){1,5}. Case #1: If n mod 6 = 1, then (k) n=6k+1. n2=36k2+12k+1, so n2−1=36k2+12k = 12(3k+1)k. Note 2|(3k+1)k since either k or 3k+1 is even. Thus 24|(n2−1). Case #2: If n mod 6 = 5, then n=6k+5. n2−1 = (n−1)·(n+1) = (6k+4)·(6k+6) = 12·(3k+2)·(k+1). Either k+1 or 3k+2 is even. Thus, 24|(n2−1). Example 3 Chứng minh bằng ví dụProof by Examples? Mệnh đề với mọi không bao giờ có thể chứng minh bằng ví dụ, trừ khi nó đưa được về hữu hạn ví dụ và bạn cần phải chứng minh tất cả ví dụ đó. Theorem: ¬x,yZ: x2+3y2 = 8. Proof: If |x|≥3 or |y|≥2 then x2+3y2 >8. This leaves x2{0,1,4} and 3y2{0,3}. The largest pair sum to 4+3 = 7 0, tồn tại dãy gồm n số liên tiêp đều không phải là số nguyên tố. Khẳng định trên viết dạng logic vị từ:n>0 x i (1in)(x+i is composite) Chứng minh trang sau… Example 7 The proof... Given n>0, let x = (n + 1)! + 1. Let i  1 and i  n, and consider x+i. Note x+i = (n + 1)! + (i + 1). Note (i+1)|(n+1)!, since 2  i+1  n+1. Also (i+1)|(i+1). So, (i+1)|(x+i).  x+i is composite.  n x 1in : x+i is composite. Q.E.D. Chứng minh tồn tại không xây dựngNonconstructive Existence Proof Định lý: Có vô số các số nguyên tố. Mọi tập hữu hạn các số luôn chứa số lớn nhất, vậy ta có thể chứng minh Định lý nếu chỉ ra rằng không có số nguyên tố lớn nhất. Tức là., chỉ ra rằng với mọi số nguyên tố luôn tồn tại số lớn hơn mà cũng là nguyên tố. generally: For any number,  a larger prime. Formally: Show n p>n : p is prime. The proof, using proof by cases... Given n>0, prove there is a prime p>n. Consider x = n!+1. Since x>1, we know that (x is prime)(x is composite). Case 1: Suppose x is prime. Obviously x>n, so let p=x and we’re done. Case 2: x has a prime factor p. But if pn, then p mod x = 1. So p>n, and we’re done. Chứng minh tồn tại thích hợpAdapting Existing Proofs Theorem: There are infinitely many primes of the form 4k+3, where kN. Recall we proved there are infinitely many primes because if p1,…,pn were all the primes, then (∏pi)+1 must be prime or have a prime factor greater than pn,  contradiction! Proof: Similarly, suppose q1,…,qn lists all primes of the form 4k+3, and analogously consider Q = 4(∏qi)+3. Unfortunately, since q1 = 3 is possible, 3|Q and so Q does have a prime factor among the qi, so this doesn’t work! So instead, consider Q = 4(∏qi)−1 = 4(∏qi−1)+3. This has the right form, and has no qi as a factor since i: Q ≡ −1 (mod qi). Example 5 Giả thuyết và chứng minhConjecture and Proof We know that some numbers of the form 2p−1 are prime when p is prime. These are called the Mersenne primes. Can we prove the inverse, that an−1 is composite whenever either a>2, or (a=2 but n is composite)? All we need is to find a factor greater than 1. Note an−1 factors into (a−1)(an−1+…+a+1). When a>2, (a−1)>1, and so we have a factor. When n is composite, r,s>1: n=rs. Thus, given a=2, an = 2n = 2rs = (2r)s, and since r>1, 2r > 2 so 2n − 1 = bs−1 with b = 2r > 2, which now fits the first case. Example 6 Giả thuyết và phản ví dụConjecture & Counterexamples Giả thuyết:  số nguyên n>0, n2−n+41 là nguyên tố. Hm, let’s see if we can find any counter-examples: 12−1+41 = 41 (prime) 22−2+41 = 4−2+41 = 43 (prime) 32−3+41 = 9−3+41 = 47 (prime) Looking good so far!! Chúng ta có thể kết luận sau khi chỉ ra 20 hoặc 30 trường hợp đúng rằng giả thuyết đó là đúng được không? KHÔNG BAO GIỜ NEVER NEVER NEVER! Of course, 412−41+41 is divisible by 41!! Example 8 Ngay cả các nhà Bác học vĩ đại cũng có thể đưa ra giả thuyết sai lầm! Euler conjectured that for n>2, the sum of n−1 nth powers of positive integers is not an nth power. Remained true for all cases checked for 200 years, but no proof was found. Finally, in 1966, someone noticed that 275 + 845 + 1105 + 1335 = 1445. Larger counter-examples have also been found for n=4, but none for n>5 yet. Example 9 Fermat’s “Last Theorem” Theorem: xn+yn=zn has no solutions in integers xyz ≠ 0 with integer n>2. In the 1600s, Fermat famously claimed in a marginal note that he had a “wondrous proof” of the theorem. But unfortunately, if he had one, he never published it! The theorem remained a publicly unproven conjecture for the next ~400 years! Finally, a proof that requires hundreds of pages of advanced mathematics was found by Wiles at Princeton in 1990. It took him 10 years of work to find it! Challenge: Find a short, simple proof of Fermat’s last theorem, and you will become instantly famous! Theorem 2 Some Open Conjectures Conjecture: There are infinitely many primes of the form n2+1, where nZ. Conjecture: (Twin Prime Conjecture) There are infinitely pairs of primes of the form (p, p+2). Conjecture: (The Hailstone Problem) If h(x) = x/2 when x is even, and 3x+1 when x is odd, then xN nN 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… Example 13 Example 12 Example 11