Bài giảng môn Toán rời rạc

111 trang ngocly 50

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng môn Toán rời rạc", để 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_mon_toan_roi_rac.pdf

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

BỘ GIAO THÔNG VẬN TẢI TRƢỜNG ĐẠI HỌC HÀNG HẢI BỘ MÔN: KHOA HỌC MÁY TÍNH KHOA: CÔNG NGHỆ THÔNG TIN BÀI GIẢNG TOÁN RỜI RẠC TÊN HỌC PHẦN : TOÁN RỜI RẠC MÃ HỌC PHẦN : 17203 TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CHÍNH QUY DÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN HẢI PHÒNG - 2010
MỤC LỤC NỘI DUNG TRANG Chƣơng 1. Đại cƣơng về logic 1 1.1. Phép tính mệnh đề 1 1.1.1. Khái niệm về mệnh đề và chân trị 1 1.1.2. Các phép toán trên mệnh đề 2 1.2. Biểu thức logic 5 1.2.1. Định nghĩa và bảng chân trị của biểu thức logic 5 1.2.2. Sự tương đương logic 8 1.2.3. Giá trị của biểu thức logic 8 1.3. Các luật logic 8 1.3.1. Các luật logic 8 1.3.2. Các quy tắc thay thế 10 1.3.3. Ví dụ áp dụng 11 1.4. Các dạng chuẩn tắc 12 1.4.1. Chuẩn tắc tuyển 12 1.4.2. Chuẩn tắc hội 13 1.5. Quy tắc suy diễn 14 1.5.1. Đại cương về quy tắc suy diễn 14 1.5.2. Kiểm tra một quy tắc suy diễn 16 1.5.3. Các quy tắc suy diễn cơ bản 17 1.5.4. Các ví dụ áp dụng 18 1.6. Vị từ, lượng từ 20 1.6.1. Định nghĩa vị từ và ví dụ 20 1.6.2. Các phép toán trên vị từ 21 1.6.3. Lượng từ và mệnh đề có lượng từ 21 1.6.4. Quy tắc phủ định mệnh đề có lượng từ 23 1.6.5. Một số quy tắc dùng trong suy luận 25 Chƣơng 2. Các phƣơng pháp chứng minh 29 2.1. Các phương pháp chứng minh cơ bản 29 2.1.1. Khái niệm về chứng minh 29 2.1.2. Chứng minh trực tiếp 29 2.1.3. Chứng minh phản chứng 31 2.1.4. Chứng minh bằng cách phân chia trường hợp 33
NỘI DUNG TRANG 2.1.5. Phản ví dụ 34 2.2. Nguyên lý quy nạp 35 2.2.1. Đại cương về quy nạp 35 2.2.2. Các nguyên lý quy nạp thường dùng 36 2.2.3. Các ví dụ 38 Chƣơng 3. Phƣơng pháp đếm 41 3.1. Tập hợp 41 3.1.1. Khái niệm tập hợp 41 3.1.2. Quan hệ “bao hàm trong” và tập hợp con 42 3.1.3. Các phép toán trên tập hợp 43 3.1.4. Tích Decartes của các tập hợp 45 3.2. Các nguyên lý đếm 45 3.2.1. Phép đếm 45 3.2.2. Nguyên lý cộng 46 3.2.3. Nguyên lý nhân 48 3.2.4. Nguyên lý bù trừ 52 3.2.5. Nguyên lý Dirichlet 53 Chƣơng 4. Quan hệ 56 4.1. Quan hệ hai ngôi 56 4.1.1. Định nghĩa quan hệ và ví dụ 56 4.1.2. Các tính chất của quan hệ 57 4.1.3. Biểu diễn quan hệ 58 4.2. Quan hệ tương đương 59 4.2.1. Khái niệm quan hệ tương đương 59 4.2.2. Lớp tương đương và tập hợp tương đương 59 4.3. Quan hệ thứ tự 60 4.3.1. Các định nghĩa 60 4.3.2. Biểu diễn quan hệ thứ tự 62 4.3.3. Tập hữu hạn có thứ tự 63 4.3.4. Sắp xếp topo 63 4.4. Dàn (lattice - tập bị chặn) 65 Chƣơng 5. Đại số Bool 71 5.1. Các phép toán 71
NỘI DUNG TRANG 5.1.1. Các định nghĩa 71 5.1.2. Các tính chất của phép toán hai ngôi 73 5.2. Đại số Bool 78 5.2.1. Định nghiã và các tính chất 82 5.2.2. Đại số Bool và dàn 80 5.3. Các cổng logic và tổ hợp các cổng logic 85 5.3.1. Các cổng logic 85 5.3.2. Mạch logic 86 5.4. Cực tiểu hoá các mạch logic 91 5.4.1. Bản đồ Karnaugh 92 5.4.2. Phương pháp Quine-McCluskey 94
Tên học phần: Toán rời rạc Loại học phần: 1 Bộ môn phụ trách giảng dạy: Khoa học máy tính Khoa phụ trách: CNTT Mã học phần: 17203 Tổng số TC: 2 TS tiết Lý thuyết Thực hành/Xemina Tự học Bài tập lớn Đồ án môn học 45 45 0 0 0 0 Điều kiện tiên quyết: Môn học có thể bố trí học từ học kỳ đầu tiên. Mục tiêu của học phần: Giúp sinh viên nắm được những kiến thức cơ bản về lý thuyết tổ hợp, toán logic, hệ toán mệnh đề. Phương pháp suy diễn và chứng minh. Đại số Bool. Nội dung chủ yếu Giúp sinh viên nắm được những kiến thức cơ bản về lý thuyết tổ hợp, hệ toán mệnh đề, các phương pháp đếm, khái niệm quan hệ, đại số Bool và làm cơ sở cho các môn học chuyên ngành khác. Nội dung chi tiết của học phần: PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH/Xemina BT KT Chƣơng 1. Đại cƣơng về logic 16 16 0 0 0 1.1. Phép tính mệnh đề 2 1.1.1. Khái niệm về mệnh đề và chân trị 1.1.2. Các phép toán trên mệnh đề 1.2. Biểu thức logic 2 1.2.1. Định nghĩa và bảng chân trị của biểu thức logic 1.2.2. Sự tương đương logic 1.2.4. Giá trị của biểu thức logic 1.3. Các luật logic 3 1.3.1. Các luật logic 1.3.2. Các quy tắc thay thế 1.3.3. Ví dụ áp dụng 1.4. Các dạng chuẩn tắc 2
PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH/Xemina BT KT 1.4.1. Chuẩn tắc tuyển 1.4.2. Chuẩn tắc hội 1.5. Quy tắc suy diễn 3 1.5.1. Đại cương về quy tắc suy diễn 1.5.2. Kiểm tra một quy tắc suy diễn 1.5.3. Các quy tắc suy diễn cơ bản 1.5.4. Các ví dụ áp dụng 1.6. Vị từ, lượng từ 4 1.6.1. Định nghĩa vị từ và ví dụ 1.6.2. Các phép toán trên vị từ 1.6.3. Lượng từ và mệnh đề có lượng từ 1.6.4. Quy tắc phủ định mệnh đề có lượng từ 1.6.5. Một số quy tắc dùng trong suy luận Chƣơng 2. Các phƣơng pháp chứng minh 6 5 0 0 1 2.1. Các phương pháp chứng minh cơ bản 2 2.1.1. Khái niệm về chứng minh 2.1.2. Chứng minh trực tiếp 2.1.3. Chứng minh phản chứng 2.1.4. Chứng minh bằng cách phân chia trường hợp 2.1.5. Phản ví dụ 2.2. Nguyên lý quy nạp 3 2.2.1. Đại cương về quy nạp 2.2.2. Các nguyên lý quy nạp thường dùng 2.2.3. Các ví dụ 1 Chƣơng 3. Phƣơng pháp đếm 5 5 3.1. Tập hợp 2 3.1.1. Khái niệm tập hợp 3.1.2. Quan hệ “bao hàm trong” và tập hợp con 3.1.3. Các phép toán trên tập hợp 3.1.4. Tích Decartes của các tập hợp 3.2. Các nguyên lý đếm 3 3.2.1. Phép đếm
PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH/Xemina BT KT 3.2.2. Nguyên lý cộng 3.2.3. Nguyên lý nhân 3.2.4. Nguyên lý bù trừ 3.2.5. Nguyên lý Dirichlet 1 Chƣơng 4. Quan hệ 7 7 4.1. Quan hệ hai ngôi 1 4.1.1. Định nghĩa quan hệ và ví dụ 4.1.2. Các tính chất của quan hệ 4.1.3. Biểu diễn quan hệ 4.2. Quan hệ tương đương 2 4.2.1. Khái niệm quan hệ tương đương 4.2.2. Lớp tương đương và tập hợp tương đương 4.3. Quan hệ thứ tự 3 4.3.1. Các định nghĩa 4.3.2. Biểu diễn quan hệ thứ tự 4.3.3. Tập hữu hạn có thứ tự 4.3.4. Sắp xếp topo 4.4. Dàn (lattice - tập bị chặn) 1 Chƣơng 5. Đại số Bool 11 10 0 0 1 5.1. Các phép toán 2 5.1.1. Các định nghĩa 5.1.2. Các tính chất của phép toán hai ngôi 5.2. Đại số Bool 2 5.2.1. Định nghĩa và các tính chất 5.2.2. Đại số Bool và dàn 5.3. Các cổng logic và tổ hợp các cổng logic 2 5.4. Cực tiểu hoá các mạch logic 4 1 Nhiệm vụ của sinh viên : Tham dự các buổi thuyết trình của giáo viên, tự học, tự làm bài tập do giáo viên giao, tham dự các bài kiểm tra định kỳ và cuối kỳ.
Tài liệu học tập : - Kenneth Rosen, Toán học rời rạc và ứng dụng trong tin học, NXB KHKT Hà nội, 1998. - Nguyễn Tô Thành và Nguyễn Đức Nghĩa, Giáo trình toán học rời rạc, ĐHBK Hà nội, 1994. - Phan Đình Diệu, Lý thuyết Ôtômát hữu hạn và thuật toán, NXB ĐHTHCN, 1977. - Vương Tất Đạt, Lôgic học đại cương, NXB Đại học quốc gia HN, 2002 Hình thức và tiêu chuẩn đánh giá sinh viên: - Hình thức thi cuối kỳ : Thi viết. - Sinh viên phải đảm bảo các điều kiện theo Quy chế của Nhà trường và của Bộ Thang điểm: Thang điểm chữ A, B, C, D, F Điểm đánh giá học phần: Z = 0,2X + 0,8Y.
CHƢƠNG 1 ĐẠI CƢƠNG VỀ LOGIC 1.1. Phép tính mệnh đề 1.1.1. Khái niệm về mệnh đề và chân trị 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 đề. Tuy nhiên trong chương nầy ta chỉ xét đến các mệnh đề toán học, và chúng ta nói vắn tắt các mệnh đề toán học là các mệnh đề. Ðó là những phát biểu để diễn đạt một ý tưởng trọn vẹn và ta có thể khẳng định một cách khách quan là nó đúng hoặc sai. Tính chất cốt yếu của một mệnh đề là nó đúng hoặc sai, và không thể vừa đúng vừa sai. Giá trị đúng hoặc sai của một mệnh đề được gọi là chân trị của mệnh đề. Về mặt ký hiệu, ta thường dùng các mẫu tự (như p, q, r, ) để ký hiệu cho các mệnh đề, và chúng cũng được dùng để ký hiệu cho các biến logic, tức là các biến lấy giá trị đúng hoặc sai. Chân trị "đúng" thường được viết là 1, và chân trị "sai" được viết là 0. Ví dụ 1: Các phát biểu sau đây là các mệnh đề (toán học). 1. 6 là một số nguyên tố. 2. 5 là một số nguyên tố. 3. -3 < 2 4. Tam giác cân có hai góc bằng nhau. 5. H2O là một axít. Các mệnh đề 2, 3, và 4 trong ví dụ trên là những mệnh đề đúng. Nói cách khác chận trị của các mệnh đề nầy là đúng. Các mệnh đề 1, 5 là những mệnh đề sai. Ví dụ 2 : Các phát biểu sau đây không phải là các mệnh đề (toán học) vì tính đúng sai của chúng không xác định. 1. Ai đang đọc sách? (một câu hỏi) 2. Hãy đóng cửa lại đi! 3. Anh ta rất thông minh. 4. Cho x là một số nguyên dương. 5. a là một số chính phương. 6. x + y = z. Trong việc khảo sát các mệnh đề, người ta còn phân ra làm hai loại: mệnh đề sơ cấp (elementary), mệnh đề phức hợp (compound). Mệnh đề sơ cấp là các "nguyên tử" theo nghĩa là nó không thể được phân tích thành một hay nhiều (từ hai trở lên) mệnh đề thành phần đơn giản hơn. Còn mệnh đề phức hợp là mệnh đề được tạo thành từ một hay nhiều mệnh đề khác 1
bằng cách sử dụng các liên kết logic như từ "không" dùng trong việc phủ định một mệnh đề, các từ nối: "và", "hay", "hoặc", "suy ra", v.v Ví dụ : Xét các mệnh đề sau đây. p = "15 chia hết cho 3". q = "2 là một số nguyên tố và là một số lẻ". Ta có p là một mệnh đề sơ cấp. Nhưng q là một mệnh đề phức hợp, vì mệnh đề q được tạo thành từ hai mệnh đề "2 là một số nguyên tố" và "2 là một số lẻ" nhờ vào liên kết logic "và". 1.1.2. Các phép toán trên mệnh đề Ðiều mà chúng ta quan tâm ở đây không phải là xác định tính đúng hoặc sai của một mệnh đề sơ cấp. Bởi vì những mệnh đề nầy thường là những phát biểu nói lên một ý tưởng nào đó trong một phạm vi chuyên môn nhất định. Vấn đề mà ta quan tâm ở đây là làm thế nào để tính toán chân trị của các mệnh đề phức hợp theo các mệnh đề sơ cấp cấu thành mệnh đề phức hợp đó nhờ vào các phép toán logic. Các phép toán logic ở đây là các ký hiệu được dùng thay cho các từ liên kết logic như "không", "và", "hay", "hoặc", "suy ra" hay "nếu thì ", "nếu và chỉ nếu". Các phép toán logic được định nghĩa bằng bảng chân trị (truth table). Bảng chân trị chỉ ra rõ ràng chân trị của mệnh đề phức hợp theo từng trường hợp của các chân trị của các mệnh đề sơ cấp tạo thành mệnh đề phức hợp. Bảng chân trị của các phép toán logic tất nhiên là phản ánh ngữ nghĩa tự nhiên của các từ liên kết tương ứng. Về mặt tự nhiên của ngôn ngữ, trong nhiều trường hợp c ng một từ nhưng có thể có nghĩa khác nhau trong những ngữ cảnh khác nhau. Do đó, bảng chân trị không thể diễn đạt mọi nghĩa có thể có của từ tương ứng với ký hiệu phép toán. Ðiều nầy cho thấy rằng đại số logic là rõ ràng hoàn chỉnh theo nghĩa là nó cho ta một hệ thống logic đáng tin cậy. Ðại số logic còn đặc biệt quan trọng trong việc thiết kế mạch cho máy tính. Bảng chân trị không chỉ dùng để kê ra sự liên hệ chân trị giữa mệnh đề phức hợp với chân trị của các mệnh đề sơ cấp cấu thành nó, mà bảng chân trị còn được dùng với mục đích rộng hơn: liệt kê sự liên hệ chân trị giữa các mệnh với các mệnh đề đơn giản hơn cấu thành chúng. 1.1.2.1. Phép phủ định Cho p là một mệnh đề, chúng ta dùng ký hiệu  p để chỉ mệnh đề phủ định của mệnh đề p. "Sự phủ định" được định nghĩa bởi bảng chân trị sau đây: p  p 0 1 1 0 2
Ký hiệu  được đọc là "không" . Trong một số sách khác, người ta còn dùng các ký hiệu sau đây để chỉ mệnh đề phủ định của một mệnh đề p: ~p, p Trong cột thứ nhất của bảng chân trị, ta liệt kê đầy đủ các trường hợp chân trị có thể có của mệnh đề p. Ở cột thứ hai kê ra chân trị tương ứng của mệnh đề p theo từng trường hợp chân trị của mệnh đề p. Ðịnh nghĩa nầy ph hợp với ngữ nghĩa tự nhiên của sự phủ định : Mệnh đề phủ định  p có chân trị là đúng (1) khi mệnh đề p có chân trị sai (0), ngược lại  p có chân trị sai (0) khi p có chân trị đúng (1). Ví dụ 1 : Nếu ta ký hiệu p là mệnh đề "5 < 3" thì Øp là ký hiệu cho mệnh đề "5 ≥ 3". Trong trường hợp nầy p sai, p đúng. Ta có thể viết p = 0,  p = 1. Ví dụ 2 : Chỉ ra rằng  ( p) và p luôn có c ng chân trị. Giải. Lập bảng chân trị của mệnh đề  ( p): p  p  ( p) 0 1 0 1 0 1 Trên mỗi dòng giá trị trong bảng chân trị ta có chân trị của p và  ( p) đều bằng nhau (so sánh cột 1 và cột 3 trong bảng). Vậy  ( p) và p có c ng chân trị. Ta cũng nói rằng  ( p) tương đương logic với p. Mệnh đề  ( p) thường được viết là  p, vì điều nầy không có gì gây ra sự nhầm lẫn. 1.1.2.2. Phép hội Cho p và q là hai mệnh đề. Ta ký hiệu mệnh đề "p hội q" là p  q. Phép "và", ký hiệu là  , được định nghĩa bởi bảng chân trị sau đây: p q p  q 0 0 0 0 1 0 1 0 0 1 1 1 Chân trị của mệnh đề p  q phụ thuộc vào các chân trị của 2 mệnh đề p, q. Ta có 4 trường hợp chân trị của p  q ứng với 4 trường hợp chân trị của cặp mệnh đề (p,q) là (0,0), (0,1), (1,0), (1,1). Trong 4 trường hợp chỉ có một trường hợp mệnh đề p  q đúng, đó là trường hợp p đúng và q đúng. Qua định nghĩa trên ta nhận thấy rằng các mệnh đề p  q và q  p luôn luôn có c ng chân trị, hay tương đương logic. Tuy nhiên, trong ngôn ngữ thông thường các mệnh đề "p và q" và "q và p" đôi khi có ý nghĩa khác nhau theo ngữ cảnh. Ví dụ: Cho các mệnh đề 3
p = "5 > -7", q = "2721 là một số nguyên tố", r = "một tam giác đều cũng là một tam giác cân". Khi đó ta có : p  q = 0 (p L q sai, tức là có chân trị bằng 0, vì p = 1 và q = 0), p  r = 1 (p L r đúng, tức là có chân trị bằng 1, vì p = 1 và r = 1). Nhận xét: Bằng cách lập bảng chân trị, ta có: 1. Các mệnh đề p và p  p luôn có c ng chân trị. 2. Mệnh đề p   p luôn có chân trị bằng 0 (tức là một mệnh đề luôn sai). Một mệnh đề phức hợp luôn luôn có chân trị là sai trong mọi trường hợp chân trị của các mệnh đề sơ cấp tạo thành nó sẽ được gọi là một sự mâu thuẩn. 1.1.2.3. Phép tuyển Cho p và q là hai mệnh đề. Ta ký hiệu mệnh đề "p hay q" là p  q. Phép "hay", ký hiệu là  , được định nghĩa bởi bảng chân trị sau đây: p q p  q 0 0 0 0 1 1 1 0 1 1 1 1 Chân trị của mệnh đề p  q phụ thuộc vào các chân trị của 2 mệnh đề p, q. Trong 4 trường hợp chỉ có một trường hợp mệnh đề p  q sai, đó là trường hợp p sai và q sai. Qua định nghĩa trên ta nhận thấy rằng các mệnh đề p  q và q  p luôn luôn có c ng chân trị, hay tương đương logic. Ví dụ : Cho các mệnh đề p = "5 > 7", q = "2721 là một số nguyên tố", r = "một tam giác đều cũng là một tam giác cân". Khi đó ta có : p  q = 0, p  r = 1. Nhận xét : 1. Cho p là một mệnh đề. Lập bảng chân trị của mệnh đề p   p p  p p  p 4
0 1 1 1 0 1 ta có mệnh đề p   p luôn luôn đúng. 2. Người ta còn sử dụng phép "hoặc" trong việc liên kết các mệnh đề. Cho p và q là hai mệnh đề. Ta ký hiệu mệnh đề "p hoặc q" là p q. Phép "hoặc", ký hiệu là , được định nghĩa bởi bảng chân trị sau đây: p q p q 0 0 0 0 1 1 1 0 1 1 1 0 Phép "hoặc" còn được gọi là "hay loại trừ". Chân trị của mệnh đề p q phụ thuộc vào các chân trị của 2 mệnh đề p, q : mệnh đề p q đúng khi trong 2 mệnh đề p và q có một mệnh đề đúng, một mệnh đề sai. 1.1.2.4. Phép kéo theo Phép kéo theo, ký hiệu bởi , được đưa ra để mô hình cho loại phát biểu điều kiện có dạng : "nếu . . . thì . . .". Cho p và q là 2 mệnh đề, ta sẽ viết p q để diễn đạt phát biểu "nếu p thì q". Phép toán kéo theo được định nghĩa bởi bảng chân trị sau đây: p q p q 0 0 1 0 1 1 1 0 0 1 1 1 Mệnh đề p q, được đọc là "nếu p thì q", còn được phát biểu dưới các dạng khác sau đây: "q nếu p". "p chỉ nếu q". "p la` điều kiện đủ cho q". "q la` điều kiện cần cho p". 1.1.2.5. Phép kéo theo hai chiều 5
Phép kéo theo 2 chiều hay phép tương đương, ký hiệu bởi , được đưa ra để mô hình cho loại phát biểu điều kiện hai chiều có dạng : ". . . nếu và chỉ nếu . . .". Cho p và q là 2 mệnh đề, ta viết p q để diễn đạt phát biểu "p nếu và chỉ nếu q". Phép toán tương đương  được định nghĩa bởi bảng chân trị sau đây: p q p  q 0 0 1 0 1 0 1 0 0 1 1 1 Mệnh đề p  q, được đọc là "p nếu và chỉ nếu q", còn được phát biểu dưới các dạng khác sau đây: "p khi và chỉ khi q". "p la` điều kiện cần va` đủ cho q". Mệnh đề p  q có chân trị đúng (=1) trong các trường hợp p và q có c ng chân trị. 1.1.2.6. Ðộ ưu tiên của các toán tử logic. Tương tự như đối với các phép toán số học, để tránh phải dùng nhiều dấu ngoặc trong các biểu thức logic, ta đưa ra một thứ tự ưu tiên trong việc tính toán. Ở trên ta có 5 toán tử logic:  (không) ,  (và),  (hay), (kéo theo),  (tương đương)  ưu tiên mức 1 (cao nhất)  ,  ưu tiên mức 2 (thấp hơn) ,  ưu tiên mức 3 (thấp nhất) trong đó, các toán tử liệt kê trên c ng dòng có c ng độ ưu tiên. Ví dụ : 1.  p  q có nghĩa là (( p)  q). 2.  p  q r  s có nghĩa là ((( p)  q) (r  s)). 3.  p  q  r là nhập nhằng. Cần phải dùng các dấu ngoặc để chỉ rõ nghĩa. 1.2. Biểu thức logic 1.2.1. Định nghĩa và bảng chân trị của biểu thức logic Trong đại số ta có các biểu thức đại số được xây dựng từ các hằng số, các biến và các phép toán. Khi thay thế các biến trong một biểu thức đại số bởi các hằng số thì kết quả thực hiện 6
các phép toán trong biểu thức sẽ là một hằng số. Trong phép tính mệnh đề ta cũng có các biểu thức logic được xây dựng từ : Các mệnh đề hay các giá trị hằng. Các biến mệnh đề. Các phép toán logic, và cả các dấu ngoặc "( )" để chỉ rõ thứ tự thực hiện của các phép toán. Giả sử E, F là 2 biểu thức logic, khi ấy  E, E  F, E F, E  F cũng là các biểu thức logic. Ví dụ: Biểu diễn E(p, q, r) = ((( p)  q) (r  s)) là một biểu thức logic trong đó p, q, r là các biến mệnh đề. Bảng chân trị Bảng chân trị của một biểu thức logic là bảng liệt kê chân trị của biểu thức logic theo các trường hợp về chân trị của tất cả các biến mệnh đề trong biểu thức logic hay theo các bộ giá trị của bộ biến mệnh đề. Với một biến mệnh đề, ta có 2 trường hợp là 0 (sai) hoặc 1 (đúng). Với 2 biến mệnh đề p, q ta 4 trường hợp chân trị của bộ biến (p,q) là các bộ giá trị (0,0), (0,1), (1,0), và (1,1). Trong trường hợp tổng quát, với n biến mệnh đề thì ta có 2n trường hợp chân trị cho bộ n biến đó. Ví dụ 1: Bảng chân trị của các biểu thức logic p q và  p  q theo các biến mệnh đề p,q như sau: p q p q  p  p  q 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 Ví dụ 2: Bảng chân trị của các biểu thức logic p  ( q  r) theo các biến mệnh đề p, q, r như sau: Thứ tự p q r q  r p  ( q  r) 1 0 0 0 0 0 2 0 0 1 0 0 3 0 1 0 0 0 4 0 1 1 1 1 5 1 0 0 0 1 6 1 0 1 0 1 7 1 1 0 0 1 7
Thứ tự p q r q  r p  ( q  r) 8 1 1 1 1 1 1.2.2. Sự tƣơng đƣơng logic Hai biểu thức logic E và F theo các biến mệnh đề nào đó được gọi là tương đương logic khi E và F luôn luôn có c ng chân trị trong mọi trường hợp chân trị của bộ biến mệnh đề. Khi đó ta viết: E F đọc là "E tương đương với F". Như vậy, theo định nghĩa ta có thể kiểm tra xem 2 biểu thức logic có tương đương hay không bằng cách lập bảng chân trị của các biểu thức logic. Ví dụ: từ bảng chân trị của các biểu thức logic p q và  p  q theo các biến mệnh đề p, q ta có: ( p q ) ( p  q ) 1.2.3. Giá trị của biểu thức logic Một biểu thức logic được tạo thành từ các biến logic kết hợp với phép toán logic, bởi vậy nên giá trị biểu thức logic cũng chỉ nhận 1 trong 2 giá trị là “đúng” (true hoặc 1) hay “sai” (false hoặc 0) t y thuộc vào giá trị của các biến logic và quy luật của các phép toán. Ví dụ: Xét biểu thức logic ( p  q ), nếu thay p = 1 và q = 0 ta có: 1  0 = 0  0 = 0 1.3. Các luật logic Các luật logic là cơ sở để ta thực hiện các biến đổi trên một biểu thức logic để có được một biểu thức logic mới tương đương logic với biểu thức logic có trước. Mỗi biểu thức logic cho ta một sự khẳng định về sự tương đương của 2 biểu thức logic. Ta sẽ sử dụng các qui tắc thay thế và các luật logic đã biết để thực hiện các phép biến đổi tương đương trên các biêu thức logic. Dưới đây, chúng ta sẽ liệt kê ra một số luật logic thường được sử dụng trong lập luận và chứng minh. Các luật nầy có thể được suy ra trực tiếp từ các bảng chân trị của các biểu thức logic. 1.3.1. Các luật logic Các luật về phép phủ định   p p (luật phủ định của phủ định)  1 0  0 1 Luật giao hoán 8
p  q q  p p  q q  p Luật kết hợp p  (q  r) (p  q)  r p  (q  r) (p  q)  r Luật phân bố p  (q  r) (p  q)  (p  r) p  (q  r) (p  q)  (p  r) Luật De Morgan  (p  q)  p   q  (p  q)  p   q Luật về phần tử bù p   p 1 p   p 0 Luật kéo theo p q  p  q Luật tương đương p  q (p q)  (q p) Các luật đơn giản của phép tuyển p  p p (tính lũy đẳng của phép tuyển) p  1 1 (luật này còn được gọi là luật thống trị) p  0 p (luật này còn được gọi là luật trung hòa) p  (p  q) p (luật này còn được gọi là luật hấp thụ) Các luật đơn giản của phép hội p  p p (tính lũy đẳng của phép hội) p  1 p (luật này còn được gọi là luật trung hòa) 9
p  0 0 (luật này còn được gọi là luật thống trị) p  (p  q) p (luật này còn được gọi là luật hấp thụ) Một số luật trong các luật trình bày ở trên có thể được suy ra từ các luật khác. Chúng ta có thể tìm ra được một tập hợp luật logic tối thiểu mà từ đó ta có thể suy ra tất cả các luật logic khác, nhưng điều nầy không quan trọng lắm đối với chúng ta. Những luật trên được chọn lựa để làm cơ sở cho chúng ta thực hiện các biến đổi logic, suy luận và chứng minh. Tất nhiên là còn nhiều luật logic khác mà ta không liệt kê ra ở đây. Các luật kết hợp trình bày ở trên còn được gọi là tính chất kết hợp của phép toán hội và phép toán tuyển . Do tính chất nầy, ta có thể viết các biểu thức logic hội và các biểu thức tuyển dưới các dạng sau: E1  E2   Em E1  E2   Em và việc tính toán chân trị có thể được thực hiện dựa trên một sự phân bố các cặp dấu ngoặc vào biểu thức một cách t y ý để xác định một trình tự thực hiện các phép toán. Ví dụ: Biểu thức E1  E2  E3  E4 có thể được tính toán chân trị bởi biểu thức sau: (E1  E2)  (E3  E4) hay có thể tính toán theo biểu thức: E1  ((E2  E3 )  E4) 1.3.2. Các quy tắc thay thế Dưới đây là các qui tắc để cho ta có thể suy ra những biểu thức logic mới hay tìm ra các biểu thức logic tương đương với một biểu thức logic cho trước. Qui tắc 1 Trong một biểu thức logic E, nếu ta thay thế một biểu thức con bởi một biểu thức logic tương đương với biểu thức con đó thì ta sẽ được một biểu thức mới E' tương đương với biểu thức E. Ví dụ: Cho biểu thức logic E = q p. Thay thế q trong biểu thức E bởi biểu thức  q (tương đương với q) ta được một biểu thức mới E' =  q  p. Theo qui tắc thay thế 1 ta có: q  p  q  p Qui tắc 2 Giả sử biểu thức logic E là một hằng đúng. Nếu ta thay thế một biến mệnh đề p bởi một biểu thức logic tuỳ ý thì ta sẽ được một biểu thức logic mới E' cũng là một hằng đúng. 10
Ví dụ: Ta có biểu thức E(p,q) = (p q)  ( p  q) là một hằng đúng. Thay thế biến q trong biểu thức E bởi biểu thức q  r ta được biểu thức logic mới: E'(p,q,r) = (p (q  r))  ( p  (q  r)) Theo qui tắc thay thế 2 ta có biểu thức E'(p,q,r) cũng là một hằng đúng. 1.3.3. Ví dụ áp dụng Ví dụ 1: Chứng minh rằng (p q) ( q  p). Chứng minh : (p q)  p  q (luật kéo theo) q   p (luật giao hoán)  q   p (luật phủ định)  q  p (luật kéo theo) Ví dụ 2: Chứng minh rằng biểu thức ((p q)  p) q là một hằng đúng. Chứng minh. ((p q)  p) q ((p q)  p)  q (luật kéo theo) ( (p q)   p)  q (luật De Morgan)  (p q)  ( p  q) (luật kết hợp)  (p q)  (p q) (luật kéo theo) 1 (luật về phần tử bù) Vậy biểu thức ((p q)  p) q là hằng đúng. Ví dụ 3: Chứng minh rằng biểu thức p  q p là một hằng đúng. Chứng minh. 11
p  q p  ( p  q)  p (luật kéo theo) ( p   q)  p (luật De Morgan) ( q   p)  p (luật giao hoán)  q  ( p  p) (luật kết hợp)  q  1 (luật về phần tử bù) 1 (luật đơn giản) Vậy mệnh đề p  q p là hằng đúng. Ví dụ 4: Chứng minh rằng biểu thức p pq là một mệnh đề hằng đúng. Chứng minh. p pq  p  (p q) (luật kéo theo) ( p  p)  q (luật kết hợp) 1  q (luật về phần tử bù) 1 (luật đơn giản) Vậy mệnh đề p pq là hằng đúng. Nhận xét: Các ví dụ trên cho ta thấy một quan hệ khác giữa các mệnh đề phức hợp hay các mệnh đề : quan hệ "suy ra". Khi mệnh đề p q là hằng đúng, ta nói rằng p suy ra q (về mặt logic). Chúng ta sẽ dùng ký hiệu để chỉ quan hệ "suy ra". Quan hệ suy ra nầy có tính truyền (hay bắc cầu), nhưng không có tính chất đối xứng. 1.4. Các dạng chuẩn tắc Dạng chuẩn tắc (chính tắc) của 1 biểu thức là biểu diễn biểu thức về dạng đơn giản, chỉ bao gồm các phép toán phủ định, hội tuyển của các mệnh đề. 1.4.1. Chuẩn tắc tuyển Giả sử p1, p2, , pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, , pn được gọi là một biểu thức hội cơ bản (hội sơ cấp) nếu nó có dạng sau: F = q1  q2   qn với qj = pj hoặc qj =  pj (j = 1, , n). 12
Ví dụ: Biểu thức x   y  z là một biểu thức hội cơ bản theo 3 biến mệnh đề x, y, z. Biểu thức logic E(p1, p2, , pn) theo các biến mệnh đề p1, p2, , pn được nói là có dạng chính tắc tuyển khi E có dạng: E = E1  E2   Em Trong đó mỗi biểu thức con Ei đều có dạng chính tắc tuyển theo các biến p1, p2, , pn. Ví dụ: Các biểu thức sau đây có dạng chính tắc tuyển: E(x,y,z) = (x  y  z)  ( x  y  z)  (x  y  z) F(p1,p2,p3,p4) = (p1  p2  p3  p4)  (p1   p2  p3  p4) Ðịnh lý : Mọi biểu thức logic E(p1, p2, , pn) đều có thể viết dưới dạng chính tắc tuyển (chuẩn tắc tuyển) duy nhất, không kể sự sai khác về thứ tự trước sau của các biểu thức hội cơ bản trong phép tuyển). Nói một cách khác, ta có duy nhất một tập hợp các biểu thức hội cơ bản E1, E2, , Em sao cho biểu thức E(p1, p2, , pn) tương đương logic với biểu thức E1  E2   Em. 1.4.2. Chuẩn tắc hội Giả sử p1, p2, , pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, , pn được gọi là một biểu thức tuyển cơ bản (tuyển sơ cấp) nếu nó có dạng sau: F = q1 q2  qn với qj = pj hoặc qj = pj (j = 1, , n). Ví dụ: Biểu thức x y z là một biểu thức tuyển cơ bản theo 3 biến mệnh đề x, y, z. Biểu thức logic E(p1, p2, , pn) theo các biến mệnh đề p1, p2, , pn được nói là có dạng chính tắc hội khi E có dạng: E = E1 E2  Em Trong đó mỗi biểu thức con Ei đều có dạng chính tắc tuyển theo các biến p1, p2, , pn. Ví dụ: Các biểu thức sau đây có dạng chuẩn tắc hội (chính tắc hội): E(x,y,z) = (x y  z) (x  y z) (x  y z) F(p1,p2,p3,p4) = (p1 p2  p3 p4)  (p1 p2 p3  p4) Ðịnh lý : 13
Mọi biểu thức logic E(p1, p2, , pn) đều có thể viết dưới dạng chính tắc hội duy nhất, không kể sự sai khác về thứ tự trước sau của các biểu thức tuyển cơ bản trong phép hội). Nói một cách khác, ta có duy nhất một tập hợp các biểu thức tuyển cơ bản E1, E2, , Em sao cho biểu thức E(p1, p2, , pn) tương đương logic với biêu thức E1 E2  Em. 1.5. Quy tắc suy diễn 1.5.1. Đại cƣơng về quy tắc suy diễn Một hệ thống toán học bao gồm các tiên đề, các định nghĩa, và những khái niệm không được định nghĩa. Các tiên đề được giả định là đúng. Các định nghĩa được sử dụng để xây dựng hay đưa ra những khái niệm mới trên cơ sở những khái niệm đã có. Một số thuật ngữ, khái niệm sẽ không được định nghĩa rõ ràng nhưng được ngầm định nghĩa bởi các tiên đề. Trong một hệ toán học chúng ta có thể suy ra được các định lý. Một định lý là một khẳng định được chứng minh là đúng. Một số loại định lý được xem là các bổ đề, các hệ quả. Một lập luận (hay lý luận) chỉ ra được tính đúng đắn của mệnh đề phát biểu trong định lý được gọi là chứng minh. Logic là một công cụ cho việc phân tích các chứng minh. Trong phần nầy chúng ta sẽ đề cập đến việc xây dựng một chứng minh toán học. Ðể thực hiện được một lập luận hay một chứng minh chúng ta cần hiểu các kỹ thuật và các công cụ được sử dụng để xây dựng một chứng minh. Thông thường một chứng minh sẽ bao gồm nhiều bước suy luận mà ở mỗi bước ta đi đến (hay suy ra) một sự khẳng định mới từ những khẳng định đã biết. Ví dụ về một bước suy diễn: 1/ Nếu một danh sách L là khác rỗng thì ta có thể lấy ra phần tử đầu trong danh sách.Vì danh sách L là rỗng nên theo sự khẳng định trên ta không thể lấy ra phần tử đầu trong danh sách. 2/ Nếu một danh sách L là khác rỗng thì ta có thể lấy ra phần tử đầu trong danh sách.Vì ta không thể lấy ra phần tử đầu trong danh sách L nên danh sách L là danh sách rỗng. Trong 2 suy diễn ở ví dụ trên thì suy diễn 2/ là một suy luận đúng, nhưng suy diễn 1/ là không đúng. Vậy làm thế nào để biết được một suy diễn là đúng hay sai ? Một bước suy luận như thế phải dựa trên một qui tắc suy diễn hợp lý nào đó để nó được xem là một suy luận đúng. Các qui tắc suy diễn là cơ sở để tay biết được một lập luận hay một chứng minh là đúng hay sai. Trong các mục tiếp theo chúng ta sẽ xem xét chi tiết hơn về các qui tắc suy diễn và giới thiệu một số qui tắc suy dễn cơ bản thường được dùng trong việc suy luận và chứng minh. Ðịnh nghĩa qui tắc suy diễn Tuy có nhiều kỹ thuật, nhiều phương pháp chứng minh khác nhau, nhưng trong chứng minh trong toán học ta thường thấy những lý luận dẫn xuất có dạng: 14
Nếu p1 và p2 và . . . và pn thì q. Dạng lý luận này được xem là hợp lý (được chấp nhận là đúng) khi ta có biểu thức (p1  p2  . . .  pn) q là hằng đúng. Ta gọi dạng lý luận trên là một luật suy diễn và người ta cũng thường viết luật suy diễn trên theo các cách sau đây : Cách 1: Biểu thức hằng đúng (p1  p2  . . .  pn) q 1 Cách 2: Dòng suy diễn (p1  p2  . . .  pn) q Cách 3: Mô hình suy diễn p1 . . . . pn ___  q Các biểu thức logic p1, p2, . . ., pn trong luật suy diễn trên được gọi là giả thiết (hay tiền đề), và biểu thức q được gọi là kết luận. Ở đây chúng ta cũng cần lưu ý rằng lý luận trên đúng không có nghĩa là ta có q đúng và cũng không khẳng định rằng p1, p2, . . ., pn đều đúng. Lý luận chỉ muốn khẳng định rằng nếu như ta có p1, p2, . . ., pn là đúng thì ta sẽ có q cũng phải đúng. Ví dụ : Giả sử p và q là các biến logic. Xác định xem mô hình sau đây có phải là một luật suy diễn hay không? p q p   q Giải: Lập bảng chân trị ta có: p q p q (p q) p ((p q) p) q 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 15
1 1 1 1 1 Bảng chân trị cho thấy biểu thức ((p q) p) q là hằng đúng. Do đó, mô hình suy luận trên đúng là một luật suy diễn. Thật ra, ta chỉ cần nhìn vào các cột chân trị của p, q, và p q trong bảng chân trị là ta có thể kết luận được rồi, vì từ bảng chân trị trên ta thấy rằng nếu các giả thiết p q và p đúng (có giá trị bằng 1) thì kết luận q cũng đúng. Ta có thể khẳng định được mô hình suy luận trên là một luật suy diễn mà không cần lập bảng chân trị. Giả sử p q và p đúng. Khi đó q phải đúng, bởi vì nếu ngược lại (q sai) thì p cũng phải sai (sẽ mâu thuẩn với giả thiết). 1.5.2. Kiểm tra một quy tắc suy diễn Ðể kiểm tra một suy luận cụ thể là đúng hay không, tức là có "hợp logic" hay không, ta có thể căn cứ vào các qui tắc suy diễn (luật suy diễn). Phép suy luận cụ thể có thể được xem như sự suy diễn trên các mệnh đề phức hợp. Các mệnh đề sơ cấp cụ thể (mà chân trị có thể đúng hoặc sai) trong phép suy luận sẽ được trừu tượng hóa (thay thế) bởi các biến logic. Như thế phép suy luận được trừu tượng hóa thành một qui tắc suy diễn trên các biểu thức logic mà ta có thể kiểm tra xem qui tắc suy diễn là đúng hay không. Ðây chính là biện pháp để ta biết được một suy luận cụ thể là đúng hay sai. Ví dụ 1: Xét sự suy luận sau đây: Nếu một danh sách L là khác rỗng thì ta có thể lấy ra phần tử đầu trong danh sách.Vì ta không thể lấy ra phần tử đầu trong danh sách L nên danh sách L là danh sách rỗng. Trong phép suy luận, ta có các mệnh đề sơ cấp "danh sách L là khác rỗng", "ta có thể lấy ra phần tử đầu (từ danh sách L)". Thay thế các mệnh đề sơ cấp nầy bởi các biến logic p, q tương ứng thì phép suy luận cụ thể trên sẽ được trừu tượng hóa thành một suy diễn trên các biểu thức logic như sau: p q q  p Mô hình suy diễn nầy chính là qui tắc suy diễn Modus Tollens, đã được biết là đúng. Vậy phép suy luận trên là suy luận đúng. Ví dụ 2: Xét xem suy luận sau đây có đúng hay không? Nếu là số hữu tĩ thì phương trình m2 = 2n2 có nghiệm nguyên dương m, n. Nếu phương trình m2 = 2n2 có nghiệm nguyên dương m và n thì ta có mâu thuẫn. Vậy là số vô tĩ. Trừu tượng hóa các mệnh đề sơ cấp " là số hữu tĩ", " phương trình m2 = 2n2 có nghiệm nguyên dương m, n " thành các biến logic p, q tương ứng thì phép suy luận trên có dạng mộ hình suy diễn 16
p q q 0   p Kiểm tra mô hình suy diễn nầy ta sẽ thấy là đúng. Như thế phép suy luận trên là đúng. 1.5.3. Các quy tắc suy diễn cơ bản Trong mục này chúng ta nêu lên một số qui tắc suy diễn (đúng) thường được sử dụng mà ta có thể kiểm tra chúng bằng các phương pháp đã được trình bày trong mục trước. Qui tắc Modus Ponens (p q) p q hoặc là viết dưới dạng mô hình suy diễn p q p  q Qui tắc Modus Tollens (p q) q p hoặc là viết dưới dạng mô hình suy diễn p q q  p Tam đoạn luận (p q) (q r) (p r) hoặc là viết dưới dạng mô hình suy diễn p q q r  p r Qui tắc chứng minh bằng phản chứng p q (p q) 0 Qui tắc nầy cho phép ta chứng minh (p q) 0 thay cho p q. Nói cách khác, nếu ta thêm giả thiết phụ vào tiền đề p mà chứng minh được có sự mâu thuẫn thì ta có thể kết luận q từ tiền đề p. Qui tắc chứng minh theo trường hợp 17
(p1 q)  (p2 q)  . . .  (pn q) (p1  p2  . . .  pn) q hoặc là viết dưới dạng mô hình suy diễn p1 q p2 q . . . pn q  (p1  p2  . . .  pn) q 1.5.4. Các ví dụ áp dụng Dưới đây ta trình bày chứng minh của một số mệnh đề mà không nêu lên một cách chi tiết về các qui tắc suy diễn đã được áp dụng. Người đọc có thể tìm thấy các qui tắc suy diễn được sử dụng trong chứng minh một cách dễ dàng. Mệnh đề 1: Với mọi số nguyên n, n3 + 2n chia hết cho 3. Suy nghĩ đầu tiên là ta thấy rằng không thể tìm thấy một thừa số 3 trong biểu thức n3 + 2n. Nhưng khi phân tích ra thừa số thì n3 + 2n = n(n2 + 2). Phát biểu "n3 + 2n chia hết cho 3" sẽ đúng nếu n là bội số của 3. Còn các trường hợp khác thì sao?. Ta thử phương pháp phân chứng. Chứng minh: Ta có n3 + 2n = n(n2 + 2), và số tự nhiên n có một trong 3 dạng ứng với 3 trường hợp dưới đây: Trường hợp 1: n = 3k, với k là một số nguyên. n3 + 2n = 3k(9k2 + 2) chia hết cho 3. Trường hợp 2: n = 3k+1, với k là một số nguyên. n3 + 2n = (3k+1)((3k+1)2 + 2) = (3k+1)(9k2 +6k+3) = (3k+1)3(3k2 +2k+1) chia hết cho 3. Trường hợp 3: n = 3k+2, với k là một số nguyên. n3 + 2n = (3k+2)((3k+2)2 + 2) = (3k+1)(9k2 +12k+6) = (3k+1)3(3k2 +4k+2) chia hết cho 3. Trong mọi trường hợp (có thể có) ta đều có n3 + 2n đều chia hết cho 3. 18
Vậy ta kết luận n3 + 2n chia hết cho 3 đối với mọi số nguyên n. Nhận xét : Chứng minh trên có thể được trình bày ngắn gọn hơn bằng cách sử dụng phép đồng dư modulo 3. Mệnh đề 2:Nếu n2 là một số chẳn thì n cũng là một số chẳn. Suy nghĩ: Giả sử n2 = 2k (là số chẳn). Ta thấy khó suy ra n là số chẳn. Nếu biết thông tin gì đó về n thì suy ra điều gì đó về n2 thì dễ hơn. Ta thử phương pháp phản chứng. Chứng minh: Ta hãy chứng minh mệnh đề "Nếu n lẻ thì n2 lẻ". Cho n là một số lẻ, ta có n = 2k+1 (k là một số nguyên). Do đó n2 = (2k+1)2 = 4k2 + 4k + 1 là một số lẻ. Mệnh đề trong cặp nháy kép là đúng nên mệnh đề phản đảo của nó cũng đúng. Vậy, nếu n2 là một số chẳn thì n cũng là một số chẳn. Mệnh đề 3:Nếu p > 3 và p nguyên tố thì p2 -1 chia hết cho 3. Chứng minh: Ta có (p-1), p, (p+1) là 3 số nguyên liên tiếp. Trong 3 số nguyên nầy có một số chia hết cho 3. Nhưng số đó không phải là p vì p là số nguyên tố lớn hơn 3. Do đó (p-1) chia hết cho 3 hoặc (p+1) chia hết cho 3. Suy ra (p-1)(p+1) chia hết cho 3, tức là p2 -1 chia hết cho 3. Mệnh đề 4:Số lượng các số nguyên tố là vô hạn. Chứng minh: Giả sử phát biểu trong mệnh đề là sai. Tức là chỉ có một số hữu hạn, k, số nguyên tố (dương). Ký hiệu k số nguyên tố là p1, p2, . . ., pk, ở đây k là số nguyên dương. Ðặt n = p1p2 . . . pk + 1. Số n lớn hớn tất cả k số nguyên tố nên n không nguyên tố. Do đó, từ định lý cơ bản của số học , n phải có một ước số nguyên tố p. p phải là một trong k số nguyên tố. Do đó p ( p1p2 . . . pk). Suy ra p (n - p1p2 . . . pk), hay p 1. Như thế, ta có p là một số nguyên tố và p 1. Ðiều nầy là không thể, hay nói cách khác, ta có một mâu thuẩn. Vậy, Số lượng các số nguyên tố là vô hạn. 19
1.6. Vị từ, lƣợng từ 1.6.1. Định nghĩa vị từ và ví dụ Ðịnh nghĩa: Một vị từ là một phát biểu p(x, y, ) phụ thuộc theo các biến x, y, lấy giá trị trên các miền xác định A, B, nào đó. Khi thay thế các biến trong vị từ bởi các giá trị cụ thể a, b, thuộc các miền xác định thì ta được một mệnh đề p(a, b, ) có chân trị đúng hoặc sai. Gọi B là tập hợp gồm có hai giá trị : Sai (ký hiệu bởi 0), và Ðúng (ký hiệu bởi 1). Một vị từ p(x, y, ) Ví dụ1: P(n)  "n là một số nguyên tố" là một vị từ trên tập hợp các số tự nhiên (hoặc trên tập hợp các số nguyên). Ta có thể thấy rằng: P(1) = 0, tức là P(1)  "1 là một số nguyên tố" là một mệnh đề sai. P(2) = 1, tức là P(2)  "2 là một số nguyên tố" là một mệnh đề đúng. P(12) = 0, tức là P(12)  "12 là một số nguyên tố" là một mệnh đề sai. P(17) = 1, tức là P(17)  "17 là một số nguyên tố" là một mệnh đề đúng. Vị từ "n là một số nguyên tố" có thể được xem là một ánh xạ đi từ tập hợp các số tự nhiên N vào tập hợp Boole B: P : N B Ví dụ2: p(m,n)  "m là một ước số của n", với m và n là các biến số tự nhiên, cho ta một vị từ theo 2 biến m và n thuộc tập hợp các số tự nhiên. Ta có: p(2,4) = 1, p(3,4) = 0. 1.6.2. Các phép toán trên vị từ Cho p(x, y, ) là một vị từ theo các biến x, y, . Phủ định của p, ký hiệu là p, là một vị từ mà khi thay các biến x, y, bởi các phần tử cụ thể a, b, tương ứng thì ta được mệnh đề (p(a, b, )). Nói một cách khác, vị từ p được định nghĩa bởi: (p) (x, y, ) = (p(x, y, )) Cho p(x, y, ) và q(x, y, ) là các vị từ theo các biến x, y, . Phép hội của p và q, ký hiệu là p q, là một vị từ mà khi thay các biến x, y, bởi các phần tử cụ thể a, b, tương ứng 20
thì ta được mệnh đề p(a, b, ) q(a, b, ). Nói một cách khác, vị từ p q được định nghĩa bởi: (p q) (x, y, ) = p (x, y, )  q (x, y, ) Một cách tương tự, các phép toán tuyển, kéo theo và tương đương của 2 vị từ p và q có thể được định nghĩa như sau: (p  q) (x, y, ) = p (x, y, ) q (x, y, ) (p q) (x, y, ) = p (x, y, ) q (x, y, ) (p  q) (x, y, ) = p (x, y, )  q (x, y, ) 1.6.3. Lƣợng từ và mệnh đề có lƣợng từ Ngoài việc thay thế giá trị cụ thể cho các biến trong vị từ để được một mệnh đề ta còn có một cách quan trọng khác để chuyển từ vị từ sang mệnh đề. Ðó là cách sử dụng các lượng từ "với mọi" và "tồn tại" (hay "có ít nhất một"). Lượng từ được sử dụng để nói lên rằng vị từ đúng đối với mọi giá trị thuộc miền xác định hay chỉ đúng với một phần các giá trị thuộc miền xác định. Cho P(n) là một vị từ theo biến số tự nhiên n. Phát biểu "với mọi n N, P(n)" hay một cách vắn tắt (hiểu ngầm miền xác định) là "với mọi n, P(n)" có nghĩa là P có giá trị đúng trên toàn bộ miền xác định. Nói cách khác, P là ánh xạ hằng có giá trị là 1. Ta sẽ dùng ký hiệu " " để thay thế cho lượng từ "với mọi". Phát biểu "Có (ít nhất) một n N, P(n)" hay một cách vắn tắt (hiểu ngầm miền xác định) là "Có (ít nhất) một n , P(n)" có nghĩa là P có giá trị đúng đối với một hay một số giá trị nào đó thuộc miền xác định. Nói cách khác, P không phải là một ánh xạ hằng 0. Ta sẽ dùng ký hiệu " " để thay thế cho lượng từ "có ít nhất một". Lượng từ nầy còn được đọc một cách khác là "tồn tại". Trong trường hợp tổng quát, giả sử P(x) là một vị từ theo biến x (biến x lấy giá trị thuộc một miền xác định đã biết nào đó và miền xác định nầy có thể được hiểu ngầm, không cần ghi rõ ra). Các cách viết sau đây:  x : P(x) (1)  x : P(x) (2) lần lượt được dùng để diễn đạt cho các phát biểu sau đây: "Với mọi x (thuộc miền xác định) ta có P(x) là đúng" "Có ít nhất mộ x (thuộc miền xác định) sao cho P(x) là đúng" 21
Các phát biểu (1) và (2) có chân trị hoàn toàn xác định. Nói cách khác chúng là những mệnh đề. Chân trị của các mệnh đề nầy được xác định một cách tự nhiên theo ngữ nghĩa thông thường của các lượng từ. Mệnh đề (1) là đúng khi và chỉ khi ứng với mỗi giá trị t y ý x thuộc miền xác định ta đều có mệnh đề P(x) có chân trị đúng. Mệnh đề (2) là đúng khi và chỉ khi có một giá trị x nào đó thuộc miền xác định mà ứng với giá trị x đó ta có P(x) có chân trị đúng. Ghi chú: Phát biểu " x : P(x)" và phát biểu " x : P(x)" không phải là vị từ theo biến x nữa mà là các mệnh đề có chân trị xác định là đúng hoặc sai. Trong các phát biểu trên biến x đã được lượng từ hóa và chân trị của phát biểu không phụ thuộc theo biến x nữa. Ta cũng nói rằng biến x bị buộc bởi lượng từ. Ðối với một vị từ theo nhiều biến thì ta có thể lượng từ hóa một số biến nào đó trong vị từ để có một vị từ mới theo các biến còn lại. Chẳng hạn, nếu p(x, y, ) là một vị từ theo các biến x, y, thì ta có biểu thức q(y, )   x : p(x, y, ) sẽ là một vị từ theo các biến y, . Nếu tất cả các biến của vị từ đều được lượng từ hóa thì ta sẽ có một mệnh đề.Chẳng hạn, nếu p(x, y) làmột vị từ theo 2 biến x, y thì biểu thức  x,  y : p(x, y) sẽ là một mệnh đề, tức là có chân trị xác định và không phụ thuộc vào các biến x, y nữa. Trong nhiều phát biểu người ta cò dùng cụm từ "tồn tại duy nhất", ký hiệu bởi $ !, như là một sự lượng từ hóa đặc biệt. Ví dụ 1: 1. Cho vị từ P(n)  "n là một số nguyên tố". Mệnh đề "Với mọi số tự nhiên n ta có n là nguyên tố" có thể được viết như sau:  n N : P(n) và mệnh đề nầy có chân trị là 0 (sai). 2. Mệnh đề "Với mọi số nguyên n ta có 2n-1 là một số lẻ" có thể được viết dưới dạng ký hiệu như sau:  n Z : 2n-1 lẻ 22
và mệnh đề nầy có chân trị là 1 (đúng). 3. Mệnh đề "Ta có x2 > 0, với mọi số thực x khác 0" có thể được viết là  x R - 0 : x2 > 0 và mệnh đề nầy có chân trị là 1 (đúng). Ví dụ 2: Chứng minh rằng : Nếu n là một số chẳn thì n2 là số chẳn. Mệnh đề cần chứng minh (là đúng) được viết dưới dạng  n Z : n chẳn n2 chẳn. Từ đó ta có thể trình bày chứng minh như sau: Cho n là một số nguyên t y ý. Ta có: n chẳn n = 2m, với m là một số nguyên nào đó n2 = 4m2 n2 chẳn. Vậy phát biểu trên là đúng. 1.6.4. Quy tắc phủ định mệnh đề có lƣợng từ Dựa vào cách xác định chân trị của các mệnh đề có lượng từ theo ngữ nghĩa tự nhiên của các phát biểu, ta có các qui tắc phủ định mệnh đề có lượng từ sau đây:  ( x : P(x))   x :  P(x) (1)  ( x : P(x))   x :  P(x) (2) Ví dụ 1: Tìm phủ định của mệnh đề "tồn tại một số thực x sao cho x2 < 0". Ðặt P(x)  "x2 < 0". Mệnh đề đã cho được viết dưới dạng ký hiệu như sau:  x : P(x) Áp dụng luật phủ định mệnh đề có lượng từ, ta có mệnh đề phủ định cần tìm có dạng :  x :  P(x). Vậy mệnh đề phủ định là: "Với mọi số thực x, x2 0". Ghi chú : Từ các qui tắc trên ta có thể nói chung về qui tắc phủ định mệnh đề có lượng từ như sau: Nếu trong một mệnh đề có lượng từ ta thay thế lượng từ  bởi lượng từ  , lượng từ  bởi lượng từ  , và biểu thức vị từ được thay thế bởi phủ định của nó thì ta sẽ được mệnh đề phủ định của mệnh đề có lượng từ ban đầu. Qui tắc nầy cũng áp dụng được cho các mệnh đề với nhiều lượng từ. Ví dụ 2: Cho p(x, y, z) là một vị từ phụ thuộc vào biến bộ ba (x,y,z) AxBxC. Miền xác định là tích Ðê-Cat của 3 tập hợp A, B, C. Trong trường hợp nầy ta nói vị từ p là một vị từ theo 3 biến x, y, z. Miền xác định tương ứng của 3 biến nầy là A, B, C. Hãy tìm phủ định của mệnh đề sau: 23
 x A,  y B,  z C : p(x,y,z) Theo qui tắc chung ta có :  ( x A,  y B,  z C : p(x,y,z))   x A,  y B,  z C :  p(x,y,z) Thật ra nếu thực hiện từng bước theo các qui tắc (1) và (2) ta cũng đạt được mệnh đề phủ định như trên:  ( x A,  y B,  z C : p(x,y,z))   x A,  ( y B,  z C : p(x,y,z))   x A,  y B,  ( z C : p(x,y,z))   x A,  y B,  z C :  p(x,y,z) Ví dụ 3: Với một hàm số f xác định ở một lân cận của điểm a R (a là một số thực), ta có định nghĩa sự liên tục của f tại a như sau : f liên tục tại a nếu và chỉ nếu cho một số dương  t y ý, ta có một số dương  sao cho | x-a | 0,   > 0 : ( x : | x-a | 0,   > 0 :  ( x : | x-a | 0,   > 0 : ( x :  (| x-a | 0,   > 0 : ( x : | x-a | 0,   > 0 : ( x : | x-a | 0,   > 0,  x : | x-a | <   | f(x) - f(a) |  Như vậy ta có thể phát biểu mệnh đề phủ định như sau:: "Tồn tại một số dương  sao cho ứng với số dương t y ý có một số thực x thoả điều kiện | x-a | <  và | f(x) - f(a) | ". Như vậy ta có thể phát biểu mệnh đề phủ định như sau: "Tồn tại một số dương  sao cho ứng với mỗi số dương  t y ý ta có một số thực x thỏa điều kiện | x-a | <  và | f(x) - f(a) |  ". 1.6.5. Một số quy tắc dùng trong suy luận Thay đổi thứ tự lượng từ hóa của 2 biến 24
Cho một vị từ p(x, y) theo 2 biến x, y. Nếu lượng từ hóa cả 2 biến x, y trong đó ta lượng từ hóa biến y trước và lượng từ hóa biến x sau thì sẽ được 4 mệnh sau đây:  x,  y : p(x,y)  x,  y : p(x,y)  x,  y : p(x,y)  x,  y : p(x,y) Tương tự ta cũng có 4 mệnh đề lượng từ hóa từ vị từ p(x, y) trong đó ta lượng từ hóa biến x trước và lượng từ hóa biến y sau:  y,  x : p(x,y)  y,  x : p(x,y)  y,  x : p(x,y)  y,  x : p(x,y) Ðịnh lý dưới đây cho ta một số tính chất liên quan đến thứ tự của việc lượng từ hóa các biến trong các mệnh đề có lượng từ. Ðịnh lý: Giả sử p(x, y) là một vị từ theo 2 biến x, y thì các mệnh đề sau là đúng ( x,  y : p(x,y) )  ( y,  x : p(x,y) ) ( x,  y : p(x,y) )  ( y,  x : p(x,y) ) ( x,  y : p(x,y) ) ( y,  x : p(x,y) ) Qui tắc đặc biệt hóa phổ dụng Qui tắc: Giả sử một mệnh đề có lượng từ trong đó biến x với miền xác định là A, được lượng từ hóa và bị buộc bởi lượng từ phổ dụng  , và mệnh đề là đúng. Khi đó nếu thay thế x bởi a A thì ta sẽ được một mệnh đề đúng. Ví dụ1: Biết rằng phát biểu "mọi số nguyên tố lớn hơn 2 đều là số lẻ" là một mệnh đề đúng. Cho a là một số nguyên tố lớn hơn 2 (cố định nhưng t y ý). Hãy chứng minh rằng a là một số lẻ. Giải: Ðặt p(n)  "n là số nguyên tố lớn hơn 2", và q(n)  "n là số lẻ". Ta có p(n) và q(n) là các vị từ theo biến số tự nhiên n, và ta có mệnh đề đúng sau đây:  n : p(n) q(n) Theo qui tắc trên ta suy ra p(a) q(a) = 1. Theo giả thiết ta cũng có 25
p(a) = 1. Suy ra q(a) = 1 (qui tắc suy diễn Modus Ponens). Vậy ta có mệnh đề "a là một số lẻ" là đúng. Ví dụ 2: Trong các định lý Toán học ta thường thấy các khẳng định là các mệnh đề lượng từ hóa phổ dụng. Ví dụ như các trường hợp bằng nhau của 2 tam giác bất kỳ. Khi áp dụng ta sẽ đặc biệt hóa cho 2 tam giác cụ thể. Qui tắc tổng quát hóa phổ dụng Qui tắc: Nếu ta thay thế biến x trong vị từ P(x) bởi một phần tử a cố định nhưng t y ý thộc miền xác định của biến x mà mệnh đề nhận được có chân trị là đúng, tức là P(a) = 1, thì mệnh đề lượng từ hóa  x : P(x) là một mệnh đề đúng. Nhận xét: Nếu xem vị từ P(x) như là một hàm lấy giá trị Bool trên miền xác định A của biến x thì ta có mệnh đề lượng từ hóa  x : P(x) là một mệnh đề đúng khi và chỉ khi P là hàm hằng 1. Từ các qui tắc trên ta có thể chứng minh được một số tính chất suy diễn được phát biểu trong các mệnh đề sau đây: Mệnh đề 1: Cho p(x) và q(x) là các vị từ theo biến x lấy giá trị trong tập hợp A (miền xác định của biến x là tập hợp A), và a là một phần tử cố định t y ý thuộc A. Khi ấy ta có qui tắc suy diễn sau đây:  x : p(x) q(x) p(a)  q(a) Mệnh đề 2: Cho p(x), q(x) và r(x) là các vị từ theo biến x lấy giá trị trong tập hợp A (miền xác định của biến x là tập hợp A). Ta có qui tắc suy diễn sau đây:  x : p(x) q(x)  x : q(x) r(x)   x : p(x) r(x) BÀI TẬP Câu 1: Qui tắc suy diễn là gì? Cho ví dụ về một qui tắc suy diễn và áp dụng qui tắc suy diễn trong một suy luận cụ thể. 26
Câu 2: Liệt kê những qui tắc suy diễn thường dùng và cho biết tên gọi (nếu có) của mỗi qui tắc suy diễn. Câu 3: Nêu lên các phương pháp để kiểm tra một qui tắc suy diễn. Ứng với mỗi phương pháp hãy cho một ví dụ minh họa. Câu 4: Vị từ là gì? Cho ví dụ. Câu 5: Phát biểu qui tắc phủ định mệnh đề có lượng từ (hay mệnh đề lượng từ hóa) và cho ví dụ cụ thể. Câu 6: P(n) là vị từ "nếu 4 n thì 2 n". Cho biết chân trị của các mệnh đề sau: a/ P(12) b/ P(10) c/  n : P(n) d/  n : P(n) Câu 7: Hãy cho biết chân trị của mỗi mệnh đề dưới đây và viết mệnh đề phủ định của mệnh đề đó. a/  x : x+3 = 5 b/  x : x+3 = 5 c/  x,  y : x+y = 3 d/  x,  y : x+y = 3 e/  x,  y : x+y = 3 f/  x,  y : x+y = 3 Trong các mệnh đề trên các biến x và y là các biến thực. Câu 8: Hãy cho biết chân trị của mỗi mệnh đề dưới đây và viết mệnh đề phủ định của mệnh đề đó. a/  x,  y : (x2 = y2) (x = y) d/  x,  y : (x2 = y2) (x = y) e/  x,  y : (x2 = y2) (x = y) f/  x,  y : (x2 = y2) (x = y) Câu 9: Hãy sử dụng các ký hiệu toán học và logic để viết lại mệnh đề sau đây: 27
Với mọi số thực dương x, có một số tự nhiên n sao cho x bằng 2n hoặc x nằm giữa 2n và 2n+1. Cho biết mệnh đề nầy đúng hay sai, và viết ra mệnh đề phủ định của nó. Câu 10: Trong bài tập nầy ký hiệu n chỉ một biến nguyên. Cho các vị từ : P(n)  "0 < n2 4" R(n)  "0 < n3 8" S(n)  "0 < n 2" a/ Ứng với mỗi vị từ trên hãy cho biết tập hợp các giá trị n làm cho vị từ có chân trị đúng (=1). b/ Trong các vị từ trên, những vị từ nào tương đương với nhau. c/ Mệnh đề " n : R(n) P(n)" là đúng hay sai? 28
CHƢƠNG 2 CÁC PHƢƠNG PHÁP CHỨNG MINH 2.1. Các phƣơng pháp chứng minh cơ bản 2.1.1. Khái niệm về chứng minh Một hệ thống toán học bao gồm các tiên đề, các định nghĩa, và những khái niệm không được định nghĩa. Các tiên đề được giả định là đúng. Các định nghĩa được sử dụng để xây dựng hay đưa ra những khái niệm mới trên cơ sở những khái niệm đã có. Một số thuật ngữ, khái niệm sẽ không được định nghĩa rõ ràng nhưng được ngầm định nghĩa bởi các tiên đề. Trong một hệ toán học chúng ta có thể suy ra được các định lý. Một định lý là một mệnh đề được chứng minh là đúng. Một số loại định lý được xem là các bổ đề, các hệ quả. Một lập luận (hay lý luận) chỉ ra đƣợc tính đúng đắn của mệnh đề phát biểu trong định lý đƣợc gọi là chứng minh. Logic là cơ sở để thực hiện việc chứng minh, đặc biệt là các luật logic và các luật suy diễn. Trong phần nầy chúng ta sẽ đề cập đến việc xây dựng một chứng minh toán học. Các cấu trúc chứng minh thường được sử dụng là : chứng minh trực tiếp, chứng minh bằng cách phân chia trường hợp (phân chứng), phản chứng, phản ví dụ, và chứng minh qui nạp. 2.1.2. Chứng minh trực tiếp Chứng minh trực tiếp là phương pháp chứng minh suy diễn trực tiếp dẫn từ giả thiết đến kết luận thông qua việc áp dụng các luật suy diễn (hay qui tắc suy diễn), các định lý, các nguyên lý và các kết quả đã biết. Ðây là một kiểu tư duy giải bài toán rất tự nhiên và người ta thường xuyên sử dụng. Trong khi suy nghĩ để tìm ra cách chứng minh theo phương pháp nầy người ta thường phải tự trả lời các câu hỏi sau đây: Ta sẽ dùng luật suy diễn nào? Các định lý nào, các kết qua nào có thể sử dụng được đề ta suy ra được một điều gì đó từ những sự kiện, những yếu tố hiện đang có? Việc áp dụng định lý có khả năng sẽ dẫn đến kết luận hay kết quả mong muốn hay không? Trong trường hợp ở một bước suy diễn nào đó có nhiều định lý hay nhiều luật nào đó có thể áp dụng được và cũng có kkhả năng sẽ dẫn đến kết luận hay kết quả mong muốn thì ta sẽ chọn cái nào? Ðến một giai đoạn nào đó, khi gặp phải sự bế tắc thì ta sẽ phải tự hỏi rằng phải chăng bài toán không có lời giải, hay vì kiến thức của ta chưa đủ, hay ta phải sử dụng một phương pháp chứng minh nào khác? Quả thật là không thể trả lời được các câu hỏi một cách đầy đủ và chính xác. Nó phụ thuộc chủ yếu vào kiến thức, kinh nghiệm của người giải bài toán và cả sự nhạy bén, tính năng động 29
sáng tạo của họ. Tuy nhiên Những câu hỏi trên cho ta một sự định hướng chung của quá trình suy nghĩ. Ngoài ra, cũng cần nói thêm rằng chúng là cơ sở cho việc phát triển các hệ chương trình trợ giúp giải toán một cách "thông minh" trên máy tính được thiết kế theo phương pháp chứng minh nầy. Dưới đây, chúng ta sẽ xem xét một 2 ví dụ về phương pháp chứng minh trực tiếp. Ví dụ 1: Giả sử p, r, s, t, u là các mệnh đề sau cho ta có các mệnh đề sau đây là đú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 là đúng. 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 toán kéo theo ta có thể viết lại (3) dưới dạng: (7) s t Áp dụng luật suy diễn tam đoạn luận, từ (6) và (7) ta suy ra: (8) p t Áp dụng luật logic về phép toán kéo theo ta có thể viết lại (4) dưới dạng: (9) t u Áp dụng luật suy diễn tam đoạn luận, từ (8) và (9) ta suy ra: (10) p u Áp dụng luật suy diễn Modus Tollens, từ (10) và (5) ta suy ra: (11)  p Vậy mệnh đề  p là đúng. 30
Ví dụ 2: 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 là đú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) là đúng. Chứng minh: Áp dụng kết quả trong mệnh đề 2, Bài 2, mục 2.5, từ (1) và (2) ta suy ra: (4)  x A : p(x) r(x) Áp dụng kết quả trong mệnh đề 1, Bài 2, mục 2.5, từ (3) và (4) ta suy ra: (5) r(a) Vậy mệnh đề r(a) là đúng. 2.1.3. Chứng minh 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 toán khá đơn giản như bài toán sau đây: Bài toá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 toán, từ đó đi đến kết luận rằng mệnh đề là đúng. Ngoài ra phép chứng minh phản chứng còn có thể được thực hiện như sau: ta giả sử mệnh đề cần chứng minh là sai, kết hợp với giả thiết đã cho để suy ra được một điều mâu thuẫn nào đó rồi từ đó kết luận rằng mệnh đề là đúng. Cơ sở cho phương pháp chứng minh nầy là qui tắc chứng minh phản chứng: p q (p   q) 0 31
Trở lại bài toá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ụ: 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 m2 = 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 . 32
Ghi chú: Ngoà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. 2.1.4. Chứng minh bằng cách phân chia trƣờng hợp Trong phương pháp chứng minh bằng cách phân chia trường hợp, để chứng minh một sự khẳng định nào đó ta xem xét tất cả các trường hợp có thể xảy ra đối với các sự kiện hay các yếu tố liên quan trong giả thiết và chứng minh rằng trong mỗi trường hợp ta đó ta đều có mệnh đề cần chứng minh là đúng, và từ đó đi đến kết luận rằng từ giả thiết ta có mệnh đề cần chứng minh là đúng. Cơ sở cho phương pháp chứng minh nầy là qui tắc chứng minh theo trường hợp: (p1 q)  (p2 q)  . . .  (pn q) (p1  p2  . . .  pn) q Ðể chứng minh khẳng định q (là đúng), chúng ta phân tích giả thiết để có được một sự khẳng định đúng dưới dạng: p1  p2  . . .  pn rồi tìm cách chứng minh rằng từ mệnh đề pk suy ra được mệnh đề q, ứng với mỗi i từ 1 tới n. Chúng ta hãy trở lại một bài toá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. Ví dụ: Cho một số nguyên n, hãy chứng minh rằng n3 + 2n chia hết cho 3. Tóm tắt chứng minh: Với một số nguyên n, gọi r là dư số trong phép chia n cho 3, ta có 3 trường hợp: Trường hợp 1: r = 0 Trường hợp 1: r = 1 Trường hợp 1: r = 2 Nói cách khác ta có: (r = 0)  (r = 1)  (r = 2). Trong mỗi trường hợp ta đều suy ra được n3 + 2n chia hết cho 3. Ở đây không trình bày lại chi tiết việc tính toán suy diễn trong mỗi trường hợp. Từ đó đi đến kết luận: n3 + 2n chia hết cho 3. 33
2.1.5. 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 toán khác mà đối với nó ta phải dùng phản ví dụ. Ðó là bài toá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 không phải là hằng đúng. Ðể làm điều nầy chúng ta chỉ cần tìm và chỉ ra một trường hợp 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ụ: Hãy kiểm tra suy luận sau đây p r p  r q  q 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 là đú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: p r = 1 p = 1  r q = 1 34
q = 0 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. 2.2. Nguyên lý quy nạp 2.2.1. Đại cƣơng về quy nạp 2.2.1.1. Tập hợp số tự nhiên Tập hợp gồm tất cả các số tự nhiên (hay các số đếm) được ký hiệu là N: N = 0, 1, 2, . . .  Các phép toán: Trên tập hợp số tự nhiên N ta có phép toán cộng (ký hiệu là +), và phép toán nhân (ký hiệu là .). Phép toán cộng 2 số tự nhiên a và b cho ta tổng số cũng là một số tự nhiên được viết là a+b; còn phép toán nhân 2 số tự nhiên a và b cho ta tích số cũng là một số tự nhiên được viết là a.b. Phép toán cộng và nhân các số tự nhiên có các tính chất sau đây: Phép cộng (+) và phép nhân (.) có tính giao hoán và kết hợp, nghĩa là với mọi số tự nhiên a, b, c ta có: a + b = b + a (a + b) + c = a + (b + c) a.b = b.a (a . b) . c = a . (b . c) Phép nhân (.) phân phối đối với phép cộng (+), nghĩa là với mọi số tự nhiên a, b, c ta có: a . (b + c) = a . b + a . c Ở đây, phép toán nhân có độ ưu tiên cao hơn phép toán cộng. Phép cộng và phép nhân lần lượt nhận 0 và 1 là phần tử trung hòa, nghĩa là ta có:  a N : a + 0 = 0 + a = a  a N : a . 1 = 1 . a = a Thứ tự trên N: 35
Ngoài các phép toán, trên N còn có một quan hệ thứ tự  được định nghĩa như sau: a b  c N : a + c = b Ðây là một quan hệ thứ tự toàn phần trên N, và theo quan hệ thứ tự nầy ta có: 0 < 1 < 2 < . . . < n < n+1 < . . . 0 là phần tử nhỏ nhất của tập N, nhưng tập N không có phần tử lớn nhất. Thứ tự trên tập hợp N có một tính chất rất quan trọng được phát biểu trong mệnh đề sau đây: Mệnh đề: Cho A là một tập hợp các số tự nhiên khác rỗng. Khi đó A có phần tử nhỏ nhất, nghĩa là tồn tại a A sao cho:  x A, a x Ghi chú: Phần tử a trong mệnh đề trên là duy nhất và được ký hiệu là min(A). Tính chất được phát biểu trong mệnh đề là cơ sở cho tính đúng đắn của các qui tắc chứng minh qui nạp sẽ được trình bày trong mục sau. 2.2.2. Các nguyên lý quy nạp thƣờng dùng Cho n0 là một số tự nhiên, và P(n) là một vị từ theo biến tự nhiên n  n0. Vấn đề được đặt ra là chứng minh tính đúng đắng của mệnh đề sau đây:  n n0 : P(n) Phương pháp chứng minh qui nạp thường được sử dụng để chứng minh khẳng định trên. Phép chứng minh qui nạp được thực hiện dựa vào các nguyên lý qui nạp. Chúng ta sẽ nêu lên hai dạng nguyên lý qui nạp thường được sử dụng. Trong các áp dụng nguyên lý qui nạp, n0 thường là 0 hoặc 1. Hai dạng nguyên lý qui nạp, được gọi là dạng qui nạp yếu và dạng qui nạp mạnh sẽ được viết dưới dạng mô hình của các luật suy diễn. Nguyên lý qui nạp dạng yếu: (cơ sở) P(n0) (qui nạp)  k n0 : P(k) P(k+1)   n n0 : P(n) Chứng minh tính đúng đắn của nguyên lý qui nạp trên: 36
Ðặt A là tập hợp các số tự nhiên n n0 mà P(n) sai. Ta chỉ cần chứng minh rằng A = (tập hợp rỗng) với giả thiết rằng ta có hai khẳng định trong phần cơ sở và phần qui nạp trong nguyên lý trên. Ta sẽ chứng minh điều nầy bằng phương pháp phản chứng. Giả sử A  . Theo tính chất của thứ tự trên tập số tự nhiên N (xem mệnh đề ở mục trên), A có phần tử nhỏ nhất. Gọi a là phần tử nhỏ nhất của tập hợp A. Vì P(n0) đúng nên a n0+1, hay a-1 n0. Do a = min(A), nên a-1 A và do đó P(a-1) đúng. Vì P(a-1) đúng nên ta cũng có P(a) đúng theo khẳng định ở phần qui nạp, nghĩa là ta cũng có a A. Ðiều nầy cho ta một sự mâu thuẫn (vì a = min(A)). Vậy A =  . Ta có điều cần chứng minh. Nguyên lý qui nạp dạng mạnh: (cơ sở) P(n0) (qui nạp) k n0 : P(n0)  P(n0+1) . . . P(k) P(k+1)   n n0 : P(n) Theo các nguyên lý trên, chứng minh qui nạp bao gồm 2 bước : bước cơ sở và bước qui nạp. Ở bước cơ sở, ta phải kiểm chứng để khẳng định P(n0) là đúng. Ở bước qui nạp, ứng với một số tự nhiên k t y ý, ta phải chứng minh một mệnh đề kéo theo. Giả thiết trong mệnh đề kéo theo ở bước 2 được gọi là giả thiết qui nạp. Giả thiết qui nạp ở dạng qui nạp yếu là P(k), và ở dạng mạnh là P(n0) P(n0+1) . . . P(k). Nguyên lý qui nạp có rất nhiều biến thể trong việc vận dụng. Chẳng hạn, từ hai nguyên lý trên ta có thể rút ra một nguyên lý qui nạp có dạng sau đây: (cơ sở) P(0) P(1) (qui nạp)  k 1 : P(k-1) P(k) P(k+1)   n 0 : P(n) Trong chứng minh mệnh đề sau đây, ta sử dụng dạng qui nạp biến thể nầy. Mệnh đề: Cho dãy số x0, x1, . . ., xn, . . . được định nghĩa bởi : 37
x0 = 0; x1 = 1; và xn = 3xn-1 - 2xn-2 với mọi n 2. n Khi đó ta có: xn = 2 - 1, với mọi n 0. Chứng minh: n Ðặt P(n)  "xn = 2 - 1". Dễ thấy rằng P(0) và P(1) là đúng. Bây giờ, ta chỉ cần thực hiện bước qui nạp để hoàn thành phép chứng minh qui nạp. Giả sử P(k-1) và P(k) đúng với một số tự nhiên (t y ý) k 1. k-1 k Thế thì xk-1 = 2 - 1 và xk = 2 - 1. Do đó xk+1 = 3xk - 2xk-1 = 3(2k - 1) - 2(2k-1 - 1) = 3*2k - 3 - 2k - 2 = 2*2k - 1 = 2k+1 - 1 Suy ra P(k+1) đúng. Vậy theo nguyên lý qui nạp (dạng biến thể được phá biểu ở trên) ta kết luận: P(n) đúng với mọi n 0. 2.2.3. Các ví dụ Ví dụ 1: Chứng minh rằng với mọi n 1 (n N) ta có: 12 + 22 + . . . + n2 = n(n+1)(2n+1) / 6 Chứng minh: Với mỗi số tự nhiên n 1 (n N), đặt P(n)  "12 + 22 + . . . + n2 = n(n+1)(2n+1) / 6" Ta sẽ chứng minh mệnh đề  n 1 : P(n) bằng phương pháp qui nạp (dạng yếu), nghĩa là thực hiện 2 bước chứng minh trong phép chứng minh qui nạp. 38
Bước cơ sở: Khi n = 1 thì P(1) là mệnh đề "1 = 1.(1+1).(2.1+1) /6". Vế phải của đẳng thức trong mệnh đề tính ra bằng 1, nên ta có P(1) đúng. Bước qui nạp: Cho n là một số tự nhiên túy ý lớn hơn 0, nghĩa là n 1, và giả sử rằng P(n) đúng, tức là ta có: 12 + 22 + . . . + n2 = n(n+1)(2n+1) / 6 (GTQN) Bây giờ ta sẽ chứng minh P(n+1) cũng đúng, tức là chứng minh rằng 12 + 22 + . . . + n2 + (n+1)2 = (n+1)(n+2)(2n+3) / 6 Thật vậy, từ (GTQN) ta suy ra 12 + 22 + . . . + n2 + (n+1)2 = n(n+1)(2n+1) / 6 + (n+1)2 = [(n+1) / 6] . [n(2n+1) + 6(n+1)] = [(n+1) / 6] . [2n2 + 7n + 6] = [(n+1) / 6] . (n+2) (2n+3) = n(n+1)(2n+1) / 6 Tức là ta đã suy ra được P(n+1) cũng đúng. Hai phần (phần cơ sở và phần qui nạp) trong phép chứng minh qui nạp đã được chứng minh. Vậy theo nguyên lý qui nạp ta kết luận rằng với mọi n 1 (n N) ta có: 12 + 22 + . . . + n2 = n(n+1)(2n+1) / 6 Ví dụ 2: Chứng minh định lý sau đây: Cho a và b là 2 số nguyên tự nhiên, với b 0. Khi đó, có duy nhất 2 số tự nhiên q và r thỏa 2 điều kiện sau đây: + a = q.b + r + 0 r < b Chứng minh: Tính duy nhất của q và r trong định lý trên có thể kiểm chứng dễ dàng. Ở đây ta sẽ chứng minh sự tồn tại của q và r. Cho b là một số tự nhiên khác 0 t y ý nhưng cố dịnh. Ðặt P(a)  "Tồn tại các số tự nhiên q và r thỏa mãn 2 điều kiện (1) và (2)" Ta sẽ chứng minh mệnh đề sau đây là đúng:  a N : P(a) bằng cách sử dụng nguyên lý qui nạp dạng mạnh. 39
Bước cơ sở: Xét trường hợp a = 0, ta thấy với q = 0 và r = 0 thì các điều kiện (1) và (2) được thỏa mãn. Vậy ta có P(0) đúng. Bước qui nạp: Cho a là một số tự nhiên t y ý và giả sử rằng các mệnh đề P(0), P(1), . . . , P(a) đều đúng (GTQN). Ta sẽ chứng minh P(a+1) cũng đúng bằng cách xét 2 trường hợp. + Trường hợp 1: a+1 < b. Ta chọn q = 0 và r = a+1 thì ta có q và r thỏa các điều kiện a+1 = q.b + r 0 r < b Vậy trong trường hợp 1 nầy thì P(a+1) đúng. + Trường hợp 2: a+1 b. Ðặt a' = a+1-b, ta có 0 a' a. Từ (GTQN) ta suy ra P(a') đúng, tức là có các số tự nhiên q' và r' sao cho a' = q'.b + r', và 0 r' < b Suy ra các số tự nhiên q = q'+1 và r = r' sẽ thỏa mãn 2 điều kiện (1) a+1 = q.b + r (2) 0 r < b Vậy ta cũng có P(a+1) đúng. Tóm lại, ta đã chứng minh phần cơ sở và phần qui nạp trong nguyên lý qui nạp. Từ đó có thể kết luận rằng:  a N : P(a) Ghi chú : Ðịnh lý trên là cơ sở cho việc định nghĩa phép toán div (chia lấy thương số) và phép toán mod (chia lấy dư số). Ðịnh lý nầy còn được gọi là thuật chia Euclide. Xem xét việc chứng minh của định lý trên theo phương pháp qui nạp, chúng ta có thể rút ra một thuật toán (khái niệm thuật toán sẽ được trình bày trong chương 3). Dạng tổng quát của định lý, cho các số nguyên, được phát biểu trong bài tập 6. 40
CHƢƠNG 3 PHƢƠNG PHÁP ĐẾM 3.1. Tập hợp 3.1.1. Khái niệm tập hợp Khái niệm tập hợp được dùng để chỉ một sưu tập hay một nhóm các đối tượng nào đó mà ta đang quan tâm xem xét, và sưu tập nầy phải được xác định tốt. Các đối tượng trong sưu tập hay trong nhóm nầy sẽ được gọi là các phần tử hay các thành viên của tập hợp. Tính xác định tốt (hay nói vắn tắt là tính xác định) của tập hợp được hiểu theo nghĩa là với một đối tượng nào đó mà ta đang quan tâm thì ta có thể xác định được đích xác rằng trường hợp nào là đúng trong hai trường hợp sau đây: Trường hợp 1: đối tượng là một phần tử của tập hợp. Trong trường hợp nầy ta nói đối tượng thuộc về tập hợp. Trường hợp 2: đối tượng không phải là một phần tử của tập hợp. Trong trường hợp nầy ta nói đối tượng không thuộc về tập hợp. Để thuận tiện cho việc đề cập đến tập hợp về sau, mỗi tập hợp thường được đặt cho một tên, chẳng hạn như A, B, C . Ta cũng dùng ký hiệu để diễn đạt quan hệ "thuộc về" của một phần tử đối với một tập hợp. Khi x là một phần tử thuộc về tập hợp A, thì ta viết x A và đọc là "x thuộc A", hay đọc là "A chứa phần tử x". Ngược lại, nếu x không phải là một phần tử của tập hợp A thì ta viết x A và đọc là "x không thuộc A", hay đọc là "A không chứa phần tử x". Tập hợp bằng nhau: Hai tập hợp A và B sẽ được xem la bằng nhau khi chúng có c ng các phần tử, tức là mỗi phần tử thuộc A đều là phần tử thuộc B và ngược lại. Khi ấy, ta viết là A = B. Tập hợp rỗng: Tập hợp không có phần tử nào được gọi là tập hợp rỗng, và được ký hiệu là  . Cách xác định một tập hợp: Để xác định một tập hợp ta có thể dùng các cách sau đây: Cách liệt kê: Ta liệt kê tất cả các phần tử của tập hợp giữa 2 ký hiệu ngoặc và  . Ví dụ: A = a, b, c  . B = 0, 1  . 41
Các nêu đặc trưng của phần tử: Theo cách nầy, để xác định một tập hợp A ta sẽ nêu lên "tính chất" dùng để xác định xem phần tử trong một không gian U có thuộc về tập hợp A hay không: phần tử x của U sẽ thuộc A khi x thỏa "tính chất", và x không thuộc A khi x không thỏa "tính chất". Từ "tính chất" thường được thể hiện dưới dạng một vị từ p(x) theo biến x U. Khi ấy, tập hợp A sẽ được viết như sau: A = x U : p(x)  hay vắn tắt (hiểu ngầm tập U) là &# A = x : p(x)  Ví dụ: A = n N : n là số nguyên tố  (khái niệm số nguyên tố được định nghĩa trong mục III) B = n N : có một số tự nhiên m sao cho n = m2  Cách xác định tập hợp dưới dạng ảnh của một tập hợp khác A' qua một phép tương ứng f mà ứng với mỗi x A' ta có một phần tử tương ứng f(x) duy nhất trong U. Khi ấy ta viết A = f(x) : x A'  Ghi chú: Phép tương ứng f được nói trên đây chính là một ánh xạ. Khái niệm ánh xạ sẽ được định nghĩa trong mục II. Ví dụ: &# B = n2 : n N  C = (2n+1)2 : n N  3.1.2. Quan hệ “bao hàm trong” và tập hợp con Định nghĩa: Cho A và B là hai tập hợp mà các phần tử của chúng đều thuộc một tập hợp lớn U (hay còn gọi là tập vũ trụ). Ta nói tập A bao hàm trong (hay chứa trong) tập B nếu mỗi phần tử của tập hợp A đều thuộc tập hợp B. Ta cũng nói rằng B bao hàm A (hay B chứa A), và viết là: A  B (hay B  A). Khi A  B ta nói A là một tập hợp con của tập hợp B. 42
Ví dụ: 0, 1, 2  n N : n < 10 N  Z  Q  R  C, trong đó N #9; là tập hợp các số tự nhiên, Z là tập hợp các số nguyên, Q #9; là tập hợp các số hữu tỉ, R #9; là tập hợp các số thực, C #9; là tập hợp các số phức. Cho X là một tập hợp. Sưu tập tất cả các tập hợp con của X được ký hiệu là P(X). Nói một cách khác, P(X) là một tập hợp mà mỗi phần tử của nó là một tập hợp con của X. Tính chất:   A và A  A, với mọi tập hợp A. (A  B)  (B  A) (A = B) (A  B)  (B  C) (A  C) X  Y P(X)  P(Y) Nếu tập hợp X có n phần tử (n N) thì tập hợp P(X) có 2n phần tử. 3.1.3. Các phép toán trên tập hợp Trong mục nầy chúng ta sẽ nêu lên định nghĩa các phép toán tập hợp trên các tập hợp con của một tập hợp vũ trụ U cho trước, và phát biểu một số tính chất liên quan đến các phép toán. Định nghĩa các phép toán: Giao của 2 tập hợp A và B, ký hiệu bởi A  B, là tập hợp gồm tất cả các phần tử của U mà vừa thuộc tập A vừa thuộc tập B. A  B = x : (x A)  (x B)  Hội của 2 tập hợp A và B, ký hiệu bởi A  B, là tập hợp gồm tất cả các phần tử của U sao cho nó thuộc tập A hay thuộc tập B. A  B = x : (x A)  (x B)  Hiệu của 2 tập hợp A và B, ký hiệu bởi A \ B (hay A - B), là tập hợp gồm tất cả các phần tử của U sao cho nó thuộc tập A và không thuộc tập B. 43
A - B = x : (x A)  (x B)  Phần bù của tập A (trong U), ký hiệu bởi Ac, là tập hợp tất cả các phần tử của U mà không thuộc A. Nói cách khác, Ac = U - A Các tính chất của các phép toán: Tính giao hoán: A  B = B  A A  B = B  A Tính kết hợp: A  (B  C) = (A  B)  C A  (B  C) = (A  B)  C Tính phân bố: A  (B  C) = (A  B)  (A  C) A  (B  C) = (A  B)  (A  C) Luật De Morgan: (A  B)c = Ac  Bc (A  B)c = Ac  Bc Phần tử trung hòa: A   = A A  U = A Phần bù: A  Ac = U A  Ac =  Tính thống trị: A  U = U A   =  44
3.1.4. Tích Decartes của các tập hợp Tích Descartes của 2 tập hợp: Cho 2 tập hợp A và B. Tích Descartes của tập hợp A và tập hợp B, được ký hiệu bởi AxB, là tập hợp gồm tất cả các cặp (a,b) sao cho a A và b B. AxB = (a,b) : a A  b B  Trong trường hợp B = A, ta kỳ hiệu AxB là A2. Tích Descartes của nhiều tập hợp: Cho n tập hợp A1, A2, , An (n > 1). Tích Descartes của n tập hợp A1, A2, , An, được ký hiệu bởi A1xA2x xAn, là tập hợp gồm tất cả các bộ n phần tử (a1, a2, , an) với ai Ai với mọi i = 1, , n. Trong trường hợp A1 = A2 = . . . = An = A thì tập hợp tích A1xA2x xAn sẽ được viết là An. 3.2. Các nguyên lý đếm Từ lâu, người ta đã nghiên cứu việc liệt kê, đếm các phần tử hay các đối tượng có những tính chất nào đó để giải quyết một số vấn đề cần thiết được đặt ra. Chẳng hạn, phép đếm được sử dụng trong việc phân tích và đánh giá độ phức tạp của thuật toán. Kỹ thuật đếm còn được sử dụng trong việc tính toán xác suất của các sự kiện. Trong mục nầy chúng ta sẽ trình bày các qui tắc cơ bản của phép đếm. Chúng sẽ giúp ích rất nhiều cho việc giải nhiều vấn đề liên quan đến việc liệt kê, sắp xếp và đếm. 3.2.1. Phép đếm Cho A là một tập hợp khác rỗng, để xác định số phần tử của tập hợp A ta thường thực hiện việc đếm bằng cách lần lượt gán cho các phần tử của A các số tự nhiên kế tiếp nhau, và số tự nhiên đầu tiên (được dùng để gán cho phần tử đầu tiên được xem xét) là 1. Nếu quá trình nầy kết thúc với số tự nhiên n (được gán cho phần tử cuối c ng) thì ta nói A là một tập hợp hữu hạn và có n phần tử. Thật ra khi thực hiện việc đếm như thế chính là thiết lập một song ánh từ A vào tập hợp 1, 2, . . ., n . Từ đó ta có thể định nghĩa phép đếm như sau: Định nghĩa: Cho A là một tập hợp khác rỗng. Nếu tồn tại một số nguyên dương n và một song ánh f từ A vào 1, 2, . . ., n thì ta nói A là một tập hợp hữu hạn và A có n phần tử. Khi đó song ánh f : A 1, 2, . . ., n là sẽ được xem là một phép đếm tập hợp A. Tập hợp rỗng có số phần tử là 0, và cũng được xem là tập hữu hạn. Số phần tử của một tập hợp hữu hạn A được ký hiệu là | A |. 45
Nếu tập hợp A không hữu hạn, ta nói A là một tập vô hạn và viết | A | = Ghi chú: Để khái quát hóa khái niệm số phần tử đối với các tập hợp t y ý và so sánh lực lượng của các tập hợp người ta đưa ra định nghĩa về quan hệ đồng lực lượng, và các quan hệ so sánh lực lượng khác dựa vào khái niệm ánh xạ. Chẳng hạn, hai tập hợp A và B được nói là đồng lực lượng khi tồn tại một song ánh f từ A vào B. Tính chất: Cho A và B là các tập hợp hữu hạn. Giả sử tồn tại đơn ánh từ A vào B. Khi ấy ta có: | A | | B |. 3.2.2. Nguyên lý cộng Cơ sở của nguyên lý cộng là mối liên hệ giữa số phần tử của một tập hợp với số phần tử của các tập hợp con tạo thành phân hoạch của tập hợp đã cho, được phát biểu trong mệnh đề sau đây: Mệnh đề: Cho A và B là 2 tập hợp hữu hạn rời nhau, nghĩa là A  B =  . Khi ấy ta có: | A  B | = | A | + | B | Một cách tổng quát: Nếu A1, A2, , An là các tập hợp hữu hạn rời nhau, nghĩa là phần giao của hai tập hợp bất kỳ trong n tập hợp là rỗng, thì số phần tử của phần hội của các tập hợp trên bằng tổng của các số lượng phần tử trong mỗi tập hợp: | A1  A2  . . .  An | = | A1 | + | A2 | + . . . + | An | Để chứng minh mệnh đề trên cho trường hợp 2 tập hợp A và B ta có thể gọi m là số phần tử của tập hợp A và n là số phần tử của tập hợp B. Sau đó, từ việc giả sử có các song ánh f : A 1, 2, . . ., m và g : B 1, 2, . . ., n , ta có thể lập dễ dàng một song ánh h : A  B 1, 2, . . ., m+n để đi đến kết luận | A  B | = m+n. Trong trường hợp tổng quát ta có thể sử dụng nguyên lý qui nạp, với bước cơ sở là việc chứng minh cho trương hợp 2 tập hợp vừa trình bày ở trên. Ghi chú: Trong trường hợp đối với hai tập hợp hữu hạn A và B t y ý thì ta có: | A  B | = | A | + | B | - | A  B | 46
Tính chất nầy có thể mở rộng cho trường hợp đối với n tập hợp t y ý A1, A2, , An như sau: | A1  A2  . . .  An | =  1 r n | Ar | -  1 r s n | Ar  As | n +  1 r s t n | Ar  As  At | - . . . + (-1) | A1  A2  . . .  An | Nguyên lý cộng : Giả sử ta phải thực hiện công việc và để thực hiện công việc nầy ta có thể chọn một trong hai biện pháp khác nhau theo nghĩa là cách thực hiện biện pháp thứ nhất luôn luôn khác cách thực hiện biện pháp thứ hai. Biện pháp thứ nhất có n cách thực hiện, và đối với biện pháp thứ hai ta có m cách thực hiện. Vậy ta có n+m cách thực hiện công việc. Ví dụ 1: Chúng ta cần chọn một sinh viên toán năm thứ 3 hay năm thứ 4 đi dự một hội nghị. Hỏi có bao nhiêu cách chọn lựa một sinh viên như thế biết rằng có 100 sinh viên toán học năm thứ 3 và 85 sinh viên toán học năm thứ tư ? Lời giải : Ta có thể thực hiện một trong 2 việc chọn lựa khác nhau: chọn một sinh viên toán năm 3, hoặc chọn một sinh viên toán năm 4. Để thực hiện công việc thứ nhất ta có 100 cách, và để thực hiện công việc thứ 2 ta có 85 cách. Vậy để chọn một sinh viên toán theo yêu cầu ta có 100+85 = 185 cách. Chúng ta có thể mở rộng nguyên lý cộng cho trường hợp nhiều sự chọn lựa hơn như sau: Giả sử ta phải thực hiện một công việc bằng cách chọn một trong m sự chọn lựa các biện pháp khác nhau T1, T2, , Tm. Để thực hiện Ti, 1 i m, ta có ni cách. Vậy ta số cách thực hiện công việc trên là n1 + n2 + + nm. Nguyên lý cộng dạng tổng quát nầy có thể được chứng minh bằng qui nạp. Ví dụ 2: Một sinh viên có thể chọn một đề tài từ một trong 3 danh sách các đề tài. Số đề tài trong các danh sách đề tài lần lượt là 23, 15, 19. Hỏi sinh viên có bao nhiêu cách chọn một đề tài. Lời giải: Sinh viên có thể chọn một đề tài trong danh sách thứ thứ nhất theo 23 cách, trong danh sách thứ hai theo 15 cách, và trong danh sách thứ ba theo 19 cách. Do đó số cách chọn đề tài là 23+15+19 = 57. Ví dụ 3: Xác định giá trị của k sau khi đoạn chương trình sau đây được thực hiện xong k := 0 for i1 := 1 to n1 do k := k + 1; for i2 := 1 to n2 do k := k + 1; . 47
. . for im := 1 to nm do k := k + 1; Lời giải. Giá trị của k ban đầu là 0. Sau đó là m vòng lặp khác nhau. Mỗi thao tác lặp trong một vòng lặp là cộng thêm 1 vào k. Vòng lặp thứ i có ni thao tác, và tất cả m vòng lặp không thể thực hiện 2 vòng lặp nào một cách đồng thời. Do đó số thao tác để thực hiện xong đoạn chương trình trên là n1 + n2 + + nm. Đây cũng chính là giá trị cuối c ng của k. 3.2.3. Nguyên lý nhân Cơ sở của nguyên lý nhân là mối liên hệ giữa số phần tử của một tập hợp tích Descartes với số phần tử của các tập hợp thành phần tạo nên tập hợp tích, được phát biểu trong mệnh đề sau đây: Mệnh đề: Cho A và B là 2 tập hợp hữu hạn rời nhau. Khi ấy ta có: | A x B | = | A | . | B | Một cách tổng quát: Nếu A1, A2, , An là các tập hợp hữu hạn thì số phần tử của tích Descartes của các tập hợp trên bằng tích của các số lượng phần tử của các tập hợp trên: | A1 x A2 x . . . x An | = | A1 | . | A2 | . . . . . | An | Để chứng minh mệnh đề trên cho trường hợp 2 tập hợp A và B ta có thể gọi m là số phần tử của tập hợp A và n là số phần tử của tập hợp B. Sau đó, từ việc giả sử có các song ánh f : A 1, 2, . . ., m và g : B 1, 2, . . ., n , ta có thể lập dễ dàng một song ánh h : A x B 1, 2, . . ., mn để đi đến kết luận | A x B | = mn. Trong trường hợp tổng quát ta có thể sử dụng nguyên lý qui nạp, với bước cơ sở là việc chứng minh cho trương hợp 2 tập hợp vừa trình bày ở trên. Nguyên lý nhân : Giả sử ta phải thực hiện một thủ tục bao gồm hai công việc kế tiếp nhau. Để thực hiện công việc thứ nhất ta có n1 cách, và ứng với mỗi cách chọn thực hiện công việc thứ nhất ta có n2 cách thực hiện công việc thứ hai. Vậy ta có số cách thực hiện thủ tục là n1 x n2. 48
Nguyên lý nhân trên có thể được mở rộng và có dạng tổng quát như sau: Giả sử một thủ tục bao gồm m công việc kế tiếp nhau T1, T2, . . ., Tm. Nếu công việc T1 có thể được thực hiện theo n1 cách, và sau khi chọn cách thực hiện cho T1 ta có n2 cách thực hiện T2, v.v cho đến cuối c ng, sau khi chọn cách thực hiện các công việc T1, T2, . . ., Tm-1 ta có nm cách thực hiện Tm. Vậy ta có n1.n2. .nm cách để thực hiện thủ tục. Nguyên lý nhân ở dạng tổng quát nầy có thể được chứng minh bằng qui nạp từ qui tắc nhân cho trường hợp thủ tục gồm 2 công việc. Ví dụ 1: Các ghế ngồi trong một hội trường sẽ được ghi nhãn gồm một mẫu tự và một số nguyên dương không lớn hơn 100. Hỏi số ghế tối đa có thể được ghi nhãn khác nhau là bao nhiêu? Lời giải. Thủ tục ghi nhãn cho một ghế gồm 2 việc : ghi một trong 26 mẫu tự và kế tiếp là ghi một trong 100 số nguyên dương. Qui tắc nhân cho thấy có 26 x 100 = 2600 cách khác nhau để ghi nhãn cho một ghế ngồi. Do đó số ghế lớn nhất có thể được ghi nhãn khác nhau là 2600. Ví dụ 2: Giả sử ta phải đi từ một địa điểm A đến một địa điểm C, ngang qua một địa điểm B. Để đi từ A đến B ta có 8 cách đi khác nhau, và có 6 cách đi từ B đến C. Hỏi có bao nhiêu cách để đi từ A đến C ? Lời giải. Một cách đi từ A đến C gồm 2 việc: đi từ A đến B, rồi đi từ B đến C. Việc thứ nhất (đi từ A đến B) có 8 cách thực hiện, việc thứ hai có 6 cách thực hiện. vậy, theo nguyên lý nhân, số cách đi từ A đến C là 8 x 6 = 48. Ví dụ 3: Hỏi có bao nhiêu chuỗi bit khác nhau có độ dài 8 (tức là gồm 8 bits) ? Lời giải. Mỗi bit có thể được chọn theo 2 cách, vì mỗi bit là 0 hoặc 1. Do đó, qui tắc nhân cho phép ta kết luận rằng có 28 = 256 chuỗi bit có độ dài 8. Ví dụ 4: Một mã bao gồm 6 ký tự, trong đó gồm 3 mẫu tự rồi đến 3 ký số thập phân. Hỏi có bao nhiêu mã khác nhau? Lời giải. Có 26 cách chọn cho mỗi mẫu tự và có 10 cách chọn cho mỗi ký số thập phân. Do đó, theo qui tắc nhân, có tất cả 26.26.26.10.10.10 = 17 576 000 mã khác nhau. Ví dụ 5: Có bao nhiêu ánh xạ đi từ một tập hợp gồm m phần tử vào một tập hợp gồm n phần tử ? Lời giải. Một ánh xạ đi từ tập A gồm m phần tử vào một tập hợp B gồm n phần tử tương ứng với việc chọn lựa một trong n phần tử của B cho mỗi phần tử của A. Do đó, theo qui tắc nhân, có n.n. .n = nm ánh xạ từ A vào B. Ví dụ 6: Có bao nhiêu đơn ánh đi từ một tập hợp gồm m phần tử vào một tập hợp gồm n phần tử ? Lời giải. Trước hết ta nhận xét rằng khi m > n thì không có một đơn ánh nào đi từ một tập hợp gồm m phần tử vào một tập hợp gồm n phần 49
tử. Vậy, cho m n. Giả sử các phần tử trong miền xác định của ánh xạ là a1, a2, . . ., am. Có n cách chọn ảnh qua ánh xạ cho phần tử a1. Vì ánh xạ là đơn ánh nên đối với phần tử a2 ta chỉ có n-1 cách chọn ảnh tương ứng (do giá trị ảnh được chọn cho a1 không thể được chọn lại cho a2). Tổng quát, giá trị ảnh của phần tử ak chỉ có thể được chọn theo n-k+1 cách. Theo qui tắc nhân, có n.(n-1). .(n-m+1) đơn ánh đi từ một tập hợp gồm m phần tử vào một tập hợp gồm n phần tử. Ví dụ 7: Phương án đánh số điện thoại. Giả sử một số điện thoại gồm 10 ký số được chia thành 3 nhóm: 2 nhóm gồm 3 ký số và một nhóm 4 ký số. Do một số lý do nào đó, có một số hạn chế trên các ký số của số điện thoại. Để xác định dạng hợp lệ của một số điện thoại. ta dùng ký hiệu X để chỉ một ký số có thể lấy giá trị từ 0 đến 9, N để chỉ một ký số từ 2 đến 9, và Y chỉ một ký số là 0 hoặc 1. Chúng ta có 2 phương án để đánh số điện thoại : một phương án cũ và một phương án mới. Theo phương án cũ, số điện thoại có dạng NYX NNX XXXX; và theo phương án mới thì số điện thoại có dạng NXX NXX XXXX. Hỏi số lượng số điện thoại khác nhau của mỗi phương án là bao nhiêu? Lời giải. Do qui tắc nhân, đối với phương án đánh số điện thoại cũ, số trường hợp khác nhau của mỗi nhóm ký số trong 3 nhóm lần lượt là : 8.2.10 = 160 (ứng với dạng NYX), 8.8.10 = 640 (ứng với dạng NNX), và 10.10.10.10 = 10000 (ứng với dạng XXXX). Vậy, trong phương án đánh số điện thoại cũ, số lượng số điện thoại là 160. 640.10000 = 1 024 000 000. Tương tự Số lượng số điện thoại trong phương án đánh số mới là : (8.10.10).(8.10.10).(10.10.10.10) = 800.800.10000 = 6 400 000 000. Ví dụ 8: Cũng theo qui tắc nhân ta thấy rằng sau khi thực hiện đoạn chương trình dưới đây thì giá trị của biến k sẽ là n1.n2. .nm. k := 0 for i1 = 1 to n1 do for i1 = 1 to n2 do . . . for i1 = 1 to nm do k := k + 1 Ví dụ 9: Sử dụng qui tắc nhân để chứng minh rằng một tập hợp S hữu hạn có tất cả 2|S| tập hợp con khác nhau. Lời giải. Cho S là một tập hợp hữu hạn, |S| = n. Liệt kê các phần tử của S theo một thứ tự bất kỳ. Ta có thể thấy rằng có sự tương ứng một-một trên (song ánh) giữa các tập hợp con của S và tập hợp các chuỗi bit gồm n bits. Một tập con của S được cho tương ứng với một chuỗi bits có bit thứ i là 1 nếu phần tử thứ i trong danh sách liệt kê thuộc tập hợp 50
con, và bit thứ i là 0 trong trường hợp ngược lại. Bởi qui tắc nhân, có 2n chuỗi bit gồm n bits. Do đó, S có 2n tập hợp con. Dưới đây chúng ta sẽ xem xét một số bài toán về phép đếm phức tạp hơn. Nó đòi hỏi chúng ta phải sử dụng cả nguyên lý cộng lẫn nguyên lý nhân. Ví dụ 10: Trong một version của ngôn ngữ BASIC tên của một biến là một chuỗi gồm 1 hoặc 2 ký tự, mỗi ký tự là mẫu tự hoặc ký số thập lục phân và không phân biệt giữa chữ in hoa và chữ thường. Hơn nữa, một tên biến phải bắt đầu bởi một mẫu tự và tên biến phải khác với 5 chuỗi gồm 2 ký tự đã được dành riêng cho ngôn ngữ. Hỏi có bao nhiêu tên biến khác nhau trong version nầy của BASIC. Lời giải. Đặt V là số tên biến khác nhau trong version nầy của BASIC, V1 là số biến gồm một ký tự, và V2 là số biến gồm hai ký tự. Theo qui tắc cộng ta có V = V1 + V2. Vì biến gồm một ký tự phải là một mẫu tự nên V1 = 26. Ngoài ra, theo qui tắc nhân ta có 26.36 chuỗi có độ dài 2 với ký tự đi đầu là mẫu tự và ký tự kế là mẫu tự hoặc ký số thập phân. Tuy nhiên, có 5 chuỗi bị loại ra nên V2 = 26.36 - 5 = 931. Vậy có V = V1 + V2 = 26 + 931 = 957 tên khác nhau cho các biến của version nầy của BASIC. Ví dụ 11: Mỗi người sử dụng trên một hệ thống máy tính có một "password" dài từ 6 đến 8 ký tự, trong đó mỗi ký tự là một chữ in hoa hoặc là một ký số thập phân. Mỗi "password" phải có ít nhất một ký số. Hỏi có bao nhiêu password khác nhau ? Lời giải. Đặt P là số lượng tất cả các "password", và P6, P7, P8 lần lượt là số các "password" có độ dài 6, 7, 8. Do qui tắc cộng ta có P = P6 + P7 + P8. Chúng ta sẽ tính P6, P7, và P8. Tính trực tiếp P6 tương đối khó. Để tính P6 cho dễ, ta tính số chuỗi có độ dài 6 gồm các chữ in hoa hay ký số thập phân, kể cả các chuỗi không có ký số thập phân, và trừ cho số chuỗi (với độ dài 6) không có ký số thập phân. Theo qui tắc nhân, số chuỗi gồm 6 ký tự là 366 và số chuỗi không có ký số là 266. Suy ra 6 6 P6 = 36 - 26 = 2 176 782 336 - 308 915 776 = 1 867 866 560. Tương tự, ta có thể tính ra được : 7 7 P7 = 36 - 26 = 78 364 164 096 - 8 031 810 176 = 70 332 353 920. và 8 8 P8 = 36 - 26 = 2 821 109 907 456 - 208 827 064 576 51
= 2 612 282 842 880. Từ đó ta tính được : P = P6 + P7 + P8 = 2 684 483 063 360. 3.2.4. Nguyên lý bù trừ Khi hai công việc có thể được làm đồng thời, ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc. Ta có thể phát biểu nguyên lý đếm này bằng ngôn ngữ tập hợp. Cho A1, A2 là hai tập hữu hạn, khi đó |A1  A2| = |A1| + |A2| |A1  A2|. Từ đó với ba tập hợp hữu hạn A1, A2, A3, ta có: |A1  A2  A3| = |A1| + |A2| + |A3| |A1  A2| |A2  A3| |A3  A1| + |A1  A2  A3|, và bằng quy nạp, với k tập hữu hạn A1, A2, , Ak ta có: k-1 | A1  A2   Ak| = N1 N2 + N3 + ( 1) Nk, trong đó Nm (1 m k) là tổng phần tử của tất cả các giao m tập lấy từ k tập đã cho, nghĩa là N = | A  A   A | m  i1 i2 im 1 i1 i2 im k Bây giờ ta đồng nhất tập Am (1 m k) với tính chất Am cho trên tập vũ trụ hữu hạn U nào đó và đếm xem có bao nhiêu phần tử của U sao cho không thỏa mãn bất kỳ một tính chất Am nào. Gọi N là số cần đếm, N là số phần tử của U. Ta có: k = N | A1  A2   Ak| = N N1 + N2 + ( 1) Nk, trong đó Nm là tổng các phần tử của U thỏa mãn m tính chất lấy từ k tính chất đã cho. Công thức này được gọi là nguyên lý bù trừ. Nó cho phép tính qua các Nm trong trường hợp các số này dễ tính toán hơn. Thí dụ 3: Có n lá thư và n phong bì ghi sẵn địa chỉ. Bỏ ngẫu nhiên các lá thư vào các phong bì. Hỏi xác suất để xảy ra không một lá thư nào đúng địa chỉ. Mỗi phong bì có n cách bỏ thư vào, nên có tất cả n! cách bỏ thư. Vấn đề còn lại là đếm số cách bỏ thư sao cho không lá thư nào đúng địa chỉ. Gọi U là tập hợp các cách bỏ thư và Am là tính chất lá thư thứ m bỏ đúng địa chỉ. Khi đó theo công thức về nguyên lý bù trừ ta có: n = n! N1 + N2 + ( 1) Nn, trong đó Nm (1 m n) là số tất cả các cách bỏ thư sao cho có m lá thư đúng địa chỉ. Nhận xét rằng, Nm là tổng theo mọi cách lấy m lá thư từ n lá, với mỗi cách lấy m lá thư, có (n-m)! cách bỏ để m lá thư này đúng địa chỉ, ta nhận được: n! 1 1 1 N = C m (n - m)! = và = n!(1 + + ( 1)n ), m n k! 1! 2! n! 52
n! trong đó C m = là tổ hợp chập m của tập n phần tử (số cách chọn m đối tượng n m!(n m)! 1 1 1 trong n đối tượng được cho). Từ đó xác suất cần tìm là: 1 + + ( 1)n . Một 1! 2! n! - 1 điều lý thú là xác suất này dần đến e 1 (nghĩa là còn > ) khi n khá lớn. 3 Số N trong bài toán này được gọi là số mất thứ tự và được ký hiệu là Dn. Dưới đây là một vài giá trị của Dn, cho ta thấy Dn tăng nhanh như thế nào so với n: n 2 3 4 5 6 7 8 9 10 11 Dn 1 2 9 44 265 1854 14833 133496 1334961 14684570 3.2.5. Nguyên lý Dirichlet 3.2.5.1. Mở đầu Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì ít nhất trong một ngăn có nhiều hơn một con chim. Nguyên lý này dĩ nhiên là có thể áp dụng cho các đối tượng không phải là chim bồ câu và chuồng chim. Mệnh đề (Nguyên lý): Nếu có k+1 (hoặc nhiều hơn) đồ vật được đặt vào trong k hộp thì tồn tại một hộp có ít nhất hai đồ vật. Chứng minh: Giả sử không có hộp nào trong k hộp chứa nhiều hơn một đồ vật. Khi đó tổng số vật được chứa trong các hộp nhiều nhất là bằng k. Điều này trái giả thiết là có ít nhất k + 1 vật. Nguyên lý này thường được gọi là nguyên lý Dirichlet, mang tên nhà toán học người Đức ở thế kỷ 19. Ông thường xuyên sử dụng nguyên lý này trong công việc của mình. Thí dụ 4: 1) Trong bất kỳ một nhóm 367 người thế nào cũng có ít nhất hai người có ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 ngày sinh nhật khác nhau. 2) Trong kỳ thi học sinh giỏi, điểm bài thi được đánh giá bởi một số nguyên trong khoảng từ 0 đến 100. Hỏi rằng ít nhất có bao nhiêu học sinh dự thi để cho chắc chắn tìm được hai học sinh có kết quả thi như nhau? Theo nguyên lý Dirichlet, số học sinh cần tìm là 102, vì ta có 101 kết quả điểm thi khác nhau. 3) Trong số những người có mặt trên trái đất, phải tìm được hai người có hàm răng giống nhau. Nếu xem mỗi hàm răng gồm 32 cái như là một xâu nhị phân có chiều dài 32, trong đó răng còn ứng với bit 1 và răng mất ứng với bit 0, thì có tất cả 232 = 4.294.967.296 hàm răng khác nhau. Trong khi đó số người trên hành tinh này là vượt quá 5 tỉ, nên theo nguyên lý Dirichlet ta có điều cần tìm. 53
3.2.5.2. Nguyên lý Dirichlet tổng quát Mệnh đề: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất ]N/k[ đồ vật. (Ở đây, ]x[ là giá trị của hàm trần tại số thực x, đó là số nguyên nhỏ nhất có giá trị lớn hơn hoặc bằng x. Khái niệm này đối ngẫu với [x] – giá trị của hàm sàn hay hàm phần nguyên tại x – là số nguyên lớn nhất có giá trị nhỏ hơn hoặc bằng x.) Chứng minh: Giả sử mọi hộp đều chứa ít hơn ]N/k[ vật. Khi đó tổng số đồ vật là N k (] [ 1) < k = N. k Điều này mâu thuẩn với giả thiết là có N đồ vật cần xếp. Thí dụ 5: 1) Trong 100 người, có ít nhất 9 người sinh c ng một tháng. Xếp những người sinh c ng tháng vào một nhóm. Có 12 tháng tất cả. Vậy theo nguyên lý Dirichlet, tồn tại một nhóm có ít nhất ]100/12[= 9 người. 2) Có năm loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là 6 người c ng nhận học bổng như nhau. Gọi N là số sinh viên, khi đó ]N/5[ = 6 khi và chỉ khi 5 < N/5 6 hay 25 < N 30. Vậy số N cần tìm là 26. 3) Số mã v ng cần thiết nhỏ nhất phải là bao nhiêu để đảm bảo 25 triệu máy điện thoại trong nước có số điện thoại khác nhau, mỗi số có 9 chữ số (giả sử số điện thoại có dạng 0XX - 8XXXXX với X nhận các giá trị từ 0 đến 9). Có 107 = 10.000.000 số điện thoại khác nhau có dạng 0XX - 8XXXXX. Vì vậy theo nguyên lý Dirichlet tổng quát, trong số 25 triệu máy điện thoại ít nhất có ]25.000.000/10.000.000[ = 3 có c ng một số. Để đảm bảo mỗi máy có một số cần có ít nhất 3 mã v ng. 3.2.5.3. Một số ứng dụng của nguyên lý Dirichlet. Trong nhiều ứng dụng thú vị của nguyên lý Dirichlet, khái niệm đồ vật và hộp cần phải được lựa chọn một cách khôn khéo. Trong phần nay có vài thí dụ như vậy. Thí dụ 6: 1) Trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau. Số người quen của mỗi người trong phòng họp nhận các giá trị từ 0 đến n 1. Rõ ràng trong phòng không thể đồng thời có người có số người quen là 0 (tức là không quen ai) và có người có số người quen là n 1 (tức là quen tất cả). Vì vậy theo số lượng người quen, ta chỉ có thể phân n người ra thành n 1 nhóm. Vậy theo nguyên lý Dirichlet tồn tai một nhóm có ít nhất 2 người, tức là luôn tìm được ít nhất 2 người có số người quen là như nhau. 54
2) Trong một tháng gồm 30 ngày, một đội bóng chuyền thi đấu mỗi ngày ít nhất 1 trận nhưng chơi không quá 45 trận. Chứng minh rằng tìm được một giai đoạn gồm một số ngày liên tục nào đó trong tháng sao cho trong giai đoạn đó đội chơi đúng 14 trận. Gọi aj là số trận mà đội đã chơi từ ngày đầu tháng đến hết ngày j. Khi đó 1 a1 < a2 < < a30 < 45 15 a1+14 < a2+14 < < a30+14 < 59. Sáu mươi số nguyên a1, a2, , a30, a1+ 14, a2 + 14, , a30+14 nằm giữa 1 và 59. Do đó theo nguyên lý Dirichlet có ít nhất 2 trong 60 số này bằng nhau. Vì vậy tồn tại i và j sao cho ai = aj + 14 (j < i). Điều này có nghĩa là từ ngày j + 1 đến hết ngày i đội đã chơi đúng 14 trận. 3) Chứng tỏ rằng trong n + 1 số nguyên dương không vượt quá 2n, tồn tại ít nhất một số chia hết cho số khác. k j Ta viết mỗi số nguyên a1, a2, , an+1 dưới dạng aj = 2 qj trong đó kj là số nguyên không âm còn qj là số dương lẻ nhỏ hơn 2n. Vì chỉ có n số nguyên dương lẻ nhỏ hơn 2n nên ki k j theo nguyên lý Dirichlet tồn tại i và j sao cho qi = qj = q. Khi đó ai= 2 q và aj = 2 q. Vì vậy, nếu ki kj thì aj chia hết cho ai còn trong trường hợp ngược lại ta có ai chia hết cho aj. Thí dụ cuối c ng trình bày cách áp dụng nguyên lý Dirichlet vào lý thuyết tổ hợp mà vẫn quen gọi là lý thuyết Ramsey, tên của nhà toán học người Anh. Nói chung, lý thuyết Ramsey giải quyết những bài toán phân chia các tập con của một tập các phần tử. Thí dụ 7. Giả sử trong một nhóm 6 người mỗi cặp hai hoặc là bạn hoặc là th . Chứng tỏ rằng trong nhóm có ba người là bạn lẫn nhau hoặc có ba người là kẻ th lẫn nhau. Gọi A là một trong 6 người. Trong số 5 người của nhóm hoặc là có ít nhất ba người là bạn của A hoặc có ít nhất ba người là kẻ th của A, điều này suy ra từ nguyên lý Dirichlet tổng quát, vì ]5/2[ = 3. Trong trường hợp đầu ta gọi B, C, D là bạn của A. nếu trong ba người này có hai người là bạn thì họ c ng với A lập thành một bộ ba người bạn lẫn nhau, ngược lại, tức là nếu trong ba người B, C, D không có ai là bạn ai cả thì chứng tỏ họ là bộ ba người th lẫn nhau. Tương tự có thể chứng minh trong trường hợp có ít nhất ba người là kẻ th của A. 55
CHƢƠNG 4 QUAN HỆ 4.1. Quan hệ hai ngôi 4.1.1. Định nghĩa quan hệ và ví dụ Giữa các phần tử trong một tập hợp nào đó mà chúng ta đang quan tâm thường có những mối liên hệ hay những quan hệ. Ví dụ: quan hệ lớn hơn giữa các số thực, quan hệ "anh em" giữa người với người, quan hệ đồng dạng giữa các tam giác, v.v Mỗi quan hệ trong một tập hợp được đặc trưng bằng một hay một số tiêu chuẩn nào đó thể hiện ngữ nghĩa của quan hệ. Ở đây chúng ta chỉ đề cập đến những quan hệ, được gọi là những quan hệ 2 ngôi, nói lên sự liên hệ giữa mỗi phần tử với các phần tử khác trong tập hợp. Khi ta đang xem xét một quan hệ như thế, thì với hai phần tử x, y t y ý trong tập hợp chúng sẽ có : hoặc là x có quan hệ với y, hoặc là x không có quan hệ với y. Nói như vậy cũng có nghĩa là tập hợp các cặp (x, y) gồm 2 phần tử có quan hệ có thể xác định được quan hệ đang xét trên tập hợp. Về mặt toán học, một quan hệ 2 ngôi được định nghĩa như sau: Định nghĩa : Cho một tập hợp X khác rỗng. Một quan hệ 2 ngôi trên X là một tập hợp con R của X2. Cho 2 phần tử x và y của X, ta nói x có quan hệ R với y khi và chỉ khi (x,y) R, và viết là x R y. Như vậy: x R y (x,y) R Khi x không có quan hệ R với y, ta viết: x y. Ví dụ: 1. Trên tập hợp X = 1,2,3,4 , xét quan hệ 2 ngôi R được định nghĩa bởi: R = (1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4) Với quan hệ nầy ta có: 2 R 4, nhưng 2 3. 2. Trên tập hợp các số nguyên Z ta định nghĩa một quan hệ 2 ngôi R như sau: x R y nếu và chỉ nếu x-y là số chẳn. hay nói cách khác: R = (x,y) Z2  x-y = 2k với k Z  Quan hệ R nầy chính là quan hệ đồng dư modulo 2. 56
3. Cho n là một số nguyên dương. Nhắc lại rằng quan hệ đồng dư modulo n trên tập hợp các số nguyên Z, ký hiệu bởi  (mod n), được định nghĩa như sau: a  b (mod n)  k Z : (a - b) = k.n Quan hệ nầy là một quan hệ 2 ngôi trên Z. 4. Quan hệ trên tập hợp các số thực R cũng là một quan hệ 2 ngôi. 5. Cho E là một tập hợp, đặt X = P(E). Mỗi phần tử thuộc X là một tập hợp con của E. Trên E có các quan hệ quen thuộc sau đây: - quan hệ bao hàm, ký hiệu bởi  - quan hệ chứa, ký hiệu bởi  - quan hệ bằng nhau, ký hiệu bởi = Ghi chú : Người ta còn định nghĩa một quan hệ (2 ngôi) giữa một tập hợp A và một tập hợp B là một tập hợp con của AxB. Ví dụ: A = 1, 2, 3, 4, 5 , B = 0, 1 . Ta có R = (1,1), (2,0), (3,1), (4,0), (5,0) là một quan hệ giữa A và B. Tổng quát hơn, ta có thể định nghĩa một quan hệ giữa các tập hợp A1, A2, . . ., An là một tập hợp con của A1 x A2 x . . . x An (tích Descartes của các tập hợp A1, A2, . . ., An). Như vậy, khi R là một quan hệ giữa các tập A1, A2, . . ., An thì mỗi phần tử của R là ột bộ n (a1, a2, . . ., an) với ai Ai (i=1, , n). Cách xác định một quan hệ: Dựa vào các phương pháp xác định một tập hợp, ta có thể xác định một quan hệ bằng các phương pháp sau đây: Liệt kê: liệt kê tất cả các cặp hay bộ phần tử có quan hệ R (tức là thuộc R). Trong ví dụ 1 ở trên, quan hệ R được cho theo cách liệt kê. Nêu tính chất đặc trưng cho quan hệ R, tức là tính chất hay tiêu chuẩn để xác định các phần tử thuộc R hay không. Trong các ví dụ 2 và 3 ở trên, quan hệ R được cho bằng cách nêu lên tính chất xác định quan hệ. 4.1.2. Các tính chất của quan hệ Một quan hệ 2 ngôi trên một tập hợp có thể có một số tính chất nào đó làm cho tập hợp có một cấu trúc nhất định. Dưới đây là định nghĩa một số tính chất thường được xét đối với một quan hệ 2 ngôi. Định nghĩa : Giả sử R là một quan hệ 2 ngôi trên một tập hợp X. Ta nói quan hệ R có tính phản xạ (reflexive) nếu và chỉ nếu 57
x R x với mọi x X. Ta nói quan hệ R có tính đối xứng (symmetric) nếu và chỉ nếu x R y y R x với mọi x,y X. Ta nói quan hệ R có tính phản xứng (antisymmetric) nếu và chỉ nếu (x R y và y R x) x = y với mọi x,y X. Ta nói quan hệ R có tính truyền hay bắc cầu (transitive) nếu và chỉ nếu (x R y và y R z) x R z với mọi x,y,z X. Ví dụ: Trong ví dụ nầy chúng ta đề cập đến một số quan hệ đã được nêu lên trong các ví dụ của mục 1.1 ở trên, và phát biểu các tính chất của chúng. Việc kiểm chứng các tính chất nầy khá dễ dàng. 1. Quan hệ đồng dư modulo n trên Z có 3 tính chất: phản xạ, đối xứng, truyền. 2. Quan hệ trên tập hợp các số thực có 3 tính chất: phản xạ, phản xứng, truyền. 3. Cho E là một tập hợp. Quan hệ  trên P(E) có 3 tính chất: phản xạ, phản xứng, truyền. 4.1.3. Biểu diễn quan hệ Ngoài phương pháp biểu diễn một quan hệ 2 ngôi dưới dạng tập hợp các cặp phần tử người ta còn có thể sử dụng ma trận để biểu diễn cho quan hệ trong trường hợp các tập hợp là hữu hạn. Khái niệm ma trận sẽ được định nghĩa và khảo sát chi tiết hơn trong phần "Đại số Tuyến tính". Ở đây chúng ta chỉ cần hiểu ma trận một cách đơn giản là một bảng liệt kê các phần tử thành các dòng và các cột. Ví dụ, bảng liệt kê 6 số nguyên thành 2 dòng và 3 cột sau đây là một ma trận: Một ma trận M gồm m dòng, n cột sẽ được gọi là một ma trận có cấp mxn. Nếu m = n thì ta nói M là một ma trận vuông cấp n. Giả sử R là một quan hệ 2 ngôi giữa một tập hợp hữu hạn A = { a1, a2, , am } và một tập hữu hạn B = {b1, b2, , bm} . Quan hệ R có thể được biểu diễn bởi ma trận MR = [mij] gồm m dòng và n cột (tức là ma trận cấp mxn), trong đó mij = 1 nếu (ai , bj) R mij = 0 nếu (ai , bj) R 58