Bài giảng Toán rời rạc (Bản mới)

138 trang phuongnguyen 6890

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc (Bản mới)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_toan_roi_rac_ban_moi.doc

Nội dung text: Bài giảng Toán rời rạc (Bản mới)

1 Bài giảng Tốn rời rạc
2 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ố Boole. 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. Điều này cũng đúng với vị trí của modul (vì người học sẽ tiếp cận modul Tốn rời rạc 2 nĩi về lý thuyết đồ thị cũng như về ngơn ngữ hình thức) 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
3 nghiệp. Mọi gĩp xin gửi về: Khoa Cơng nghệ Thơng tin – Trường ĐHSPKT Hưng Yên
4 BÀI 1: TỔNG QUAN MƠN HỌC 1.1. MỞ ĐẦU 1.1.1 Giới thiệ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 tinh 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
5 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 - 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 LẠI 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ẽ
6 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 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ể
7 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, thì thuật tốn là đượ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 thí 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 toná 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ĩ 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
8 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ệ - 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à 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 – 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 - đượ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”
9 Như chúng ta đã 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), cấu trúc này chúng ta sẽ sớm tiếp cận. 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, chúng ta 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
10 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à bạn cĩ khả năng vượt qua các kỳ thi bằng cách học rất ít trước kỳ thi, nhưng với cách học như vậy thì kiến thức tốn mà bạn học 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 của bạ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 của bạn sẽ làm hại chính bạn.
11 BÀI 2: 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. LOGIC MÊNH ĐỀ (propositional logic) 2.1.1 Những khái niệm cơ bản 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
12 đị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. 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".
13 Ví dụ: 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: "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!" đều khơng phải là mệnh đề. 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 phải 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 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.1.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. 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.
14 Ví dụ 1: 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( a ) = 0. Ví dụ 2: Nếu b = "15 lớn hơn 30" thì mệnh đề phủ định cĩ thể diễn đạt như sau: = "Khơng phải 15 lớn hơn 30" hoặc = "15 khơng lớn hơn 30" hoặc = "15 nhỏ hơn 30" Ở đây G(b) = 0 cịn G( ) = 1. Ví dụ 3: Nếu c = "Chuyến tàu TN1 hơm nay bãi bỏ" thì mệnh đề phủ định cĩ thể diễn đạt như sau: = "Chuyến tàu TN1 hơm nay khơng bãi bỏ". Nếu qua xác minh mệnh đề c đú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". 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. ả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
15 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ụ 1: "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: "Thành phố Hồ Chí Minh là thành phố lớn nhất trong cả nước nhưng khơng phải 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. Ví dụ 3: "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". 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
16 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. 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ụ 1: "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. Ví dụ 2: "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ừ. "20 là số lẻ hoặc nĩ chia hết cho 2"← là phép tuyển loại trừ. 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,
17 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ụ: "15 cĩ chữ số tận cùng bằng 5 suy ra 15 chia hết cho 5"← 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"←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ụ: "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"← 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. 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:
18 "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". 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. Chú ý: 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ụ: "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
19 b ta chứng minh hai mệnh đề a b và b a. 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.1.3 Sự tương đương lơgic và luật Cơng thức 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ụ: (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)
20 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 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. Đẳng thức 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
21 (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) Chứng minh đẳng thức Để chứng minh một đẳng thức trong lơgic mệnh đề ta thường dùng phương pháp lập bảng giá trị chân lí. Ví dụ 1: Chứng minh:≡ Bảng giá trị chân lí a b 1 1 0 0 1 0 1 1 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. Ví dụ 2: Chứng minh: Bảng giá trị chân lí
22 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. 2.2. LOGIC VỊ TỪ (predicate logic) 2.2.1 Vị từ Ta xét các ví dụ sau: Ví dụ 1: "Số tự nhiên n chia hết cho 5". Về phương diện ngơn ngữ thì đây là một câu. Nhưng câu này chưa phản ánh tính đúng hoặc sai một thực tế khách quan nào, cho nên nĩ chưa phải là mệnh đề. Song nếu ta thay n bằng số tự nhiên cụ thể, chẳng hạn: Thay n = 100 ta được mệnh đề đúng: "Số 100 chia hết cho 5". Thay n = 101 ta được mệnh đề sai: "Số 101 chia hết cho 5". Ví dụ 2: "x + 3 > 7". Tương tự như trong ví dụ 1, x + 3 > 7 chưa phải là mệnh đề, song nếu ta thay x bởi một số thực cụ thể, chẳng hạn: Thay x = 0 ta được mệnh đề sai: "0 + 3 > 7". Thay x = 5 ta được mệnh đề đúng: "5 + 3 > 7". Ví dụ 3: "Ơng A là nhà 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
23 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). 2.2.2 Lượng từ Mệnh đề tồn tại Cho T(x) là hàm mệnh đề xác định trên miền X. Nếu ta đặt thêm cụm từ "Tồn tại sao cho " vào trước hàm mệnh đề T(x) ta được mệnh đề: "Tồn tại sao cho T(x)" Ta gọi mệnh đề cĩ cấu trúc như trên là mệnh đề tồn tại. Kí hiệu là: hoặc Kí hiệu gọi là lượng từ tồn tại. Ví dụ: "Tồn tại số thực x sao cho x + 4 > 7" là mệnh đề đúng. Kí hiệu là: "Tồn tại số tự nhiên n sao cho n chia hết cho 5" là mệnh đề đúng. Kí hiệu là: "Tồn tại số thực x sao cho x2 + 1 = 0" là mệnh đề sai. 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
24 sao cho T(x)". Mệnh đề tổng quát Cho T(x) là hàm mệnh đề xác định trên miền X. Nếu ta đặt thêm cụm từ "Với mọi ta cĩ " vào trước hàm mệnh đề T(x) ta được mệnh đề: "Với mọi ta cĩ T(x)" Ta gọi mệnh đề cĩ cấu trúc như trên là mệnh đề tổng quát (hoặc 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ụ: "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". "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".
25 Phủ định của mệnh đề tồn tại và tổng quát Phủ định các mệnh đề tồn tại và tổng quát được thiết lập theo hai quy tắc dưới đây: Như vậy, hai mệnh đề: và là phủ định của nhau. và là phủ định của nhau. Ví dụ: Kí hiệu là:
26 Kí hiệu là: 2.2.3 Ứng dụng Giải bài tốn bằng suy luận lơgic Thơng thường khi giải một bài tốn dùng cơng cụ của lơgic mệnh đề ta tiến hành theo các bước sau: Bước 1: Phiên dịch đề bài từ ngơn ngữ đời thường sang ngơn ngữ của lơgic mệnh đề: Tìm xem bài tốn được tạo thành từ những mệnh đề nào. Diễn đạt các điều kiện (đã cho và phải tìm) trong bài tốn bằng ngơn ngữ của lơgic mệnh đề Bước 2: Phân tích mối liên hệ giữa điều kiện đã cho với kết luận của bài tốn bằng ngơn ngữ của lơgic mệnh đề. Bước 3: Dùng các phương pháp suy luận lơgic dẫn dắt từ các điều kiện đã cho tới kết luận của bài tốn. Ví dụ: Tại Tiger Cup 98 cĩ bốn đội lọt vào vịng bán kết: Việt Nam, Singapor, 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: Singapor nhì, cịn Thái Lan ba. Quang: Việt Nam nhì, cịn Thái Lan tư. Trung: Singapor 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.
27 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 Singapor 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 Singapor nhất, Việt Nam nhì, Thái Lan ba cịn Inđơnêxia đạt giải tư. 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ụ: 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: 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
28 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".
30 BÀI 3: MỘT SỐ PHƯƠNG PHÁP CHỨNG MINH 3.1 GIỚI THIỆU (tầm quan trọng, ứng dụng, các thuật ngữ) 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 . 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. Correctness prevents us from fooling ourselves. – Đầ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à
31 đầ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. Một số thuật ngữ: Một hệ thống tốn học bao gồm • Đị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 đề.
32 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. 3.2 CHỨNG MINH NHỜ LUẬT SUY DIỄN Chúng ta sẽ giới thiệu luật suy diễn cho logic mệnh đề. Những luật này cung cấp cho chúng ta một chuỗi các bước biến đổi để đi tới kết luận một cách logic nhờ tập các giả thiết. Phép lặp thừa (p^(p->q))->q được coi là cơ sở cho luật suy diễn modus ponens p->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.
33 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 3. Bảng sau đây đưa ra các luật suy diễn cho các luận điểm cho các vị từ 4. Luật modus ponens tổng quát:
34 R(a) S(a) với mọi a D  z D [ R(z) S(z)] 5. Luật generalizing from the generic particular xác định rất nhiều trong tốn học 6. Luật existential speciﬁcation được dùng để lập luận chỉ ra một số đối tượng tồn tại tuy nhiên khơng biết đích xác giá trị của nĩ. Một số ví dụ 3.3 CHỨNG MINH CÁC MỆNH ĐỀ SUY DIỄN Bây giờ chúng ta sẽ làm rõ hơn về các phương pháp xây dựng chứng minh, chúng ta sẽ mơ tả các chứng minh cho các loại mệnh đề khác nhau. Trong nhiều định lý, kỹ thuật chứng minh các mệnh đề kiểu kéo theo là quan trọng. Ta thấy p q sẽ luơn đúng trừ khi p là đúng nhưng q sai. Chú ý
35 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; 3.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? - Các định lý nào, các kết qua nào cĩ thể sử dụng được đề ta suy ra được một điều gì đĩ từ những sự kiện, những yếu tố hiện đang cĩ? - Việc áp dụng định lý cĩ khả năng sẽ dẫn đến kết luận hay kết quả mong muốn hay khơng? - Trong trường hợp ở một bước suy diễn nào đĩ cĩ nhiều định lý hay nhiều luật nào đĩ cĩ thể áp dụng được và cũng cĩ kkhả năng sẽ dẫn đến kết luận hay kết quả mong muốn thì ta sẽ chọn cái nào? - Ðến một giai đoạn nào đĩ, khi gặp phải sự bế tắc thì ta sẽ phải tự hỏi rằng phải chăng bài 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
36 trực tiếp. Ví dụ 1: Chứng minh rằng { Nếu n là số lẻ thì n2 là số lẻ } Giải : Giả sử rằng giả thiết của định lý này là đúng, tức là n là số lẻ. Ta cĩ n = 2k + 1 ( k=0,1,2, ) n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1 là lẻ. Vậy nếu n là số lẻ thì n2 là số lẻ. Ví dụ 2 : Cho hàm mệnh đề P(n) = " Nếu n>1 thì n 2 >n " Chứng minh rằng P(n) là đúng với n là số nguyên dương. Giải : Giả sử n > 1 là đúng, ta cĩ : n = 1 + k ( k ≥ 1) n2 = ( 1 + k )2 = 1 + 2k + k2 = (1 + k) + k + k2 > n Vậy Nếu n>1 thì n2 >n . Ví dụ 3 Giả sử p, r, s, t, u là các mệnh đề sau cho ta cĩ các mệnh đề sau đây la` đúng: (1) p r (2) r s (3) t   s (4)  t  u (5)  u. Hãy chứng minh mệnh đề p là sai, tức là chứng minh mệnh đề  p la` đúng.
37 Chứng minh: Áp dụng luật suy diễn tam đoạn luận, từ (1) và (2) ta suy ra: (6) p s Áp dụng luật logic về phép tốn kéo theo ta cĩ thể viết lại (3) dưới dạng: (7) s t Áp dụng luật suy diễn tam đoạn luận, từ (6) và (7) ta suy ra: (8) p t Áp dụng luật logic về phép tốn kéo theo ta cĩ thể viết lại (4) dưới dạng: (9) t u Áp dụng luật suy diễn tam đoạn luận, từ (8) và (9) ta suy ra: (10) p u Áp dụng luật suy diễn Modus Tollens, từ (10) và (5) ta suy ra: (11)  p Vậy mệnh đề  p là đúng. Ví dụ 4: Cho p(x), q(x) và r(x) là các vị từ theo biến x (x A), và a là một phần tử cố định nhưng tùy ý của tập hợp A. Giả sử ta cĩ các mệnh đề sau đây la` đúng: (1) x A : p(x) q(x) (2) x A : q(x) r(x) (3) p(a) Chứng minh rằng mệnh đề r(a) la` đúng. Chứng minh: Áp dụng kết quả từ bảng 3 trong 3.2 ta suy ra: (4) x A : p(x) r(x) Áp dụng kết quả bảng 3 trong 3.2 ta suy ra: (5) r(a) Vậy mệnh đề r(a) la` đúng. 3.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: Chứng minh định lý { Nếu 3n + 2 là số lẻ thì n là số lẻ }
38 Giải : Giả sử ngược lại kết luận của phép kéo theo là sai, tức n là chẳn. Ta cĩ n = 2k( k N ) 3n + 2 = 3.2k + 2 = 2( 3k + 1 ) là số chẳn Vậy Nếu 3n + 2 là số lẻ thì n là số lẻ Nhận xét Cĩ những bài tốn cĩ thể sử dụng phương pháp chứng minh trực tiếp hay gián tiếp đều được cả. Tuy nhiên, cĩ những bài 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ụ 6 : Sử dụng chứng minh gián tiếp để chứng minh rằng " Nếu n>1 thì n2 >n " Giải : Giả sử ngược lại kết luận của phép kéo theo là sai, tức là n2 1 thì n2 >n. Ví dụ 7 : Sử dụng chứng minh trực tiếp để chứng minh rằng " Nếu 3n + 2 là số lẻ thì n là số lẻ ". Giải : Giả sử 3n + 2 là số lẻ là đúng. Nhận thấy rằng vì 2 là số chẳn nên suy ra được 3n là số lẻ. Vì 3 là số lẻ do đĩ n là số lẻ. Vậy Nếu 3n + 2 là số lẻ thì n là số lẻ. Ở đâ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. 3.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.
39 Ví dụ 8: 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" 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 = 9k2 + 6k + 1 = 3(3k2 + 2k) + 1 khơng chia chẳn 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 chẳn cho 3. Do đĩ, P2 → Q là đúng. 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ụ 9: 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
40 p3: n2 -1 chia hết cho 3 3.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ụ 10: Chứng minh rằng mệnh đề P(0) là đúng trong đĩ P(n) là mệnh đề “nếu n>1 thì n2>n”. Giải: Mệnh đề P(0) chỉ ra rằng “nếu 0>1 thì 0 2>0”. Bởi vì giả thiết 0>1 là sai, do đĩ P(0) là đúng. Ví dụ 11: Với mọi n, nếu n vừa lẻ vừa chẵn, thì n2 = n + n. Giải: Khẳng định “n vừa lẻ vừa chẵn” là sai, bởi vì khơng cĩ số nào vừa lẻ vừa chẵn. Do vậy mọi kết luận là đúng. 3.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ụ 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.
41 Giải: Mệnh đề P(0) là “nếu a>=b, thì a0>=b0 ” bởi vì a0=b0 =1, vậy P(0) là đúng. Vì vậy, P(0) là đúng. Đây là một ví dụ của chứng minh trivial. Như vậy là khẳng định a>=b khơng cần thiết trong chứng minh. Ví dụ 13: Với mọi số tự nhiên n, nếu n là tổng của hai số nguyên tố, thì hoặc n là chẵn hoặc n là lẻ. Giải: Bất kỳ một số tự nhiên n nào cũng hoặc là chẵn hoặc là lẻ. Do vậy kết luận của phép duy dẫn là đúng bất chấp điều kiện là đúng hay sai. Phép duy dẫn được gọi là phép duy dẫn trivial□ 3.4 CHỨNG MINH 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ài tốn: Chứng minh rằng khơng cĩ hai số nguyên dương m và n sao cho Bằng cách suy nghĩ để tìm một cách chứng minh trực tiếp ta sẽ gặp phải bế tắc: Với q = m/n là một số hữu tỉ cho trước (m và n là các số nguyên dương) ta khơng biết làm thế nào để suy ra một cách trực tiếp rằng q2 2. Ðể 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 đề la` đú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 đề la` đúng.
42 Trở lại bài tốn trên như một ví dụ, chúng ta cĩ thể thực hiện việc chứng minh một cách dễ dàng nhờ phương pháp chứng minh phản chứng. Ví dụ 1: Chứng minh rằng khơng cĩ hai số nguyên dương m và n sao cho Chứng minh phản chứng: Giả sử ta cĩ mệnh đề ngược lại của điều cần phải chứng minh, tức là giả sử rằng: Cĩ hai số nguyên dương m và n sao cho . Vì một phân số cĩ thể viết dưới dạng tối giản, nên ta cĩ thể giả thiết thêm rằng các số dương m và n trong mệnh đề (1) nguyên tố cùng nhau, tức là: m và n khơng cĩ ước số chung lớn hơn 1. Do m 2 = 2n2, từ (1) ta suy ra: Cĩ hai số nguyên dương m và n nguyên tố cùng nhau sao cho m2 = 2n2. Với m và n là hai số nguyên dương thỏa mãn điều kiện trong mệnh đề (2) ở trên thì ta dễ dàng lần lượt suy ra được các khẳng định sau đây: m và n nguyên tố cùng nhau. m2=2 n2. m là số chẵn. m là số chẵn, tức là m = 2k với k là một số nguyên dương. n2 = 2k2. n2 là số chẵn. n là số chẵn. 2 là một ước số chung của m và n, và 2 > 1. Sự mâu thuẫn do (3) và (10). Từ lập luận trên ta đi đến kết luận: khơng cĩ hai số nguyên dương m và n sao cho . Ghi chú: Ngồi cách chứng minh phản chứng ta cịn cĩ thể thực hiện phép chứng minh gián tiếp mà về thực chất phương pháp này là cùng loại với phương pháp chứng minh phản chứng. Trong cách chứng minh gián tiếp người ta thiệt lập sự đúng đắn của một mệnh đề bằng cách chứng minh rằng mệnh đề ngược lại (tức là mệnh đề phủ định của mệnh đề đĩ) là sai. Ví dụ 2 : Một trong những cách giải bài tốn tồn tại là dùng lập luận phản chứng. Cho 7 đoạn thẳng cĩ độ dài lớn hơn 10 và nhỏ hơn 100. Chứng
43 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). 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. 3.5 CHỨNG MINH BẰNG QUY NẠP 3.5.1 Đị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ới. Thêm vào đĩ, khá nhiều bạn trong chúng ta cịn cho rằng, bản chất của phép quy nạp chính là phép đệ quy địi hỏi phép quy nạp. Về mặt định nghĩa, người ta cho rằng, quy nạp là kết luận đi từ trường hợp riêng đi tới trường hợp tổng quát. Nghĩa là, kết luận tổng quát dựa trên việc nghiên cứu các tính chất của nhiều sự kiện, nhiều thí nghiệm hay nhiều quan sát riêng lẻ. Nếu kết luận chung dựa vào nghiên cứu tất cả các sự kiện riêng (các đối tượng, các hình, các số, vv ) thì quy nạp được gọi là đầy đủ hayhồn chỉnh. Nếu kết luận chung dựa vào nghiên cứu một phần của tâp hợp tất cả các sự kiện (các đối tượng) thì quy nạp được gọi là khơng đầy đủ hay khơng hồn
44 chỉnh. Trong nhiều lĩnh vực khác nhau của Tốn học ( số học, hình học, giải tích ) ta thường gặp những bài tốn với yêu cầu chứng minh mệnh đề chứa biến P(n) là một mệnh đề đúng với mọi giá trị nguyên dương của biến n. Một cách khái quát, để chứng minh mệnh đề chứa biến P(n) là một mệnh đề đúng với mọi giá trị nguyên dương của n, ta thực hiện hai bước sau: Bước 1: ( bước cơ sở hay bước mở đầu) Chứng minh P(n) đúng khi n=1. Bước 2: ( bước quy nạp hay bước di truyền) Với k là một số nguyên dương, xuất phát từ giả thiết ( được gọi là giả thiết quy nạp) P(n) đúng với n=k, ta chứng minh P(n) cũng là mệnh đề đúng với n=k+1. Chú ý rằng khi chúng ta sử dụng quy nạp tốn học để chứng minh, đầu tiên chúng ta chỉ ra rằng P(1) là đúng. Khi đĩ chúng biết rằng P(2) là đúng, bởi vì P(1) đã ngầm dẫn tới P(2). Hơn nữa, chúng ta cũng chỉ ra được P(3) là đúng vì P(2) đã ngầm dẫn tới P(3). Tiếp tục như vậy P(k) là đúng cho bất kỳ số nguyên dương k nào. Chú ý thêm rằng trong chứng minh quy nạp chúng ta khơng giả định là P(n) đúng với mọi số nguyên dương! Đĩ chỉ là việc giả định rằng nếu P(n) mà đúng thì P(n+1) cũng đúng. Một minh họa hình thức cho quy nập tốn học cĩ thể hình ảnh hĩa bằng hiệu ứng đổ của các quân domino. Tại sao chứng minh quy nạp là đúng? Kỹ thuật chứng minh quy nạp dựa trên cơ sở lập luận chính xác. Giả sử chúng ta đã cĩ P(1) là đúng và mệnh đề P(n) P(n+1) là đúng cho mọi số nguyên n. Để chỉ ra P(n) đúng cho mọi số nguyên dương, giả định cĩ ít nhất một số P(n) là sai. Thì khi đĩ tập S gồm các số nguyên dương để P(n) sai là khác rỗng. Từ đĩ ta kết luận S cĩ ít nhất 1 phần tử, trong các phần tử sai đĩ ta chọn một phần tử, chúng ta ký hiệu là k sao cho P(k) sai cịn P(k-1) đúng (chúng ta luơn chọn được k như vậy nếu khơng thì sao? Sinh viên cĩ
45 thể chứng minh điều này? ). Rõ ràng rằng k khác 1, bởi vì P(1) là đúng (đã được kiểm tra). Bởi vì k dương và lớn hơn 1 nên k-1 nguyên dương. Hơn nữa k-1 nhỏ hơn k, và k-1 khơng nằm trong tập S nên P(k-1) đúng. Phép kéo theo P(k-1) P(k) đúng, mà P(k- 1) đúng nên P(k) phải đúng. Vì vậy, điều này mâu thuẫn với sự lựa chọn của k. Như vậy, P(n) đúng cho mọi số nguyên dương n. 3.5.2 Một số ví dụ về phương pháp chứng minh quy nạp. 3.6. CHỨNG MINH BẰNG CÁCH ĐƯA RA PHẢN VÍ DỤ Nĩi một cách tổng quát, phản ví dụ là việc chỉ ra một tình huống hay trường hợp sai của một khẳng định phổ quát để chứng tỏ rằng khẳng định phổ quát đĩ l à sai. Chẳng hạn như để chứng minh mệnh đề x A : P(x) là sai ta chỉ cần đưa ra một phần tử a cụ thể thuộc tập hợp A mà P(a) là sai. Thật ra làm như vậy tức là ta đã chứng minh mệnh đề x A :  P(x) (cĩ cùng chân trị với mệnh đề  [ x A : P(x)] ) là đúng. Chúng ta cĩ thể nêu lên một bài tốn khác mà đối với nĩ ta phải dùng phản ví dụ. Ðĩ là bài tốn chứng minh một phép suy diễn từ p1, p2, , pn suy ra q là sai. Ðể chứng minh phép suy diễn là sai ta phải chứng minh rằng p1 p2 . . . pn q cụ thể của các biến mệnh đề mà ứng với chúng ta cĩ các tiền đề p1, p2, , pn đều đúng nhưng kết luận q là sai. Ví dụ 1: Hãy kiểm tra suy luận sau đây Sử dụng các phương pháp để kiểm tra một phép suy luận ta cĩ thể thấy được suy luận trên là khơng đúng. Ðể tìm một phản ví dụ ta chỉ cần chỉ ra một trường hợp về chân trị của các biến mệnh đề sao cho các tiền đề trong phép suy luận la` đúng cịn kết luận là sai. Về mặt kỹ thuật ta sẽ tìm p, q, và r thỏa mãn các đẳng thức sau đây:
46 Dễ dàng tìm thấy một trường hợp phản ví dụ là: p = 1, q = 0, r = 1. Vậy suy luận đã cho là khơng đúng. Ví dụ 2: Chứng minh “mọi số nguyên tố là lẻ” là sai. Sinh viên hãy tự làm bài tập này. Ví dụ 3. Mệnh đề sau đúng hay khơng? "Những giá trị của hàm số với n = 0, 1, 2, là những số nguyên tố." Lời giải. Ta tính f(0) = 1, f(1) = 41, f(2) = 43, f(3) = 47, f(4) = 53, f(5) = 61, f(6) =71, f(7) = 83, f(8) = 97, f(9) = 113. Ta cĩ thể tiếp tục tính f(n)cho đến giá trị n = 40,tất cả giá trị này đề là số nguyên tố. Nhưng với n = 41 ta cĩ f(41) = 412. Kết quả f(41) khơng phải là số nguyên tố, nên kết luận của bài tốn là khơng đúng
47 3.7 THẢO LUẬN 3.7.1 Một số ngộ nhận thường gặp • Một ngộ nhận là một luận suy diễn hay một phương pháp chứng minh khác mà nĩ khơng logic. – May yield a false conclusion! • Ngộ nhận khi khẳng định kết luận: – “p q là đúng, và nếu p là đúng, thì p phải là đúng.” (khẳng định này là sai vì F T là đúng) • Ngộ nhận khi bác bỏ giả thiết Fallacy of denying the hypothesis: – “p q là đúng, và nếu p là sai, thì p phải là sai.” (khơng phải vì F T là đúng.) Lập luận vịng • Ngộ nhận (cĩ thể là tường minh hoặc khơng rõ ràng) về việc giả định mỗi luận cứ phải chứng minh nằm trong yêu cầu phải chứng minh. Ví dụ • Chứng minh rằng n là chẵn nếu n2 là chẵn. • Chứng minh “Giả sử n2 là chẵn. khi đĩ n2 =2k với k là số tự nhiên. Ta suy ra n = (2k)/n = 2(k/n). So there is an integer j (namely k/n) such that n=2j. Therefore n is even.” Loại bỏ vịng lập luận Suppose n2 is even 2|n2  n2 mod 2 = 0. Of course n mod 2 is either 0 or 1. If it’s 1, then n1 (mod 2), so n21 (mod 2), using the theorem that if ab (mod m) and cd (mod m) then acbd (mod m), with a=c=n and b=d=1. Now n21 (mod 2) implies that n2 mod 2 = 1. So by the hypothetical syllogism rule, (n mod 2 = 1) implies (n2 mod 2 = 1). Since we know n2 mod 2 = 0 1, by modus tollens we know that n mod 2 1. So by disjunctive syllogism we have that n mod 2 = 0 2|n  n is even. 3.7.2 Một số nhận xét trong chứng minh Chúng ta đã mơ tả một vài phương pháp chứng minh khác nhau, tuy nhiên khơng cĩ thuật tốn nào dùng cho chứng minh được nêu ra. Bởi vì khơng cĩ thuật tốn nào như vậy. Cĩ nhiều định lý mà chứng minh của nĩ dễ dàng tìm thấy bằng việc
48 phân tích trực tiếp từ các giả thiết và định nghĩa của các thành phần trong định lý. Tuy nhiên, thơng thường là khĩ để chứng minh một định lý mà khơng sử dụng khéo léo một số phương pháp chứng minh như trực tiếp, phản chứng, quy nạp hay các kỹ thuật khác. Xây dựng các chứng minh được coi như là một nghệ thuật trong tốn học. Cĩ nhiều định lý tưởng như là đơn giản đã xuất hiện hàng trăm năm mà vẫn chưa được chứng minh. Ví dụ, cĩ một khẳng định “với mọi số tự nhiên dương lớn hơn bốn thì đều bằng tổng của hai số nguyên tố”. Nhiều người vẫn chưa tìm ra một phản ví dụ, mặc dù người ta đã kiểm định tới số 1014. Cịn nhiều cách chứng minh khác, sinh viên cĩ thể tham khảo thêm tại:
49 BÀI 4: LÝ THUYẾT TẬP (THEORY OF SET) 4.1. GIỚI THIỆU VỀ TẬP 4.1.1 Vai trị của tập hợp Lý thuyết tập hợp là một nhánh của tốn học nghiên cứu về tập các đối tượng. Mặc dù bất kỳ một loại đối tượng nào tập hợp với nhau cũng tạo thành tập hợp, nhưng lý thuyết tập chỉ áp dụng cho các đối tượng liên quan trong tốn học. Lý thuyết tập hiện nay được Cantor và Dedekind đưa ra những năm 1870. Sau khi người ta tìm ra một số các nghịch lý trong lý thuyết tập, một số tiên đề đã được Zermelo–Fraenkel đưa ra nhằm hồn thiện lý thuyết tập. Lý thuyết tập, cĩ thể phát biểu bằng logic vị từ cấp I, thường được coi là nền tảng cơ bản của hệ thống tốn học. Ngơn ngữ lý thuyết tập được dùng để định nghĩa hầu hết các đối tượng trong tốn học, ví dụ như hàm hay quan hệ. Đối tượng nghiên cứu của lý thuyết tập là các tập. Trong khi các tập là các đối tượng cơ bản dùng để định nghĩa tất cả các khái niệm khác của tốn học, chúng khơng thể được định nghĩa thơng qua các khái niệm nào khác cơ bản hơn. Như vậy, tập hợp được giới thiệu một cách khơng phải là hình thức, mà nĩ được hiểu một cách nơm na, (như điểm trong tốn học cũng vậy). Hiện nay, trong tốn học hiện đại, tập hợp được nghiên cứu như một nhánh thực sự trong tốn học, các tính chất, tiên đề của nĩ được cơng nhận thơng qua một hệ thống các tiên đề hình thức. Một tập là một loại cấu trúc mới, dùng để diễn tả các đối tượng khác nhau mà khơng cĩ trật tự . Lý thuyết tập cũng giải quyết các thao tác, các quan hệ, các định đề của các tập. Các tập thì cĩ mặt khắp nơi trong hệ thống phần mềm máy tính Tất cả những đối tượng của tốn học đều cĩ thể định nghĩa thơng qua lý thuyết tập (dùng logic vị từ) 4.1.2. Những khái niệm, tính chất cơ bản Định nghĩa: Một tập hợp là một sự lựa chọn các đối tượng được định nghĩa, trong đĩ mỗi một đối tượng được gọi là một thành viên hay là một
50 phần tử của tập đĩ. Ký hiệu x A nghĩa là x là một phần tử của tập A. Ký hiệu x A nghĩa là x khơng là thành viên của A. Tập rỗng: = {} = {x|False} (“null”, “the empty set”) là tập duy nhất khơng chứa bất kỳ một phần tử nào. Biểu diễn tập hợp Khơng phải mọi tập hợp đều cần phải liệt kê rành mạch theo thứ tự nào đĩ. Chúng cĩ thể được mơ tả bằng các tính chất đặc trưng mà nhờ chúng cĩ thể xác định một đối tượng nào đĩ cĩ thuộc tập hợp này hay khơng. Tập hợp cĩ thể được xác định bằng lời: A là tập hợp bốn số nguyên dương đầu tiên. B là tập hợp các màu trên quốc kỳ Pháp. Cĩ thể xác định một tập hợp bằng cách liệt kê các phần tử của chúng giữa cặp dấu {}, chẳng hạn: C = {4, 2, 1, 3} D = {đỏ, trắng, xanh} Các tập hợp cĩ nhiều phần tử cĩ thể liệt kê một số phần tử. Chẳng hạn tập hợp 1000 số tự nhiên đầu tiên cĩ thể liệt kê như sau: {0, 1, 2, 3, , 999}, Tập các số tự nhiên chẵn cĩ thể liệt kê: {2, 4, 6, 8, }. Tập hợp F của 20 số chính phương đầu tiên cĩ thể cho như sau F = {n2 / n là số nguyên và 0 ≤ n ≤ 19} Tập hợp cĩ thể xác định bằng đệ quy. Chẳng hạn tập các số tự nhiên lẻ L cĩ thể cho như sau: Nếu thì Các tập hợp cĩ thể biểu diễn bằng biểu đồ Venn, tên của nhà tốn học người anh John Venn, giới thiệu năm 1881. Trong đĩ biểu đồ Venn, tập vũ trụ U, chứa tất cả các đối tượng được quan tâm, biểu diễn bằng hình chữ nhật. Trong hình chữ nhật Biểu diễn tập hợp trong máy tính: Biểu diễn các phần tử bằng một danh sách khơng cĩ thứ tự khơng
51 hiệu quả đối với các phép tốn tập hợp. Dùng các chuỗi bit để biểu diễn sự tồn tại của một phần tử trong tập hợp. - Xét tập vũ trụ U cĩ n phần tử. Ví dụ U={a,b,c,d,e} - Mỗi tập A Ucĩ thể biểu diễn bằng chuỗi gồm n bit. Ví dụ A={a,d,e} được biểu diễn bằng 10011. - Khi n lớn thì sao? Dùng một danh sách cĩ thứ tự. 4.2 CÁC PHÉP TỐN TRÊN TẬP HỢP 4.2.1 Các định nghĩa Hợp: Hợp của A và B là tập hợp gồm tất cả các phần tử thuộc ít nhất một trong hai tập hợp A và B, ký hiệu A B Ta cĩ A B = {x: x A hoặc x B} {a,b,c}{2,3} = {a,b,c,2,3} {2,3,5}{3,5,7} = {2,3,5,3,5,7} ={2,3,5,7} Giao: Giao của hai tập hợp A và B là tập hợp tất cả các phần tử vừa thuộc A, vừa thuộc B, ký hiệu A B Ta cĩ A B = {x: x A và x B} Ví dụ: {a,b,c}{2,3} = ?
52 {2,4,6}{3,4,5} = ? Hiệu: Hiệu của tập hợp A với tập hợp B là tập hợp tất cả các phần tử thuộc A nhưng khơng thuộc B, ký hiệu A B Ta cĩ: A \ B = {x: x A và x B} Lưu ý, A \ B B \ A Phần bù: là hiệu của tập hợp con. Nếu A B thì B \ A được gọi là phần bù của A trong B, ký hiệu CAB Phần bù của A trong B Trong nhiều trường hợp, khi tất cả các tập hợp đang xét đều là tập con của một tập hợp U (được gọi là tập vũ trụ-đơi khi cĩ nghĩa như trường hay khơng gian - trong vật lý), người ta thường xét phần bù của mỗi tập A, B, C, đang xét trong tập U, khi đĩ ký hiệu phần bù khơng cần chỉ rõ U mà ký hiệu đơn giản là CA,CB, hoặc , Ví dụ: Z N { , -1, 0, 1, 2, } {0, 1, } = {x | x is an integer but not a nat. #}
53 = {x | x is a negative integer} = { , -3, -2, -1} Tích đề các Tích Đề-các của hai tập hợp tích Đề-các (Cartesian product). Xét trường hợp đơn giản gồm hai tập . Tích Đề-các là tập tất cả các cặp cĩ trật tự sắp xếp được sinh ra bởi một phần tử thuộc với phần tử đứng kế tiếp . Biểu diễn: Tích Đề-các của một số hữu hạn nhiều hơn hai tập Giả sử bây giờ chúng ta cĩ một lớp các tập . Nếu tập hữu hạn, chẳng hạn cĩ dạng , thì tích Đề-các được định nghĩa là một tập hợp của các bộ -số sao cho với mỗi . Ta gọi là tọa độ thứ của , và là cấu phần thứ của. Tích Đề-các của vơ số các tập hợp Khi là một họ khơng đếm được hoặc vơ hạn các tập hợp, để định nghĩa tích Đề- các , ta cần sử dụng đến khái niệm hàm số (sẽ đề cập sau). Theo cách này, được định nghĩa là một tập tất cả các hàm sao cho: . 4.2.2 Các tính chất cơ bản Các phép tốn trên tập hợp cĩ các tính chất sau: Luật luỹ đẳng A A = A A A = A Luật nuốt (cịn gọi là luật hấp thụ)
54 A (A B) = A A (A B) = A Luật nuốt cịn được viết dưới dạng khác như sau: Nếu A B thì A B = B và A B = A Luật giao hốn: A B = B A A B = B A Luật kết hợp: A (B C) = (A B) C A (B C) = (A B) C Luật phân phối: A (B C) = (A B) (B C) A (B C) = (A B) (A C) Luật De Moocgan: = = 4.3 LỰC LƯỢNG CỦA TẬP HỢP - Hữu hạn và vơ hạn Lực lượng của một tập hợp chính là số phần tử trong tập hợp đĩ Khái quát hố khái niệm số lượng phần tử của các tập hợp hữu hạn là khái niệm lực lượng của tập hợp (Cardinality). Hai tập hợp được gọi là cĩ cùng lực lượng nếu cĩ một song ánh giữa chúng. Các tập hợp hữu hạn cĩ cùng lực lượng khi và chỉ khi chúng cĩ cùng số phần tử theo nghĩa thơng thường. Tập hợp A và tập hợp B cĩ cùng lực lượng Khác biệt cơ bản của các tập hữu hạn với các tập vơ hạn là mọi tập hữu hạn khơng cĩ cùng lực lượng với một tập con thực sự của nĩ. Đối với các tập hợp vơ hạn thì khơng phải như vậy. Sau đây là một vài ví dụ đơn giản: Tập con là tập con thực sự của , tuy nhiên ta cĩ thể kiểm tra ánh xạ sau là song ánh hay khơng:
55 Nghĩa là chúng cĩ cùng lực lượng. Georg Cantor đã chứng minh rằng khơng thể cĩ một song ánh giữa tập các số tự nhiên và tập hợp các số thực, vì thế lực lượng của tập hợp số tự nhiên là "nhỏ hơn" lực lượng của tập số thực. Các tập cĩ cùng lực lượng với tập số tự nhiên được gọi là các tập đếm được, các tập hợp cĩ cùng lực lượng với tập số thực được gọi là tập cĩ lực lượng continuum. Nếu ký hiệu là và là ,thì ta cĩ: < . Tuy nhiên, cĩ hay khơng một tập hợp cĩ lực lượng lớn hơn lực lượng đếm được và nhỏ hơn lực lượng continuum lại là vấn đề khác, Cantor giả thiết rằng khơng cĩ điều đĩ (giả thiết continuum - tiếng Anh: continuum hypothesis). Điều này tương đương với: 4.4 THẢO LUẬN Nghịch lý Russell (Russell's paradox) được mơ tả qua một câu chuyện vui về ơng thợ cạo như sau: Cĩ ơng thợ cạo, vốn là cư dân của làng wikipedia, tuyên bố: "Tơi chỉ cạo râu cho những người đàn ơng nào của làng wikipedia mà khơng tự cạo râu". Như thế các đấng nam nhi của làng wikipedia chia làm 2 nhĩm: nhĩm tự cạo râu và nhĩm khơng tự cạo râu. Vậy thì ơng thợ cạo thuộc nhĩm nào đây? Nếu thuộc nhĩm 1 tức là nhĩm tự cạo râu nên ơng khơng cạo cho những người tự cạo râu, tức là ơng khơng cạo cho ơng. Nhưng nếu như vậy thì ơng thuộc nhĩm hai. Nếu ở nhĩm 2 thì ơng sẽ cạo râu cho ơng vì ơng cạo râu cho những người thuộc
56 nhĩm 2. Lúc đĩ hố ra ơng lại tự cao râu cho mình. Té ra ơng này thuộc loại đại rắc rối, xếp vào nhĩm nào cũng gặp mâu thuẫn cả! Thật ra mâu thuẫn này gặp phải khi ta xét tập hợp "E là tập hợp của tất cả các tập hợp" để rồi gặp phải tình huống: “Tập E là một phần tử của chính nĩ hay khơng phải là phần tử của nĩ đều gặp chuyện ngược đời”. Sau đĩ để sửa sai, người ta khơng dùng "tập hợp của tất cả các tập hợp" mà đề xuất một khái niệm mới, tổng quát hơn là "lớp". Trong cơng việc của các nhà tốn học cụ thể, người ta chỉ cần khoanh vùng một tập hợp bao gồm đủ nhiều các tập hợp nào đĩ (nhưng khơng phải là tất cả) để làm việc thì sẽ khơng phải gặp mâu thuẫn nữa. Tập này được gọi là một "vũ trụ" của người làm tốn ứng với một ngành tốn nào đĩ. Một phần của nghịch lý, được khám phá bởi Bertrand Russell vào năm 1901. Giả sử tập M là "tập hợp tất cả các tập hợp khơng chứa chính nĩ". Một cách hình thức : A là một phần tử của tập M nếu và chỉ nếu A khơng là phần tử của chính A. Nếu M chứa chính nĩ thì theo định nghĩa của M,tập M khơng phải là một phần tử của M . Nếu M khơng chứa chính nĩ thì cũng do định nghĩa của M chính M lại là một phần tử của M. Các mệnh đề "M là một phần tử của M" và "M khơng là phần tử của M" cả hai khơng thể đúng, đĩ chính là mâu thuẫn. Nghịch lý này thúc đẩy Russell phát triển lý thuyết kiểu và Ernst Zermelo phát triển lý thuyết tập hợp tiên đề ngày nay trở thành lý thuyết tập hợp Zermelo– Fraenkel.
57 BÀI 5: HÀM, DÃY, TỔNG 5.1. GIỚI THIỆU VỀ HÀM 5.1.1. Định nghĩa và sự thể hiện bằng đồ thị 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 ánhxạ, khi tập nguồn và tập đích đều là tập hợp số. Ví dụ một hàm số f xác định trên tập hợp số thực R được miêu tả bằng biểu thức:y =x2 - 5 sẽ cho tương ứng mỗi số thực x với một số thực y duy nhất nhận giá trị là x2- 5, như vậy 3 sẽ tương ứng với 4. Khi hàm f đã được xác định, ta cĩ thể viết f(3) =4. Đơi khi chữ hàm được dùng như cách gọi tắt thay cho hàm số. Tuy nhiên trong các trường hợp sử dụng khác, hàm mang ý nghĩa tổng quát của ánh xạ, như trong lý thuyết hàm. Các hàm hay ánh xạ tổng quát cĩ thể là liên hệ giữa các tập hợp khơng phải là tập số. Ví dụ cĩ thể định nghĩa một hàm là qui tắc cho tương ứng mỗi hãng xe với tên quốc gia xuất xứ của nĩ, chẳng hạn cĩ thể viết Xuất_xứ(Honda) = Nhật. Định nghĩa Cho X, Y là hai tập hợp số, ví dụ tập số thực R, hàm số f xác định trên X, nhận giá trị trong Y là một qui tắc cho tương ứng mỗi số x thuộc X với một số y duy nhất thuộc Y. Ký hiệu Với: hoặc hoặc
58 Tập X gọi là miền xác định. Tập Y gọi là miền giá trị. x gọi là biến độc lập hay cịn gọi là đối số. y gọi là biến phụ thuộc hay cịn được gọi là hàm số. f(x) được gọi là giá trị của hàm f tại x. f AB f y ba x A B 5.1.2 Các dạng của hàm số Đơn ánh, song ánh, tồn á Như trên đã đề cập, hàm số là một trường hợp ánh xạ, nên người ta cũng miêu tả hàm số dưới 3 dạng là đơn ánh, tồn ánh và song ánh. Đơn ánh Một hàm số là đơn ánh khi nĩ áp dụng lên 2 đối số khác nhau luơn cho 2 giá trị khác nhau. Một cách chặt chẽ, hàm f, xác định trên X và nhận giá trị trong Y, là đơn ánh nếu như nĩ thỏa mãn điều kiện với mọi x1 và x2 thuộc X và nếu x1 ≠ x2 thì f(x1) ≠ f(x2). Nghĩa là, hàm số f là đơn ánh khi và chỉ khi: Với đồ thị hàm số y = f(x) trong hệ tọa độ Đề các, mọi đường thẳng vuơng gĩc với trục đối số Ox sẽ chỉ cắt đường cong đồ thị tại nhiều nhất là một điểm Tồn ánh Hàm số f đươc gọi là tồn ánh nếu như với mọi số y thuộc Y ta luơn tìm đươc ít nhất một số x thuộc X sao cho f(x) = y. Theo cách gọi của ánh xạ thì điều kiện này cĩ nghĩa là mỗi phần tử y thuộc Y đều là tạo ảnh của ít nhất một mẫu x thuộc X qua ánh xạ f. Nghĩa là, hàm số f là tồn ánh khi và chỉ khi:
59 cũng tức là Đồ thị hàm y = f(x) cắt đường thẳng y = y0 y0 Song ánh Một hàm số vừa là đơn ánh vừa là tồn ánh được gọi là song ánh. Hàm hợp Cho các hàm số: trong đĩ X, Y, Z là các tập hợp số nĩi chung. Hàm hợp của f1 và f2 là hàm số: được định nghĩa bởi: Cĩ thể ký hiệu hàm hợp là: Ví dụ, hàm số f(x) = sin (x2+1) là hàm số hợp f2(f1(x)), trong đĩ f2(y) = sin(y), f1(x) = (x2 +1).
60 Việc nhận biết một hàm số là hàm hợp của các hàm khác, trong nhiều trường hợp cĩ thể khiến các tính tốn giải tích (đạo hàm, vi phân, tích phân) trở nên đơn giản hơn. Hàm ngược Cho hàm số song ánh: trong đĩ X, Y là tập hợp số nĩi chung. Khi đĩ mổi phần tử y = f(x) với y nằm trong Y đều là ảnh của một và chỉ một phần tử x trong X. Như vậy, cĩ thể đặt tương ứng mỗi phần tử y trong Y với một phần tử x trong X. Phép tương ứng đĩ đã xác định một hàm số, ánh xạ từ Y sang X, hàm số này được gọi là hàm số ngược của hàm số f và được kí hiệu là: Nếu f-1(x) tồn tại ta nĩi hàm số f(x) là khả nghịch. Cĩ thể nĩi tính chất song ánh là điều kiện cần và đủ để hàm f(x) khả nghịch, tức là nếu f(x) là song ánh thì ta luơn tìm được hàm ngược f -1(x) và ngược lại. 5.1.3 Một số ví dụ về hàm • Một mệnh đề cĩ thể được xem như một hàm từ một tình huống
61 nào đĩ và bảng chân lý {T,F} – Một hệ thống logic là một lý thuyết tình huống – p=“It is raining.”; s= our situation here,now – p(s) {T,F}. • Một phép tốn trên mện đề cĩ thể xem như một hàm từ tập cĩ thứ tự của các giá trị chân lý tới các giá trị chân lý: ((F,T)) = T. • Một vị từ cĩ thể xem như một hàm của các đối tượng tới các mệnh đề (hay là các giá trị chân lý) P :≡ “is 7 feet tall”; P(Mike) = “Mike is 7 feet tall.” = False. • Một chuỗibit B độ dái n là một hàm từ các số {1, ,n} (vị trí bit) tới {0,1}. • E.g., B=101 B(3)=1. • Một tập S xác định trong tập vũ trụ U cĩ thể xem như một hàm từ các phần tử của U tới {T, F}, để cho chúng ta biết rằng mỗi phần tử U trong S hay khơng. S={3}; S(0)=F, S(3)=T. • Một thao tác trên tập như ,, cĩ thể xem như một hàm từ một cặp các tập tới các tập. – Ví dụ: (({1,3},{3,4})) = {3} 5.2 CHUỖI. 5.2.1 Giới thiệu và ví dụ Chuỗi là một danh sách các phần tử cĩ tính tới trật tự. Chuỗi được dùng trong tốn học theo nhiều cách. Chúng cĩ thể dùng để biểu diễn nghiêm trong các bài tốn đếm, nĩ cũng là một cấu trúc dữ liệu quan trọng trong khoa học máy tính. Định nghĩa • Một cách hình thức: Một chuỗi {an} được chỉ định bẳng một hàm tạo f:S A với SN (thường S=N hay S=N {0}) và một tập A. • Nếu f là một hàm taọu cho chuỗi {an}, khi đĩ n S, thì ký tự cũng được coi là một phần tử thứ n của S Ví dụ:
62 • Nhiều khi ta viết “a1, a2, ” thay cho {an}, để cho tập chỉ ra được rõ ràng • Một ví dụ về chuỗi vơ hạn: – Xét chuỗi {an} = a1, a2, , trong đĩ (n 1) an= f(n) = 1/n. – Do vậy {an} = 1, 1/2, 1/3, • Xét thêm chuỗi {bn} = b0, b1, trong đĩ bn = ( 1)n. • {bn} = 1, 1, 1, 1, • Như vậy là lặp lại! {bn} là một chuỗi vơ hạn 1 và 1 5.2.2 Nhận dạng chuỗi Một bài tốn hay gặp trong tốn học rời rạc là tìm ra cơng thức hay luật tổng quát cho một chuỗi được đưa ra. Trong một số trường hợp, chỉ một số ít các phần tử đầu được biết, mục tiêu là phải xác định được chuỗi. Ngay cả khi một số phần tử đầu khơng xác định được tồn bộ chuỗi (điều này là do cĩ rất nhiều các chuỗi bắt đầu với bất kỳ một hữu hạn phần tử), nĩ cũng sẽ giúp phỏng đốn được. Khi cĩ được phỏng đốn, chúng ta cần phải tìm cách chứng minh tính đúng đắn của nĩ. Trong quá trình tìm ra luật của chuỗi từ những các phần tử ban đầu, hãy cố gắng tìm ra các đặc điểm chung của chúng. Sau đây là một số câu hỏi giúp cho quá trình tìm kiếm dễ dàng hơn:  Chuỗi cĩ bị lặp lại khơng? Tức là các giá trị giống nhau cĩ xảy ra nhiều lần trên một hàng khơng?  Các phần tử cĩ đạt được từ các phần tử trước bằng cách thêm vào cùng một giá trị hay giá trị đĩ cĩ phụ thuộc thêm vào vị trí của chuỗi hay khơng?  Các phần tử cĩ đạt được từ các phần tử trước bằng cách nhân vào cùng một giá trị cụ thể hay giá trị đĩ phụ thuộc thêm vào vị trí của chuỗi hay khơng?  Các phần tử cĩ đạt được từ các phần tử trước bằng cách kết hợp một số các phần tử trước hay khơng?  Cĩ chu kỳ nào giữa các phần tử khơng? • Ví dụ: Tìm sồ tiếp theo? – 1,2,3,4, – 1,3,5,7,9,
63 – 2,3,5,7,11, – 1, 2, 2, 3, 3, 3, 4,4, 4, 4, – 5, 11, 17, 23, 29, 35, 41, 47, 53, 59, – 1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047 • Khi bài tốn yêu cầu tìm ra hàm tổng quát mà chỉ bằng một số các phần tử của chuỗi thì đây là yêu cầu khơng thực sự rõ ràng. Bởi vì cĩ thể cĩ vơ số các hàm giống nhau một số các phần tử đầu • Chúng ta phải ngầm định là tìm hàm đơn giản nhất, tuy nhiên chúng ta nên hiểu hàm thế nào là đơn giản? Chúng ta cĩ thể định nghĩa đơn giản là khơng phức tạp, tuy nhiên nĩ địi hỏi nhiều những kiến thức mà chúng ta khơng thể thảo luận ở đây. Do vậy câu hỏi thực sự vẫn chưa cĩ câu trả lời xác đáng. 5.2.3 Chuỗi (String) • Trong modul này thì “chuỗi hữu hạn cĩ dạng a1, a2, , an”, tuy nhiên đơi khi chúng ta cũng nĩi tới chuỗi vơ hạn. • Chuỗi cũng thường được xét giới hạn trong các bảng chữ cái alphabet, đơi khi chỉ là 0 và 1. • Độ dài của chuỗi là số phần tử của chuỗi đấy. • Coi  là tập hữu hạn các ký tự, ví dụ như bảng alphabet. • Một chuỗi s trên alphabet  là bất kỳ chuỗi {si} ký tự nào, si . • Nếu a, b, c, là các ký tự, chuỗi s = a, b, c, cĩ thể được viết abc (khơng cĩ dấu phẩy). • Nếu s là một chuỗi hữu hạn và t là một chuỗi, khi ta nối s với t, viết là st, là một chuỗi mới bao gồm các ký tự của s, theo sau là ccs ký tự của t • Độ dài |s| của một chuỗi hữu hạn s là số ký tự của nĩ. • Nếu s là một chuỗi và n N, sn ký hiệu n chuỗi s nối liên tiếp nhâu. • ký hiệu là một chuỗi rỗng, độ dài bằng 0. • Nếu là bảng alphabet và n N, n {s | s là một chuỗi trên cĩ độ dài n}, và *  {s | s là một chuỗi hữu hạn trên }.
64 5.3 TỔNG 5.3.1 Tổng Chúng ta sẽ xem xét khái niệm về tổng. Chúng ta muốn tính tổng của các phần tử: Từ chuỗi {an}. Chúng ta dùng ký hiệu Để ký hiệu cho am + am+1 +···+ an. Chúng ta hãy xem các chỉ số i, j, k dưới đây và tự rút ra kết luận về chúng. Chúng ta cĩ thể áp dụng một số luật tốn học để áp dụng cho tổng. Ví dụ, khi a và b là các số thực, chúng ta cĩ thể: y1, y2, , yn là các số thực. • Cho một tập vơ hạn, chúng ta viết: 5.4. THẢO LUẬN VỀ CÁC CẤU TRÚC CƠ BẢN: Tập, hàm, dãy, tổng. Tìm hiểu lý thuyết và bài tập ở 2 cuốn [1] và [2] những phần liên quan tới hàm, dãy, tổng. Cĩ thể sinh viên cần đọc nhiều lần để cĩ được những kiến thức cơ bản của tốn học
65 mà sau này cịn sử dụng rất nhiều lần.
66 BÀI 6: THUẬT TỐN, SỐ, MA TRẬN VÀ ĐỆ QUI 6.1 THUẬT TỐN (Algorithms) 6.1.1. Giới thiệu Cĩ nhiều lớp bài tốn tổng quát xuất hiện trong tốn học rời rạc. Chẳng hạn, cho một dãy các số nguyên, tìm số lớn nhất; cho một tập hợp, liệt kê các tập con của nĩ; cho tập hợp các số nguyên, xếp chúng theo thứ tự tăng dần; cho một mạng, tìm đường đi ngắn nhất giữa hai đỉnh của nĩ. Khi được giao cho một bài tốn như vậy thì việc đầu tiên phải làm là xây dựng một mơ hình dịch bài tốn đĩ thành ngữ cảnh tốn học. Các cấu trúc rời rạc được dùng trong các mơ hình này là tập hợp, dãy, hàm, hốn vị, quan hệ, cùng với các cấu trúc khác như đồ thị, cây, mạng, Lập được một mơ hình tốn học thích hợp chỉ là một phần của quá trình giải. Để hồn tất quá trình giải, cịn cần phải cĩ một phương pháp dùng mơ hình để giải bài tốn tổng quát. Nĩi một cách lý tưởng, cái được địi hỏi là một thủ tục, đĩ là dãy các bước dẫn tới đáp số mong muốn. Một dãy các bước như vậy, được gọi là một thuật tốn. Khi thiết kế và cài đặt một phần mềm tin học cho một vấn đề nào đĩ, ta cần phải đưa ra phương pháp giải quyết mà thực chất đĩ là thuật tốn giải quyết vấn đề này. Rõ ràng rằng, nếu khơng tìm được một phương pháp giải quyết thì khơng thể lập trình được. Chính vì thế, thuật tốn là khái niệm nền tảng của hầu hết các lĩnh vực của tin học. 6.1.2. Định nghĩa Thuật tốn là một bảng liệt kê các chỉ dẫn (hay quy tắc) cần thực hiện theo từng bước xác định nhằm giải một bài tốn đã cho. Thuật ngữ “Algorithm” (thuật tốn) là xuất phát từ tên nhà tốn học Ả Rập Al-Khowarizmi. Ban đầu, từ algorism được dùng để chỉ các quy tắc thực hiện các phép tính số học trên các số thập phân. Sau đĩ, algorism chuyển thành algorithm vào thế kỷ 19. Với sự quan tâm ngày càng tăng đối với các máy tính, khái niệm thuật tốn đã được cho một ý nghĩa chung hơn, bao hàm cả các thủ tục xác định để giải các bài tốn, chứ khơng phải chỉ là thủ tục để thực hiện các phép tính số học. Cĩ nhiều cách trình bày thuật tốn: dùng ngơn ngữ tự nhiên, ngơn ngữ lưu đồ (sơ đồ khối), ngơn ngữ lập trình. Tuy nhiên, một khi dùng ngơn ngữ lập trình thì chỉ những lệnh được phép trong ngơn ngữ đĩ mới cĩ thể dùng được
67 và điều này thường làm cho sự mơ tả các thuật tốn trở nên rối rắm và khĩ hiểu. Hơn nữa, vì nhiều ngơn ngữ lập trình đều được dùng rộng rãi, nên chọn một ngơn ngữ đặc biệt nào đĩ là điều người ta khơng muốn. Vì vậy ở đây các thuật tốn ngồi việc được trình bày bằng ngơn ngữ tự nhiên cùng với những ký hiệu tốn học quen thuộc cịn dùng một dạng giả mã để mơ tả thuật tốn. Giả mã tạo ra bước trung gian giữa sự mơ tả một thuật tốn bằng ngơn ngữ thơng thường và sự thực hiện thuật tốn đĩ trong ngơn ngữ lập trình. Các bước của thuật tốn được chỉ rõ bằng cách dùng các lệnh giống như trong các ngơn ngữ lập trình. Thí dụ 1: Mơ tả thuật tốn tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên. a) Dùng ngơn ngữ tự nhiên để mơ tả các bước cần phải thực hiện: 1. Đặt giá trị cực đại tạm thời bằng số nguyên đầu tiên trong dãy. (Cực đại tạm thời sẽ là số nguyên lớn nhất đã được kiểm tra ở một giai đoạn nào đĩ của thủ tục.) 2. So sánh số nguyên tiếp sau với giá trị cực đại tạm thời, nếu nĩ lớn hơn giá trị cực đại tạm thời thì đặt cực đại tạm thời bằng số nguyên đĩ. 3. Lặp lại bước trước nếu cịn các số nguyên trong dãy. 4. Dừng khi khơng cịn số nguyên nào nữa trong dãy. Cực đại tạm thời ở điểm này chính là số nguyên lớn nhất của dãy. b) Dùng đoạn giả mã: procedure max (a1, a2, , an: integers) max:= a1 for i:= 2 to n if max <ai then max:= ai {max là phần tử lớn nhất} Thuật tốn này trước hết gán số hạng đầu tiên a 1 của dãy cho biến max. Vịng lặp “for” được dùng để kiểm tra lần lượt các số hạng của dãy. Nếu một số hạng lớn hơn giá trị hiện thời của max thì nĩ được gán làm giá trị mới của max.
68 6.1.3. Các đặc trưng của thuật tốn: Đầu vào (Input): Một thuật tốn cĩ các giá trị đầu vào từ một tập đã được chỉ rõ. Đầu ra (Output): Từ mỗi tập các giá trị đầu vào, thuật tốn sẽ tạo ra các giá trị đầu ra. Các giá trị đầu ra chính là nghiệm của bài tốn. Tính dừng: Sau một số hữu hạn bước thuật tốn phải dừng. Tính xác định: Ở mỗi bước, các bước thao tác phải hết sức rõ ràng, khơng gây nên sự nhập nhằng. Nĩi rõ hơn, trong cùng một điều kiện hai bộ xử lý cùng thực hiện một bước của thuật tốn phải cho những kết quả như nhau. Tính hiệu quả: Trước hết thuật tốn cần đúng đắn, nghĩa là sau khi đưa dữ liệu vào thuật tốn hoạt động và đưa ra kết quả như ý muốn. Tính phổ dụng: Thuật tốn cĩ thể giải bất kỳ một bài tốn nào trong lớp các bài tốn. Cụ thể là thuật tốn cĩ thể cĩ các đầu vào là các bộ dữ liệu khác nhau trong một miền xác định. 6.1.4 Độ phức tạp của thuật tốn. 1. Khái niệm về độ phức tạp của một thuật tốn: Thước đo hiệu quả của một thuật tốn là thời gian mà máy tính sử dụng để giải bài tốn theo thuật tốn đang xét, khi các giá trị đầu vào cĩ một kích thước xác định. Một thước đo thứ hai là dung lượng bộ nhớ địi hỏi để thực hiện thuật tốn khi các giá trị đầu vào cĩ kích thước xác định. Các vấn đề như thế liên quan đến độ phức tạp tính tốn của một thuật tốn. Sự phân tích thời gian cần thiết để giải một bài tốn cĩ kích thước đặc biệt nào đĩ liên quan đến độ phức tạp thời gian của thuật tốn. Sự phân tích bộ nhớ cần thiết của máy tính liên quan đến độ phức tạp khơng gian của thuật tốn. Vệc xem xét độ phức tạp thời gian và khơng gian của một thuật tốn là một vấn đề rất thiết yếu khi các thuật tốn được thực hiện. Biết một thuật tốn sẽ đưa ra đáp số trong một micro giây, trong một phút hoặc trong một tỉ năm, hiển nhiên là hết sức quan trọng. Tương tự như vậy, dung lượng bộ nhớ địi hỏi phải là khả dụng để giải một bài tốn,vì vậy độ phức tạp khơng gian cũng cần phải tính đến.Vì việc xem xét độ phức tạp khơng gian gắn liền với các cấu trúc dữ liệu đặc biệt được dùng để thực hiện thuật tốn nên ở đây ta sẽ tập trung xem xét độ phức tạp thời gian. Độ phức tạp thời gian của một thuật tốn cĩ thể được biểu diễn qua số các phép tốn được dùng bởi thuật tốn đĩ khi các giá trị đầu vào cĩ một
69 kích thước xác định. Sở dĩ độ phức tạp thời gian được mơ tả thơng qua số các phép tốn địi hỏi thay vì thời gian thực của máy tính là bởi vì các máy tính khác nhau thực hiện các phép tính sơ cấp trong những khoảng thời gian khác nhau. Hơn nữa, phân tích tất cả các phép tốn thành các phép tính bit sơ cấp mà máy tính sử dụng là điều rất phức tạp. Thí dụ 3: Xét thuật tốn tìm số lớn nhất trong dãy n số a 1, a2, , an. Cĩ thể coi kích thước của dữ liệu nhập là số lượng phần tử của dãy số, tức là n. Nếu coi mỗi lần so sánh hai số của thuật tốn địi hỏi một đơn vị thời gian (giây chẳng hạn) thì thời gian thực hiện thuật tốn trong trường hợp xấu nhất là n-1 giây. Với dãy 64 số, thời gian thực hiện thuật tốn nhiều lắm là 63 giây. Thí dụ 4:Thuật tốn về trị chơi “Tháp Hà Nội” Trị chơi “Tháp Hà Nội” như sau: Cĩ ba cọc A, B, C và 64 cái đĩa (cĩ lỗ để đặt vào cọc), các đĩa cĩ đường kính đơi một khác nhau. Nguyên tắc đặt đĩa vào cọc là: mỗi đĩa chỉ được chồng lên đĩa lớn hơn nĩ. Ban đầu, cả 64 đĩa được đặt chồng lên nhau ở cột A; hai cột B, C trống. Vấn đề là phải chuyển cả 64 đĩa đĩ sang cột B hay C, mỗi lần chỉ được di chuyển một đĩa. Xét trị chơi với n đĩa ban đầu ở cọc A (cọc B và C trống). Gọi S n là số lần chuyển đĩa để chơi xong trị chơi với n đĩa. Nếu n=1 thì rõ ràng là S1=1. Nếu n>1 thì trước hết ta chuyển n-1 đĩa bên trên sang cọc B (giữ yên đĩa thứ n ở dưới cùng của cọc A). Số lần chuyển n-1 đĩa là S n-1. Sau đĩ ta chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng, ta chuyển n-1 đĩa từ cọc B sang cọc C (số lần chuyển là Sn-1). Như vậy, số lần chuyển n đĩa từ A sang C là: Sn=Sn-1+1+Sn=2Sn-1+1=2(2Sn-2+1)+1=22Sn-2+2+1= =2n-1S1+2n- 2+ +2+1=2n 1. Thuật tốn về trị chơi “Tháp Hà Nội” địi hỏi 2 64 1 lần chuyển đĩa (xấp xỉ 18,4 tỉ tỉ lần). Nếu mỗi lần chuyển đĩa mất 1 giây thì thời gian thực hiện thuật tốn xấp xỉ 585 tỉ năm!
70 Hai thí dụ trên cho thấy rằng: một thuật tốn phải kết thúc sau một số hữu hạn bước, nhưng nếu số hữu hạn này quá lớn thì thuật tốn khơng thể thực hiện được trong thực tế. Ta nĩi: thuật tốn trong Thí dụ 3 cĩ độ phức tạp là n-1 và là một thuật tốn hữu hiệu (hay thuật tốn nhanh); thuật tốn trong Thí dụ 4 cĩ độ phức tạp là 2n 1 và đĩ là một thuật tốn khơng hữu hiệu (hay thuật tốn chậm). 2. So sánh độ phức tạp của các thuật tốn: Một bài tốn thường cĩ nhiều cách giải, cĩ nhiều thuật tốn để giải, các thuật tốn đĩ cĩ độ phức tạp khác nhau. Xét bài tốn: Tính giá trị của đa thức P(x)=anxn+an-1xn-1+ +a1x+a0 tại x0. Thuật tốn 1: Procedure tính giá trị của đa thức (a0, a1, , an, x0: các số thực) sum:=a0 for i:=1 to n sum:=sum+aix0i {sum là giá trị của đa thức P(x) tại x0} Chú ý rằng đa thức P(x) cĩ thể viết dưới dạng: P(x)=( ((anx+an-1)x+an-2)x )x+a0. Ta cĩ thể tính P(x) theo thuật tốn sau: Thuật tốn 2: Procedure tính giá trị của đa thức (a0, a1, , an, x0: các số thực) P:=an for i:=1 to n P:=P.x0+an-i {P là giá trị của đa thức P(x) tại x0} Ta hãy xét độ phức tạp của hai thuật tốn trên.
71 Đối với thuật tốn 1: ở bước 2, phải thực hiện 1 phép nhân và 1 phép cộng với i=1; 2 phép nhân và 1 phép cộng với i=2, , n phép nhân và 1 phép cộng với i=n. Vậy số phép tính (nhân và cộng) mà thuật tốn 1 địi hỏi là: (1+1)+(2+1)+ +(n+1)= n(n )1 +n= n(n )3 . 2 2 Đối với thuật tốn 2, bước 2 phải thực hiện n lần, mỗi lần địi hỏi 2 phép tính (nhân rồi cộng), do đĩ số phép tính (nhân và cộng) mà thuật tốn 2 địi hỏi là 2n. Nếu coi thời gian thực hiện mỗi phép tính nhân và cộng là như nhau và là một đơn vị thời gian thì với mỗi n cho trước, thời gian thực hiện thuật tốn 1 là n(n+3)/2, cịn thời gian thực hiện thuật tốn 2 là 2n. Rõ ràng là thời gian thực hiện thuật tốn 2 ít hơn so với thời gian thực hiện thuật tốn 1. Hàm f1(n)=2n là hàm bậc nhất, tăng chậm hơn nhiều so với hàm bậc hai f2(n)=n(n+3)/2. Ta nĩi rằng thuật tốn 2 (cĩ độ phức tạp là 2n) là thuật tốn hữu hiệu hơn (hay nhanh hơn) so với thuật tốn 1 (cĩ độ phức tạp là n(n+3)/2). Để so sánh độ phức tạp của các thuật tốn, điều tiện lợi là coi độ phức tạp của mỗi thuật tốn như là cấp của hàm biểu hiện thời gian thực hiện thuật tốn ấy. Các hàm xét sau đây đều là hàm của biến số tự nhiên n>0. Định nghĩa 1:Ta nĩi hàm f(n) cĩ cấp thấp hơn hay bằng hàm g(n) nếu tồn tại hằng số C>0 và một số tự nhiên n0 sao cho |f(n)| C|g(n)| với mọi n n0. Ta viết f(n)=O(g(n)) và cịn nĩi f(n) thoả mãn quan hệ big-O đối với g(n). Theo định nghĩa này, hàm g(n) là một hàm đơn giản nhất cĩ thể được, đại diện cho “sự biến thiên” của f(n). Khái niệm big-O đã được dùng trong tốn học đã gần một thế kỷ nay. Trong tin học, nĩ được sử dụng rộng rãi để phân tích các thuật tốn. Nhà tốn học người Đức Paul Bachmann là người đầu tiên đưa ra khái niệm big- O vào năm 1892.
72 Mệnh đề: Cho f1(n)=O(g1(n)) và f2(n) là O(g2(n)). Khi đĩ (f1 + f2)(n) = O(max(|g1(n)|,|g2(n)|), (f1f2)(n) = O(g1(n)g2(n)). Chứng minh. Theo giả thiết, tồn tại C1, C2, n1, n2 sao cho |f1(n)| C1|g1(n)| và |f2(n)| C2|g2(n)| với mọi n > n1 và mọi n > n2. Do đĩ |(f1 + f2)(n)| = |f1(n) + f2(n)| |f1(n)| + |f2(n)| C1|g1(n)| + C2|g2(n)| (C1+C2)g(n) với mọi n > n0=max(n1,n2), ở đâyC=C1+C2 và g(n)=max(|g1(n)| , |g2(n)|). |(f1f2)(n)| = |f1(n)||f2(n)| C 1|g1(n)|C2|g2(n)| C1C2|(g1g2)(n)| vớimọi n> n0=max(n1,n2). Định nghĩa 2: Nếu một thuật tốn cĩ độ phức tạp là f(n) với f(n)=O(g(n)) thì ta cũng nĩi thuật tốn cĩ độ phức tạp O(g(n)). Nếu cĩ hai thuật tốn giải cùng một bài tốn, thuật tốn 1 cĩ độ phức tạp O(g1(n)), thuật tốn 2 cĩ độ phức tạp O(g 2(n)), mà g1(n) cĩ cấp thấp hơn g2(n), thì ta nĩi rằng thuật tốn 1 hữu hiệu hơn (hay nhanh hơn) thuật tốn 2. 3. Đánh giá độ phức tạp của một thuật tốn: 1) Thuật tốn tìm kiếm tuyến tính: Số các phép so sánh được dùng trong thuật tốn này cũng sẽ được xem như thước đo độ phức tạp thời gian của nĩ. Ở mỗi một bước của vịng lặp trong thuật tốn, cĩ hai phép so sánh được thực hiện: một để xem đã tới cuối bảng chưa và một để so sánh phần tử x với một số hạng của bảng. Cuối
73 cùng cịn một phép so sánh nữa làm ở ngồi vịng lặp. Do đĩ, nếu x=a i, thì đã cĩ 2i+1 phép so sánh được sử dụng. Số phép so sánh nhiều nhất, 2n+2, địi hỏi phải được sử dụng khi phần tử x khơng cĩ mặt trong bảng. Từ đĩ, thuật tốn tìm kiếm tuyến tính cĩ độ phức tạp là O(n). 2) Thuật tốn tìm kiếm nhị phân: Để đơn giản, ta giả sử rằng cĩ n=2 k phần tử trong bảng liệt kê a1,a2, ,an, với k là số nguyên khơng âm (nếu n khơng phải là lũy thừa của 2, ta cĩ thể xem bảng là một phần của bảng gồm 2 k+1 phần tử, trong đĩ k là số nguyên nhỏ nhất sao cho n <2k+1). Ở mỗi giai đoạn của thuật tốn vị trí của số hạng đầu tiên i và số hạng cuối cùng j của bảng con hạn chế tìm kiếm ở giai đoạn đĩ được so sánh để xem bảng con này cịn nhiều hơn một phần tử hay khơng. Nếu i < j, một phép so sánh sẽ được làm để xác định x cĩ lớn hơn số hạng ở giữa của bảng con hạn chế hay khơng. Như vậy ở mỗi giai đoạn, cĩ sử dụng hai phép so sánh. Khi trong bảng chỉ cịn một phần tử, một phép so sánh sẽ cho chúng ta biết rằng khơng cịn một phần tử nào thêm nữa và một phép so sánh nữa cho biết số hạng đĩ cĩ phải là x hay khơng. Tĩm lại cần phải cĩ nhiều nhất 2k+2=2log2n+2 phép so sánh để thực hiện phép tìm kiếm nhị phân (nếu n khơng phải là lũy thừa của 2, bảng gốc sẽ được mở rộng tới bảng cĩ 2k+1 phần tử, với k=[log2n] và sự tìm kiếm địi hỏi phải thực hiện nhiều nhất 2[log2n]+2 phép so sánh). Do đĩ thuật tốn tìm kiếm nhị phân cĩ độ phức tạp là O(log 2n). Từ sự phân tích ở trên suy ra rằng thuật tốn tìm kiếm nhị phân, ngay cả trong trường hợp xấu nhất, cũng hiệu quả hơn thuật tốn tìm kiếm tuyến tính. 3) Chú ý: Một điều quan trọng cần phải biết là máy tính phải cần bao lâu để giải xong một bài tốn. Thí dụ, nếu một thuật tốn địi hỏi 10 giờ, thì cĩ thể cịn đáng chi phí thời gian máy tính địi hỏi để giải bài tốn đĩ. Nhưng nếu một thuật tốn địi hỏi 10 tỉ năm để giải một bài tốn, thì thực hiện thuật tốn đĩ sẽ là một điều phi lý. Một trong những hiện tượng lý thú nhất của cơng nghệ hiện đại là sự tăng ghê gớm của tốc độ và lượng bộ nhớ trong máy tính. Một nhân tố quan trọng khác làm giảm thời gian cần thiết để giải một bài tốn là sự xử lý song song - đây là kỹ thuật thực hiện đồng thời các dãy phép tính. Do sự tăng tốc độ tính tốn và dung lượng bộ nhớ của máy tính, cũng như nhờ việc dùng các thuật tốn lợi dụng được ưu thế của kỹ thuật xử lý song song, các bài tốn vài năm trước đây được xem là
74 khơng thể giải được, thì bây giờ cĩ thể giải bình thường. Các thuật ngữ thường dùng cho độ phức tạp của một thuật tốn: Thời gian máy tính được dùng bởi một thuật tốn: 6.2 SỐ NGUYÊN VÀ THUẬT TỐN 6.2.1. Thuật tốn Euclide Phương pháp tính ước chung lớn nhất của hai số bằng cách dùng phân tích các số nguyên đĩ ra thừa số nguyên tố là khơng hiệu quả. Lý do là ở chỗ thời gian phải tiêu tốn cho sự phân tích đĩ. Dưới đây là phương pháp hiệu quả hơn để tìm ước số chung lớn nhất, gọi là thuật tốn Euclide. Thuật tốn này đã biết từ thời cổ đại. Nĩ mang tên nhà tốn học cổ Hy lạp Euclide, người đã mơ tả thuật tốn này trong cuốn sách “Những yếu tố” nổi tiếng của ơng. Thuật tốn Euclide dựa vào 2 mệnh đề sau đây.
75 Mệnh đề 1 (Thuật tốn chia): Cho a và b là hai số nguyên và b 0. Khi đĩ tồn tại duy nhất hai số nguyên q và r sao cho a = bq+r, 0 r r1 > r2 > 0 khơng thể chứa quá a số hạng được. Hơn nữa, từ Mệnh đề 2 ở trên ta suy ra: UCLN(a,b) = UCLN(r0,r1) = UCLN(r1,r2) = = UCLN(rn-2, rn-1) = UCLN(rn-1,rn) = rn. Do đĩ, ước chung lớn nhất là số dư khác khơng cuối cùng trong dãy các phép chia. Thí dụ 6: Dùng thuật tốn Euclide tìm UCLN(414, 662). 662 = 441.1 + 248 414 = 248.1 + 166 248 = 166.1+ 82 166 = 82.2 + 2 82 = 2.41. Do đĩ, UCLN(414, 662) = 2. Thuật tốn Euclide được viết dưới dạng giả mã như sau:
76 Trong thuật tốn trên, các giá trị ban đầu của x và y tương ứng là a và b. Ở mỗi giai đoạn của thủ tục, x được thay bằng y và y được thay bằng x mod y. Quá trình này được lặp lại chừng nào y 0. Thuật tốn sẽ ngừng khi y = 0 và giá trị của x ở điểm này, đĩ là số dư khác khơng cuối cùng trong thủ tục, cũng chính là ước chung lớn nhất của a và b. 6.2.2. Biểu diễn các số nguyên Mệnh đề 3: Cho b là một số nguyên dương lớn hơn 1. Khi đĩ nếu n là một số nguyên dương, nĩ cĩ thể được biểu diễn một cách duy nhất dưới dạng: n = akbk + ak-1bk-1 + + a1b + a0. Ở đây k là một số tự nhiên, a0, a1, , ak là các số tự nhiên nhỏ hơn b và ak 0. Biểu diễn của n được cho trong Mệnh đề 3 được gọi là khai triển của n theo cơ số b, ký hiệu là (akak-1 a1a0)b. Bây giờ ta sẽ mơ tả thuật tốn xây dựng khai triển cơ số b của số nguyên n bất kỳ. Trước hết ta chia n cho b để được thương và số dư, tức là n = bq0 + a0, 0 a0 < b. Số dư a0 chính là chữ số đứng bên phải cùng trong khai triển cơ số b của n. Tiếp theo chia q0 cho b, ta được: q0 = bq1 + a1, 0 a1 < b. Số dư a1 chính là chữ số thứ hai tính từ bên phải trong khai triển cơ số
77 b của n. Tiếp tục quá trình này, bằng cách liên tiếp chia các thương cho b ta sẽ được các chữ số tiếp theo trong khai triển cơ số b của n là các số dư tương ứng. Quá trình này sẽ kết thúc khi ta nhận được một thương bằng 0. Thí dụ 7: Tìm khai triển cơ số 8 của (12345)10. 12345 = 8.1543 + 1 1543 = 8.192 + 7 192 = 8.24 + 0 24 = 8.3 + 0 3 = 8.0 + 3. Do đĩ, (12345)10 = (30071)8. Đoạn giả mã sau biểu diễn thuật tốn tìm khai triển cơ số b của số nguyên n. 6.2.3. Thuật tốn cho các phép tính số nguyên Các thuật tốn thực hiện các phép tính với những số nguyên khi dùng các khai triển nhị phân của chúng là cực kỳ quan trọng trong số học của máy tính. Ta sẽ mơ tả ở đây các thuật tốn cộng và nhân hai số nguyên trong biểu diễn nhị phân. Ta cũng sẽ phân tích độ phức tạp tính tốn của các thuật tốn này thơng qua số các phép tốn bit thực sự được dùng. Giả sử khai triển nhị phân của hai số nguyên dương a và b là: a = (an-1an-2 a1 a0)2 và b = (bn-1 bn-2 b1 b0)2