Đề cương Bài giảng Toán rời rạc

TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN KHOA CƠNG NGHỆ THƠNG TIN ĐỀ CƯƠNG BÀI GIẢNG TỐN RỜI RẠC Trình độ đào tạo: Đại học Hệ đào tạo: Chính qui Hưng Yên, Tháng 8 năm 2016 TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 1 LỜI NĨI ĐẦU Tốn học rời rạc (tiếng Anh: discrete mathematics) là tên chung của nhiều ngành tốn học cĩ đối tượng nghiên cứu là các tập hợp cấu trúc, đối tượng rời rạc, các ngành này được tập hợp lại từ khi xuất hiện khoa học máy tính làm thành cơ sở tốn học của khoa học máy tính. Nĩ cịn được gọi là tốn học dành cho máy tính. Người ta thường kể đến trong tốn học rời rạc lý thuyết tổ hợp, lý thuyết đồ thị, lý thuyết độ phức tạp, đại số Boolean. Một quan điểm rộng rãi hơn, gộp tất cả các ngành tốn học làm việc với các tập hữu hạn hoặc đếm được vào tốn học rời rạc như số học modulo m, lý thuyết nhĩm hữu hạn, lý thuyết mật mã, ... Trong các cấu trúc, đối tường rời rạc khơng cĩ một cấu trúc nào là cơ bản thực sự, bởi vì hầu hết cấu trúc cĩ thể được định nghĩa thơng qua hầu như bất kỳ các kiểu khác. Do vậy, trong modul này, nội dung sẽ trình bày những cấu trúc cơ bản và quan trọng nhất. Cĩ thể nĩi tốn học rời rạc là mơn tiên quyết và hiệu quả nhất để người học nâng cao tư duy tốn học trong phân tích, thiết kế thuật tốn và rèn luyện kỹ năng lập trình với những thuật tốn phức tạp. Khơng những thế nĩ cịn là “cửa ngõ” để người học cĩ thể tiếp cận với rất nhiều modul trong khoa học máy tính (như Chương trình dịch, lý thuyết tính tốn, Trí tuệ nhân tạo, ...). Mặc dù đã rất cẩn trọng trong quá trình biên soạn, tuy nhiên tài liệu khơng tránh khỏi những thiếu sĩt và hạn chế. Chúng tơi rất mong được sự gĩp ý quí báu của tất cả đọc giả và các bạn đồng nghiệp. Mọi gĩp xin gửi về: Khoa Cơng nghệ Thơng tin – Trường ĐHSPKT Hưng Yên TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 2 Mục lục LỜI NĨI ĐẦU ................................................................................................................................ 0 Mục lục ........................................................................................................................................... 2 Danh mục các hình vẽ ..................................................................................................................... 6 Bài 1 Tổng quan mơn học ............................................................................................................... 8 1.1 Mở đầu................................................................................................................................... 8 1.2 Tại sao học tốn rời rạc ......................................................................................................... 9 1.3 Tốn học rời rạc nghiên cứu những gì ................................................................................ 10 1.4 Học tốn rời rạc như thế nào ............................................................................................... 12 1.5. Tốn rời rạc và ứng dụng ................................................................................................... 13 BÀI 2: Logic mệnh đề (propositional logic) ................................................................................ 14 2.1. Mệnh đề .............................................................................................................................. 14 2.2. Các phép tốn lơgic cơ bản ................................................................................................ 16 2.2.1. Phép phủ định .............................................................................................................. 16 2.2.2. Phép hội ....................................................................................................................... 16 2.2.3. Phép tuyển ................................................................................................................... 17 2.2.4. Phép kéo theo ............................................................................................................... 18 2.2.5. Phép tương đương ........................................................................................................ 19 2.3. Sự tương đương lơgic và luật ............................................................................................. 20 2.3.1. Giới thiệu ..................................................................................................................... 20 2.3.2. Sự tương đương lơgic .................................................................................................. 20 2.4. Bài tập................................................................................................................................. 23 Bài 3 Logic vị từ (predicate logic) ................................................................................................ 24 3.1. Vị từ .................................................................................................................................... 24 3.1.1. Định nghĩa ................................................................................................................... 24 3.1.1. Các phép tốn vị từ ...................................................................................................... 24 3.2. Lượng từ ............................................................................................................................. 25 3.2.1. Mệnh đề tồn tại ............................................................................................................ 25 3.2.2. Mệnh đề tất cả .............................................................................................................. 26 3.2.3. Quy tắc phủ định mệnh đề cĩ lượng từ........................................................................ 27 3.2.4 Một số lượng từ hai biến ............................................................................................... 28 3.2.5 Một số quy tắc phổ dụng .............................................................................................. 28 3.3. Logic trong tìm kiếm trên mạng ........................................................................................ 29 3.4. Logic trong lập trình .......................................................................................................... 29 3.5. Logic trong đời sống .......................................................................................................... 29 3.6. Logic trong tính tốn .......................................................................................................... 30 3.7. Logic trong suy luận ........................................................................................................... 30 3.8. Logic trong giải bài tốn trong kĩ thuật .............................................................................. 31 Bài 4 Thảo luận Logic ................................................................................................................... 34 4.1. Logic mệnh đề .................................................................................................................... 34 4.1.1 Logic trong suy luận ..................................................................................................... 34 4.1.2. Mạch logic số ............................................................................................................... 34 4.2. Logic vị từ .......................................................................................................................... 34 4.2.1 Logic trong suy luận ..................................................................................................... 34 4.3. Logic mờ (*) ....................................................................................................................... 34 4.4. Thảo luận ............................................................................................................................ 34 Bài 5 Một số phương pháp chứng minh........................................................................................ 35 5.1. Giới thiệu ............................................................................................................................ 35 5.1.1. Vai trị của chứng minh ............................................................................................... 35 5.1.2. Một số thuật ngữ .......................................................................................................... 35 5.2. Chứng minh nhờ luật suy diễn ........................................................................................... 36 5.2.1. Giới thiệu ..................................................................................................................... 36 TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 3 5.2.2. Một số ví dụ ................................................................................................................. 38 5.3. Các phương pháp chứng minh cho mệnh đề kéo theo ....................................................... 39 5.3.1. Chứng minh trực tiếp ................................................................................................... 39 5.3.2. Chứng minh gián tiếp .................................................................................................. 40 5.3.3. Chứng minh bằng cách phân chia trường hợp ............................................................. 41 5.3.4. Chứng minh vacuous ................................................................................................... 42 5.3.5. Chứng minh trivial ...................................................................................................... 42 5.4. Chứng minh bằng phản chứng ........................................................................................... 43 5.5. Chứng minh bằng quy nạp ................................................................................................. 44 5.6. Chứng minh bằng cách đưa ra phản ví dụ .......................................................................... 45 5.7. Một số ngộ nhận thường gặp ............................................................................................. 46 Bài 6. Ứng dụng của phương pháp chứng minh nhờ luật suy diễn .............................................. 47 6.1. Ứng dụng ............................................................................................................................ 47 6.2. Bài tập ................................................................................................................................ 47 Bài 7 Số và Ma trận ...................................................................................................................... 49 7.1. Thuật tốn .......................................................................................................................... 49 7.1.1. Giới thiệu ..................................................................................................................... 49 7.1.2. Định nghĩa ................................................................................................................... 49 7.1.3. Các đặc trưng của thuật tốn: ...................................................................................... 50 7.2. Độ phức tạp của thuật tốn ................................................................................................ 50 7.2.1. Khái niệm về độ phức tạp của một thuật tốn ............................................................. 50 7.2.2. So sánh độ phức tạp của các thuật tốn: ...................................................................... 52 7.3. Số nguyên và thuật tốn ..................................................................................................... 55 7.3.1 Thuật tốn Euclide ........................................................................................................ 55 7.3.2 Biểu diễn các số nguyên ............................................................................................... 57 7.3.3 Thuật tốn cho các phép tính số nguyên ...................................................................... 58 7.4. Số học đồng dư ................................................................................................................... 60 7.5. Ma trận ............................................................................................................................... 62 7.5.1. Giới thiệu ma trận và ứng dụng của ma trận ............................................................... 62 7.5.2. Các phép tốn trên ma trận .......................................................................................... 62 7.5.3. Các loại ma trận đặc biệt ............................................................................................. 63 Bài 8 Số nguyên và ứng dụng ....................................................................................................... 65 8.1. Số học đồng dư và ứng dụng .............................................................................................. 65 8.1.1. Hàm băm ..................................................................................................................... 65 8.1.2. Các số giả ngẫu nhiên .................................................................................................. 65 8.1.3. Mật mã ......................................................................................................................... 65 8.2. Số nguyên tố và ứng dụng .................................................................................................. 66 8.2.1. Số nguyên tố ................................................................................................................ 66 8.2.2. Thuật tốn sàng số nguyên tố ...................................................................................... 67 8.3. Giải thuật đệ quy ................................................................................................................ 69 8.3.1. Khái niệm đệ quy ......................................................................................................... 69 8.3.2. Thuật tốn đệ qui ......................................................................................................... 70 8.3.3. Đệ quy và lặp ............................................................................................................... 71 BÀI 9 Kỹ thuật đếm cơ bản (Count technique) ............................................................................ 74 9.1. Định nghĩa .......................................................................................................................... 74 9.2. Nguyên lý cộng và nguyên lý nhân .................................................................................... 74 9.2.1. Nguyên lý cộng ........................................................................................................... 74 9.2.2. Nguyên lý nhân ........................................................................................................... 76 9.3. Nguyên lý bù trừ ................................................................................................................ 79 9.4. Nguyên lý Dirichlet ............................................................................................................ 80 9.4.1. Nguyên lý Dirichlet tổng quát ..................................................................................... 81 9.4.2. Một số ứng dụng của nguyên lý Dirichlet ................................................................... 81 TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 4 9.5. Hốn vị, tổ hợp, chỉnh hợp (*) ........................................................................................... 82 9.5.1. Chỉnh hợp .................................................................................................................... 82 9.5.2. Tổ hợp .......................................................................................................................... 83 9.5.3. Hốn vị ........................................................................................................................ 85 9.5.4. Hốn vị lặp ................................................................................................................... 86 9.6. Bài tập................................................................................................................................. 87 Bài 10 Quan hệ truy hồi (Recurrence Relations) .......................................................................... 88 10.1. Định nghĩa ........................................................................................................................ 88 10.2. Một số ví dụ ...................................................................................................................... 88 10.3. Kỹ thuật giải phương trình truy hồi .................................................................................. 90 10.4. Bài tập............................................................................................................................... 90 Bài 11. Thảo luận về kỹ thuật đếm ............................................................................................... 91 11.1. Nhắc lại lý thuyết ............................................................................................................. 91 11.2. Bài tập kỹ thuật đếm cơ bản ............................................................................................. 91 11.3. Bài tập kỹ thuật đếm nâng cao ......................................................................................... 92 Bài 12 Các khái niệm cơ bản của Lý thuyết đồ thị .................................................................... 93 12.1 Định nghĩa cơ bản về đồ thị .............................................................................................. 93 12.2. Đường đi - chu trình - Đồ thị liên thơng .......................................................................... 95 12.3. Phân loại đồ thị ................................................................................................................. 98 12.3.1. Đồ thị vơ hướng liên thơng ........................................................................................ 98 12.3.2. Đồ thị cĩ hướng liên thơng ........................................................................................ 99 12.4. Một số loại đồ thị đặc biệt .............................................................................................. 100 Bài 13 Biểu diễn đồ thị trên máy tính ...................................................................................... 104 13.1. Ma trận kề - Ma trận trọng số ......................................................................................... 104 13.2. Danh sách cạnh (cung) ................................................................................................... 106 13.3. Danh sách kề .................................................................................................................. 107 13.4. Bài tập............................................................................................................................. 108 Bài 14 Đồ thị Euler – Hamilton ............................................................................................... 109 14.1 Đồ thị Euler ..................................................................................................................... 109 14.1.1. Định nghĩa ............................................................................................................... 109 14.1.2. Các ví dụ .................................................................................................................. 109 14.1.3. Định lý Euler ............................................................................................................ 110 14.1.4. Thuật tốn Flor tìm đường đi chu trình Euler .......................................................... 113 14.1.5. Một số bài tốn liên quan(*) .................................................................................... 113 14.2 Đồ thị Hamilton ............................................................................................................... 113 14.2.1 Định nghĩa ................................................................................................................ 114 14.2.2 Định lý Dirak ............................................................................................................ 114 14.2.3 Thuật tốn liệt kê tất cả các chu trình Hamilton của đồ thị ...................................... 115 Bài 15 Cài đặt đồ thị, thuật tốn tìm chu trình Euler và liệt kê chu trình Hamilton ................ 118 15.1. Cài đặt biểu diễn đồ thị trên máy tính ............................................................................ 118 15.2. Cài đặt thuật tốn liệt kê chu trình Euler ........................................................................ 118 15.3. Cài đặt thuật tốn liệt kê chu trình Hamilton ................................................................. 119 Bài 16 Thuật tốn tìm kiếm trên đồ thị và ứng dụng ............................................................... 120 16.1. Duyệt đồ thị theo chiều rộng (BFS) ............................................................................... 120 16.2. Duyệt đồ thị theo chiều sâu (DFS) ................................................................................. 123 16.3. Bài tập............................................................................................................................. 125 16.4. Ứng dụng ........................................................................................................................ 126 Bài 17 Cây và cây khung ......................................................................................................... 128 17.1. Cây và cây khung ........................................................................................................... 128 17.1.1. Cây ........................................................................................................................... 128 17.1.2. Cây khung của đồ thị ............................................................................................... 129 17.2. Bài tốn cây khung nhỏ nhất .......................................................................................... 131 TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 5 17.3 Xây dựng tập các chu trình cơ bản của đồ thị ................................................................. 132 17.4 Thuật tốn Kruskal .......................................................................................................... 133 17.5. Thuật tốn Prim .............................................................................................................. 135 Bài 18 Ứng dụng của bài tốn đồ thị liên thơng liên thơng và bài tốn cây khung nhỏ nhất .. 137 18.1. Thuật tốn duyệt đồ thị và bài tốn liên thơng ............................................................... 137 18.2. Một số thuật tốn xây dựng cây khung(*) ..................................................................... 138 18.3. Ứng dụng của bài tốn cây khung nhỏ nhất ................................................................... 139 18.4 Cài đặt thuật tốn Prim/Kruskal ...................................................................................... 140 18.4.1. Cài đặt thuật tốn Prim ............................................................................................ 140 18.4.2. Cài đặt thuật tốn Kruskal ....................................................................................... 142 Bài 19 Bài tốn tìm đường đi ngắn nhất .................................................................................. 146 19.1. Các khái niệm mở đầu .................................................................................................... 146 19.2. Đường đi ngắn nhất xuất phát từ một đỉnh. Thuật tốn Ford-Bellman .......................... 146 19.3. Trường hợp ma trận trọng số khơng âm. Thuật tốn Dijkstra ....................................... 148 19.4 Đường đi trong đồ thị khơng cĩ chu trình (*) ................................................................. 150 19.5 Đường đi ngắn nhất giữa tất cả các cặp đỉnh (*) ............................................................. 153 Bài 20. Ứng dụng của bài tốn tìm đường đi ngắn nhất ............................................................. 155 20.1. Ứng dụng của bài tốn tìm đường đi ngắn nhất ............................................................. 155 20.2. Cài đặt thuật tốn Dijkstra .............................................................................................. 155 Bài 21 Bài tốn luồng cực đại trong mạng .............................................................................. 158 21.1. Mạng - Luồng trong mạng – Bài tốn luồng cực đại ..................................................... 158 21.1.1 Mạng – Luổng trong mạng ....................................................................................... 158 21.2. Bài tốn luồng cực đại .................................................................................................... 159 21.3. Lát cắt. đường tăng luồng. Định lý Ford_Fulkerson ...................................................... 159 21.4. Thuật tốn tìm luồng cực đại ......................................................................................... 162 21.5 Bài tập ............................................................................................................................. 170 Bài 22 Lý thuyết đồ thị và ứng dụng ....................................................................................... 171 22.1. Một số bài tốn liên quan tới đồ thị ............................................................................... 171 22.1.1 Các bài tốn liên quan tới bậc của đồ thị .................................................................. 171 22.1.2 Các bài tốn liên quan đến tính liên thơng của đồ thị .............................................. 172 22.1.3 Các bài tốn cĩ liên quan đến đường đi và chu trình Hamilton ............................... 172 22.1.4 Các bài tốn liên quan đến đồ thị tơ màu ................................................................. 176 22.1.5 Bài tốn về cây ......................................................................................................... 180 22.1.6. Bài tốn về ghép cặp ................................................................................................ 181 22.1.7. Đồ thị Euler ............................................................................................................. 181 22.1.8. Các bài tốn cĩ tính tổng hợp .................................................................................. 182 22.2 Duyệt rộng trên mảng hai chiều ...................................................................................... 183 22.3 Bài tốn đám cưới vùng quê ........................................................................................... 185 22.4. Bài tập ............................................................................................................................ 186 TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 6 Danh mục các hình vẽ Hình 12.1 Sơ đồ mạng máy tính ................................................................................................... 93 Hình 12.2 Sơ đồ mạng máy tính với đa kênh thoại....................................................................... 93 Hình 12.3 Sơ đồ mạng máy tính với kênh thoại thơng báo .......................................................... 94 Hình 12.4 Mạng máy tính với kênh thoại một chiều .................................................................... 94 Hình 12.5 Đường đi trên đồ thị ..................................................................................................... 95 Hình 12.6 Đồ thị G và H ............................................................................................................... 96 Hình 12.7 Đồ thị liên thơng mạnh G và đồ thị liên thơng yếu H .................................................. 97 Hình 12.8 Đồ thị vơ hướng ........................................................................................................... 98 Hình 12.9 Đồ thị cĩ hướng ........................................................................................................... 99 Hình 12.10 Đồ thị đầy đủ ............................................................................................................ 100 Hình 12.11 Đồ thị vịng............................................................................................................... 101 Hình 12.12 Đồ thị bánh xe .......................................................................................................... 101 Hình 12.13 Đồ thị lập phương .................................................................................................... 101 Hình 12.14 Đồ thị hai phía .......................................................................................................... 102 Hình 12.15 Đồ thị K4 là đồ thị phẳng ......................................................................................... 102 Hình 12.16 Các miền tương ứng với biểu diễn phẳng của đồ thị ............................................... 103 Hình 13.1 Đồ thị vơ hướng G và Đồ thị cĩ hướng G1 ................................................................ 104 Hình 14.1 Mơ hình 7 cây cầu ở Konigsberg ............................................................................... 109 Hình 14.2 Đồ thị G1, G2, G3 ........................................................................................................ 110 Hình 14.3 Đồ thị H1, H2, H3 ........................................................................................................ 110 Hình 14.4 Minh hoạ cho chứng minh định lý 14.1 ..................................................................... 111 Hình 14.5 Du lịch 20 thành phố .................................................................................................. 113 Hình 14.6 Đồ thị Hamilton G3, nửa Hamilton G2, và G1 khơng là nửa Hamilton ...................... 114 Hình 14.7 Đồ thị đấu loại D5, đấu loại liên thơng mạnh D6........................................................ 115 Hình 16.1 Đồ thị vơ hướng ......................................................................................................... 121 Hình 16.2 Đồ thị vơ hướng ......................................................................................................... 127 Hình 17.1 Cây và rừng ................................................................................................................ 128 Hình 17.2 Đồ thị và các cây khung của nĩ. ................................................................................ 129 Hình 17.3 Đồ thị và cây khung nhỏ nhất .................................................................................... 136 Hình 18.1 Minh họa từng bước thuật tốn Prim tìm cây khung nhỏ nhất .................................. 142 Hình 18.2 Minh họa từng bước thuật tốn Kruskal tìm cây khung nhỏ nhất .............................. 145 Hình 19.3 Đồ thị minh hoạ PERT. .............................................................................................. 153 Hình 21.1 Mạng G và luồng f. Đồ thị cĩ trọng số Gf tương ứng. ............................................... 161 Hình 21.2 Mạng G và minh họa từng bước thuật tốn ford-Fullkerson ..................................... 166 Hình 21.3 Mạng G với luồng cực đại và lát cắt hẹp nhất ........................................................... 167 Hình 21.4 Ví dụ tồi tệ đối với thuật tốn ford_Fulkerson. .......................................................... 169 Hình 21.5 Tăng luồng dọc theo đường tăng. .............................................................................. 170 Hình 22.1 Kết quả thi đấu của 5 đội bĩng chuyền A, B, C, B, E ................................................ 173 Hình 22.2 Sơ đồ nhà của 8 học sinh............................................................................................ 174 Hình 22.3 10 thành phố ............................................................................................................... 174 Hình 22.4 bố trí lịch thi cho học sinh THPT với 7 mơn thi trong 7 ngày ................................... 175 Hình 22.5 Vị trí nhà ở và đường nối giữa các nhà của 9 học sinh .............................................. 176 TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 7 Hình 22.6 Bản đồ cĩ 6 miền ....................................................................................................... 177 Hình 22.7 Lập lịch thi 7 mơn ...................................................................................................... 179 Hình 22.8 Tơ màu cho đồ thị lịch thi .......................................................................................... 180 Hình 22.9 Kết quả xếp hạng của các đội .................................................................................... 181 Hình 22.10 Tuyển chọn biên dịch viên ....................................................................................... 183 Hình 22.11 Hướng di chuyển của robot ...................................................................................... 184 Hình 22.12 Mạng tương ứng với bài tốn đám cưới vùng quê. .................................................. 185 TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 8 Bài 1 Tổng quan mơn học 1.1 Mở đầu Tốn học rời rạc ngày nay đã trở thành quen thuộc trong những năm gần đây bởi những ứng dụng to lớn của nĩ trong các ngành tin học. Tốn học rời rạc là một ngành tốn học giải quyết các đối tượng hay cấu trúc rời rạc. Đối tượng rời rạc là những đối tượng mà chúng cĩ thể được phân biệt, phân tách ra khỏi nhau để cĩ thể đếm được. Số tự nhiên, số hữu tỉ (được coi như là tỉ số của 2 số tự nhiên), mơtơ, nhà, người, là những đối tượng rời rạc. Mặt khác số thực bao gồm số vơ tỉ là khơng rời rạc (chúng ta biết rằng giữa hai số thực khác nhau luơn tồn tại một số thực khác chúng). Thuật ngữ ”Tốn học rời rạc”cũng để phân biệt với”Tốn học liên tục”. Trong khi các đối tượng rời rạc thường được coi như cĩ sự liên quan mật thiết tới số tự nhiên thì các đối tượng liên tục là số thực Trong modul này, chúng ta sẽ nghiên cứu những đối tượng rời rạc như số tự nhiên, mệnh đề, tập, quan hệ, hàm, đồ thị, hay lý thuyết số, tất cả chúng đều rời rạc. Chúng ta sẽ học các khái niệm, tính chất và quan hệ giữa chúng với nhau và với các đối tượng khác. Một quan điểm rộng rãi hơn, gộp tất cả các ngành tốn học làm việc với các tập hữu hạn hoặc đếm được vào tốn học rời rạc như số học modulo m, lý thuyết nhĩm hữu hạn, lý thuyết mật mã, ... Cĩ thể nêu ra đây một vài ví dụ dùng tới tốn học rời rạc: - Cĩ bao nhiêu password hợp lệ cho một hệ thống máy tính? - Cĩ tồn tại một đường nối giữa 2 máy tính trong một mạng? - Cĩ bao nhiêu địa chỉ internet hợp lệ? - Đường đi ngắn nhất giữa 2 máy tính trong một mạng là gì? - Cĩ bao nhiêu bước trong quá trình sắp xếp? - Cĩ bao nhiêu mạch để cộng 2 số nguyên được thiết kế? - Khả năng trúng giải thưởng cho một vé số là bao nhiêu? - Cách tốt nhất để lập lịch 8 cuộc họp hội đồng các thành viên mà khơng cĩ bất kỳ sự cạnh tranh nào, giả thiết đưa ra là 1 vài người cĩ tên trong hơn 1 hội đồng. - Làm thế nào chúng ta cĩ thể lập lịch tất cả các nhiệm vụ trong dự án lớn này (giống như 1 dự án xây dựng hoặc dự án để bắt đầu đưa 1 sản phẩm mới ra thị trường). - Sẽ cĩ đủ số điện thoại để cung cấp tất cả điện thoại, máy fax, và điện thoại di động trong cho Việt Nam? - Làm thể nào chúng ta cĩ thể mơ hình và phân tích 1 sự thay đổi dân số, hoặc thay đổi lượng tiền trong một dự án đầu tư Modul sẽ học những cấu trúc rời rạc và các kỹ thuật để giải quyết những vấn đề này. Vậy một câu hỏi đặt ra là: Tốn rời rạc được dùng khi nào? Thực tế tốn học rời rạc được dùng rất đa dạng trong nhiều chuyên ngành, lĩnh vực. Tuy nhiên, cĩ thể thấy phần lớn nĩ được dùng khi liên quan tới: - Đếm các đối tượng TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 9 - Xem xét quan hệ giữa những tập hữu hạn (hoặc đếm được) - Phân tích quá trình cĩ số bước hữu hạn - Cơ bản về tất cả những xử lý thơng tin số: Những thao tác trên các cấu trúc rời rạc trong bộ nhớ - Nĩ là ngơn ngữ cơ bản và là khái niệm nền tảng cho tất cả các lĩnh vực trong khoa học máy tính - Các khái niệm rời rạc cũng được sử dụng rộng rãi trong tốn học, kỹ thuật, kinh tế, sinh học, Đặc biệt tốn học rời rạc là một cơng cụ tuyệt vời để suy luận logic. 1.2 Tại sao học tốn rời rạc Cĩ một số lý do quan trọng để nghiên cứu tốn học rời rạc. Thứ nhất, thơng qua modul này, người học cĩ thể phát triển khả năng tốn học, đĩ là khả năng hiểu và tạo ra các chủ đề của tốn học. Người học sẽ vơ cùng khĩ khăn để tiến xa trong ngành tin học mà khơng cĩ những kiến thức tốn học này. Thứ hai, tốn học rời rạc cung cấp cơ sở tốn học để mở ra cánh cửa cho người học cĩ thể tiếp tục với những modul cao hơn cho các khĩa học của khoa học máy tính, bao gồm: cấu trúc dữ liệu, thuật tốn, lý thuyết cơ sở dữ liệu, lý thuyết automat, ngơn ngữ hình thức, trình biên dịch, bảo mật máy tính, thiết kế mạch máy tính, mạng máy tính và hệ điều hành, sinh viên cĩ thể nhận thấy những khĩa học trên vơ cùng khĩ khăn nếu khơng cĩ một cơ sở tốn học của modul tốn học rời rạc này. Tốn học rời rạc là tốn tính tốn Khoa học máy tính hiện đại được xây dựng hầu hết dựa trên tốn học rời rạc, đặc biệt là tốn tập hợp và lý thuyết đồ thị. Điều này cĩ nghĩa là: các nhà lập trình máy tính và sinh viên muốn học các thuật tốn cơ bản thì sẽ phải cần một nền tảng tốn học rời rạc chắc chắn. Bởi vậy, tại hầu hết các trường đại học, mơn tốn học rời rạc là bắt buộc với sinh viên bậc đại học. Tốn học rời rạc là tốn thế giới thực Nhiều sinh viên than phiền về tính truyền thống của tốn cấp 3 như: đại số, đồ thị, lượng giác, và phần tương tự như vậy- câu hỏi đặt ra là: “học tốn cấp 3 với nội dung truyền thống như vậy tốt ở điểm nào?” Một vài chủ đề trừu tượng của tốn học thường làm sinh viên sợ và khơng vượt qua được. Ngược lại, tốn học rời rạc , đặc biệt là tốn đếm và xác suất, cho phép sinh viên (kể cả h/s đang học cấp 3 nhanh chĩng tìm ra vấn đề quan trọng trong thế giới thực những vấn đề khĩ nhưng lại rất thú vị). Tốn học rời rạc dạy suy luận tốn học và các kỹ thuật chứng minh Đại số thường dạy sinh viên nhớ chuỗi các cơng thức và thuật tốn (ví dụ, cơng thức quadratic, các hệ thống phương trình tuyến tính..), và hình học thường được dạy như là 1 chuỗi các bài tập áp dụng”định nghĩa – định lý – chứng minh”. Cịn với tốn học rời rạc, sinh viên sẽ suy nghĩ linh hoạt và sáng tạo. Cĩ các mối quan hệ giữa 1 vài cơng thức. Cĩ 1 số khái niệm cơ bản để làm chủ và ứng dụng tốn học TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 10 rời rạc trong nhiều cách khác nhau. Tốn học rời rạc rất vui Nhiều sinh viên, đặc biêt là những sinh viên sáng dạ và năng động tìm ra rằng đại số, hình học và thậm chí cả tích phân khơng gây thích thú. Hiếm khi những chủ đề này gây thích thú như những chủ đề tốn học rời rạc . Khi chúng ta hỏi sinh viên về chủ đề mà họ thích, hầu hết đều nhận được trả lời là tốn tập hợp hoặc lý thuyết số. (Khi chúng ta hỏi sinh viên về chủ đề mà ít gây thích thú với họ nhất, phần đa trả lời là”hình học”). Và thật đơn giản hầu hết sinh viên đều nhận ra rằng tốn học rời rạc nhiều niềm vui hơn đại số và hình học. 1.3 Tốn học rời rạc nghiên cứu những gì Tốn học rời rạc là tên chung của nhiều ngành tốn học cĩ đối tượng nghiên cứu là các tập hợp rời rạc, các ngành này được tập hợp lại từ khi xuất hiện khoa học máy tính làm thành cơ sở tốn học của khoa học máy tính. Nĩ cịn được gọi là tốn học dành cho máy tính. Cĩ thể nĩi tốn học rời rạc ngày càng cĩ tầm quan trọng trong nhiều ngành khoa học máy tính cũng như trong cơng việc lập trình. Cĩ nhiều khái niệm của tốn học được nghiên cứu trong tốn học rời rạc. Chúng ta cĩ thể nhắc tới một số chủ đề trong tốn học rời rạc sau đây khi chúng đã được áp dụng rất nhiều trong khoa học máy tính: Algorithmics – Thuật tốn, cịn gọi là giải thuật, là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hồn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đốn. Nĩi cách khác, thuật tốn là một bộ các qui tắc hay qui trình cụ thể nhằm giải quyết một vấn đề trong một số bước hữu hạn, hoặc nhằm cung cấp một kết quả từ một tập hợp của các dữ kiện đưa vào. Thuật tốn đơi khi cịn được gọi là phương thức, thủ tục, hay kỹ thuật. Trong ngành khoa học máy tính, thuật tốn được thể hiện thơng qua một chương trình máy tính (hay một tập hợp các chương trình máy tính) được thiết kế để giải quyết một số loại vấn đề một cách cĩ hệ thống. Một ví dụ kinh điển trong ngành khoa học máy tính là thuật tốn đệ quy dùng để giải bài tốn tháp Hà Nội. Boolean Algebra – cách tính tốn và biểu diễn các biểu thức trên hệ cơ số, nĩ cũng nghiên cứu các khái niệm điện tử học như cổng logic. Combinatorics – Là một nhánh của tốn học nghiên cứu tới liệt kê, tổ hợp, hốn vị các tập phần tử, những tính chất và những quan hệ của chúng. Computability and Complexity Theories – Lý thuyết về độ phức tạp và khả năng tính tốn - Liên quan tới combinatorics và algorithmics, nhưng nĩ tập trung vào những giới hạn về thực hành cũng như lý thuyết trong các mơ hình tính tốn khác nhauđể giải quyết bài tốn. Lý thuyết về độ phức tạp và khả năng tính tốn. Trong khoa học máy tinh, nĩ thường dùng ký hiệu O (Big-O). Counting – Liên quan tới các khái niệm và kỹ thuật đếm, liệt kê và tính tốn trong các hệ số khác nhau. Graph Theory – Lý thuyết đồ thị - Đồ thị biểu diễn được rất nhiều cấu trúc, nhiều bài tốn thực tế cĩ thể được biểu diễn bằng đồ thị. Ví dụ, cấu trúc liên kết của một website cĩ TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 11 thể được biểu diễn bằng một đồ thị cĩ hướng như sau: các đỉnh là các trang web hiện cĩ tại website, tồn tại một cạnh cĩ hướng nối từ trang A tới trang B khi và chỉ khi A cĩ chứa 1 liên kết tới B. Do vậy, sự phát triển của các thuật tốn xử lý đồ thị là một trong các mối quan tâm chính của khoa học máy tính. Information Theory – Lý thuyết thơng tin – Áp dụng tốn học vào truyền thơng, nĩ dựa phần lớn vào xác suất và thơng kê để nghiên cứu những lĩnh vực như phân tích dữ liệu, mạng, truyền thơng, tính tốn lượng tử Logic – Theo truyền thống, logic được nghiên cứu như là một nhánh của triết học. Kể từ giữa thế kỉ 19 logic đã thường được nghiên cứu trong tốn học và luật. Gần đây nhất logic được áp dụng vào khoa học máy tính và trí tuệ nhân tạo. Là một ngành khoa học hình thức, logic nghiên cứu và phân loại cấu trúc của các khẳng định và các lý lẽ, cả hai đều thơng qua việc nghiên cứu các hệ thống hình thức của việc suy luận và qua sự nghiên cứu lý lẽ trong ngơn ngữ tự nhiên. Mathematical Relations (Quan hệ): Phần này liên quan tới lý thuyết tập, các quan hệ là việc gán một giá trị cho một tổ hợp của k-phần tử. Number Theory (lý thuyết số): Là một nhánh lớn của tốn học nghiên cứu những tính chất của số nguyên. Proofs (chứng minh): Dùng lập luận logic tốn học để chứng minh một biểu thức là đúng, sai. Functions (Hàm): Trong tốn học, khái niệm hàm số (hay hàm) được hiểu tương tự như khái niệm ánh xạ. Nếu như ánh xạ được định nghĩa là một qui tắc tuơng ứng áp dụng lên hai tập hợp bất kỳ (cịn được gọi là tập nguồn và tập đích), mà trong đĩ mỗi phần tử của tập hợp này (tập hợp nguồn) tương ứng với một và chỉ một phần tử thuộc tập hợp kia (tập hợp đích), thì ta hồn tồn cĩ thể coi hàm số là một trường hợp đặc biệt của ánh xạ, khi tập nguồn và tập đích đều là tập hợp số. Set Theory (lý thuyết tập hợp): Nghiên cứu tập các phần tử. Mặc dù bất ký một kiểu đối tượng nào cũng cĩ thể tập hợp lại thành tập nhưng lý thuyết tập thường áp dụng cho các đối tượng trong tốn học. Linear algebra (Đại số tuyến tính): Phần này được sử dụng nhiều trong tốn học, như trong đại số đại cương, giải tích hàm, hình học giải tích... để giải các bài tốn như phép quay trong khơng gian, nội suy bình phương nhỏ nhất, nghiệm của hệ phương trình vi phân, tìm đường trịn qua ba điểm... Nĩ cũng cĩ vơ vàn ứng dụng trong khoa học tự nhiên (vật lý, cơng nghệ...) và khoa học xã hội (kinh tế...), vì các mơ hình phi tuyến tính hay gặp trong tự nhiên và xã hội thường cĩ thể xấp xỉ bằng mơ hình tuyến tính. Ký hiệu “→”:≡”cĩ thể được định nghĩa bởi” TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 12 HÌnh 1.1. Mối quan hệ giữa các kiểu dữ liệu Như đã thảo luận phần trước, các cấu trúc tốn học cĩ thể được xây dựng hay chỉ ra thơng qua các cấu trúc đơn giản hơn. Chính biểu đồ trên phác thảo một vài cách mà các cấu trúc rời rạc (và liên tục) đa dạng cuối cùng cũng được tạo nên từ cấu trúc rời rạc rất đơn giản là tập (set). Biểu đồ cũng cho chúng ta thấy được phần nào quan hệ của các đối tượng tốn học. Tuy nhiên, biểu đồ đã được đơn giản hĩa đi rất nhiều, nhiều cấu trúc khác cũng như các cách định nghĩa các cấu trúc thơng chúng đã được lược bỏ. Ví dụ, các tập cĩ thể được định nghĩa thơng qua các hàm, hoặc các quan hệ. Khơng cĩ một cấu trúc nào là cơ bản thực sự, bởi vì hầu hết cấu trúc cĩ thể được định nghĩa thơng qua hầu như bất kỳ các kiểu khác. Các tập chỉ cĩ thể là điểm bắt đầu nhưng chúng phổ cập được bởi vì định nghĩa của chúng quá đơn giản. Trong modul này sẽ xem xét biểu đồ chi tiết để thấy được các cấu trúc này liên hệ với nhau như thế nào. 1.4 Học tốn rời rạc như thế nào Một số lời khuyên cho người học để cĩ thể đạt hiệu quả cho modul này như sau: Thứ nhất, sinh viên hãy coi bài tập như một phần quan trọng trong quá trình học. Người học sẽ học được phần lớn kiến thức thơng qua bài tập, do vậy sinh viên hãy làm càng nhiều bài tập càng tốt, bao gồm cả bài tập cuối mỗi phần và các bài tập giảng viên cung cấp. Sinh viên hãy cố gắng tự giải bài tập trước khi xem lời giải. Đây là một yêu cầu rất quan trọng với sinh viên, người học chỉ cĩ thể đạt được nhiều kiến thức nhất khi trải qua quá trình tự làm, tự học. Thứ hai, sinh viên khơng được bỏ một buổi học nào, thời gian học trên lớp là quá trình trao đổi rất tốt giữa giảng viên và sinh viên. Thứ ba, nếu học viên học ít hơn 3 ngày trong tuần trong quá trình học modul này thì học viên đang lãng phí thời gian của mình, do vậy tốt nhất cho học viên là học tập thường xuyên. Thứ tư, hãy tạo cho mình mơi trường học tập thoải mái: cĩ thể đan xen giữa việc giải tốn, nghỉ ngơi và giải tốn. Cuối cùng, khơng bao giờ quên bài giảng. Hãy nhớ là: cho dù là cĩ khả năng vượt qua các kỳ thi bằng cách học rất ít trước kỳ TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 13 thi, nhưng với cách học như vậy thì kiến thức tốn sẽ chỉ đi vào”bộ nhớ tạm thời”mà thơi. Kết quả cuối cùng là kiến thức tốn sẽ ở mức độ mà khơng tồn tại lâu dài do cách học”sổi”, và chính thĩi quen học tập nghiên cứu như vậy sẽ làm hại chính mình. 1.5. Tốn rời rạc và ứng dụng - Ứng dụng của Logic mệnh đề - Ứng dụng của Logic vị từ - Ứng dụng của Logic mờ - Ứng dụng của luật suy diễn - Ứng dụng của số nguyên - Ứng dụng của bài tốn đếm - Ứng dụng của lý thuyết đồ thị TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 14 BÀI 2: Logic mệnh đề (propositional logic) Logic sử dụng để biểu diễn những luận điểm chính xác các mênh đề tố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 tố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 tồ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ự đố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 tố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ự đố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 tố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 tố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 tố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.1. Mệnh đề Các đối tượng cơ bản mà chúng ta khảo sát ở đây là các phát biểu hay các mệnh đề. Trong lơgic tốn, một phân ngành lơgic học, cơ sở của mọi ngành tốn học, mệnh đề, hay gọi đầy đủ là mệnh đề lơgic là một khái niệm nguyên thủy, khơng định nghĩa. Thuộc tính cơ bản của một mệnh đề là giá trị chân lí của nĩ, được quy định như sau: Mỗi mệnh đề cĩ đúng một trong hai giá trị chân lí 0 hoặc 1. Mệnh đề cĩ giá trị chân lí 1 là mệnh đề đúng, mệnh đề cĩ giá trị chân lí 0 là mệnh đề sai. Kí hiệu: Người ta thường dùng các chữ cái a, b, c, ... để kí hiệu cho các mệnh đề. Nếu mệnh đề a cĩ giá trị chân lí là 1 thì ta kí hiệu G(a) = 1, nếu mệnh đề a cĩ giá trị chân lí là 0 thì ta kí hiệu là G(a) = 0. Chẳng hạn, để kí hiệu a là mệnh đề”Paris là thủ đơ của nước Pháp”ta sẽ viết: a = “Paris là thủ đơ của nước Pháp”hoặc a: “Paris là thủ đơ của nước Pháp”. Ở đây, a là mệnh đề đúng nên G(a) = 1. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 15 Chú ý:1. Trong thực tế cĩ những mệnh đề mà tính đúng sai của nĩ luơn gắn với một thời gian và địa điểm cụ thể: đúng ở thời gian hoặc địa điểm này nhưng sai ở thời gian hoặc địa điểm khác. Nhưng ở bất kì thời điểm nào, địa điểm nào cũng luơn cĩ giá trị chân lí đúng hoặc sai. Chẳng hạn: Sáng nay bạn An đi học. Trời mưa. Học sinh tiểu học đang đi nghỉ hè. 2. Ta thừa nhận các luật sau đây của lơgic mệnh đề: Luật bài trùng: Mỗi mệnh đề phải hoặc đúng, hoặc sai; khơng cĩ mệnh đề nào khơng đúng cũng khơng sai. Luật mâu thuẫn: Khơng cĩ mệnh đề nào vừa đúng lại vừa sai. 3. Cĩ những mệnh đề mà ta khơng biết (hoặc chưa biết) đúng hoặc sai nhưng biết”chắc chắc”nĩ nhận một giá trị. Chẳng hạn: Trên sao Hỏa cĩ sự sống. Mệnh đề và câu Mệnh đề cĩ thể là một câu nhưng khơng phải mọi câu đều là mệnh đề. Cĩ thể chia các câu trong khoa học cũng như trong cuộc sống ra làm hai loại: loại thứ nhất gồm những câu phản ánh tính đúng hoặc sai một thực tế khách quan và loại thứ hai gồm những câu khơng phản ánh tính đúng hoặc sai một thực tế khách quan nào. Những câu thuộc loại thứ nhất là chính những mệnh đề. Vì vậy cĩ thể nĩi: “Mệnh đề là một câu khẳng định cĩ tính chất hoặc đúng hoặc sai”. Ví dụ 2.1: 1.”Paris là thủ đơ của nước Pháp” là mệnh đề đúng. 2.”Nước Việt Nam nằm ở châu Âu” là mệnh đề sai. 3.”Tháng 12 cĩ 28 ngày” là mệnh đề sai. 4.”Một năm cĩ 12 tháng và mỗi tuần cĩ 7 ngày” là mệnh đề đúng. 5.”20 là số chẵn” là mệnh đề đúng. 6.”Số 123 chia hết cho 3” là mệnh đề đúng. 7.”2 cộng với 3 bằng 7” là mệnh đề sai. 8.”15 lớn hơn 30” là mệnh đề sai. 9. Các câu sau đều khơng phải là mệnh đề. “Cuốn sách này giá bao nhiêu tiền?” “Bao giờ lớp mình đi tham quan Đền Hùng?” “Ơi! ngơi nhà mới đẹp làm sao!” “Tất cả hãy anh dũng tiến lên!” Nhận xét: nĩi chung những câu nghi vấn, câu cảm thán, câu mệnh lệnh đều khơng là mệnh đề. Mệnh đề lơgic và mệnh đề mờ Nếu như trong Lơgic tốn, một mệnh đề chỉ cĩ thể nhận một trong hai giá trị chân lí 0 hoặc 1 thì trong Trí tuệ nhân tạo người ta dùng lơgic mờ, mà ở đĩ giá trị chân lí của một TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 16 mệnh đề là một số nằm giữa 0 và 1. Mệnh đề cĩ giá trị chân lí 0 là sai, cĩ giá trị chân lí 1 là đúng. Cịn giá trị chân lí nằm giữa 0 và 1 chỉ ra mức độ thay đổi của chân lí. 2.2. Các phép tốn lơgic cơ bản Trong tốn học, khi cĩ hai số, người ta dùng các phép tốn số học (cộng, trừ, nhân, chia, ...) tác động vào chúng để nhận được những số mới. Tương tự, khi cĩ mệnh đề, người ta dùng các phép lơgic tác động vào chúng để nhận được những mệnh đề mới. Dưới đây ta trình bày định nghĩa và các tính chất cơ bản của các phép tốn này. 2.2.1. Phép phủ định Phủ định của mệnh đề a là một mệnh đề, kí hiệu là , đúng khi a sai và sai khi a đúng. Bảng giá trị chân lý của phép phủ định a 0 1 1 0 Ví dụ 2.2: Nếu a = “Paris là thủ đơ của nước Pháp” thì mệnh đề phủ định cĩ thể diễn đạt như sau: = “Khơng phải Paris là thủ đơ của nước Pháp” hoặc = “Paris khơng phải là thủ đơ của nước Pháp”. Ở đây G(a) = 1 cịn G( ) = 0. Nếu qua xác minh mệnh đề a đúng (hoặc sai) thì mệnh đề phủ định sẽ sai (hoặc đúng). Chú ý: Mệnh đề phủ định a thường được diễn đạt là “khơng phải a”. 2.2.2. Phép hội Hội của hai mệnh đề a, b là một mệnh đề, đọc là a và b, kí hiệu a Λ b (hoặc a.b), đúng khi cả hai mệnh đề a, b cùng đúng và sai trong các trường hợp cịn lại. Bảng giá trị chân lí của phép hội a b a Λ b 1 1 1 1 0 0 0 1 0 0 0 0 Chú ý: Để thiết lập mệnh đề hội của hai mệnh đề a, b ta ghép hai mệnh đề đĩ bởi liên từ “và” hay một liên từ khác cùng loại. Những liên từ đĩ là: mà, nhưng, song, đồng thời, vẫn, cùng, ... hoặc dùng dấu phảy hoặc khơng dùng liên từ gì. Ví dụ 2.3 “Lúc 8 giờ sáng nay Hà cĩ mặt ở Hà Nội và thành phố Hồ Chí Minh” là hội của hai mệnh đề a = “Lúc 8 giờ sáng nay Hà cĩ mặt ở Hà Nội”và b = “Lúc 8 giờ sáng nay Hà cĩ mặt ở thành phố Hồ Chí Minh”. Vì hai mệnh đề này khơng thể cùng đúng, nên G(a Λ b) = 0. Ví dụ 2.4 “Thành phố Hồ Chí Minh là thành phố lớn nhất trong cả nước nhưng khơng phải TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 17 là thủ đơ” là hội của hai mệnh đề a = “Thành phố Hồ Chí Minh là thành phố lớn nhất trong cả nước” và b = “Thành phố Hồ Chí Minh khơng phải là thủ đơ”. Rõ ràng là G(a) = 1 và G(b) = 1 nên G(a Λ b) = 1. “Số π lớn hơn 2 song nhỏ hơn 3”. “Chị Nga nĩi thạo tiếng Pháp mà khơng biết tiếng Anh”. “ABC là tam giác vuơng cân” là hội của của hai mệnh đề a = “ABC là tam giác vuơng” và b = “ABC là tam giác cân”. “Khơng những trời nắng to mà cịn giĩ tây”. “Chồng cày, vợ cấy, con trâu đi bừa”. Chú ý: Đơi khi trong mệnh đề cĩ liên từ “và” nhưng khơng cĩ nghĩa của mệnh đề hội. Chẳng hạn: “Số lẻ và số chẵn là hai tập con rời nhau của tập số tự nhiên”; “Hùng đạt được tất cả 20 điểm 9 và 10”. 2.2.3. Phép tuyển Tuyển của hai mệnh đề a, b là một mệnh đề đọc là a hoặc b, kí hiệu là a ν b (hoặc a+b), sai khi cả hai mệnh đề cùng sai và đúng trong trường hợp cịn lại. Bảng giá trị chân lí của phép tuyển a b a ν b 1 1 1 1 0 1 0 1 1 0 0 0 Phép tuyển trên cịn được gọi là phép tuyển khơng loại trừ. Phép tuyển loại trừ của hai mệnh đề a và b, chỉ đúng khi hoặc a, hoặc b đúng ta thường kí hiệu là a b. Chú ý: Để thiết lập mệnh đề tuyển của hai mệnh đề a, b ta ghép hai mệ nh đề đĩ bởi liên từ “hoặc” (hay liên từ khác cùng loại). Ví dụ 2.5 “Tháng 12 cĩ 31 ngày hoặc 2 + 2 = 4” là tuyển của hai mệnh đề a = “Tháng 12 cĩ 31 ngày”và b = “2 + 2 = 4”. Ở đây G(a ν b) = 1. “3 nhỏ hơn hoặc bằng 4” là mệnh đề đúng “Số lẻ là số cĩ chữ số tận cùng bằng 1, 3, 5, 7 hoặc 9” là mệnh đề đúng “20 là số lẻ hoặc chia hết cho 3” là mệnh đề sai Chú ý: Trong thực tế, liên từ “hoặc” thường được dùng với hai nghĩa “loại trừ” và “khơng loại trừ”; Phép tuyển “hoặc a hoặc b” là phép tuyển loại trừ để chỉ a hoặc b nhưng khơng thể cả a lẫn b; Phép tuyển “a hoặc b” là phép tuyển khơng loại trừ để chỉ a hoặc b và cĩ thể cả a lẫn b. Chẳng hạn: “Hơm nay là ngày Chủ nhật hoặc ngày lễ” là phép tuyển khơng loại trừ. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 18 “20 là số lẻ hoặc nĩ chia hết cho 2” là phép tuyển loại trừ. 2.2.4. Phép kéo theo a kéo theo b là một mệnh đề, kí hiệu là a→b, chỉ sai khi a đúng và b sai và đúng trong các trường hợp cịn lại. Bảng giá trị chân lí của phép kéo theo a b a →b 1 1 1 1 0 0 0 1 1 0 0 1 Chú ý: Mệnh đề a kéo theo b thường được diễn đạt dưới nhiều hình thức khác nhau, chẳng hạn: “Nếu a thì b” “Cĩ b khi cĩ a” “Từ a suy ra b” “a là điều kiện đủ để cĩ b” “b là điều kiện cần (ắt cĩ) để cĩ a” Ví dụ 2.6 “15 cĩ chữ số tận cùng bằng 5 suy ra 15 chia hết cho 5” là mệnh đề đúng. “Nếu dây tĩc bĩng đèn cĩ dịng điện chạy qua thì bĩng đèn sáng” là mệnh đề đúng Chú ý: 1. Trong lơgic, khi xét giá trị chân lí của mệnh đề a→b người ta khơng quan tâm đến mối quan hệ về nội dung của hai mệnh đề a, b. Khơng phân biệt trường hợp a cĩ phải là nguyên nhân để cĩ b hay khơng, mà chỉ quan tâm đến tính đúng, sai của chúng. Ví dụ 2.7 “Nếu mặt trời quay quanh trái đất thì Việt Nam nằm ở Châu Âu” mệnh đề đúng. Vì ở đây hai mệnh đề a = “mặt trời quay quanh trái đất”và b = “Việt Nam nằm ở Châu Âu” đều sai. “Nếu tháng 12 cĩ 31 ngày thì mỗi năm cĩ 13 tháng” là mệnh đề sai. 2. Theo bảng chân lí trên, ta thấy: Nếu a sai thì a →b luơn đúng. Nếu a đúng thì a →b đúng khi b đúng. Vì vậy để chứng minh mệnh đề a →b đúng ta chỉ cần xét trường hợp a và b cùng đúng và phép chứng minh mệnh đề a →b được tiến hành theo ba bước: Bước 1. Giả sử a đúng. Bước 2. Từ giả thiết a đúng, dùng lập luận và các mệnh đề tốn học đã biết, suy ra b đúng. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 19 Bước 3. Kết luận a →b luơn đúng. Trong mệnh đề a →b ta gọi a là giả thiết, b là kết luận. 3. Nếu ta coi là mệnh đề thuận thì b→a là mệnh đề đảo, 4. Trong văn học, mệnh đề kéo theo cịn được diễn đạt bằng nhiều hình thức phong phú. Chẳng hạn: “Bao giờ bánh đúc cĩ xương Bấy giờ dì ghẻ mới thương con chồng” hoặc “Chuồn chuồn bay thấp thì mưa, Bay cao thì nắng bay vừa thì râm”. 2.2.5. Phép tương đương a tương đương b là một mệnh đề, kí hiệu là a↔b, nếu cả hai mệnh đề a và b cùng đúng hoặc cùng sai. Bảng giá trị chân lí của mệnh đề tương đương a b a↔b 1 1 1 1 0 0 0 1 0 0 0 1 1. Trong thực tế, mệnh đề “a tương đương b” thường được diễn đạt dưới nhiều hình thức khác nhau. Chẳng hạn: “a khi và chỉ khi b” “a nếu và chỉ nếu b” “a và b là hai mệnh đề tương đương” “a là điều kiều kiện cần và đủ để cĩ b” 2. Hai mệnh đề a, b tương đương với nhau hồn tồn khơng cĩ nghĩa là nội dung của chúng như nhau, mà nĩ chỉ nĩi lên rằng chúng cĩ cùng giá trị chân lí (cùng đúng hoặc cùng sai). Ví dụ 2.8 “Tháng 12 cĩ 31 ngày khi và chỉ khi trái đất quay quanh mặt trời” là mệnh đề đúng. “12 giờ trưa hơm nay Tuấn cĩ mặt ở Hà Nội nếu và chỉ nếu vào giờ đĩ anh đang ở thành phố Hồ Chí Minh” là mệnh đề sai. “Hình vuơng cĩ một gĩc tù khi và chỉ khi 100 là số nguyên tố” là mệnh đề đúng. 3. Một cách khác, người ta cũng nĩi rằng a tương đương b khi và chỉ khi cả hai mệnh đề a→b và b→a cùng đúng. Vì vậy để chứng minh mệnh đề a↔b ta chứng minh hai mệnh đề a→b và b→a. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 20 4. Các cặp mệnh đề thuận và phản đảo, đảo và phản là những cặp mệnh đề tương đương. Đây chính là cơ sở của phương pháp chứng minh gián tiếp trong tốn học. 2.3. Sự tương đương lơgic và luật 2.3.1. Giới thiệu Trong phần trên ta đã xét năm phép tốn trên các mệnh đề. Như vậy, nếu cĩ các mệnh đề a, b, c,... khi dùng các phép tốn lơgic tác động vào, chúng ta sẽ nhận được những mệnh đề ngày càng phức tạp hơn. Mỗi mệnh đề như thế và cả những mệnh đề xuất phát ta gọi là cơng thức. Hay nĩi cách khác: Mỗi cơng thức được tạo thành từ những mệnh đề dưới tác dụng của các phép tốn lơgic. Như vậy ta gán cho mỗi mệnh đề cĩ mặt trong cơng thức P một giá trị chân lí, dùng bảng chân lí của các phép lơgic ta khẳng định được cơng thức P là mệnh đề đúng hoặc sai. Nếu P là mệnh đề đúng (hoặc sai) thì ta nĩi cơng thức P cĩ giá trị chân lí bằng 1 (hoặc 0). Ví dụ 2.9 (1) là cơng thức cĩ giá trị chân lí bằng 1 (với mọi mệnh đề a). Bảng giá trị chân lí của cơng thức (1) a a Λ 0 1 0 1 1 0 0 1 (2) là một cơng thức cĩ giá trị chân lí bằng 0 (với mọi mệnh đề a, b). Bảng giá trị chân lí của cơng thức (2) 2.3.2. Sự tương đương lơgic Cho P và Q là hai cơng thức. Ta nĩi rằng hai cơng thức P, Q tương đương lơgic với TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 21 nhau, kí hiệu là P ≡ Q, nếu với mọi hệ chân lí gán cho các mệnh đề cĩ mặt trong hai cơng thức đĩ thì chúng luơn nhận giá trị chân lí như nhau. Đặc biệt, hai mệnh đề a, b gọi là tương đương lơgic, kí hiệu là a ≡ b, nếu chúng cùng đúng hoặc cùng sai. Chú ý: 1. Kí hiệu a ≡ b là để chỉ hai mệnh đề tương đương lơgic chứ khơng phải là hai mệnh đề bằng nhau. 2. Hai mệnh đề tương đương lơgic cĩ thể về nội dung chúng hồn tồn khơng cĩ liên quan. Chẳng hạn: “Tháng 2 cĩ 31 ngày ≡ 2 + 2 = 11”. 3. Quan hệ P ≡ Q cịn được gọi là một đẳng thức. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 22 Dưới đây là một số đẳng thức thường gặp trong lơgic mệnh đề: Phủ định của phủ định (1) ≡ a. Luật Đờ Moĩcgăng (2) ≡ (3) ≡ Tính chất kết hợp của các phép lơgic (4) (a Λ b) Λ c ≡ a Λ (b Λ c) (5) (a ν b) ν c ≡ a ν (b ν c) Tính chất giao hốn của các phép lơgic (6) a Λ b ≡ b Λ a (7) a ν b ≡ b ν a (8) a↔b ≡ b↔a Tính chất phân phối (9) a Λ (b ν c) ≡ (a Λ b) ν (a Λ c) (10) a ν (b Λ c) ≡ (a ν b) Λ (a ν c) Tính lũy đẳng (11) a Λ a ≡ a (12) a ν a ≡ a Biểu diễn phép kéo theo qua các phép lơgic khác Biểu diễn tương đương qua các phép lơgic khác Các đẳng thức về 0 và 1 Người ta cịn dùng kí hiệu 1 (hoặc 0) để chỉ một mệnh đề luơn luơn đúng (hoặc luơn luơn sai). Ta cĩ các đẳng thức sau về 0 và 1: (18) a Λ 0 ≡ 0 (19) a ν 0 ≡ a (20) a Λ 1 ≡ a (21) a ν 1 ≡ 1 (22) a ν ≡ 1 (luật bài trung) (23) a Λ ≡ 0 (luật mâu thuẫn) TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 23 2.4. Bài tập Chứng minh đẳng thức Để chứng minh một đẳng thức trong lơgic mệnh đề ta cĩ thể dùng phương pháp lập bảng giá trị chân lí. Ví dụ 2.10 Chứng minh: ≡ Ta cĩ bảng giá trị chân lí như sau: Cột 1 2 3 4 5 6 7 a b a Λ b 1 1 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 0 1 1 1 1 Nhìn cột 4 và 7 trong bảng trên ta thấy hai cơng thức và luơn nhận giá trị chân lí như nhau. Vậy ta cĩ điều phải chứng minh. Ví dụ 2.11 Chứng minh: ≡ Ta cĩ bảng giá trị chân lí a b 1 1 1 1 1 0 0 0 0 1 1 1 0 0 1 1 Nhìn cột 3 và 4 trong bảng trên ta thấy hai cơng thức và luơn nhận giá trị chân lí như nhau. Vậy ta cĩ điều phải chứng minh. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 24 Bài 3 Logic vị từ (predicate logic) 3.1. Vị từ 3.1.1. Định nghĩa Ta xét các ví dụ sau: Ví dụ 3.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ụ 3.2 “x + 3 > 7” Tương tự như trong ví dụ 3.1 ta cĩ 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.3 “Ơng A là nhà tố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à tố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à tố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 đố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ừ. 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). 3.1.1. Các phép tốn vị từ Phép phủ định Cho p(x,y,..) là một vị từ theo các biến x, y, .. Phủ định của p kí hiệu là  p là một vị từ mà khi thay các biến x, y, .. bởi các phần tử cụ thể a, b, .. tương ứng thì ta cĩ mệnh đề  (p(a,b,..)). TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 25 ( p)( x,y,..)   (p(x,y,..)) Phép hội Cho p(x,y,..) và q(x,y,..) là các vị từ theo các biến x, y, .. Phép hội của p và q kí hiệu là p q là một vị từ mà khi thay các biến x, y, .. bởi các phần tử cụ thể a, b, .. tương ứng thì ta cĩ mệnh đề p(x,y,..)  q(x,y,..) (p  q)(x,y,..)  p(x,y,..)  q(x,y,..) Phép tuyển Cho p(x,y,..) và q(x,y,..) là các vị từ theo các biến x, y, .. Phép tuyển của p và q kí hiệu là p q là một vị từ mà khi thay các biến x, y, .. bởi các phần tử cụ thể a, b, .. tương ứng thì ta cĩ mệnh đề p(x,y,..)  q(x,y,..) (p  q)(x,y,..)  p(x,y,..)  q(x,y,..) Phép kéo theo Cho p(x,y,..) và q(x,y,..) là các vị từ theo các biến x, y, .. Phép p kéo theo q kí hiệu là pq là một vị từ mà khi thay các biến x, y, .. bởi các phần tử cụ thể a, b, .. tương ứng thì ta cĩ mệnh đề p(x,y,..) q(x,y,..) (p  q)(x,y,..)  p(x,y,..) q(x,y,..) Phép tương đương Cho p(x,y,..) và q(x,y,..) là các vị từ theo các biến x, y, .. Phép tương đương của p và q kí hiệu là pq là một vị từ mà khi thay các biến x, y, .. bởi các phần tử cụ thể a, b, .. tương ứng thì ta cĩ mệnh đề p(x,y,..) q(x,y,..) (p  q)(x,y,..)  p(x,y,..) q(x,y,..) 3.2. Lượng từ 3.2.1. 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ụ 3.4 “Tồn tại số thực x sao cho x + 4 > 7” là mệnh đề đúng. Kí hiệu là: “Tồn tại số tự nhiên n sao cho n chia hết cho 5” là mệnh đề đúng. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 26 Kí hiệu là: “Tồn tại số thực x sao cho x2 + 1 = 0” là mệnh đề sai. 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à tốn học”. “Một số người là nhà tốn học”. “Cĩ nhiều người là nhà tốn học” 2. Ta dùng kí hiệu với nghĩa “Tồn tại duy nhất một sao cho T(x)”. 3.2.2. Mệnh đề tất cả 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 tồ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 tồn thể, phổ biến, phổ cập, ...) Ví dụ 3.5 “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. 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”. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 27 “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”. 3.2.3. Quy tắc phủ định mệnh đề cĩ lượng 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: Như vậy, hai mệnh đề: và là phủ định của nhau. và là phủ định của nhau. Ví dụ 3.6 Kí hiệu là: Kí hiệu là: Mệnh đề Biểu thức tương đương Khi nào đúng Khi nào sai P(x) sai với mọi giá trị của x Cĩ một giá trị của x sao cho P(x) đúng Cĩ một giá trị của x sao cho P(x) sai P(x) đúng với mọi giá trị của x Từ các quy tắc trên cĩ thể nĩi quy tắc phủ định của mệnh đề cĩ lượng từ như sau: Nếu trong một mệnh đề cĩ lượng từ thì cĩ thể thay thế lượng từ  bởi lượng từ  và ngược lại cĩ thể thay thế lượng từ  bởi lượng từ  ; Biểu thức vị từ được thay thế bởi phủ định của nĩ sẽ được mệnh đề phủ định của mệnh đề cĩ lượng từ ban đầu, quy tắc này cũng cĩ thể áp dụng cho các mệnh đề với nhiều lượng từ. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 28 Ví dụ 3.7 Tìm phủ định của mệnh đề sau: , , : ( , , )x A y B z C p x y z      Theo quy tắc chung ta cĩ , , : ( , , )x A y B z C p x y z       , ( , : ( , , ))x A y B z C p x y z        , , ( : ( , , ))x A y B z C p x y z        , , : ( , , )x A y B z C p x y z       3.2.4 Một số lượng từ hai biến Mệnh đề Khi nào đúng Khi nào sai P(x,y) đúng với mọi cặp (x,y) Cĩ một cặp (x,y) sao cho P(x,y) sai Với mọi x, cĩ một y sao cho P(x,y) đúng Cĩ một x sao cho P(x,y) sai với mọi y Cĩ một x sao cho P(x,y) đúng với mọi y Với mọi x cĩ một y sao cho P(x,y) sai Cĩ một cặp (x,y) sao cho P(x,y) đúng Mọi cặp (x,y) sao cho P(x,y) sai 3.2.5 Một số quy tắc phổ dụng Quy tắc 1 Cho p(x) và q(x) là các vị từ theo biến x, A là miền giá trị, a là một phần tử bất kỳ thuộc A. Ta cĩ Quy tắc 2 Cho p(x), q(x) và r(x) là các vị từ theo biến x, A là miền giá trị. Ta cĩ TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 29 3.3. Logic trong tìm kiếm trên mạng Sử dụng kết hợp các tốn tử logic như phép and sẽ thu hẹp kết quả tìm kiếm và cho kết quả chính xác hơn khi kết quả trả về quá nhiều. Ngược lại, thay đổi tốn tử logic khác như phép or hay phép trừ thì cho nhiều kết quả hơn, khi quá ít kết quả trả về. 3.4. Logic trong lập trình Đặt vấn đề: Bạn muốn đặt điều kiện là nếu 0<x<10 hay x=10 thì tăng x lên 1 đơn vị. if (0<x<10 OR x=10) x++; Cách giải quyết: Bạn cĩ thể viết lại câu lệnh như sau if (x>0 AND x < = 10) x++ ; 3.5. Logic trong đời sống Ví dụ 3.8 Mẹ của bé An nĩi rằng: “Nếu con ngoan thì con cĩ thể được ăn kem hoặc ăn bánh bơng lan”. Bé An hiểu rằng nếu nĩ ngoan thì nĩ sẽ được ăn kem và ăn bánh bơng lan. Tuy nhiên, mẹ của bé An tức giận vì thật sự bà ta chỉ cho phép nĩ được ăn một trong hai thứ mà thơi. Cách giải quyết là mẹ của bé An phải nĩi như thế này: “Nếu con ngoan thì con sẽ được ăn hoặc là kem hoặc là bánh bơng lan nhưng khơng được ăn cả hai”. Ví dụ 3.9 Sau khi nướng 1 chiếc bánh cho 2 đứa cháu trai và 2 đứa cháu gái đến thăm, Dì Nellie lấy bánh ra khỏi lị nướng và để nguội. Sau đĩ, cơ rời khỏi nhà để đến đĩng cửa hàng ở gần đĩ. Lúc trở về thì cĩ ai đĩ đã ăn 1/4 chiếc bánh và thậm chí cịn đặt lại cái dĩa dơ bên phần bánh cịn lại. Vì khơng cịn ai đến nhà Dì ngày hơm đĩ trừ 4 đứa cháu nên Dì biết ngay là 1 trong 4 đứa đã ăn mà chưa được cho phép. Dì Nellie bèn hỏi 4 đứa thì được các câu trả lời như sau: - Charles: Kelly đã ăn phần bánh - Dawn: Con khơng ăn bánh - Kelly: Tyler ăn bánh - Tyler: Con khơng ăn, Kelly nĩi chơi khi bảo rằng con ăn bánh. Nếu chỉ 1 trong 4 câu trả lời trên là đúng và chỉ 1 trong 4 đứa cháu là thủ phạm, hãy tìm ra người mà Dì Nellie phải phạt? Cách giải quyết: Vì chỉ 1 trong 4 câu trả lời trên là đúng nên chúng ta cĩ thể dùng phép vét cạn để tìm lời giải. - Giả sử Charles nĩi đúng nghĩa là Kelly ăn bánh. Ba câu cịn lại là sai. Dawn nĩi” Con khơng ăn bánh” là sai nghĩa là Dawn cĩ ăn bánh. Vậy cĩ đến 2 người ăn bánh, điều này mâu thuẫn giả thiết, giả sử khơng được chấp thuận. - Giả sử Dawn nĩi đúng nghĩa là Dawn khơng ăn bánh và 3 câu cịn lại là sai. Nhận thấy cĩ mâu thuẫn giữa Kelly và Tyler. Bởi vì Kelly nĩi”Tyler ăn bánh” là sai nghĩa là Tyler khơng ăn. Trong khi đĩ, Tyler lại nĩi rằng”Con khơng ăn...” là sai, vậy thực tế là nĩ cĩ ăn. Giả thuyết này là khơng chấp nhận được. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 30 - Giả sử Kelly nĩi đúng nghĩa là Tyler ăn bánh và 3 câu cịn lại là sai. Như vậy, cũng cĩ 2 thủ phạm là Kelly và Dawn. Mâu thuẫn giả thiết. - Giả sử sau cùng là Tyler nĩi đúng nghĩa là nĩ khơng ăn bánh và 3 câu cịn lại là sai. Nhận thấy chỉ cĩ một người ăn bánh chính là Dawn. Vậy giả thuyết này là hợp lý và thủ phạm chính là Dawn. 3.6. Logic trong tính tốn Ví dụ 3.10 Bạn cĩ 3 lần kiểm tra trong lớp học. Nếu bạn đạt được 2 lần điểm A, hoặc chỉ một lần điểm A nhưng khơng được cĩ một lần nào rớt trong 3 lần kiểm tra đĩ thì bạn sẽ đạt điểm A cho tồn khĩa học. Bạn là người khơng được siêng năng lắm, vậy thì bạn sẽ chọn cách nào để đạt điểm A cho tồn khĩa học ? Cách giải quyết: Bởi vì điều kiện là OR nên cách giải quyết là bạn cĩ thể đạt 2 điểm A và rớt lần 3, hay là chỉ cần đạt một điểm A và khơng rớt lần nào. Bạn sẽ lựa chọn đạt một điểm A và khơng rớt lần nào. 3.7. Logic trong suy luận Ví dụ 3.10 Tìm số tự nhiên a biết rằng trong 3 mệnh đề dưới đây cĩ 2 mệnh đề là đúng và 1 mệnh đề là sai. 1/ a + 51 là số chính phương 2/ Chữ số tận cùng của a là 1 3/ a - 38 là số chính phương Cách giải quyết: Trước hết, chúng ta sẽ phải xác định xem 2 mệnh đề đúng và 1 mệnh đề sai là mệnh đề nào? Sau đĩ từ 2 mệnh đề đúng để tìm ra số tự nhiên a. Số chính phương là số nguyên dương khi lấy căn bậc hai. Do đĩ, số chính phương cĩ các chữ số tận cùng là 0, 1, 4, 5, 6, 9. - Nhận thấy giữa mệnh đề 1 và 2 cĩ mâu thuẫn. Bởi vì, giả sử 2 mệnh đề này đồng thời là đúng thì a+51 cĩ chữ số tận cùng là 2 nên khơng thể là số chính phương. Vậy trong 2 mệnh đề này phải cĩ 1 mệnh đề là đúng và 1 là sai. - Tương tự, nhận thấy giữa mệnh đề 2 và 3 cũng cĩ mâu thuẫn. Bởi vì, giả sử mệnh đề này đồng thời là đúng thì a-38 cĩ chữ số tận cùng là 3 nên khơng thể là số chính phương. Vậy trong 3 mệnh đề trên thì mệnh đề 1 và 3 là đúng, cịn mệnh đề 2 là sai. Với x > 0 và y > 0 . Đặt: a + 51 = x2 - a - 38 = y 2 ---------------- 89 = 1.89 = x2 - y2 = (x + y)(x - y) Suy ra: TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 31 x + y = 1 (loại vì x, y là nguyên dương nên khơng thể cĩ x + y = 1) x - y = 89 Hay là: x + y = 89 x - y = 1 Giải hệ phuơng trình này ta được x = 45 và y = 44. Vậy a = 1974. Ví dụ 3.11 Tại Tiger Cup 98 cĩ bốn đội lọt vào vịng bán kết: Việt Nam, Singapo, Thái Lan và Inđơnêxia. Trước khi thi đấu vịng bán kết, ba bạn Dụng, Quang, Trung dự đốn như sau: Dụng: Singapo nhì, cịn Thái Lan ba. Quang: Việt Nam nhì, cịn Thái Lan tư. Trung: Singapo nhất và Inđơnêxia nhì. Kết quả, mỗi bạn dự đốn đúng một đội và sai một đội. Hỏi mỗi đội đã đạt giải mấy? Giải: Kí hiệu các mệnh đề: d1, d2 là hai dự đốn của Dụng. q1, q2 là hai dự đốn của Quang. t1, t2 là hai dự đốn của Trung. Vì Dụng cĩ một dự đốn đúng và một dự đốn sai, nên cĩ hai khả năng: Nếu G(d1) = 1 thì G(t1) = 0. Suy ra G(t2) = 1. Điều này vơ lí vì cả hai đội Singapo và Inđơnêxia đều đạt giải nhì. Nếu G(d1) = 0 thì G(d2) = 1. Suy ra G(q2) = 0 và G(q1) = 1. Suy ra G(t2) = 0 và G(t1) = 1. Vậy Singapo nhất, Việt Nam nhì, Thái Lan ba cịn Inđơnêxia đạt giải tư. 3.8. Logic trong giải bài tốn trong kĩ thuật Lơgic mệnh đề cịn được ứng dụng trong kĩ thuật lắp ráp các mạch điện và thiết bị trong nhà máy. Dưới đây là một ví dụ minh họa. Ví dụ 3.12 Giữa cơng tắc và dây may so của một chiếc Bàn là cĩ rơle tự ngắt (để khi dây may so nĩng đến nhiệt độ quy định cho phép thì rơle tự ngắt mạch điện cho Bàn là được an tồn). Hãy thiết lập nguyên tắc lơgic của quá trình hoạt động của chiếc Bàn là đĩ (thiết lập mối liên hệ giữa việc đĩng, ngắt mạch của cơng tắc, rơle với nhiệt độ cho phép của dây may so). Giải: Kí hiệu các mệnh đề: c = “Cơng tắc Bàn là đĩng mạch”. r = “Rơ le Bàn là đĩng mạch”. t = “Dây may so trong Bàn là nĩng tới nhiệt độ cho phép”. Mối liên hệ giữa trạng thái an tồn của Bàn là và giá trị chân lí của các mệnh đề c, r, t cĩ thể biểu diễn bởi bảng sau: TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 32 Trạng thái c r t Trạng thái an tồn 1 1 1 1 khơng 2 1 1 0 cĩ 3 1 0 1 cĩ 4 1 0 0 khơng 5 0 1 1 khơng 6 0 1 0 cĩ 7 0 0 1 cĩ 8 0 0 0 khơng Trạng thái 1 và 5 khơng đảm bảo an tồn, vì khi dây may so đã nĩng tới nhiệt độ quy định cho phép mà rơle vẫn đĩng mạch thì dẫn đến hỏng Bàn là hoặc đồ là. Trạng thái 4 và 8 khơng đảm bảo an tồn vì dây may so chưa nĩng tới nhiệt độ quy định cho phép mà rơle đã ngắt mạch thì Bàn là khơng sử dụng được. Các trạng thái cịn lại: 2, 3, 6 và 7 đều đảm bảo an tồn. Các trạng thái đĩ được mơ tả bằng các cơng thức lơgic sau: Trạng thái Cơng thức 2 3 6 7 Vậy Bàn là hoạt động an tồn khi và chỉ khi: (1) Áp dụng các đẳng thức về luật phân phối, các đẳng thức về 0 và 1 cho trạng thái 2 với 6 và 3 với 7, ta cĩ: (2) Dùng bảng chân lí ta nhận được: (3) (4) Từ (1), (2), (3) và (4) ta suy ra: Bàn là hoạt động an tồn khi và chỉ khi Quy trình trên ta cĩ thể phát biểu thành lời như sau: để Bàn là hoạt động an tồn phải đảm bảo nguyên tắc: “Cơng tắc rơle đĩng mạch khi và chỉ khi nhiệt độ dây may so chưa tới hạn cho phép” hay “nhiệt độ dây may so tới hạn cho phép khi và chỉ khi cơng tắc rơle ngắt mạch điện”. Cách giải quyết khác: Cơng tắc Bàn khơng đĩng mạch bàn thì bàn là luơn ở trạng thái an tồn. Sau đây ta xét trường hợp bàn là đĩng mạch, chỉ quan tâm tới 2 mệnh đề là “Rơ le TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 33 Bàn là đĩng mạch” và mệnh đề “Dây may so trong Bàn là nĩng tới nhiệt độ cho phép” ảnh hưởng tới trạng thái an tồn của bàn là. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 34 Bài 4 Thảo luận Logic 4.1. Logic mệnh đề 4.1.1 Logic trong suy luận Trong một phiên tịa xử án 3 bị can cĩ liên quan đến vấn đề tài chánh để xét xem ai là người cĩ tội? Trước tịa cả 3 bị cáo đều tuyên thệ khai đúng sự thật và lời khai như sau: Anh A: Chị B cĩ tội hoặc anh C vơ tội Chị B : Nếu anh A cĩ tội thì anh C cũng cĩ tội Anh C: Tơi vơ tội nhưng một trong hai người kia là cĩ tội 4.1.2. Mạch logic số Trang 64 (Discrete Mathematics with Application, Susana) 4.2. Logic vị từ 4.2.1 Logic trong suy luận Ví dụ: Kiểm tra suy luận sau: Là người ai cũng phải chết; Ơng A là 1 người; Vậy ơng A phải chết. 4.3. Logic mờ (*) Được phát triển từ lý thuyết tập mờ để thực hiện lập luận một cách xấp xỉ thay vì lập luận chính xác theo lơgic vị từ cổ điển. Lơgic mờ cĩ thể được coi là mặt ứng dụng của lý thuyết tập mờ để xử lý các giá trị trong thế giới thực cho các bài tốn phức tạp (Klir 1997). 4.4. Thảo luận Cách giải một bài tốn dùng cơng cụ của lơgic mệnh đề Các bước tiến hành. Yêu cầu thảo luận: Hãy thiết lập biểu thức logic tương ứng với các đồ vật trong gia đình như: máy giặt, nồi cơm điện, ... (*) Ứng dụng logic vị từ và logic mờ. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 35 Bài 5 Một số phương pháp chứng minh 5.1. Giới thiệu Suy luận được xem là một trong những nền tảng xây dựng nên các ngành khoa học tự nhiên. Từ xưa đến nay, nhờ suy luận mà người ta cĩ thể nhận thức được cái chưa biết từ những cái đã biết. Suy luận cịn là cơ sở của sự sáng tạo. Từ các phán đốn, đưa đến các chứng minh để chấp nhận hay bác bỏ một vấn đề nào đĩ. Suy luận tốn học dựa trên nền tảng của các phép tốn mệnh đề, chủ yếu là phép kéo theo. Để chứng minh một vấn đề nào đĩ, thơng thường người ta phải xác định điểm ban đầu (cĩ thể gọi là giả thiết) và điểm kết thúc (gọi là kết luận). Quá trình đi từ giả thiết đến kết luận gọi là quá trình chứng minh và quá trình này đươc thực thi bằng cách nào thì gọi đĩ là phương pháp chứng minh. Một khẳng định mà chưa được chứng minh được gọi là phỏng đốn. Trong tốn học, chứng minh là cơng việc đưa ra minh chứng thuyết phục (dựa vào những kiến thức chuẩn trong ngành học) một mệnh đề tốn học là đúng cho mọi trường hợp, khơng trừ một trường hợp cụ thể nào. Một mệnh đề đã được chứng minh thì gọi là các định lý và nĩ cĩ thể được sử dụng để chứng minh cho các mệnh đề khác. 5.1.1. Vai trị của chứng minh Các phương pháp chứng minh là rất quan trọng vì khơng những chúng thường được sử dụng trong tốn học mà cịn được áp dụng nhiều trong tin học. Ví dụ, sự kiểm tra tính đúng đắn của một chương trình, của một hệ điều hành, xây dựng các luật suy diễn trong lĩnh vực trí tuệ nhận tạo... Do đĩ, chúng ta cần phải nắm vững các phương pháp chứng minh. • Trong tốn học chứng minh là: – Một luận cứ đúng đắn (dựa trên lập luận logic vững chắc) and và đầy đủ (rõ ràng và chi tiết) dựa trên những thiết lập khơng thể chối cái của các khẳng định tốn học. • Tại sao luận cứ lại phải đúng đắn và đầy đủ lại? – Đúng đắn sẽ tránh cho chúng ta những ngộ nhận từ chính chúng ta. – Đầy đủ cho phép bất kỳ ai cũng cĩ thể kiểm định kết quả. • Trong modul này, một yêu cầu rất quan trọng là tính đúng đắn và đầy đủ cho bất kỳ một chứng minh nào! • Các phương pháp chứng minh một luận cứ tốn học cĩ thể được cơng thức hĩa thành các luật suy diến. • Các chứng minh tốn học cĩ thể được thể hiện hình thức như là chính các cấu trúc rời rạc. 5.1.2. Một số thuật ngữ Một hệ thống tốn học bao gồm TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 36 • Định lý (Theorem) – Một mệnh đề được chứng minh là đúng. • Tiên đề, giả thiết (Axioms, hypotheses) – Một giả định (khơng chứng minh) định nghĩa về các cấu trúc mà chúng ta dùng để lập luận. • Luật suy diễn (rules of inferences) – Một hình thức dùng logic để lập luận từ những giả thiết để đi tới kết luận. • Bổ đề (Lemma) - Một định lý nhỏ được dùng như là một bước vững chắc để chứng minh định lý chính. • Hệ quả (Corollary) – Một định lý nhỏ được chứng minh một cách dễ dàng từ định lý chính. • Sự phỏng đốn (Conjecture) – Một khẳng định mà chưa được chứng minh • Lý thuyết (Theory) – Bao gồm một tập các định lý đã được chứng minh từ một tập các tiên đề. Cĩ hai kiểu chứng minh trong chứng minh tốn học [3]. Thứ nhất là chứng minh informal proof, ở đĩ những diễn tả bằng ngơn ngữ tự nhiên nhằm hướng mọi người tới sự thật của định lý. Đây là kiểu chứng minh đặc trưng trong tốn học. Bởi vì dùng ngơn ngữ tự nhiên, nĩ phụ thuộc nhiều vào kiến thức nền tảng chứng minh của người đọc. Thứ hai là kiểu chứng minh hình thức (formal proof). Đĩ là việc sử dụng một chuỗi các ký hiệu và những định nghĩa chính xác. Chứng minh hình thức và tính chất của nĩ được nghiên cứu trong lý thuyết chứng minh. Chứng minh hình thức khơng được phổ biến. 5.2. Chứng minh nhờ luật suy diễn 5.2.1. Giới thiệu 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 TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 37 ------ 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 Bảng5.1 Các luật suy diễn trong logic mệnh đề hay sử dụng 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ừ TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 38 5.2.2. Một số ví dụ Ví dụ 5.1 a Nếu trời mưa, thì đường ướt. Về mặt hình thức, chúng ta cĩ thể viết: p → q: Nếu trời mưa, thì đường ướt. Trong biểu thức này, Nếu trời mưa là tiền đề, cịn Đường ướt là hậu đề. Bây giờ, nếu chúng ta biết rõ một thực tế rằng trời mưa, thì chúng ta phải kết luận rằng đường ướt. Nếu tiền đề (Trời mưa) đúng, thì hậu đề (Đường ướt) cũng cần phải đúng, theo Modus Ponens. Chúng ta hãy viết các bước của mình về mặt hình thức: p → q: Nếu trời mưa, thì đường ướt. p: Trời mưa. ---------- q: Đường ướt. Phép kéo theo p → q và p đã cho sẵn là ở trên đường gạch ngang, cịn kết luận q thu được bằng việc áp dụng Modus Ponens ở dưới đường gạch ngang. Ví dụ 5.1 b W → C: Nếu các cầu thủ đội Chelsea thắng trận đấu hơm nay, họ sẽ là những nhà vơ địch. W: Các cầu thủ đội Chelsea thắng trận đấu hơm nay. ---------- C: Các cầu thủ đội Chelsea là những nhà vơ địch. Ví dụ 5.1 c W → B: Nếu thời tiết tốt, chúng ta cĩ thể đi ra bãi biển. W: Thời tiết tốt. ---------- B: Chúng ta cĩ thể đi ra bãi biển. Ví dụ 5.2 Nếu được thưởng cuối năm An sẽ đi Đà Lạt. Nếu An đi Đà Lạt An sẽ đến hồ Than Thở. An chưa đến hồ Than thở, vậy An khơng được thưởng cuối năm. Ví dụ 5.3 Nếu B được lên chức và làm việc chăm chỉ thì B được tăng lương. Nếu B được tăng lương thì B sẽ mua xe máy SH. Mà B khơng mua xe máy vậy B khơng được lên chức hoặc B khơng làm việc chăm chỉ. Suy luận trên đúng khơng? TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 39 Ví dụ 5.4 Tất cả sư tử đều hung dữ Một số sư tử khơng uống cà phê ---------- Một số sinh vật hung dữ khơng uống cà phê Gọi P(x) là “x là sư tử” Q(x) “x hung dữ” R(x) “x khơng uống cà phê” Trong đĩ x X, X là khơng gian tất cả sinh vật Về mặt hình thức, chúng ta cĩ thể viết:  x (P(x)=>Q(x)) “Tất cả sư tử đều hung dữ”  x (P(x) R(x)) “Một số sư tử khơng uống cà phê”  x (Q(x) R(x)) “Một số sinh vật hung dữ khơng uống cà phê” Chúng ta hãy viết các bước của mình về mặt hình thức:  x (P(x)=>Q(x)) “Tất cả sư tử đều hung dữ”  x (P(x) R(x)) “Một số sư tử khơng uống cà phê” ----------  x (Q(x) R(x)) “Một số sinh vật hung dữ khơng uống cà phê” 5.3. Các phương pháp chứng minh cho mệnh đề kéo theo 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; 5.3.1. Chứng minh 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 tố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? TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 40 - Các định lý nào, các kết quả 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? - 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ách 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 tố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 tố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ĩ. Ngồ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 tố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ụ 5.5 a. 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ẻ. b. 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 . 5.3.2. Chứng minh 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.6 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) Từ đĩ ta cĩ 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 tốn cĩ thể sử dụng phương pháp chứng minh trực tiếp hay gián tiếp đều TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 41 được cả. Tuy nhiên, cĩ những bài tố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ụ 5.7 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ụ 5.8 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ẻ. Ở đây chúng ta phải chứng minh thêm định lý là tích của 2 số lẻ là một số lẻ thì bài giải chặt chẽ hơn. Do đĩ, trong bài tốn này việc sử dụng chứng minh gián tiếp là hay hơn dùng trực tiếp. 5.3.3. Chứng minh bằng cách phân chia trường hợp Để chứng minh mệnh đề cĩ dạng: (P1 v P2v...v Pn) → Q Chúng ta cĩ thể sử dụng hằng đúng sau: ((P1v P2v..v Pn) →Q) ↔ ((P1→Q) v (P2→Q) v....v(Pn→Q)) Cách chứng minh này gọi là chứng minh bằng cách phân chia trường hợp. Ví dụ 5.9 Chứng minh rằng: “Nếu n khơng chia hết cho 3 thì n2 khơng chia hết cho 3”. Giải: Gọi P là mệnh đề”n khơng chia hết cho 3”và Q là mệnh đề” n2 khơng chia hết cho 3”. Khi đĩ, P tương đương với P1 v P2. Trong đĩ: P1 = “n mod 3 =1” và P2 = “n mod 3 =2” Vậy, để chứng minh P → Q là đúng, cĩ thể chứng minh rằng: (P1 v P2) → Q hay là (P1 → Q) v (P2→ Q) Giả sử P1 là đúng. Ta cĩ, n mod 3 = 1. Đặt n = 3k + 1 (k là số nguyên nào đĩ). Suy ra n2 = (3k+1)2 = 9 k2 + 6k + 1 = 3(3k2 + 2k) + 1 khơng chia hết cho 3. Do đĩ, P1→ Q là đúng. Tương tự, giả sử P2 là đúng. Ta cĩ, n mod 3 = 2. Đặt n = 3k + 2 (k là số nguyên nào đĩ). Suy ra n2 = (3k+2)2 = 9k2 + 12k + 4 = 3(3k2 + 4k + 1) + 1 khơng chia hết cho 3. Do đĩ, P2 → Q là đúng. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 42 Do P1 → Q là đúng và P2 → Q là đúng, hay là (P1 → Q) v (P2→ Q). Vậy (P1 v P2) → Q. Chúng ta hãy trở lại một bài tốn về số nguyên đã được trình bày trong phần trước về các ví dụ áp dụng của logic trong việc lập luận và chứng minh. Để chứng minh một biểu thức tương đương dạng p↔q, trong đĩ p và q là các mệnh đề. Chúng ta cĩ thể sử dụng hằng đúng sau: (p ↔ q) ≡ [(p → q) (q → p)] Đơi khi chúng ta muốn chứng minh một vài mệnh đề tương đương nhau ví dụ: p1↔ p2↔ p3 ↔...↔ pn , ta cĩ thể sử dụng hằng đúng. Ví dụ 5.10 Hãy áp dụng để chứng minh rằng 3 khẳng định sau là tương đương với n là số tự nhiên: p1: n mod 3= 1 hoăc n mod 3= 2 p2: n khơng chia hết cho 3 p3: n 2 -1 chia hết cho 3 5.3.4. Chứng minh vacuous 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ụ 5.11 a. 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ụ 5.11.b 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. 5.3.5. Chứng minh trivial 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ụ 5.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. TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 43 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ụ 5.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. 5.4. Chứng minh bằng phản chứng Chứng minh bằng phản chứng cĩ thể áp dụng cho dạng suy diễn, p→q, trong phần trên. Tuy nhiên nĩ cũng là một phương pháp rất hữu ích cho chứng minh các mệnh đề tổng quát. Giả sử rằng phủ định của q cĩ thể được tìm thấy trong ⌐p → q là đúng, khi đĩ ⌐p→ F đúng thì suy ra ⌐p phải là sai, nghĩa là p phải đúng. Kỹ thuật này được sử dụng trong phản chứng. Phương pháp chứng minh trực tiếp khơng phải bao giờ cũng sử dụng được trong việc chứng minh ngay cả đối với những bài tốn khá đơn giản như bài tốn sau đây: Ðể bằng phản chứng một khẳng định hay một mệnh đề nào đĩ, ta tìm cách rút ra từ mệnh đề đĩ một điều rõ ràng là vơ lý hay một sự mâu thuẫn. Về mặt kỹ thuật ta thường giả sử rằng mệnh đề cần chứng minh là sai rồi từ đĩ suy ra một điều mâu thuẫn với giả thiết hay các tiền đề của bài tốn, từ đĩ đi đến kết luận rằng mệnh đề là đúng. Ngồi ra phép chứng minh phản chứng cịn cĩ thể được thực hiện như sau: ta giả sử mệnh đề cần chứng minh là sai, kết hợp với giả thiết đã cho để suy ra được một điều mâu thuẫn nào đĩ rồi từ đĩ kết luận rằng mệnh đề là đúng. Ví dụ 5.14 Cho 101 đồ vật và 5 cái hộp, cần đặt hết cả 101 đồ vật vào trong 5 cái hộp. Chứng minh rằng tồn tại ít nhất 1 hộp cĩ khơng ít hơn 21 đồ vật. Giải: Giả sử điều cần chứng minh là khơng xảy ra, nghĩa là khơng tồn tại hộp nào cĩ đến 21 đồ vật (hay ít hơn 21 đồ vật). Khi đĩ, với 5 hộp cĩ thể đựng được thì số đồ vật lớn nhất là 5.20=100<101 (mâu thuẫn) Vậy điều phải chứng minh là đúng. Ví dụ 5.15 Cho 7 đoạn thẳng cĩ độ dài lớn hơn 10 và nhỏ hơn 100. Chứng minh rằng luơn tìm được 3 đoạn để cĩ thể ghép thành một tam giác. Giải: Trước hết sắp xếp các đoạn đã cho theo thứ tự tăng dần của độ dài a1, a2,..., a7, và chứng minh rằng trong dãy đã xếp luơn tìm được 3 đoạn liên tiếp sao cho tổng của 2 đoạn đầu lớn hơn đoạn cuối (vì điều kiện để 3 đoạn cĩ thể ghép thành một tam giác là tổng của 2 đoạn nhỏ hơn đoạn thứ ba). TỐN RỜI RẠC Khoa Cơng nghệ Thơng tin - ĐHSPKT Hưng Yên Trang 44 Giả sử điều cần chứng minh là khơng xảy ra, nghĩa là đồng thời xảy ra các bất đẳng thức sau: a1 + a2 ≤ a3 a2 + a3 ≤ a4 a3 + a4 ≤ a5 a4 + a5 ≤ a6 a5 + a6 ≤ a7 Từ giả thiết a1, a2 cĩ giá trị lớn hơn 10, ta nhận được a3 > 20 . Từ a2 >10 và a3 > 20 ta nhận được a4 > 30, a5 > 50, a6 > 80 và a7 > 130. Điều a7 > 130 là mâu thuẫn với giả thiết các độ dài nhỏ hơn 100. Cĩ mâu thuẫn này làdo giả sử điểu cần chứng minh khơng xảy ra. Vậy, luơn tồn tại 3 đoạn liên tiếp sao cho tổng của 2 đoạn đầu lớn hơn đoạn cuối. Hay nĩi cách khác là 3 đoạn này cĩ thể ghép thành một tam giác. 5.5. Chứng minh bằng quy nạp Định nghĩa Quy nạp và đệ quy là hai khái niệm cực kì quan trọng trong tốn học và trong tin học. Vì vậy nắm rõ được bản chất về mặt kiến thức, về mặt phương pháp cũng như tư duy là điều bất cứ ai trong chúng ta đều mong muốn hướng t