Chương 1: Tập hợp, quan hệ

Nội dung tài liệu trình bày phép toán tập hợp (Set operations); đại số tập hợp (Set Algerbra); biểu diễn tập hợp trên máy tính quan hệ tương đương và quan hệ thứ tự; lực lượng của tập hợp (Cardinality) và PP qui nạp toán học.
Nội dung trích xuất từ tài liệu:
Chương 1: Tập hợp, quan hệNội dungChương 11.1. Tập hợp (Set)11.2. Phép toán tập hợp (Set operations)Tập hợp, Quan hệ1.3. Đại số tập hợp (Set Algerbra)1.4. Biểu diễn tập hợp trên máy tính (Computer Representation)(Set, Relation)1.5. Quan hệ (Relation)1.6. Ánh xạ (Mapping)1.7. Quan hệ tương đương và Quan hệ thứ tự1.8. Lực lượng của tập hợp (Cardinality)1.9. PP qui nạp toán học. Định nghĩa tập hợp theo qui nạp.Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội21.1. Tập hợp (Set)1.1.1 Tập hợp và phần tử• 1.1.1 Tập hợp và phần tử (Set and Element)• 1.1.2 Các cách xác định tập hợp (Set Definition)• 1.1.3 Nghịch lý Russell (Russell Paradox)• Tập hợp là một khái niệm cơ bản của toán học không đượcđịnh nghĩa.• Ta hiểu tập hợp là một họ xác định các đối tượng nào đó. Cácđối tượng cấu thành tập hợp được gọi là các phần tử của tậphợp. Các phần tử trong tập hợp là khác nhau.• Ví dụ:(Set and Element)––––––Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội3Tập các số tự nhiên N.Tập tất cả các số nguyên tốTập các số nguyên Z, tập các số nguyên không âm Z+.Tập các số thực R, tập các số thực không âm R+.Tập các học sinh của một lớp, Tập các phòng học của trường ĐHBK...Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội41.1.1 Tập hợp và phần tử1.1.1 Tập hợp và phần tử• Nếu x là phần tử của tập S thì ta nói x là thuộc vào S và kýhiệu: x Î S.• Trái lại, ta nói x không thuộc vào S và ký hiệu x Ï S.• Ta thường sử dụng các chữ cái latin in hoa A, B, C, ... để kýhiệu tập hợp và các chữ cái latin in thường a, b, c, ... để kýhiệu phần tử của tập hợp.• Chú ý: Thoạt nhìn khái niệm tập hợp có vẻ là trực quan rõràng. Nhưng thực ra vấn đề không đơn giản. Chẳng hạn, việcxác nhận một đối tượng có phải là phần tử của một tập hợpkhông đơn giản một chút nào.• Các tập hợp như là các đối tượng lại có thể là phần tửcủa các hợp khác. Tập hợp mà các phần tử có thể làcác tập hợp thường được gọi là họ hay lớp. Người tathường sử dụng các chữ cái latin viết tay hoa: A, B,C,...để ký hiệu lớp hay họ.• Tập hợp không chứa phần tử nào cả được gọi là tậprỗng (trống). Tập rỗng được ký hiệu là Æ.• Trong những nghiên cứu cụ thể, các phần tử của cáctập hợp được quan tâm đều được lấy từ một tập rộnglớn hơn U được gọi là tập vũ trụ.– Chẳng hạn, 86969696969696969696969696967111 là số nguyên tố?Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội51.1.2 Các cách xác định tập hợp(Set Definition)61.1.2 Các cách xác định tập hợp• Để xác định một tập hợp cần chỉ ra các phần tử nào thuộc vàonó. Để làm điều đó có một số cách cơ bản sau đây:1. Liệt kê (set extension): Liệt kê các phần tử của tập hợp trongdấu ngoặc nhọn {}.– Ví dụ: M9 = {1, 2, ...,8, 9}, G = {Mai, Mơ, Mận, Me, Muỗm}.2. Vị từ đặc trưng (set intension): Đưa ra điều kiện mà hễ mộtđối tượng thoả mãn nó sẽ là phần tử của tập hợp.– Ví dụ: M9={n | (nÎN)Ù(n < 10)}, Neven={n| n - số nguyên dươngchẵn}, Q = { p / q | pÎZ, qÎZ, q ¹ 0 } – tập các số hữu tỷ.– Tổng quát: M = { x| P(x)}, trong đó P(x) là vị từ.Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà NộiToán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội73. Thủ tục sinh: Chỉ ra thủ tục sinh các phần tử của tập hợp– Ví dụ: M9 = {n| for n:=1 to 9 do }• Bằng liệt kê chỉ có thể xác định các tập hợp hữu hạn. Các tậpvô hạn được xác định bởi vị từ đặc trưng hoặc thủ tục sinh– Ví dụ:N = {n | n:=1; while n < n+1 do },R+ = {x| x là số thực không âm}.Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội81.1.3 Nghịch lý Russell (Russell’s Paradox)1.1.3 Nghịch lý Russell• Cách xác định tập hợp bởi vị từ đặc trưng có thể dẫn đến mâuthuẫn. Tất cả các tập xét trong các ví dụ đã nêu không có tậpnào chứa chính nó như là phần tử. Bây giờ ta xét tập tất cả cáctập không chứa chính nó như là phần tử:Y = {X | X Ï X}• Nếu tập Y như vậy là tồn tại, thì ta phải trả lời được câu hỏi:• Có nhiều biện pháp để thoát khỏi nghịch lý Russell. Chẳnghạn:1. Hạn chế sử dụng vị từ đặc trưng dưới dạngP(x) = x Î A thoả mãn Q(x)trong đó A là tập vũ trụ cho trước. Trong trường hợp này tậphợp được ký hiệu là {x Î A | Q(x)}. Đối với tập Y, ta không chỉra tập vũ trụ, vì vậy Y không là tập hợp.2. Vị từ đặc trưng P(x) được cho dưới dạng hàm tính được(thuật toán). Phương pháp tính giá trị của vị từ X Î X khôngđược xác định, vì thế Y không là tập hợp.• Cách tiếp cận thứ hai là cơ sở để xây dựng toán kiến thiết.YÎY?– Giả sử Y Î Y, khi đó theo định nghĩa Y Ï Y ?!– Giả sử Y Ï Y, khi đó theo định nghĩa Y Î Y ?!• Mâu thuẫn thu được được biếtdưới tên gọi nghịch lý Russell.Bertrand Russell1872-1970Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội9Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội101.2 Các phép toán tập hợpNội dung(Set Operations)• 1.2.1 So sánh các tập hợp (Set Comparision)• 1.2.2 Các phép toán tập hợp (Set Operations)• 1.2.3 Phân hoạch và phủ (Set Partition and Cover)1.1. Tập hợp11.2. Các phép toán tập hợp1.3. Đại số tập hợp1.4. Biểu diễn tập hợp trên máy tính1.5. Quan hệ1.6. Ánh xạ1.7. Quan hệ tương đương và Quan hệ thứ tự1.8. Lực lượng của tập hợp.1.9. PP qui nạp toán học. Định nghĩa tập hợp theo qui nạp.Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội11Toán rời rạc - NGUYỄN ĐỨC NGHĨA, Bộ môn KHMT, ĐHBK Hà Nội12So sánh các tập hợpSo sánh các tập hợp• Tập A được gọi là tập con của tập B, ký hiệu là A Ì B, nếu mỗiphần tử của A đều là phần tử của B:A Ì B Û x Î A Þ x Î B.• Nếu A là tập con của B thì ta cũng nói là A chứa trong B hoặcB chứa A.• Nếu A Ì B và A ¹ B thì ta nói A là tập con thực sự của B.• Ta có: M: M Ì M và theo định nghĩa Æ Ì M.• Hai tập A và B là bằng nhau nếu mọi phần tử của Ađều là phần tử của B và ngược lại:A = B Û A Ì B và B Ì A.• Lực lượng của tập A được ký hiệu là |A|. Đối với tậphữu hạn lực lượng chính là số phần tử của nó.• Nếu |A| = |B ...