CHƯƠNG 1: KHÁI NIỆM VỀ TẬP HỢP VÀ TẬP HỢP MỜ 1.1 Khái niệm về tập hợp Tập hợp là khái niệm cơ sở của toán học [1, 2, 5]. Mô tả một tập hợp T đồng nhất với việc liệt kê các phần tử của tập đó. Kí hiệu x T cho biết x là một phần tử của tập hợp T. Thí dụ T = {1, 3, 5, 7 } cho biết tập T gồm bốn số tự nhiên là 1, 3, 5 và 7.
Khi đó ta có 3 T: 3 là phần tử của tập T 2 T: 2 không phải là phần tử của tập T. Trong toán học thường sử dụng các tập hợp sau đây: Tập các số tự nhiên, ℕ = {0, 1, …, }. Tập các số tự nhiên dương, ℕ+ = {1, …, }. Tập các số nguyên, ℤ = {…, 2, 1, 0, 1, 2, …, }.
Tập các số nguyên dương, ℤ+ = ℕ+ = {1, 2, …, }. Tập các số hữu tỷ ℚ. Tập các số thực ℝ.2 Mô tả tập hợp Thông thường, để mô tả tập hợp người ta phát biểu các tính chất của các phần tử của tập đó. Thí dụ, ABC = {‘A’, … ,’Z’} là tập các chữ cái IN HOA trong bảng chữ cái tiếng Latin.
L = {2k+1 | k ℕ} tập các số tự nhiên lẻ, L = {1, 3, …} Các đặc trưng của tập hợp Số phần tử trong tập T được gọi là lực lượng của tập T và thường được kí hiệu là |T|, ||T||, hoặc #T. Trong tài liệu này sử dụng kí hiêu #T. Tập rỗng, kí hiệu, là tập không có phần tử nào: # = 0. Tập ABC nói trên có 26 phần tử, #ABC = 26.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 5 Nếu X là một tập và a là một phần tử thì ta kí hiệu X[a] là hàm cho ra giá trị 1 (true) nếu a X; ngược lại, hàm cho ra giá trị 0 (false). Thí dụ ABC[‘Y’] = 1; ABC[‘?’] = 0; ABC[‘y’] = 0; Các tập có vô hạn phần tử được gọi là tập vô hạn. Các tập hợp số trong toán học, ℕ, ℤ, ℚ, ℝ là những tập vô hạn.3 Trật tự các tập hợp Hai tập X và Y được gọi là khác nhau nếu có một phần tử thuộc tập này mà không thuộc tập kia. XYeXeY Tập X được gọi là tập con của tập Y, X Y nếu mọi phần tử của X đều thuộc tập Y.
XYeXeY Tập X được gọi là tập con đúng hay tập con thực sự của tập Y, X Y nếu X khác Y và mọi phần tử của X đều thuộc tập Y. X Y X ≠ Y, e X e Y Hai tập X và Y được gọi là bằng nhau nếu tập này là tập con của tập kia và ngược lại.2 Các phép toán trên tập hợp Cho tập U gọi là tập vũ trụ hoặc tập nền. Ta xét các tập con của U. Trên các tập con X, Y, Z, … của U ta định nghĩa các phép toán sau đây [2, 4, 5].1 Phép hợp Hợp của hai tập X và Y cho ta tập chứa đồng thời các phần tử của X và của Y, X Y = { e | e X và e Y } Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.2 Phép giao Giao của hai tập X và Y cho ta tập chứa các phần tử thuộc đồng thời X và Y, XY={e|eX eY} 1.3 Phép trừ Hiệu của hai tập X và Y cho ta tập chứa các phần tử của X và không thuộc Y, X Y = { e | e X và e Y } Tập X’ = U X được gọi là phần bù của tập X (đối với tập nền U).4 Biểu đồ Venn Biểu đồ Venn là một trong những công cụ trực quan biểu diễn các phép toán tập hợp.
Mỗi tập hợp được biểu diễn dưới dạng một hình tròn. Riêng tập nền được biểu diễn mhư một hình chữ nhật. Các phần tử thuộc tập hợp nào thì nằm trọn trong hình tròn tương ứng. Giao của hai tập hợp được biểu diễn như phần chung của hai hình tròn.
Hợp của hai tập hợp là toàn bộ phàn chung và phần riêng của chúng. Phần bù của một tập hợp là phần ngoài của tập hợp nhưng nằm trong tập nền. LX R Y Z X X Y Z = X Y, L = X Y, R = Y X XY UX X X Y XY X’ Các phép toán tập hợp Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 7 Thí dụ Xét các tập sau đây U = {x ℕ | x ≤ 500}, S = {x U | 100 ≤ x ≤ 200}, K = {x U | 80 ≤ x ≤ 120}. Ngữ nghĩa U là tập các lượng mưa tính theo milimet, bao gồm các mức từ 0 mm (không mưa) đến 500 mm (lượng mưa tối đa); S là các vùng mưa nhiều (ngập sâu) gồm các mức từ 100 mm đến 200 mm; K là các vùng mưa khá nặng gồm các mức từ 80 mm đến 120 mm.5 Các tính chất của các phép toán tập hợp Các phép toán và các toán tử trên tập hợp có các tính chất sau đây [2, 5].
Với mọi tập con X, Y, Z của tập nền U ta có: Tính chất giao hoán XY=YX XY=YX Tính chất kết hợp (X Y) Z = X (Y Z) (X Y) Z = X (Y Z) Nhờ tính chất giao hoán và kết hợp ta có thể vận dụng qui tắc sau khi tính toán các biểu thức tập hợp chỉ chứa các phép hợp hoặc chỉ chứa các phép giao: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 8 Qui tắc Trong biểu thức tập hợp chỉ chứa các phép hợp (giao) ta có thể thực hiện phép toán theo trật tự tùy ý. Tính chất phân phối (X Y) Z = (X Z) (Y Z) (X Y) Z = (X Z) (Y Z) Luật De Morgan (X Y)’ = X’ Y’ (Bù của hợp bằng giao các bù) (X Y)’ = X’ Y’ (Bù của giao bằng hợp các bù) Ngoài ra, trật tự (bao hàm) của các tập hợp thỏa các tính chất sau đây: Tính chất bắc cầu X Y và Y Z X Z Tính chất tựa bắc cầu XY XZ YZ 1.6 Biểu diễn tập hợp Trong tin học, các tập hợp được mô tả như là những tập con của một tập nền U cho trước. Tập nền U trước hết cần được được mô tả tường minh như một kiểu dữ liệu. Thí dụ, trong ngôn ngữ lập trình Pascal có kiểu dữ liệu set.
Khai báo var x: set of char; cấp phát một biến x thuộc kiểu tập con của tập nền U gồm 256 kí tự của bộ mã ASCII với mã số từ 0 đến 255. Trong ngôn ngữ lập trình C++ có kiểu enum cho phép khai báo tập hợp bằng phương thức liệt kê các phần tử và có thể chỉ định mã số của các phần tử. Thí dụ, Khai báo Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 9 enum Colors { DARKBLUE = 1, DARKGREEN, DARKTEAL, DARKRED, DARKPINK, DARKYELLOW, GRAY, DARKGRAY, BLUE, GREEN, TEAL, RED, PINK, YELLOW, WHITE }; mô tả tập Colors gồm các màu trên màn hình, trong đó qui ước màu đầu tiên là DARKBLUE mang mã số 1. Như vậy các màu tiếp theo sẽ có mã số lần lượt là 2, 3, … Khai báo trên thiết lập một kiểu dữ liệu tên là Colors như là một đoạn của kiểu nguyên, trong trường hợp này, Colors chứa các trị nguyên từ 1 đến 15.
Sau, đó ta có thể khai báo một biến thuộc kiểu Colors, thí dụ, #include <iostream> #include <windows.h> using namespace std; enum Colors { DARKBLUE = 1, DARKGREEN, DARKTEAL, DARKRED, DARKPINK, DARKYELLOW, GRAY, DARKGRAY, BLUE, GREEN, TEAL, RED, PINK, YELLOW, WHITE }; main() { Colors c; c = RED; cout << c; //---------------------------- cout << "\n T H E E N D."; return 0; } enum Colors { DARKBLUE = 1, DARKGREEN, DARKTEAL, DARKRED, DARKPINK, DARKYELLOW, GRAY, DARKGRAY, BLUE, GREEN, TEAL, RED, PINK, YELLOW, WHITE }; hiển thị Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 10 Có hai loại tổ chức dữ liệu dùng cho biểu diễn tập là danh sách tuyến tính và dãy bit (0/1). Biểu diễn tập bằng danh sách tuyến tính Mỗi phần tử của danh sách gồm hai trường data và ptr data 'a' ptr 1234 Trường data chứa giá trị của phần tử trong tập, trường ptr chứa con trỏ đến phần tử tiếp theo. Thí dụ, tập X = {'a', 'b', 'd''} sẽ được biểu diễn như sau: X → ('a')→('b')→('d')● Kí hiệu ● cho biết điểm kết thúc danh sách (với con trỏ NULL) Biểu diễn tập bằng dãy bit Dạng biểu diễn thứ hai đòi hỏi phải cho trước tập nền. Khi đó mỗi tập con của tập vũ trụ sẽ được biểu diễn bằng dãy bit 0/1.
Riêng tập nền được biểu diễn bằng một mảng động name, trong đó phần tử thứ i chính là tên của phần tử trong tập nền. Thí dụ, tập nền U gồm các mặt hàng trong một cửa hàng văn phòng phẩm có thể được biểu diễn như sau: index 1 2 3 4 5 6 Name Vở Bút Tẩy Cặp Balo Kẹp giấy Khi đó, mỗi lượt khách hàng mua văn phòng phẩm sẽ sinh ra một giao tác dưới dạng một vector bít 0/1, trong đó 1 cho biết khách mua loại hàng tương ứng, Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 11 0 không mua. Thí dụ dưới đây cho biết ba giao tác ứng với ba khách hàng X, Y và Z, index 1 2 3 4 5 6 Name Vở Bút Tẩy Cặp Balo Kẹp giấy X 1 0 1 1 0 0 Y 1 1 0 1 0 0 Z 0 1 1 1 0 1 Ta có X = {Vở, Tẩy, Cặp}, ứng với biểu diễn 101100 Y = {Vở, Bút, Cặp}, ứng với biểu diễn 110100 Z = {Bút, Tẩy, Cặp, Kẹp giấy}, ứng với biểu diễn 011101. Dạng biểu diễn này cho phép cài đặt các phép toán tập hợp nhanh chóng.
Khi cần hiển thị cụ thể chương trình sẽ tham chiếu đến các name của từng phần tử trong tập vũ trụ. Cho biết các mặt hàng cả ba người cùng mua? Giải M = X Y Z = 101100 and 110100 and 011101 = 000100 = {Cặp} Q2. Cho biết các mặt hàng X không mua? Giải K = X’ = U X = ~101100 = 010011 = {Bút, Balo, Kẹp giấy} trong đó ~ là phép toán lật bit, đổi bít 0 thành 1 và ngược lại. Cho biết các mặt hàng X và Y cùng không mua? Giải V = (X Y)’ = ~(101100 or 110100) = ~(111100) = 000011 = {Balo, Kẹp giấy} Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.