Tài liệu Toán rời rạc 1

Toán rời rạc 1 Biên tập bởi: Khoa CNTT ĐHSP KT Hưng Yên Toán rời rạc 1 Biên tập bởi: Khoa CNTT ĐHSP KT Hưng Yên Các tác giả: Khoa CNTT ĐHSP KT Hưng Yên Phiên bản trực tuyến: http://voer.edu.vn/c/b8a0fb4b MỤC LỤC 1. Bài 1: Tổng quan môn học 2. Bài 2: Logic 2.1. Logic 2.2. Logic vị từ (predicate logic)) 3. Bài 3: Một số phương pháp chứng minh 3.1. chứng minh các mệnh đề suy diễn 3.2. Chứng minh nhờ luật suy diễn 3.3. Chứng minh vacuous & Chứng minh trivial 3.4. Chứng minh bằng cách phân chia trường hợp 4. Bài 4: Lý thuyết về bài tập 4.1. giới thiệu về tập 4.2. các phép toán trên tập hợp 4.3. lực lượng của tập hợp - Hữu hạn và vô hạn 5. Bài 5: Hàm, dãy, tổng 5.1. giới thiệu về hàm 5.2. chuỗi 6. Bài 6: Thuật toán, số, ma trận và đệ quy 6.1. Ma trận (Matrices) 7. Bài 7: Kỹ thuật đếm cơ bản 7.1. Nguyên lý bù trừ 7.2. nguyên lý DIRICHLET 7.3. Chỉnh hợp và tổ hợp 8. Bài 8: Kỹ thuật đếm cao cấp 8.1. quan hệ ngôi n- những ứng dụng Tham gia đóng góp 1/72 Bài 2: Logic Logic LOGIC Logic sử dụng để biểu diễn những luận điểm chính xác các mênh đề toán học. Những luật trong logic được dùng để phân biệt những luận điểm đúng và sai. Bài học này cũng giúp người học cách thức để hiểu và xây dựng các luận điểm toán học đúng đắn. Logic là nội dung trung tâm của khoa học máy tính từ khi ngành này được hình thành: công trình của Alan Turing về Entscheidungsproblem theo sau từ công trình của Kurt Gödel về các định lý về sự không toàn vẹn, và khái niệm của các máy tính dành cho mục đích tổng quát bắt nguồn từ công trình này đã có tầm quan trọng mang tính nền tảng đối với các nhà thiết kế máy tính trong những năm 1940. Trong những năm 1950 và 1960, các nhà nghiên cứu dự đoán rằng khi tri thức của con người có thể được biểu diễn bằng logic và các ký hiệu toán học, sẽ có khả năng tạo ra một máy tính có khả năng lập luận, hay nói cách khác là trí tuệ nhân tạo. Điều này hóa ra là khó khăn hơn đã dự đoán do sự phức tạp trong lập luận của con người. Trong lập trình logic, một chương trình bao gồm một tập hợp các tiên đề và các luật. Các hệ thống lập trình logic như Prolog tính toán các hệ quả của các tiên đề và luật để trả lời một truy vấn. Ngày nay, logic được ứng dụng rộng rãi trong các lãnh vực của trí tuệ nhân tạo, và khoa học máy tính, và những ngành này cung cấp một nguồn dồi dào các bài toán trong logic hình thức và phi hình thức. Lý thuyết lý luận là một ví dụ tốt cho thấy logic được áp dụng vào trí tuệ nhân tạo như thế nào. Thêm vào đó, máy tính có thể được sử dụng như công cụ cho các nhà logic học. Ví dụ, trong logic biểu tượng và logic toán học, các chứng minh bởi con người có thể được hỗ trợ bởi máy tính. Sử dụng chứng minh định lý tự động, máy tính có thể tìm ra và kiểm tra các chứng minh, cũng như là làm việc với những chứng minh quá dài cho việc viết ra 2/72 Logic vị từ (predicate logic)) LOGIC VỊ TỪ (pre d icate logic) V ị từ Ta xét các ví dụ sau: Ví dụ 1: "Số tự nhiên n chia hết cho 5". Về phương diện ngôn ngữ thì đây là một câu. Nhưng câu này chưa phản ánh tính đúng hoặc sai một thực tế khách quan nào, cho nên nó chưa phải là mệnh đề. Song nếu ta thay n bằng số tự nhiên cụ thể, chẳng hạn: Thay n = 100 ta được mệnh đề đúng: "Số 100 chia hết cho 5". Thay n = 101 ta được mệnh đề sai: "Số 101 chia hết cho 5". Ví dụ 2: "x + 3 > 7". Tương tự như trong ví dụ 1, x + 3 > 7 chưa phải là mệnh đề, song nếu ta thay x bởi một số thực cụ thể, chẳng hạn: Thay x = 0 ta được mệnh đề sai: "0 + 3 > 7". Thay x = 5 ta được mệnh đề đúng: "5 + 3 > 7". Ví dụ 3: "Ông A là nhà toán học vĩ đại". Câu trên chưa phải là mệnh đề. Nhưng nếu ta chọn "ông A" là "Gausơ" sẽ được mệnh đề đúng: "Gausơ là nhà toán học vĩ đại", nếu ta chọn "ông A" là "Đinh Bộ Lĩnh" thì sẽ được mệnh đề sai: "Đinh Bộ Lĩnh là nhà toán học vĩ đại". Từ các ví dụ trên ta đi đến định nghĩa sau: Những câu có chứa các biến mà bản thân nó chưa phải là mệnh đề nhưng khi ta thay các biến đó bởi các phần tử thuộc tập xác định X thì nó trở thành mệnh đề (đúng hoặc sai) ta sẽ gọi là hàm mệnh đề (hoặc vị từ, hàm phán đoán, mệnh đề không xác định, mệnh đề chứa biến). Tập X gọi là miền xác định của hàm mệnh đề đó. Ta dùng kí hiệu: T(n), F(x),... để chỉ các vị từ. 3/72 Chẳng hạn: vị từ T(n) : "Số tự nhiên n chia hết cho 5" có miền xác định là tập các số tự nhiên N. Tập các số tự nhiên có tận cùng bằng 0 hoặc 5 là miền đúng của T(n). vị từ F(x) = "x + 3 > 7" có miền xác định là các số thực. Tập các số thực lớn hơn 4 ta gọi là miền đúng của vị từ F(x). L ư ợ n g từ Mệnh đề tồn tại Cho T(x) là hàm mệnh đề xác định trên miền X. Nếu ta đặt thêm cụm từ "Tồn tại sao cho ..." vào trước hàm mệnh đề T(x) ta được mệnh đề: "Tồn tại sao cho T(x)" Ta gọi mệnh đề có cấu trúc như trên là mệnh đề tồn tại. Kí hiệu là: hoặc Kí hiệu gọi là lượng từ tồn tại. Ví dụ: "Tồn tại số thực x sao cho x + 4 > 7" là mệnh đề đúng. Kí hiệu là: 4/72 "Tồn tại số tự nhiên n sao cho n chia hết cho 5" là mệnh đề đúng. Kí hiệu là: "Tồn tại số thực x sao cho x2 + 1 = 0" là mệnh đề sai. Chú ý: Kí hiệu là: 1. Trong thực tế, mệnh đề tồn tại còn được diễn đạt dưới những dạng khác nhau, chẳng hạn: "Tồn tại ít nhất một sao cho T(x)". "Có một sao cho T(x)". "Có ít nhất một sao cho T(x)". "Ít ra cũng có một người là nhà toán học". "Một số người là nhà toán học". "Có nhiều người là nhà toán học" 2. Ta dùng kí hiệu với nghĩa "Tồn tại duy nhất một 5/72 sao cho T(x)". Mệnh đề tổng quát Cho T(x) là hàm mệnh đề xác định trên miền X. Nếu ta đặt thêm cụm từ "Với mọi ta có ..." vào trước hàm mệnh đề T(x) ta được mệnh đề: "Với mọi ta có T(x)" Ta gọi mệnh đề có cấu trúc như trên là mệnh đề tổng quát (hoặc toàn thể, phổ biến, phổ cập,...). Kí hiệu là: hoặc hoặc Kí hiệu gọi là lượng từ tổng quát (hay toàn thể, phổ biến, phổ cập,...) Ví dụ: "Với mọi số tự nhiên n ta có n chia hết cho 5" là mệnh đề sai. Kí hiệu là: "Với mọi số thực x ta có x + 3 > 7" là mệnh đề sai. 6/72 Kí hiệu là: ? "Với mọi số thực x ta có x2 + 1 > 0" là mệnh đề đúng. Kí hiệu là: Chú ý: Trong thực tế, mệnh đề tổng quát thường được diễn đạt dưới nhiều hình thức khác nhau, chẳng hạn: ? "Tất cả người Việt Nam đều nói tiếng Anh". ? "Mọi người Việt Nam đều nói thạo tiếng Anh". ? "Người Việt Nam nào cũng nói thạo tiếng Anh". ? "Đã là người Việt Nam thì ai chẳng nói thạo tiếng Anh". ? .................... Phủ định của mệnh đề tồn tại và tổng quát Phủ định các mệnh đề tồn tại và tổng quát được thiết lập theo hai quy tắc dưới đây: 7/72 Như vậy, hai mệnh đề: ? và là phủ định của nhau. ? và là phủ định của nhau. Ví dụ: ? Kí hiệu là: ? 8/72 Bài 3: Một số phương pháp chứng minh chứng minh các mệnh đề suy diễn C HỨ N G M I N H C Á C M Ệ N H Đ Ề SUY D I ỄN Bây giờ chúng ta sẽ làm rõ hơn về các phương pháp xây dựng chứng minh, chúng ta sẽ mô tả các chứng minh cho các loại mệnh đề khác nhau. Trong nhiều định lý, kỹ thuật chứng minh các mệnh đề kiểu kéo theo là quan trọng. Ta thấy p→q sẽ luôn đúng trừ khi p là đúng nhưng q sai. Chú ý rằng khi p→q được chứng minh, nếu chúng ta chỉ cần chỉ ra q là đúng nếu p đúng; C h ứ n g m i n h tr ự c tiếp Ta thấy p→q sẽ được chứng minh bằng cách chỉ ra p là đúng, sau đó q phải là đúng. Điều này cho thấy rằng không thể có p đúng và q sai cùng xảy ra. Một chứng minh như vậy được gọi là chứng minh trực tiếp. Để áp dụng chứng minh kiểu này, giả định p là đúng và dùng luật suy diễn cùng các định lý đã được chứng minh để chỉ ra rằng q phải là đúng. Chứng minh trực tiếp là phương pháp chứng minh suy diễn trực tiếp dẫn từ giả thiết đến kết luận thông qua việc áp dụng các luật suy diễn (hay qui tắc suy diễn), các định lý, các nguyên lý và các kết quả đã biết. Ðây là một kiểu tư duy giải bài toán rất tự nhiên và người ta thường xuyên sử dụng. Trong khi suy nghĩ để tìm ra cách chứng minh theo phương pháp nầy người ta thường phải tự trả lời các câu hỏi sau đây: - Ta sẽ dùng luật suy diễn nào? - Các định lý nào, các kết qua nào có thể sử dụng được đề ta suy ra được một điều gì đó từ những sự kiện, những yếu tố hiện đang có? - Việc áp dụng định lý có khả năng sẽ dẫn đến kết luận hay kết quả mong muốn hay không? 9/72 - Trong trường hợp ở một bước suy diễn nào đó có nhiều định lý hay nhiều luật nào đó có thể áp dụng được và cũng có kkhả năng sẽ dẫn đến kết luận hay kết quả mong muốn thì ta sẽ chọn cái nào? - Ðến một giai đoạn nào đó, khi gặp phải sự bế tắc thì ta sẽ phải tự hỏi rằng phải chăng bài toán không có lời giải, hay vì kiến thức của ta chưa đủ, hay ta phải sử dụng một phương pháp chứng minh nào khác? Quả thật là không thể trả lời được các câu hỏi một cách đầy đủ và chính xác. Nó phụ thuộc chủ yếu vào kiến thức, kinh nghiệm của người giải bài toán và cả sự nhạy bén, tính năng động sáng tạo của họ. Tuy nhiên Những câu hỏi trên cho ta một sự định hướng chung của quá trình suy nghĩ. Ngoài ra, cũng cần nói thêm rằng chúng là cơ sở cho việc phát triển các hệ chương trình trợ giúp giải toán một cách "thông minh" trên máy tính được thiết kế theo phương pháp chứng minh nầy. Dưới đây, chúng ta sẽ xem xét một vài ví dụ về phương pháp chứng minh trực tiếp. Vídụ1:Chứng minh rằng { Nếu n là số lẻ thì n2 là số lẻ } Giải : Giả sử rằng giả thiết của định lý này là đúng, tức là n là số lẻ. Ta có n = 2k + 1 ( k=0,1,2,...) ? n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1 là lẻ. Vậy nếu n là số lẻ thì n2 là số lẻ. Vídụ2:Cho hàm mệnh đề P(n) = " Nếu n>1 thì n2 >n " Chứng minh rằng P(n) là đúng với n là số nguyên dương. Giải : Giả sử n > 1 là đúng, ta có : n = 1 + k ( k ≥ 1) ? n2 = ( 1 + k )2 = 1 + 2k + k2 = (1 + k) + k + k2 > n Vậy Nếu n>1 thì n2 >n . Vídụ3Giả sử p, r, s, t, u là các mệnh đề sau cho ta có các mệnh đề sau đây la` đúng: 10/72 (1) p →r (2) r → s (3) t ∨ ? s (4) ? t ∨ u (5) ? u. Hãy chứng minh mệnh đề p là sai, tức là chứng minh mệnh đề ? p la` đúng. C h ứ n g m i nh : Áp dụng luật suy diễn tam đoạn luận, từ (1) và (2) ta suy ra: (6) p → s Áp dụng luật logic về phép toán kéo theo ta có thể viết lại (3) dưới dạng: (7) s → t Áp dụng luật suy diễn tam đoạn luận, từ (6) và (7) ta suy ra: (8) p → t Áp dụng luật logic về phép toán kéo theo ta có thể viết lại (4) dưới dạng: (9) t → u Áp dụng luật suy diễn tam đoạn luận, từ (8) và (9) ta suy ra: (10) p → u Áp dụng luật suy diễn Modus Tollens, từ (10) và (5) ta suy ra: (11) ? p Vậy mệnh đề ? p là đúng. Vídụ4:Cho p(x), q(x) và r(x) là các vị từ theo biến x (x ∈ A), và a là một phần tử cố định nhưng tùy ý của tập hợp A. Giả sử ta có các mệnh đề sau đây la` đúng: Chứng minh rằng mệnh đề r(a) la` đúng. C h ứ n g m i nh : Áp dụng kết quả từ bảng 3 trong 3.2 ta suy ra: (4) x∈ A : p(x) → r(x) Áp dụng kết quả bảng 3 trong 3.2 ta suy ra: (5) r(a) Vậy mệnh đề r(a) la` đúng. 11/72 3 . 3 . 2 C h ứ n g m i n h gi á n tiếp Vì mệnh đề P→Q ⇔ (¬Q → ¬P). Do đó, để chứng minh mệnh đề P→Q là đúng, người ta có thể chỉ ra rằng mệnh đề ¬Q → ¬P là đúng. Vídụ 5:Chứng minh định lý { Nếu 3n + 2 là số lẻ thì n là số lẻ } Giải : Giả sử ngược lại kết luận của phép kéo theo là sai, tức n là chẳn. Ta có n = 2k( k∈ N ) 3n + 2 = 3.2k + 2 = 2( 3k + 1 ) là số chẳn Vậy Nếu 3n + 2 là số lẻ thì n là số lẻ Nh ậ n x ét Có những bài toán có thể sử dụng phương pháp chứng minh trực tiếp hay gián tiếp đều được cả. Tuy nhiên, có những bài toán không thể sử dụng phương pháp chứng minh trực tiếp được hoặc sử dụng trực tiếp thì bài giải sẽ dài dòng phức tạp hơn là sử dụng chứng minh gián tiếp ( hoặc ngược lại). Đây chính là sự khác biệt của chứng minh trực tiếp và chứng minh gián tiếp. Ví d ụ 6 : Sử dụng chứng minh gián tiếp để chứng minh rằng " Nếu n>1 thì n2 >n " Giải : Giả sử ngược lại kết luận của phép kéo theo là sai, tức là n2 < n Vì n là nguyên dương nên ta có thể chia 2 vế cho n mà bất đẳng thức không đổi chiều. Ta có : n < 1. Vậy từ ¬Q đã dẫn đến ¬P. Do đó, Nếu n>1 thì n2 >n. Vídụ7:Sử dụng chứng minh trực tiếp để chứng minh rằng " Nếu 3n + 2 là số lẻ thì n là số lẻ ". Giải : Giả sử 3n + 2 là số lẻ là đúng. Nhận thấy rằng vì 2 là số chẳn nên suy ra được 3n là số lẻ. Vì 3 là số lẻ do đó n là số lẻ. Vậy Nếu 3n + 2 là số lẻ thì n là số lẻ. 12/72 Ởđâychúngta phảichứngminhthêmđịnhlýlàtíchcủa2sốlẻlàmộtsốlẻthì bàigiảichặtchẽhơn.Dođó,trongbàitoánnàyviệcsửdụngchứngminhgiántiếp làhayhơndùngtrựctiếp. 13/72 Chứng minh nhờ luật suy diễn Chứng minh nhờ luật suy diễn Chúng ta sẽ giới thiệu luật suy diễn cho logic mệnh đề. Những luật này cung cấp cho chúng ta một chuỗi các bước biến đổi để đi tới kết luận một cách logic nhờ tập các giả thiết. Phép lặp thừa (p^(p->q))->q được coi là cơ sở cho luật suy diễn modus ponens p p->q ------- q Modus ponens khẳng định rằng nếu cả giả thiết và phép kéo theo là đúng là đúng thì kết luận của phép kéo theo là đúng. Giả sử “nếu sinh viên làm hết bài tập vê nhà, thì sinh viên sẽ đạt kết quả cao” và nếu giả sử có “sinh viên làm hết bài tập về nhà”, khi đó theo luật modus ponens, kết luận “sinh viên sẽ đạt kết quả cao” là đúng. Sau đây là một số luật suy diễn hay gặp: 1. Luật thay thế: Bất kỳ một biến nào xuất hiện trong một luận cứ đều có thể được thay thế bằng một biểu thức cùng kiểu mà không ảnh hưởng tới sự chính xác của luận điểm với điều kiện là sự thay thế đó phải được làm tại mọi nơi mà biến đó xuất hiện 2. Bảng sau đây đưa ra các luật suy diễn cho các luận điểm 14/72 3. Bảng sau đây đưa ra các luật suy diễn cho các luận điểm cho các vị từ 4. Luật modus ponens tổng quát: R(a)? S(a) với mọi a ∈ D ? ∀z∈ D[ R(z)? S(z)] 15/72 5. Luật generalizingfromthegenericparticular xác định rất nhiều trong toán học 6. Luật existentialspecificationđược dùng để lập luận chỉ ra một số đối tượng tồn tại tuy nhiên không biết đích xác giá trị của nó. Một số ví dụ 16/72 Chứng minh vacuous & Chứng minh trivial C h ứ n g m i n h va c u ous Giả sử giả thiết p trong phép kéo theo p→q là sai. Khi đó ta có thể suy ra ngay phép kéo theo p→q luôn đúng, bởi vì câu lệnh có dạng F→T hay F→F, nên nó luôn đúng. Chính vì vậy, nếu chúng ta chỉ ra p là sai, khi đó phép chứng minh của chúng ta gọi là chứng minh vacuous. Chứng minh vacuous thường dùng cho các trường hợp đặc biệt khi phép kéo theo là đúng cho tất cả các số nguyên dương. Vídụ10: Chứng minh rằng mệnh đề P(0) là đúng trong đó P(n) là mệnh đề “nếu n>1 thì n2>n”. Giải: Mệnh đề P(0) chỉ ra rằng “nếu 0>1 thì 02>0”. Bởi vì giả thiết 0>1 là sai, do đó P(0) là đúng. Ví d ụ 11: Với mọi n, nếu n vừa lẻ vừa chẵn, thì n2 = n + n. Giải: Khẳng định “n vừa lẻ vừa chẵn” là sai, bởi vì không có số nào vừa lẻ vừa chẵn. Do vậy mọi kết luận là đúng. C h ứ n g m i n h tr i vial Giả sử rằng kết luận q trong phép duy dẫn p→q là đúng. Khi đó p→q là đúng, bởi vì câu lệnh dạng T→T hay F→T đều là đúng. Vì vậy, nếu để chứng minh q là đúng, thì khi đó chứng minh được gọi là chứng minh trivial. Chứng minh trivial thường quan trọng trong khi chứng minh một số trường hợp đặc biệt. Ví d ụ 12: Coi P(n) là mệnh đề: “nếu a và b là hai số nguyên dương và a>=b thì an>=bn”. Chứng minh rằng P(0) là đúng. 17/72 Giải: Mệnh đề P(0) là “nếu a>=b, thì a0>=b0 ” bởi vì a0=b0 =1, vậy P(0) là đúng. Vì vậy, P(0) là đúng. Đây là một ví dụ của chứng minh trivial. Như vậy là khẳng định a>=b không cần thiết trong chứng minh. Vídụ13: Với mọi số tự nhiên n, nếu n là tổng của hai số nguyên tố, thì hoặc n là chẵn hoặc n là lẻ. Giải: Bất kỳ một số tự nhiên n nào cũng hoặc là chẵn hoặc là lẻ. Do vậy kết luận của phép duy dẫn là đúng bất chấp điều kiện là đúng hay sai. Phép duy dẫn được gọi là phép duy dẫn trivial□ 18/72