Bài giảng Toán rời rạc: Các phương pháp chứng minh cơ bản

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 Bài 2:Các phương pháp chứng minh cơ bản Rosen 5th ed., §1.5 48 slides, ~3 lectures Bản chất và tầm quan trọng của chứng minh Trong toán học, chứng minh là: Diễn giải đúng đắn (suy luận được, đúng về logic) và hoàn chỉnh (rõ ràng, chi tiết) để xác định chân lý của khẳng định toán học một cách không từ chối được và chặt chẽ. Tại sao diễn giải cần đúng đắn và hoàn chỉnh? Đúng đắn ngăn chúng ta khỏi bị lừa chính mình. Hoàn chỉnh cho phép bất kỳ ai có thể kiểm chứng kết quả. Trong môn này (& cũng như các môn toán) đòi hỏi chuân rất cao về chứng minh tính đúng đắn và hoàn chỉnh!! Tổng quan về §1.5 Các phương pháp chứng minh có thể được hình thức hoá trong thuật ngữ các luật suy diễn logic (rules of logical inference). Chứng minh toán học có thể tự biểu diễn hình thức như cấu trúc rời rạc. Chúng ta có thể xem lại các suy diễn đúng đắn và sai lầm và một số phương pháp chứng minh. Các ứng dụng chứng minh Như bài tập trong trao đổi rõ ràng về các suy luận logic trong bất cứ lĩnh vực học tập nào. Hoạt động cơ bản của toán học là khám phá và làm sáng tỏ thông qua chứng minh các định lý mới lý thú. Chứng minh định lý có ứng dụng trong kiểm chứng chương trình, an toàn máy tính và các hệ suy luận tự động, v.v Chứng minh định lý cho phép ta tin cậy vào tính đúng đắn của nó ngay cả trong tình huống căng thẳng nhất. Thuật ngữ chứng minhProof Terminology Định lý Khẳng định cần được chứng minh đúng đắn. Tiên đề, nguyên lý, giả thuyết, giả thiết Các đề xuất (thường không được chứng minh) xác định cấu trúc mà ta đang suy luận về chúng. Các luật suy diễn Mẫu suy luận đúng từ giả thiết đến kết luận. Nói thêm về thuật ngữ Bổ đề - định lý nhỏ sử dụng như bước đệm để chứng minh định lý chính. Hệ quả - định lý nhỏ được chứng minh bằng cách suy luận dễ dàng từ định lý chính. Giả thuyết - khẳng định mà giá trị chân lý đúng của nó chưa được chứng minh. (Tuy nhiên, giả thuyết có thể được tin tưởng rộng rãi vào tính đúng đắn) Lý thuyết – tập tất cả các định lý mà được chứng minh từ tập các tiên đề. Trực quan bằng đồ thị … Various Theorems The Axiomsof the Theory A Particular Theory Luật suy diễn - Dạng tổng quát Luật suy diễn là Mẫu xác lập rằng nếu chúng ta biết tập các tiền đề (antecedent) ở một dạng nào đó là đúng, thì chúng ta có thể suy luận một cách đúng đắn rằng các mệnh đề kết quả (consequent) là đúng. antecedent 1 antecedent 2 …  consequent “” nghĩa là “khi đó” Luật suy diễn và phép kéo theo Mỗi luật suy diễn đúng tương ứng với phép kéo theo là hằng đúng. antecedent 1 Luật suy diễn  antecedent 2 …  consequent Hằng đúng tương ứng: ((ante. 1)  (ante. 2)  …)  consequent Một số luật suy diễn p Luật cộng  pq pq Luật đơn giản  p p Luật hội q  pq Modus Ponens & Tollens p Luật suy xét độc lập pq (Rule of modus ponens)q q pq Luật cách từ chốip (Rule of modus tollens) “the mode of affirming” “the mode of denying” Luật tam đoạn luận pq Luật tam đoạn luận kéo theo  qr Rule of hypothetical syllogismpr p  q Luật tam đoạn luận tuyển p Rule of disjunctive syllogism  q Aristotle(ca. 384-322 B.C.) Chứng minh hình thức Chứng minh hình thức của kết luận C, cho trước tiền đề p1, p2,…,pn bao gồm dãy các bước, mỗi bước áp dụng một luật suy diễn cho một tiền đề hoặc các mệnh đề đã được chứng minh trước (antecedents) để tạo ra mệnh đề đúng tiếp theo (the consequent). Chứng minh chứng tỏ rằng nếu tiền đề đúng thì kết luận sẽ đúng. Ví dụ chứng minh hình thức Giả sử ta có các tiền đề sau:“Trời không nắng và trời lạnh.”“Để chúng ta bơi được thì trời cần phải nắng.”“Nếu chúng ta không bơi, thì chúng ta sẽ đi cano.”“Nếu chúng ta đi cano, thì chúng ta sẽ về nhà sớm.” Cho trước các tiền đề, chứng minh định lý“Chúng ta sẽ về nhà sớm” sử dụng các luật suy diễn. Chứng minh tiếp theo. G/s ta viết tắt: sunny = “It is sunny”; cold = “It is cold”; swim = “We will swim”; canoe = “We will canoe”; early = “We will be home early”. Khi đó các tiền đề được viết như sau:(1) sunny  cold (2) swim  sunny(3) swim  canoe (4) canoe  early Proof Example cont. Step Proved by1. sunny  cold Premise #1.2. sunny Simplification of 1.3. swimsunny Premise #2.4. swim Modus tollens on 2,3.5. swimcanoe Premise #3.6. canoe Modus ponens on 4,5.7. canoeearly Premise #4.8. early Modus ponens on 6,7. Các luật suy diễn lượng tử x P(x)P(o) (thế đối tượng cụ thể bất kỳ o) P(g) (cho p/tử tổng quan g từ u.d.)x P(x) x P(x)P(c) (thế hằng mới c) P(o) (thế đối tượng hiện có bất kỳ o) x P(x) Nguỵ biện chung Nguỵ biện là luật suy diễn hoặc chứng minh khác mà không đúng về logic. Nguỵ biện có thể dẫn đến kết luận sai! Nguỵ biện về ngộ nhận kết luận: “pq là đúng, và q là đúng, vậy p cần phải đúng.” Nguỵ biện phủ nhận giả thiết: “pq là đúng, và p là sai, vậy q cần phải là sai.” Suy luận vòng quanh Ngụy biện giả thiết tường minh hay ẩn ngay chính mệnh đề đang cần phải chứng minh tính đúng đắn. Ví dụ: Chứng minh số nguyên n là chẵn, nếu n2 là chẵn. Thử chứng minh: “G/s n2 là chẵn. Khi đó n2=2k với số nguyên k nào đó. Chia cả hai vế cho n được n = (2k)/n = 2(k/n). Vậy có số nguyên j (ký hiệu thay k/n) sao cho n=2j. Vì vậy n là chẵn” Đã có suy luận vòng quanh trong chứng minh trên. Ở đâu? Begs the question: How doyou show that j=k/n=n/2 is an integer, without first assuming that n is even? Chứng minh đúng Ta biết n cần phải là lẻ hoặc chẵn. Nếu n là lẻ, thì n2 cần phải là lẻ, (vì số lẻ nhân với số lẻ luôn được số lẻ). Vì n2 là chẵn, nó không lẻ, (vì không có số nào vừa là chẵn vừa là lẻ). Nên, theo modus tollens, n không là số lẻ được. Vậy, theo tam đoạn luận tuyển (disjunctive syllogism), n cần phải là chẵn. ■ This proof is correct, but not quite complete,since we used several lemmas without provingthem. Can you identify what they are? Một phương án c/m dài dòng nữa G/s n2 là chẵn2|n2  n2 mod 2 = 0. Tất nhiên n mod 2 bằng 0 hoặc 1. Nếu bằng 1, thì n1 (mod 2), khi đó n21 (mod 2), sử dụng định lý nếu ab (mod m) và cd (mod m) thì acbd (mod m), với a=c=n và b=d=1. Bây giờ n21 (mod 2) suy ra n2 mod 2 = 1. Vậy theo Luật tam đoạn luận kéo theo, (n mod 2 = 1) suy ra (n2 mod 2 = 1). Vì ta biết n2 mod 2 = 0  1, bằng Luật modus tollens ta biết rằng n mod 2  1. Vậy theo tam đoạn luận tuyển ta có n mod 2 = 0 2|n  n là chẵn. Uses some number theory we haven’t defined yet. Các phương pháp chứng minh kéo theo Để chứng minh kéo theo pq, ta có: Chứng minh trực tiếp: G/s p đúng, và c/m q. C/m phản chứng: G/s q, và c/m p. Chứng minh trống rỗng: c/m tự có p. Chứng minh hiển nhiên: C/m tự có q. Chứng minh phân trường hợp: Chỉ ra p(a  b), và (aq) và (bq). Ví dụ chứng minh trực tiếp Định nghĩa: Số n gọi là lẻ iff n=2k+1 với k nguyên; n là chẵn iff n=2k với k nguyên. Định lý: Mọi số nguyên hoặc là chẵn hoặc là lẻ Có thể chứng minh từ các tiên đề đơn giản hơn Định lý: (Với mọi số n) Nếu n là lẻ, thì n2 là số nguyên lẻ. C/m: nếu n lẻ, thì n = 2k+1 với k nguyên nào đó. Vậy, n2 = (2k+1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1. Nên n2 có dạng 2j + 1 (với j bằng 2k2 + 2k), vậy n2 là lẻ. □ Ví dụ chứng minh phản chứng Định lý: (Với mọi số nguyên n)  Nếu 3n+2 là lẻ, thì n là lẻ. C/m: Giả sử kết luận là sai, tức là, n là chẵn. Khi đó n=2k với k nguyên nào đó. Vậy 3n+2 = 3(2k)+2 = 6k+2 = 2(3k+1). Do đó 3n+2 là chẵn, vì nó bằng 2j với j = 3k+1. Vậy 3n+2 không là lẻ. Ta vừa chỉ ra rằng ¬(n is odd)→¬(3n+2 is odd), vậy mệnh đề phản đảo của nó là (3n+2 is odd) → (n is odd) cũng là đúng. □ Ví dụ chứng minh trống rỗng Định lý: (Với mọi n) Nếu n cả là chẵn và lẻ, thì n2 = n + n. C/m: Khẳng định “n là cả chẵn và lẻ” là chắc chắn sai, vì không có số nào có thể như vậy cả. Vậy, Định lý là đúng trống rỗng (không nói lên điều gì cả). □ Ví dụ chứng minh hiển nhiên Định lý: (Cho số nguyên n) Nếu n là tổng của hai số nguyên tố thì hoặc n là lẻ hoặc n là chẵn. C/m: Mọi số nguyên n hoặc là lẻ hoặc là chẵn. Vì vậy kết luận của định lý là đúng bất kể tiền đề có đúng hay không. Vậy phép kéo theo hiển nhiên đúng. □ Chứng minh bằng mâu thuẫn Phương pháp chứng minh p. G/s p, và ta chứng minh khi đó cả q và q đúng với q là mệnh đề nào đó. (có thể là bất cứ cái gì!) Vậy p (q  q) (q  q) là hằng sai bằng F Vậy pF, mà chỉ đúng khi p=F Suy ra p là đúng. Ví dụ chứng minh mâu thuẫn Định lý: là số vô tỉ. C/m: Giả sử 21/2 là hữu tỉ. Điều đó có nghĩa là có hai số nguyên i, j không có ước chung sao cho 21/2 = i/j. Bình phương hai vế, 2 = i2/j2, nên 2j2 = i2. Vậy i2 là chẵn; suy ra i là chẵn. G/s i=2k. Vậy 2j2 = (2k)2 = 4k2. Chia cả hai vế cho 2, j2 = 2k2. Vậy j2 là chẵn, nên j là chẵn. Nhưng khi đó i và j có ước chung, chẳng hạn là 2, vậy ta có mâu thuẫn. □ Ôn tập: Các phương pháp chứng minh Các chứng minh trực tiếp, gián tiếp, trống rỗng, và hiển nhiên của khẳng định dạng pq. Chứng minh bằng mâu thuẫn của khẳng định bất kỳ. Tiếp theo: Chứng minh có tính xây dựng và chứng minh tồn tại không xây dựng. Chứng minh tồn tại Chứng minh khẳng định dạng x P(x) được gọi là chứng minh tồn tại. Nếu chứng minh chỉ ra cách tìm cụ thể hoặc xây dựng phần tử cụ thể a sao cho P(a) đúng, thì nó gọi là chứng minh xây dựng. Ngược lại, gọi là không xây dựng (nonconstructive). Chứng minh tồn tại xây dựng Định lý: Tồn tại một số nguyên n mà nó có hai cách khác nhau biểu diễn dạng là tổng của hai số lập phương: Bằng j3 + k3 và l3 + m3 trong đó j, k, l, m là các số nguyên, và {j,k} ≠ {l,m} Chứng minh: Xét n = 1729, j = 9, k = 10, l = 1, m = 12. Hãy kiểm tra rằng các đẳng thức đều thoả mãn. Ví dụ tồn tại xây dựng khác Định lý: Với bất kỳ số nguyên n>0, tồn tại dãy n số liên tiếp đều không là nguyên tố. Khẳng định trên trong predicate logic:n>0 x i (1in)(x+i is composite) Chứng minh trang sau… Chứng minh... Cho n>0, G/s x = (n + 1)! + 1. G/s i  1 và i  n, và xét x+i như sau. Đặt x+i = (n + 1)! + (i + 1). Ta có (i+1)|(n+1)!, do 2  i+1  n+1. và (i+1)|(i+1). nên, (i+1)|(x+i).  x+i không là nguyên tố (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ựng Định lý: “Có vô hạn số nguyên tố.” Mọi tập hữu hạn số phải chứa phần tử lớn nhất, vì vậy ta sẽ chứng minh được đị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ố, sẽ có số lớn hơn cũng là nguyên tố. Tổng quát hơn: Với mọi số,  số nguyên tố lớn hơn. Hình thức: Chỉ ra rằng n p>n : p nguyên tố. Chứng minh sử dụng chia trường hợp Cho trước n>0, chứng minh có số nguyên tố p>n. Xét x = n!+1. Vì x>1, ta biết (x nguyên tố)(x không nguyên tố). Case 1: x nguyên tố. Rõ ràng x>n, nên G/s p=x và ta đã c.m xong. Case 2: x có thừa số nguyên tố p. Nhưng nếu pn, thì x mod p = 1, mâu thuẫn với x chia hết cho p. Vậy p>n, và ta chứng minh xong. Bài toán dừng (Turing‘36) Bài toán dừng là một hàm toán học đầu tiên được chứng minh không có thuật toán tính nó! Chúng ta nói, nó không tính được. Hàm thiết kế là Halts(P,I) :≡ giá trị chân lý của khẳng định: Chương trình P, với đầu vào I, có chắc chắn dừng hay không “Program P, given input I, eventually terminates.” Theorem: Halts là không tính toán được! Tức là, không tồn tại thuật toán A nào đó mà tính đúng  Halts cho mọi khả năng của đầu vào. Chứng minh của nó là chứng minh không tồn tại. Hệ quả: Tính không thể phân tích dự báo trước của một chương trình máy tính tuỳ ý. Alan Turing1912-1954 Chứng minh Cho chương trình tùy ý H(P,I), Xét thuật toán Breaker, xác định như sau:procedure Breaker(P: a program) halts := H(P,P) if halts then while T begin end Nhận thấy Breaker(Breaker) halts iff H(Breaker,Breaker) = F. Vậy H không thể tính được hàm Halts! (chính nó dừng khi nó không dừng) Breaker makes a liar out of H, by doing the opposite of whatever H predicts. Giới hạn của chứng minh Một số khẳng định rất đơn giản của lý thuyết số không thể chứng minh được hoặc bác bỏ! VD. Giả thuyết Goldbach: Mọi số nguyên n≥2 chính xác là trung bình cộng của hai số nguyên tố nào đó. n≥2  primes p,q: n=(p+q)/2. Có những khẳng định về lý thuyết số mà không bao giờ có thể chứng minh (hoặc bác bỏ) được. (Gödel). Ví dụ thêm về chứng minh Câu hỏi thưởng 1a: Lập luận sau đúng hay sai? “Mọi trợ giảng (TA) soạn các bài toán thưởng dễ. Ramesh là TA. Suy ra, Ramesh soạn bài toán thưởng dễ.” Trước hết, tách tiền đề khỏi kết luận: Tiền đề #1: Mọi TA soạn bài toán thưởng dễ. Tiền đề #2: Ramesh là TA. Kết luận: Ramesh soạn bài toán thưởng dễ. Trả lời Viết ví dụ trên trong ký hiệu logic. Tiền đề #1: Mọi trợ giảng (TA) soạn bài toán thưởng dễ. G/s vũ trụ U.D. = mọi người G/s T(x) :≡ “x là trợ giảng (TA)” G/s E(x) :≡ “x soạn bài toán thưởng dễ” Khi đó tiền đề #1 cho biết: x, T(x)→E(x) Tiếp trả lời… Tiền đề #2: Ramesh là trợ giảng TA. G/s R :≡ Ramesh Khi đó tiền đề #2 cho biết: T(R) Và kết luận là: E(R) Lập luận đúng, vì có thể suy ra từ một dãy áp dụng liên tiếp các luật suy diễn như sau: Chứng minh chi tiết Statement How obtained x, T(x) → E(x) (Premise #1) T(Ramesh) → E(Ramesh) (Universal instantiation) T(Ramesh) (Premise #2) E(Ramesh) (Modus Ponens from  statements #2 and #3) Ví dụ khác Câu hỏi thưởng 2b: Đúng hay không đúng: Ít nhất một trong 280 sinh viên trong lớp là học giỏi xuất sắc (intelligent). Y là một sinh viên trong lớp. Vậy Y học giỏi xuất sắc. Trước hết: Tách tiền đề và kết luận,và dịch sang logic: Premises: (1) x InClass(x)  Intelligent(x) (2) InClass(Y) Conclusion: Intelligent(Y) Trả lời Không, lập luận trên là sai; Ta có thể phản bác với phản ví dụ như sau: Xét trường hợp chỉ có một sinh viên X học giỏi xuất sắc trong lớp đó, và X≠Y. Khi đó tiền đề x InClass(x)  Intelligent(x) là đúng, do khái quát tồn tại của InClass(X)  Intelligent(X) Nhưng kết luận Intelligent(Y) là sai, vì X là sinh viên giỏi duy nhất trong lớp, và Y≠X. Do đó, Tiền đề không suy ra được kết luận. Ví dụ khác Câu hỏi thưởng #2: Chứng minh rằng tổng của số hữu tỉ và số vô tỉ luôn là số vô tỉ. Trước hết, bạn cần hiểu chính xác câu hỏi mà bạn cần chứng minh: “Với mọi số thực x, y, nếu x là số hữu tỉ và y là số vô tỉ, thì x+y là số vô tỉ.” x,y: Rational(x)  Irrational(y) → Irrational(x+y) Trả lời Sau đó, nghĩ lại về các định nghĩa của các khái niệm trong khẳng định của định lý:  reals r: Rational(r) ↔  Integer(i)  Integer(j): r = i/j.  reals r: Irrational(r) ↔ ¬Rational(r) Bạn luôn cần các định nghĩa của các khái niệm để chứng minh định lý! Bây giờ, xem một chứng minh đúng: What you might write Theorem: x,y: Rational(x)  Irrational(y) → Irrational(x+y) Proof: G/s x, y tương ứng là các số vô tỉ và hữu tỉ. … (Khái quát vũ trụ) Bây giờ ta biết gì về x và y? Bạn cần quay về định nghia số hữu tỉ: … Vì x là hữu tỉ, ta biết (từ định nghĩa số hữu tỉl) rằng có các số nguyên i và j sao cho x = i/j. Giả sử ix,jx là các số như vậy … Ta cho chúng tên cụ thể để sau này sử dụng chúng. Cái gì tiếp theo? Ta biết gì về y? Chỉ là y là vô tỉ: ¬ các số nguyên i,j: y = i/j. Nhưng, khó nhìn thấy chứng minh trực tiếp trong trường hợp này. Ta thử chứng minh gián tiếp, nhưng trong trường hợp này đơn giản hơn là dùng chứng minh mâu thuẫn (rất giống với gián tiếp). Vậy, ta cần chỉ ra điều gì? Chỉ là x+y là vô tỉ. Tức là, ¬i,j: (x + y) = i/j. Điều gì xảy ra nếu ta giả thiết phủ định của khẳng định trên? Viết tiếp… G/s x +y không là vô tỉ. Khi đó x+y phải là hữu tỉ, vì vậy có tồn tại các số nguyên i,j: x +y = i/j. Vậy, g/s is và js là các số như vậy: x +y = is /js. Khi đó, ta có (ix/jx) + y = (is/js). Hãy quan sát! Chúng ta có đủ thông tin để kết luận điều gì đó về y không. Hãy giải phương trình trên cho y. Kết thúc chứng minh Giải phương trình cho y, ta có:  y = (is/js) – (ix/jx) = (isjx – ixjs)/(jsjx)Vì tử số và mẫu số của biểu thức trên là hai số nguyên, do đó theo định nghĩa số hữu tỉ, y là số hữu tỉ. Điều này mâu thuẫn với giả thiết y là số vô tỉ. Vậy giả thiết x +y là hữu tỉ là sai, và như vậy định lý được chứng minh. Ví dụ về trả lời sai 1 là hữu tỉ. √2 là vô tỉ. 1+√2 là vô tỉ. Do đó, tổng của một số hữu tỉ và một số vô tỉ là một số vô tỉ. (Direct proof.) Tại sao câu trả lời này không có điểm? Sinh viên tìm cách dùng ví dụ để chứng minh khẳng định với mọi. Điều đó luôn sai! Ngay cả ví dụ cũng chưa hoàn chỉnh, vì sinh viên chưa chứng minh được 1+√2 là vô tỉ! Một số luật suy diễn Ví dụ dùng luật chứng minh Chứng minh R đúng Chứng minh bằng mâu thuẫn, dấu * ký hiệu mâu thuẫn Một số luật của Logic vị từ Ứng dụng Logic Hình thức hóa-Chuyển sang hệ logic Đặc tả bằng biểu thức logic Kiểm tra tính tương thích – Dùng bảng chân lý Kiểm tra bằng cách phân trường hợp