Tài liệu Một số dạng toán chứng minh bằng phản chứng và quy nạp toán học

TRƯỜNG ĐẠI HỌC THÁI NGUYÊN ĐẠI HỌC KHOA HỌC ĐẶNG ĐÌNH HƯNG MỘT SỐ DẠNG TOÁN CHỨNG MINH BẰNG PHẢN CHỨNG VÀ QUY NẠP TOÁN HỌC LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2014 TRƯỜNG ĐẠI THÁI NGUYÊN ĐẠI HỌC KHOA HỌC ĐẶNG ĐÌNH HƯNG MỘT SỐ DẠNG TOÁN CHỨNG MINH BẰNG PHẢN CHỨNG VÀ QUY NẠP TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60.46.01.13 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học TS. TRẦN NGUYÊN AN THÁI NGUYÊN - 2014 Mục lục LỜI NÓI ĐẦU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Chương 1. Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. Mệnh đề và các phép toán mệnh đề . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Công thức mệnh đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3. Hệ quả logic và quy tắc suy luận . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4. Đại số vị từ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5. Tính sắp thứ tự tốt của tập số tự nhiên . . . . . . . . . . . . . . . . . . . 11 Chương 2. Phương pháp chứng minh phản chứng . . . . . . . 12 2.1. Một số dạng chứng minh phản chứng . . . . . . . . . . . . . . . . . . . . . 12 2.2. Một số bài toán chứng minh bằng phản chứng. . . . . . . . . . . . . 17 Chương 3. Phương pháp chứng minh quy nạp toán học . 32 3.1. Phương pháp chứng minh quy nạp cơ bản . . . . . . . . . . . . . . . . . 32 3.2. Một số phương pháp quy nạp đặc biệt . . . . . . . . . . . . . . . . . . . . 38 3.3. Một số sai lầm học sinh hay mắc phải . . . . . . . . . . . . . . . . . . . . . 46 3.4. Một số bài toán sử dụng phương pháp quy nạp . . . . . . . . . . . . 48 KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 1 LỜI NÓI ĐẦU Logic toán là một ngành khoa học còn non trẻ ra đời từ thế kỷ 17, nhưng nó đóng vai trò quan trọng trong toán học. Nó là phương tiện để xây dựng các kiến thức toán học và là chất keo nối kết các ngành, các vấn đề toán học với nhau làm cho toán học trở thành một thể thống nhất. Logic toán rất quan trọng với các thày giáo dạy toán. Nó tạo cho người thày khả năng đi sâu vào bản chất của sự chứng minh. Nó tạo cho người thày những phương tiện mới để rèn luyện cho học sinh thói quen suy nghĩ chính xác. Trong luận văn này tôi trình bày cơ sở logic cũng như các dạng đặc biệt của hai phương pháp chứng minh toán học quen thuộc và quan trọng: phương pháp chứng minh phản chứng và phương pháp quy nạp toán học. Cả hai phương pháp này đã được sử dụng trong chương trình nâng cao ở phổ thông, trong các bài toán thi học sinh giỏi. Điều quan trọng trọng trong phương pháp chứng minh phản chứng là tạo ra mệnh đề phủ định và tìm ra sự vô lý với giả thiết hay vô lý với kiến thức toán học đã biết. Phương pháp quy nạp toán học chứng minh các mệnh đề phụ thuộc vào số tự nhiên dạng ∀nP (n), n ∈ N. Để chứng minh những mệnh đề như thế hiển nhiên ta không thể thử trực tiếp với mọi số tự nhiên vì tập số tự nhiên là vô hạn. Nguyên lý cơ bản của phương pháp quy nạp toán học là chứng minh mệnh đề đúng với n = 0 sau đó ta chứng minh nếu mệnh đề đúng với một số tự nhiên k thì nó cũng với k + 1. Ở đây ta theo quy ước tập các số tự nhiên N là tập các số nguyên không âm: 0, 1, 2, .... Tuy nhiên chúng ta không hiểu tại sao chúng ta lại chứng minh như vậy. Hơn nữa trong thực tế chứng minh xuất hiện rất nhiều các dạng biến thể của hai phương pháp trên. Trong luận văn này trước hết chúng tôi giải thích cơ sở logic của các phương pháp chứng minh trên. Sau đó chúng tôi liệt kê một số dạng chứng minh đặc biệt. Luận văn bao gồm ba chương. Chương 1 trình bày ngắn gọn những kiến thứ cơ bản của đại số mệnh đề, vị từ và tính sắp thứ tự tốt của tập các số tư nhiên làm cơ sở cho việc trình bày các chương sau. Một số khái niệm và kết quả được trình bày trong chương này nhưng không có ví dụ minh họa nhằm mục đích cho luận văn được trình bày cô đọng hơn. Chương 2 và 3 là các chương chính của luận văn. Trong Chương 2, 2 chúng tôi trình bày các dạng toán chứng minh bằng phương pháp phản chứng. Với những kiến thức về đại số mệnh đề trình bày trong Chương 1 ta có thể hiểu rõ cơ sở logic của phương pháp chứng minh này. Chương 3 dành cho việc trình bày phương pháp quy nạp toán học. Để hiểu rõ phương pháp này ta cần tính sắp thứ tự tốt của tập các số tự nhiên và phương pháp chứng minh phản chứng. Luận văn này được hoàn thành dưới sự hướng dẫn tận tình của thầy giáo TS. Trần Nguyên An. Tôi xin bày tỏ lòng kính trọng và biết ơn sâu sắc đến Thầy. Tôi cũng xin bày tỏ lời cảm ơn sâu sắc đến các thầy cô giáo của trường Đại Học Khoa Học - Đại Học Thái Nguyên, những người đã tận tình giảng dạy, giúp đỡ tôi trong quá trình học tập. Cuối cùng tôi xin cảm ơn gia đình, bạn bè đã giúp đỡ, động viên, ủng hộ tôi để tôi có thể hoàn thành khóa học này! Thái Nguyên, tháng 9 năm 2014 Tác giả Đặng Đình Hưng 3 Chương 1 Kiến thức chuẩn bị Chương này trình bày một số kiến thức chuẩn bị làm cơ sở cho việc trình bày các chương sau. 1.1. Mệnh đề và các phép toán mệnh đề Mệnh đề là một khái niệm nguyên thuỷ của toán học. Ta có thể quan niệm mệnh đề là một câu trần thuật biểu thị một ý trọn vẹn mà ta có thể khẳng định một cách khách quan nó là "đúng" hoặc "sai". Trong Logic Toán, khi xét một mệnh đề, ta không quan tâm đến cấu trúc ngữ pháp cũng như ý nghĩa nội dung của nó, mà chỉ quan tâm đến tính đúng sai của nó mà thôi. Giá trị "đúng" hay "sai" của một mệnh đề gọi là giá trị chân lý của mệnh đề đó. Ta quy ước ký hiệu giá trị chân lý "đúng" bằng số 1, giá trị "sai" bằng số 0. Một mệnh đề mà không một bộ phận thực sự nào của nó cũng là mệnh đề, gọi là mệnh đề đơn giản. Ta ký hiệu các mệnh đề đơn giản bằng các chữ cái la tinh nhỏ (có thể với các chỉ số): a, b, c, ..., p, q, r, a1, a2 , .... Đây là các biến lấy giá trị 1 hoặc 0 khi ta thay chúng bằng các mệnh đề cụ thể. Vì vậy ta gọi chúng là các biến mệnh đề. Từ các mệnh đề đơn giản nhờ các liên kết lôgic, cũng gọi là các phép toán logic ta lập được các mệnh đề phức hợp. Sau đây là một số phép toán logic cơ bản. Định nghĩa 1.1.1 (Phép phủ định). Giả sử a là mệnh đề. Phủ định của a là một mệnh đề, ký hiệu a (hoặc ¬ a), là một mệnh đề đúng khi a là một mệnh đề sai và là một mệnh đề sai khi a là mệnh đề đúng. Ta có thể mô tả định nghĩa trên bằng bảng sau, gọi là bảng giá trị 4 chân lý của phép toán. a a 0 1 1 0 Định nghĩa 1.1.2 (Phép hội). Giả sử a và b là các mệnh đề. Hội của chúng, ký hiệu là a ∧ b, là một mệnh đề đúng khi a và b đều đúng, và là một mệnh đề sai trong các trường hợp còn lại. Định nghĩa 1.1.3 (Phép tuyển). Giả sử a và b là các mệnh đề. Tuyển của chúng ký hiệu là a ∨ b, là một mệnh đề sai khi a và b đều sai, và là một mệnh đề đúng trong các trường hợp còn lại. Định nghĩa 1.1.4 (Phép kéo theo). Giả sử a và b là các mệnh đề. a kéo theo b là một mệnh đề, ký hiệu a → b, là một mệnh đề sai khi a đúng b sai và là một mệnh đề đúng trong các trường hợp còn lại. Định nghĩa 1.1.5 (Phép tương đương). Giả sử a và b là các mệnh đề. a tương đương b là một mệnh đề, ký hiệu là a ↔ b, là một mệnh đề đúng khi a và b cùng đúng hoặc cùng sai và là một mệnh đề sai trong các trường hợp còn lại. Ta có bảng giá trị chân lý của các phép toán hội, tuyển, kéo theo và tương đương như sau. a 0 0 1 1 b a∧b a∨b a→b a↔b 0 0 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 1 1 1 Chú ý: Trong mệnh đề a → b, a được gọi là tiền đề hay giả thiết, b gọi là kết luận. Mệnh đề a → b được gọi là mệnh đề thuận, mệnh đề b → a được gọi là mệnh đề đảo, mệnh đề a → b được gọi là mệnh đề phản còn mệnh đề b → a được gọi là mệnh đề phản đảo của mệnh đề a → b. Ta có thể thấy được giá trị chân lý của các mệnh đề thuận, đảo, phản và phản đảo qua bảng chân lý sau a 0 0 1 1 b a→b b→a a→b b→a 0 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 1 1 5 Theo bảng giá trị chân lý mệnh đề thuận và mệnh đề phản đảo; mệnh đề đảo và mệnh đề phản luôn có cùng giá trị chân lý với mọi giá trị chân lý của các mệnh đề thành phần a, b. 1.2. Công thức mệnh đề Nhờ các phép toán logic từ các mệnh đề đơn giản ta có thể thành lập được những mệnh đề mới, ngày càng phức tạp hơn, bằng cách thực hiện trên các mệnh đề đã cho một số hữu hạn tuỳ ý những phép toán logic. Các mệnh đề thành lập theo cách ấy gọi là công thức của đại số mệnh đề. Để định nghĩa một cách chính xác khái niệm này, ta xuất phát từ một tập hợp ký hiệu cơ bản gọi là bảng chữ cái. Bảng chữ cái trong Đại số mệnh đề bao gồm: (i) 0, 1 là ký hiệu các mệnh đề sai, tương ứng đúng. Ta gọi chúng là các hằng. (ii) Các chữ cái la tinh nhỏ a, b, c, ... là ký hiệu của các biến mệnh đề. (iii) −, ∧, ∨, →, ↔ là ký hiệu của các phép toán logic và (, ) là dấu ngoặc. Định nghĩa 1.2.1. Một dãy hữu hạn tuỳ ý những ký hiệu trong bảng chữ cái được gọi là một từ trên bảng chữ cái đó. Ta ký hiệu các từ bằng các chữ cái la tinh lớn A, B, C, P, Q, .... Trong lớp tất cả các từ, ta xét lớp từ gọi là công thức và được định nghĩa bằng quy nạp như sau: (i) Các hằng, các biến mệnh đề là những công thức. (ii) Nếu A là một công thức thì (A) là một công thức. (iii) Nếu A và B là những công thức thì (A∧B), (A∨B), (A → B), (A ↔ B), ... là những công thức. (iv) Mọi từ khác không được thành lập theo các quy tắc (i), (ii), (iii) thì không phải là công thức. Công thức A chứa các biến mệnh đề a1 , a2, ..., an thường được ký hiệu là A = A(a1 , a2, ..., an). Giả sử A = A(a1 , a2, ..., an) là một công thức mệnh đề phụ thuộc n biến mệnh đề a1 , a2 , ..., an. Đặt I = {0, 1} là tập các giá trị chân lý của các mệnh đề. Dãy e = (e1, e2 , ..., en) ∈ I n được gọi là một dãy giá trị chân lý (dãy giá trị) cho tương ứng với các biến mệnh đề a1 , a2, ..., an trong công thức A. 6 Giá trị chân lý của A tại e, ký hiệu A|e và được định nghĩa như sau: (i) Nếu A là một biến mệnh đề ai thì A|e = ei . (ii) Nếu A có dạng B, trong đó B là một công thức và nếu B|e đã được xác định thì ( 0 nếu B|e = 1 A|e = 1 nếu B|e = 0. (iii) Nếu A là một trong các dạng B ∧ C, B ∨ C, B → C, B ↔ C, trong đó B và C là những công thức, B|e , C|e đã được xác định thì A|e cũng được xác định và việc xác định giá trị của A trên e phù hợp với định nghĩa của các phép toán ∧, ∨, →, ↔ . Cụ thể ta có bảng giá trị chân lý tương ứng sau B|e C|e (B ∧ C)|e (B ∨ C)|e (B → C)|e (B ↔ C)|e 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 1 1 Tập Giả A = A(a1, a2 , ..., an) là công thức mệnh đề phụ thuộc n biến. EA = {e ∈ I n | A|e = 1} ⊆ I n được gọi là miền đúng của công thức A. Định nghĩa 1.2.2. Một công thức A được gọi là hằng đúng nếu nó nhận giá trị 1 trên mọi dãy giá trị của các biến mệnh đề có mặt trong công thức A, tức là A|e = 1 trên mọi dãy giá trị e của A. Nếu A là một công thức hằng đúng thì ta viết |= A. Các công thức hằng đúng đóng một vai trò rất quan trọng trong logic. Chúng là những luật logic. Định nghĩa 1.2.3. Giả sử A, B là hai công thức. Ta nói A và B là tương đương logic nếu chúng có cùng giá trị trên mọi dãy giá trị của các biến mệnh đề, tức là A|e = B|e trên mọi dãy giá trị e của A và B. Ta ký hiệu hai công thức tương đương logic là A ⇔ B (hoặc A ≡ B ). Ví dụ 1.2.4. (i) A = a ∧ a là công thức hằng đúng. (ii) a → b ⇔ a ∨ b. (iii) a → b ⇔ (a ∨ b) ∧ (c ∨ c). 7 Nhận xét:(i) Quan hệ tương đương logic giữa các công thức là quan hệ tương đương trên tập các công thức của đại số mệnh đề. (ii) Giả sử A, B là hai công thức. Khi đó A ⇔ B nếu và chỉ nếu |= (A ↔ B). Bằng cách lập bảng giá trị chân lý ta có thể chứng minh một số công thức là tương đương logic. 1.3. Hệ quả logic và quy tắc suy luận Định nghĩa 1.3.1. (i) Giả sử A và B là hai công thức. Công thức B được gọi là hệ quả logic (hay hệ quả) của công thức A, ký hiệu A ⇒ B (hoặc A |= B) nếu với mọi dãy giá trị e của các biến mệnh đề có mặt trong A và B, mỗi khi A|e = 1 thì B|e = 1. Khi đó ta cũng nói có một quy tắc suy luận từ tiền đề (hay giả thiết) A đến kết luận (hay hệ quả) B, quy tắc suy luận đó được ký hiệu bởi A . B (ii) Giả sử ∆ = {A1, A2, ..., Am} là một dãy hữu hạn những công thức. Công thức B được gọi là hệ quả logic (hay hệ quả) của ∆, ký hiệu ∆ ⇒ B (ta còn viết ∆ |= B, hay A1 , A2, ..., Am ⇒ B), nếu B là hệ quả logic của công thức A1 ∧ A2 ∧ ... ∧ Am. Khi đó ta cũng nói có một quy tắc suy luận từ các tiền đề (hay các giả thiết A1, A2, ..., Am đến kết luận (hay hệ quả) B, quy tắc suy luận đó được ký hiệu bởi A1, ..., Am ∆ hoặc . B B Nhận xét. (i) Giả sử A, B là các công thức. Khi đó B là hệ quả logic của A khi và chỉ khi EA ⊆ EB . A khi và (ii) B là hệ quả logic của A hay ta có quy tắc suy luận B chỉ khi A → B là hằng đúng. 1.4. Đại số vị từ Logic vị từ là sự phát triển của Đại số Mệnh đề. Nó chứa trong bản thân nó toàn bộ Đại số Mệnh đề, nghĩa là các mệnh đề đơn giản, các phép toán logic và do đó tất cả các công thức của Đại số Mệnh đề. 8 Xét mệnh đề đơn giản: "5 là một số nguyên tố". Cố định vị từ "là một số nguyên tố" và thay đổi chủ từ 5 bởi x là một số tự nhiên nào đó, ta có phát biểu F (x): "x là một số nguyên tố". Với mỗi giá trị x = a, ta có F (a) là một mệnh đề chỉ mang một giá trị "đúng" hoặc "sai". Từ đó ta có ánh xạ F : N −→ I, a 7−→ F (a)-giá trị chân lý của mệnh đề: "a là một số nguyên tố". Ánh xạ F được gọi là một vị từ 1 ngôi xác định trên N còn phát biểu F (x) không phải là một mệnh đề nó được gọi là một mệnh đề chứa biến (hay một dạng mệnh đề). Thông thường ta cũng dùng ký hiệu F (x) để chỉ vị từ F , x được gọi là một biến vị từ. Định nghĩa 1.4.1. (i) Giả sử M là tập khác rỗng và I = {0, 1}. Vị từ n ngôi xác định trên M là ánh xạ F : M n −→ I, ký hiệu F = F (x1, x2, ..., xn), x1, x2, ..., xn gọi là các biến vị từ. Với mỗi a = (a1, a2 , ..., an) ∈ M n thì F |a = F (a1 , a2, ..., an) gọi là giá trị của vị từ F tại dãy a các giá trị của các biến vị từ. (ii) Tập sau được gọi là miền đúng của vị từ F EF (x1 ,x2 ,...,xn ) = {(a1 , a2, ..., an) ∈ M n | F (a1, a2 , ..., an) = 1}. (iii) Ta quy ước mệnh đề là một vị từ 0 ngôi trên một tập M bất kỳ. Nhận xét. Một vị từ hoàn toàn được xác định khi biết miền đúng của nó. Định nghĩa 1.4.2. (i) Giả sử F = F (x1, x2, ..., xn) là vị từ n ngôi xác định trên tập M. Vị từ F được gọi là hằng đúng trên M, ký hiệu là 1, nếu với mọi dãy a = (a1 , a2, ..., an) các phần tử của M ta luôn có F |a = F (a1, a2 , ..., an) = 1. (ii) Giả sử F = F (x1, x2, ..., xn), G = G(x1, x2, ..., xn) là các vị từ n ngôi xác định trên tập M. Vị từ F được gọi là tương đương logic với vị từ G, ký hiệu F ⇔ G nếu F |a = G|a với mọi dãy a = (a1, a2 , ..., an) các phần tử của M. Tương tự như trong đại số mệnh đề ta có các định nghĩa của các phép toán vị từ: phủ định, hội, tuyển, kéo theo, tương đương. Ngoài ra ta còn có các phép toán mới là đặt các lượng từ cho các biến vị từ. Các phép toán này đóng một vai trò hết sức quan trọng. Chính nhờ chúng mà Logic Vị từ trở nên phong phú hơn nhiều so với Đại số Mệnh đề. Có hai lượng từ, lượng từ tồn tại, ký hiệu ∃, và lượng từ với mọi (hay 9 phổ biến ), ký hiệu là ∀. Chúng ứng với điều được biểu thị trong ngôn ngữ thông thường bởi các từ "có một" và "với mọi" (hay "tất cả", "bất kỳ"). Định nghĩa 1.4.3. Giả sử F = F (x1, x2, ..., xn) là một vị từ n ngôi xác định trên tập M, n ≥ 1. Đặt lượng từ tồn tại trước biến xi, trong đó i ∈ {1, 2, ..., n}, ta được vị từ n − 1 ngôi của các biến đối đượng x1, ..., xi−1, xi+1, ..., xn xác định trên M, ký hiệu ∃xi F (x1, x2, ..., xn). Với mỗi dãy (a1, ..., ai−1, ai+1, ..., an) ∈ M n−1 ta có giá trị của vị từ n − 1 ngôi ∃xiF (x1, x2, ..., xn) là: ( 1 nếu ∃ai ∈ M : F (a1 , ..., ai, ..., an) = 1 ∃xi F |a = 0 nếu ∀ai ∈ M : F (a1 , ..., ai, ..., an) = 0 Biến xi gọi là biến ràng buộc, các biến còn lại gọi là biến tự do. Đặc biệt, giả sử F (x) là một vị từ 1 ngôi xác định trên M. Khi đó ∃xF (x) là một vị từ 0 ngôi, tức là một mệnh đề sao cho ∃xF (x) = 1 khi và chỉ khi EF (x) 6= ∅. Bảng giá trị chân lý EF (x) ∃xF (x) EF (x) 6= ∅ 1 EF (x) = ∅ 0 Ví dụ: Trên R, vị từ F (x) :′′ x2 + 1 = 0” luôn sai nên vị từ "Tồn tại x để x2 + 1 = 0" là sai. Tuy nhiên trên C vị từ không ngôi trên đúng. Định nghĩa 1.4.4. Giả sử F = F (x1, x2, ..., xn) là một vị từ n ngôi xác định trên tập M, n ≥ 1. Đặt lượng từ với mọi trước biến xi , trong đó i ∈ {1, 2, ..., n}, ta được vị từ n − 1 ngôi của các biến đối đượng x1, ..., xi−1, xi+1, ..., xn xác định trên M, ký hiệu ∀xi F (x1, x2, ..., xn). Với mỗi dãy (a1, ..., ai−1, ai+1, ..., an) ∈ M n−1 ta có giá trị của vị từ n − 1 ngôi ∀xiF (x1, x2, ..., xn) là: ( 1 nếu ∀ai ∈ M : F (a1 , ..., ai, ..., an) = 1 ∀xi F |a = 0 nếu ∃ai ∈ M : F (a1 , ..., ai, ..., an) = 0 Biến xi gọi là biến ràng buộc, các biến còn lại gọi là biến tự do. Đặc biệt, giả sử F (x) là một vị từ 1 ngôi xác định trên M. Khi đó ∀xF (x) là một vị từ 0 ngôi, tức là một mệnh đề sao cho ∀xF (x) = 1 khi 10 và chỉ khi EF (x) = M. Bảng giá trị chân lý EF (x) ∀xF (x) EF (x) = M 1 EF (x) 6= M 0 Ví dụ: Trên R, vị từ F (x) : ”(x + 1)2 ≤ 0” luôn đúng nên mệnh đề với mọi x ta có (x + 1)2 ≤ 0 là mệnh đề đúng. 1.5. Tính sắp thứ tự tốt của tập số tự nhiên Cho X là một tập hợp khác rỗng. Một tập con của tích Descartes X × X được gọi là một quan hệ (hai ngôi) trên X. Ta thường kí hiệu các quan hệ hai ngôi bằng các chữ cái ∼, 6, R, S, T, . . . . Cho R là một quan hệ hai ngôi trên X. Nếu (a, b) ∈ R thì ta viết aRb. Trong trường hợp này ta nói a quan hệ với b. Dưới đây là một số tính chất quan trọng mà R có thể có (i) Phản xạ: aRa với mọi a ∈ X. (ii) Đối xứng: Nếu aRb thì bRa với mọi a, b ∈ X. (iii) Phản đối xứng hay phản xứng: Nếu aRb và bRA thì a = b với mọi a, b ∈ X. (iv) Bắc cầu: Nếu aRb và bRc thì aRc với mọi a, b, c ∈ X. Định nghĩa. Một quan hệ trên tập hợp X được gọi là quan hệ thứ tự nếu nó phản xạ, đối xứng và bắc cầu. Theo truyền thống, quan hệ thứ tự thường được kí hiệu bởi 6 . Nếu a 6 b thì ta đọc là a nhỏ hơn hay bằng b hoặc b lớn hơn hay bằng a. Một tập hợp X được gọi là tập sắp thứ tự nếu nó có trang bị một quan hệ thứ tự. Cho X là một tập sắp thứ tự với quan hệ thứ tự 6 . (i) Tập X được gọi là sắp thứ tự toàn phần hay sắp thứ tự tuyến tính nếu a 6 b hoặc b 6 a với mọi a, b ∈ X. (ii) Cho a ∈ X. Ta nói a là phần tử lớn nhất (tương ứng, nhỏ nhất) nếu x 6 a với mọi x ∈ X (tương ứng, a 6 x với mọi x ∈ X). (iii) Tập X được gọi là sắp thứ tự tốt nếu mọi tập con khác rỗng của X đều có phần tử bé nhất. Ta sử dụng một tính chất rất quan trọng của tập các số tự nhiên, thường người ta công nhận như một tiên đề (được gọi là tiên đề thứ tự). Tiên đề 1.5.1. Tập các số tự nhiên là tập sắp thứ tự tốt. 11 Chương 2 Phương pháp chứng minh phản chứng 2.1. Một số dạng chứng minh phản chứng Trong toán học phương pháp phản chứng được sử dụng rất sớm. Ta bắt đầu bằng việc chứng minh nguyên lý Đirichlê (còn gọi là nguyên lý lồng và thỏ), nguyên lý có rất nhiều ứng dụng. Người ta nhốt thỏ vào trong một số lồng, biết rằng số thỏ nhiều hơn số lồng. Chứng minh rằng có ít nhất hai con thỏ được nhốt trong cùng một lồng. Để chứng minh ta giả sử ngược lại mỗi lồng chỉ nhốt nhiều nhất có một con thỏ, như vậy số thỏ nhỏ hơn hoặc bằng số lồng, mà theo giả thiết số thỏ nhiều hơn số lồng. Điều này dẫn đến vô lý. Từ đó ta có điều phải chứng minh. Tại sao lại như vậy? Đề lý giải điều này ta xuất phát từ kết quả sau trong Đại số mệnh đề cũng gọi là quy tắc phản chứng. Định lý 2.1.1. Cho P, Q là các công thức của đại số mệnh đề. Khi đó ta có quy tắc suy luận sau P → Q, P → Q . P Chứng minh. Theo nhận xét cần chứng minh A = (P → Q) ∧ (P → Q) → P là hằng đúng. Gọi e là dãy giá trị chân lý của các biến mệnh đề chung của các công thức P và Q và đặt B = ((P → Q) ∧ (P → Q)), ta có P |e Q|e P |e Q|e (P → Q)|e (P → Q)|e B|e A|e 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 12 Dựa trên quy tắc suy luận trên ta có nội dung phương pháp chứng minh phản chứng: Giả sử ta phải chứng minh một mệnh đề P nào đó là đúng, ta giả thiết ngược lại P đúng và chỉ ra một mệnh đề Q vừa đúng vừa sai, tức là chứng minh các mệnh đề P → Q, P → Q là đúng. Khi đó ta kết luận P là đúng. Chú ý: Ta có thể giải thích trực tiếp cơ sở của quy tắc phản chứng như sau: Ta có P → Q, P → Q. Mặt khác bằng cách lập bảng ta có quy tắc suy luận A → B, A → C , A→B∧C với A, B, C là các công thức. Do đó P → Q ∧ Q đúng hay P → 0 đúng. Kéo theo P sai. Điều này suy ra P đúng. Trong ví dụ mở đầu, đặt P là mệnh đề: "ít nhất hai con thỏ được nhốt trong cùng một lồng". Phủ định mệnh đề ta được hai mệnh đề Q: "số thỏ nhiều hơn số lồng" và Q: "số thỏ nhỏ hơn hoặc bằng số lồng". Như vậy P được chứng minh. √ Ví dụ 2.1.2. Chứng minh rằng 3 3 là một số vô tỉ. √ Chứng √ minh. Gọi P là mệnh đề " 3 3 là một số vô tỉ". Giả sử ngược lại tức là 3 3 là√một số hữu tỉ. Do đó tồn tại các số nguyên a và b sao cho: a/b =√ 3 3; (a, b) = 1. Đặt Q là mệnh đề "a, b ∈ Z, (a, b) = 1". Vì a/b = 3 3 nên 3b3 = a3 , kéo theo 3 chia hết a. Gọi a = 3m thì 3b2 = 27m3. Từ đó suy ra 3 chia hết b. Từ trên ta có 3 chia hết (a, b). Vậy ta có mệnh đề Q "(a, b) 6= 1". Điều mâu thuẫn này chứng tỏ P đúng. Các bài toán thường được phát biểu dưới dạng p → q. Ta sẽ phân tích một số dạng chứng minh phản chứng mệnh đề dạng này. Trước hết theo Ví dụ 1.2.4 và tính chất của các phép toán mệnh đề ta có p → q ⇔ p ∨ q ⇔ p ∧ q nên ta có quy tắc phủ định một mệnh đề dạng kéo theo: Muốn phủ định một mệnh đề dạng kéo theo ta "ghép" giả thiết của mệnh đề với phủ định kết luận của nó. Chữ "ghép" ở đây có nghĩa là giả thiết bài toán mới bao gồm giả thiết của bài toán cũ và kết luận của nó. Từ đó ta thiết lập được một số dạng chứng minh phản chứng mệnh đề p → q như sau: 13 Dạng 1. Phủ định mệnh đề rồi suy ra điều trái với điều đúng (các tiên đề, các định lý đã được chứng minh): p ∧ q → 0. Cơ sở logic: Vì p ∧ q → 0 đúng nên p ∧ q sai, suy ra p ∧ q ⇔ p → q đúng. Ví dụ 2.1.3. Cho n > 1 và a1 , a2, ..., an là các số tự nhiên. Chứng minh rằng nếu a1 , a2 , ..., an là các số phân biệt thì không thể có đẳng thức 1 1 1 + + ... + = 1. a21 a22 a2n Chứng minh. Giả sử ta có đẳng thức 1 1 1 1 = 2 + 2 + ... + 2 . a1 a2 an Vì a1 , a2 , ..., an là các số phân biệt nên không mất tính tổng quát ta có thể giả sử a1 < a2 < ... < an . Dễ thấy a1 ≥ 2 ta nhận được ak ≥ k + 1, vì thế 1 1 1 2 + 2 + ... + 2 a1 a2 an 1 1 1 1 1 1 < + + ... + ≤ 2 + 2 + ... + 2 3 1.2 2.3 n(n + 1) (n + 1)2 1 1 1 1 1 1 = (1 − ) + ( − ) + ... + ( − )=1− < 1. 2 2 3 n n+1 n+1 Điều này vô lý. 1= Dạng 2. Phủ định mệnh đề rồi suy ra hai điều trái nhau p ∧ q → r ∧ r. Cơ sở logic: Vì r ∧ r ⇔ 0 nên khẳng định được suy ra từ Dạng 1. Ví dụ 2.1.4. Chứng minh rằng nếu hai đường thẳng cắt một đường thẳng tạo thành một cặp góc so le trong bằng nhau thì hai đường thẳng đó không có điểm chung. c3 = B c1 . Kết luận A và B không có điểm chung Chứng minh. Giả thiết A C. Ta đã biết trong tam giác ABC tổng hai góc A và B nhỏ hơn 1800. Suy ra góc c4 + B c1 < 1800. (1) A c3 = B c1 nên A c4 + B c1 = A c4 + A c3 . Nhưng A c4 + A c3 = 1800 hai góc bù Vì A nhau. Nên c4 + B c1 = 1800. (2) A 14 3 b c A a 2 a 4 1 c A 3 b B 4 C 2 1 B Từ (1) và (2) theo Dạng 2 của phương pháp chứng minh phản chứng ta kết luận a và b không có điểm chung. Dạng 3. Phủ định mệnh đề rồi suy ra điều trái với giả thiết: p ∧ q → p. Cơ sở logic: Vì ta có p ∧ q → p, kết hợp p ∧ q → p, theo luật phản chứng ta có p ∧ q ⇔ p → q đúng. Ví dụ 2.1.5. Chứng minh rằng một đa giác lồi n cạnh với n lẻ không thể chia ra thành những hình bình hành. Chứng minh. Ta giả sử một đa giác lồi n cạnh có thể cắt thành những hình bình hành. Khi đó mỗi cạnh của đa giác sẽ là một cạnh của hình bình hành và suy ra những cạnh của đa giác sẽ là đôi một song song cùng nhau (ba cạnh không thể song song cùng nhau vì đa giác là lồi). Nhưng trong trường hợp như vậy đa giác sẽ có số cạnh chẵn, nhưng giả thiết cho n lẻ. Suy ra đa giác loại này không thể chia ra thành những hình bình hành. Dạng 4. Phủ định mệnh đề rồi suy ra kết luận của mệnh đề: p ∧ q → q. Cơ sở logic: Vì ta luôn có p ∧ q → q, mà p ∧ q → q nên theo luật phản chứng ta có p ∧ q ⇔ p → q đúng. Ví dụ 2.1.6. Cho a là môt số tự nhiên. Chứng minh rằng nếu a là bội của 6 thì a là bội của 2. Chứng minh. Giả sử a là bội của 6 nhưng a không là bội của 2. Vì a là bội của 6 nên ta có a = 6b với b ∈ N. Do đó a = 2(3b) kéo theo a chia hết cho 2. Vậy ta có điều phải chứng minh. Chý ý ở dạng này ta đã chứng minh được kết luận do đó ta nên dùng phương pháp chứng minh trực tiếp: nếu p đúng thì q đúng. Chú ý: Ta cần phân biệt chứng minh phản chứng (proof by contradiction) và chứng minh phản đảo (proof by contrapositive). Chứng 15 minh phản đảo mệnh đề p → q là ta giả sử q sai và chứng minh p sai. Cơ sở logic của phương pháp là tương đương logic p → q ⇔ q → p. Trong khi chứng minh phản chứng dạng mệnh đề này là ta giả sử đồng thời p đúng và q sai rồi dẫn đến điều vô lý. Ví dụ 2.1.7. Cho A, B là các tập hợp thỏa mãn A ⊆ B. Chứng minh rằng nếu x ∈ / B thì x ∈ / A. Chứng minh. Chứng minh bằng phản chứng: Giả sử x ∈ / B và x ∈ A. Vì A ⊆ B nên x ∈ B. Điều này là vô lý dẫn đến điều phải chứng minh. Chứng minh bằng phản đảo: Giả sử x ∈ A. Vì A ⊆ B nên x ∈ B. Do đó ta có điều phải chứng minh. Tương tự như trong Đại số mệnh đề, phương pháp chứng minh phản chứng có thể được áp dụng cho các công thức trong Đại số vị từ. Ta tìm hiểu chứng minh phản chứng của các mệnh đề dạng (i) (∀x ∈ Ux )P (x), (ii) (∀x ∈ Ux )(P (x) −→ Q(x)). Nguyên lý chung là ta tìm các mệnh đề phủ định rồi dẫn đến các điều vố lý. Điểm cần quan tâm ở đây là tìm các mệnh đề phủ định của các mệnh đề trên. Ta có (i) (∀x ∈ Ux )P (x) ⇔ (∃x ∈ Ux )P (x), (ii) (∀x ∈ Ux )(P (x) −→ Q(x)) ⇔ (∃x ∈ Ux )(P (x) ∧ Q(x). Thật vậy ta có bảng giá trị chân lý với chú ý EP (x) = Ux \ EP (x) EP (x) (∀x ∈ Ux )P (x) (∀x ∈ Ux )P (x) (∃x ∈ Ux )P (x) EP (x) EP (x) = Ux EP (x) = ∅ 1 0 0 Do đó ta có (i) chứng minh tương tự ta có (ii). Ví dụ 2.1.8. (i) Chứng minh rằng với mọi số thực dương x, ta có x+1 x < . x+1 x+2 (ii) Với mọi số thực x. Chứng minh rằng nếu x > 0 thì x + Chứng minh. (i) Giả sử tồn tại số thực x thỏa mãn x+1 x ≥ x+1 x+2 16 1 x ≥ 2. Vì x dương nên x + 1 và x + 2 dương. Nhân hai vế với (x + 1)(x + 2) rồi rút gọn dẫn đến 0 ≥ 1. Điều vô lý này dẫn đến bài toán được chứng minh. (ii) Giả sử tồn tại x > 0 và x + x1 < 2. Từ đó ta có (x − 1)2 < 0. Điều này là vô lý. Do đó ta có điều phải chứng minh. 2.2. Một số bài toán chứng minh bằng phản chứng Trong mục này ta phân tích một số bài toán chứng minh bằng phản chứng. Một số ví dụ đầu mục được phân tích bởi các luật logic nhằm hiểu cặn kẽ hơn các lập luận. Tiếp theo luận văn trình bày một số bài toán về tính vô hạn của số nguyên tố,ứng dụng phần tử cực biên và phương pháp chứng minh phản chứng, các bài toán trong hình học, phương trình nghiệm nguyên, .... Đặc biệt trong phần cuối của mục chúng tôi trình bày phương pháp chứng minh bất đẳng thức bằng phản chứng. Ví dụ 2.2.1 (Đề Thi học sinh giỏi Tiệp Khắc 1959). Cho các số a, b, c thỏa điều kiện    a + b + c > 0 ab + bc + ca > 0 ,   abc > 0 Chứng minh rằng a > 0, b > 0, c > 0. Chứng minh. Giả thiết: A = A1 ∧ A2 ∧ A3, kết luận: B = B1 ∧ B2 ∧ B3 , trong đó:   ′′ ′′ ′′ ′′      A1 = a + b + c > 0 B1 = a > 0 A2 =′′ ab + bc + ca >′′ B2 =′′ b > 0′′ .     A =′′ abc > 0′′ , B =′′ c > 0′′ 3 3 Ta chứng minh bằng phương pháp phản chứng. Ta xét A ∧ B. Điều này tương đương với ⇔ A ∧ B1 ∧ B2 ∧ B3 ⇔ A ∧ (B 1 ∨ B 2 ∨ B 3 ) ⇔ (A ∧ B 1 ) ∨ (A ∧ B 2 ) ∨ (A ∧ B 3 ). 17 Hướng của ta tìm mệnh đề D (chẳng hạn A, B, O, C ∧ C...). Theo luật A∨B →C logic , ta có A → C, B → C (A ∧ B → D) ⇔ ((A ∧ B 1 ) ∨ (A ∧ B 2) ∨ (A ∧ B 3) → D) ⇔ (A ∧ B 1 → D) ∧ (A ∧ B 2 → D) ∧ (A ∧ B 3 → D). Vậy ta phải xét 3 trường hợp B 1 , B 2 , B 3 hay a ≤ 0, b ≤ 0, c ≤ 0. Giả sử a ≤ 0 từ A3 ta phải có a 6= 0 do đó a < 0 ta suy ra bc < 0. Từ A2 suy ra a(b + c) = −bc > 0 → b + c < 0 ( vì a < 0.) Suy ra a + b + c < 0 mâu thuẫn với (A1 hay với A.) Từ đó ta có A ∧ B 1 → A theo Dạng 2 suy ra a > 0. Tương tự cho các trường hợp b ≤ 0, c ≤ 0. Tuy nhiên ta có thể kết luận vì vai trò của a, b, c như nhau nên ta có a > 0, b > 0, c > 0. Ví dụ 2.2.2. Cho 4 số a, b, c, d thỏa mãn điều kiện: ac ≥ 2(b+d). Chứng minh rằng có ít nhất 1 trong 2 bất đẳng thức sau là sai: a2 < 4b; c2 < 4d. Chứng minh. Giả thiết A: ′′ac ≥ 2(b + d)′′. Kết luận: C ∨ B trong đó C :′′ a2 < 4b′′ B :′′ c2 < 4d”. Như vậy phủ định kết luận là C ∨ B ⇔ C ∧ B. Tức ta có cả 2 bất đẳng thức a2 < 4b ; c2 < 4d Cộng 2 bất đẳng thức trên ra có: a2 + c2 < 4(b + d) ≤ 2ac ( kết hợp giả thiết A). Suy ra a2 + c2 < 2ac ⇔ (a − c)2 < 0. Điều này là vô lý. Theo Dạng 1 của phương pháp chứng minh phản chứng ta có điều phải chứng minh. Trong phần tiếp theo ta đề cập đến một số bài toán điển hình sử dụng phương pháp phản chứng mà không phân tích quy tắc sử dụng trong đó. Trước hết ta đề cập một số bài toán chứng minh phản chứng liên quan đến số nguyên tố. Ví dụ 2.2.3. Chứng minh rằng tập các số nguyên tố là vô hạn. 18