1-0Set.pptx

Toán rời rạc Tài liệu tham khảo chính Nguyễn Đức Nghĩa, Nguyễn Tô Thành TOÁN RỜI RẠC (in lần thứ ba) Nhà xuất bản Đại học Quốc gia Hà nội, 2003, 290 trang Tài liệu tham khảo 1. Rosen K.H. Discrete Mathematics and its Applications (8th Editions). McGraw - Hill Book Company, 2...

Toán rời rạc Tài liệu tham khảo chính Nguyễn Đức Nghĩa, Nguyễn Tô Thành TOÁN RỜI RẠC (in lần thứ ba) Nhà xuất bản Đại học Quốc gia Hà nội, 2003, 290 trang Tài liệu tham khảo 1. Rosen K.H. Discrete Mathematics and its Applications (8th Editions). McGraw - Hill Book Company, 2019. 2. Johnsonbaugh R. Discrete Mathematics. Prentice Hall Inc., N. J., 1997. 3. Grimaldi R.P. Discrete and Combinatorial Mathematics (an Applied Introduction), Addison-Wesley, 5th edition, 2004. 4. R. Graham, O. Patashnik, and D.E. Knuth. Concrete Mathematics, Second Edition. Addison-Wesley, 1994. Tài liệu tham khảo 5. Nguyễn Hữu Anh. Toán rời rạc, NXB Giáo dục,1999. 6. Nguyễn Xuân Quỳnh. Cơ sở Toán rời rạc và ứng dụng. NXB KHKT, Hà nội, 1996. 7. Đỗ Đức Giáo. Toán rời rạc. NXB KHKT, Hà nội, 2001. PHẦN 1: LÝ THUYẾT TỔ HỢP (Combinatorial Theory) PHẦN 2: LÝ THUYẾT ĐỒ THỊ (Graph Theory) 5  Nội dung phần 1 Chương 0. Mở đầu Chương 1. Bài toán đếm Chương 2. Bài toán tồn tại Chương 3. Bài toán liệt kê tổ hợp Chương 4. Bài toán tối ưu tổ hợp 6 Chương 0. Mở đầu 1. Tập hợp 2. Ánh xạ 7 1. Tập hợp 1.1. Các khái niệm cơ bản 1.2. Sơ đồ Venn 1.3. Các phép toán tập hợp 1.4. Các đẳng thức 8 1. Tập hợp 1.1. Các khái niệm cơ bản 1.2. Sơ đồ Venn 1.3. Các phép toán tập hợp 1.4. Các đẳng thức 9 1. Các khái niệm cơ bản Ta hiểu: Tập hợp như là sự tụ tập của các phần tử. Ta nói tập hợp chứa các phần tử của nó. Các tập hợp được ký hiệu bởi A-Z, các phần tử a-z Thông thường phải có một tập vũ trụ U mà tất cả các phần tử được xét trong nó. Tập U có thể được chỉ rõ hoặc được ngầm định. Các tập vũ trụ thường dùng R = tập số thực R+ : tập số thực dương N = tập số tự nhiên = 0,1, 2, 3,  Z = tập các số nguyên =  , -3, -2, -1, 0, 1, 2, 3,  Z+ tập các số nguyên không âm Q = {p/q : p, q Z và q ≠ 0} tập các số hữu tỉ C = {x + iy : x, y R và i2 = −1} tập các số phức. 10 Một số cách xác định tập hợp 1. Danh sách các phần tử: S = a, b, c, d = b, c, a, d, d  (Chú ý: Việc liệt kê lặp lại một phần tử không dẫn đến tập mới. Th ứ tự liệt kê là không có vai trò) 2. Mô tả cách xây dựng tập hợp bằng việc sử dụng mệnh đề lôgic: S = x | P(x) } S chứa các phần tử thoả mãn mệnh đề P. Ví dụ, S = { x x là sinh viên ĐHBK HN} đọc là “S là tập tất cả các phần tử x sao cho x là sinh viên ĐHBK HN.” 3. Liệt kê các phần tử: S = , -3, -2, -1 - tập các số nguyên âm. Chú ý: tập hợp có thể là phần tử của một tập hợp khác Ví dụ: S1 = { ,{a},{b},{a,b},c} S2={{1},{2,4,8},{3},{6},4,5,6} 11 So sánh hai tập hợp Tập A được gọi là tập con của tập B nếu mỗi phần tử của A đều là phần tử của B, nghĩa là  A x x [x B] Ký hiệu: A B hoặc B A Ví dụ 1: Nếu S = 1, 2, 3, , 11, 12 và T =  1, 2, 3, 6  Thế thì T S. Ví dụ 2: N ⊆ Z ⊆ Q ⊆ R ⊆ C. A A : một tập luôn là tập con của chính nó. Để chứng minh tập A là tập con của tập B, ta cần chỉ ra với một phần tử x bất kì, x A thì x cũng thuộc B. 12 So sánh hai tập hợp Nếu A B, nhưng A B khi đó ta nói A là tập con thực sự của B. Ký hiệu: A B. Ví dụ: Giả sử A = { 1, 2, 3 }, B = { 2, 3, 1 }, C = { 3 }. Khi đó: B = A, C A, C B. Để chứng minh A là tập con thực sự của B, ta cần chứng minh A là tập con của B và  x (xB) (xA) Tập rỗng (trống) là tập không có phần tử nào cả. Ký hiệu: . là tập con của mọi tập Tập tất cả các tập con (Power set) của tập A Ký hiệu: 2A (đôi khi dùng ký hiệu: P(A)) 13 Tập tất cả các tập con (Power Set) Định lý 1: Cho A là tập có lực lượng |A|=n, khi đó |P(A)| = 2n Định lý 2: Cho 2 tập A và B: 1. A B khi và chỉ khi P (A) P (B). 2. P (A) ∩ P (B) = P (A ∩ B). 3. P (A)  P (B) P (A B). So sánh hai tập hợp Hai tập là bằng nhau khi và chỉ khi mỗi phần tử của tập thứ nhất đều là phần tử của tập thứ hai và ngược lại, nghĩa là A = B khi và chỉ khi A B và B A Ví dụ: {2,3,5,7}={3,2,7,5}, vì tập hợp là tập không có thứ tự {2,3,5,7}={2,2,3,5,3,7} việc liệt kê lặp lại một phần tử không dẫn đến tập mới {2,3,5,7}  {2,3} A = {x: (x − 4)2 = 25} , B = {x: (x + 1)(x − 9) = 0}, hỏi A = B ? 15 Lực lượng của tập hợp Lực lượng (cardinality) của tập A là số phần tử trong A. Ký hiệu: |A| (đôi khi còn ký hiệu là #A, N(A)). Nếu lực lượng của một tập hợp là số tự nhiên thì nó được gọi là tập hữu hạn, nếu trái lại nó là tập vô hạn. Ví dụ: N (tập các số tự nhiên) là vô hạn, bởi vì |N| không là số tự nhiên. Z, Q, R là các tập vô hạn Chú ý: Nếu |A| = n thì |P(A)| = 2n. Ví dụ: || = 0 vì tập rỗng không chứa phần tử nào. |{π, 2, Newton}| = 3. Nếu Nn = {0, 1, …, n} thì | Nn | = n + 1. |{n: n là một số nguyên tố}| = ∞. 16 1. Tập hợp 1.1. Các khái niệm cơ bản 1.2. Sơ đồ Venn 1.3. Các phép toán tập hợp 1.4. Các đẳng thức 17 1.2. Sơ đồ VENN John Venn 1834-1923 Venn diagrams: Là cách biểu diễn rất trực quan giúp chỉ ra mối liên hệ giữa 2 hoặc 3 t ập hợp. Tập vũ trụ U được biểu diễn bởi hình chữ nhật. Mỗi tập con của U được biểu diễn bởi phần trong của một vòng kín. Ví dụ: Cho 2 tập Cho 3 tập 18 1.2. Sơ đồ Venn Ví dụ U A B Nếu A B: vùng biểu diễn A hoàn toàn nằm trong vùng biểu diễn B để đảm bảo rằng mọi phần tử thuộc vùng biểu diễn tập A cũng nằm trong vùng biểu diễn tập B 19 1.2. Sơ đồ Venn Ví dụ: Vẽ sơ đồ Venn biểu diễn 3 tập: A = {1, 2, …, 10}, B = {2, 4, 6, 8, 12, 13}, C = {2, 3, 5, 7, 11, 13} 20 1. Tập hợp 1.1. Các khái niệm cơ bản 1.2. Sơ đồ Venn 1.3. Các phép toán tập hợp 1.4. Các đẳng thức 21 1.3. Các phép toán tập hợp Hợp (union) của 2 tập A và B: là tập tất cả các phần tử hoặc thuộc A hoặc thuộc vào B. Ký hiệu: A B A B = x x A x B U B A Tổng quát: Hợp của n tập A1, A2,…,An: A1 A2 An ((…((A1 … A2 )  …)An) (ghép nhóm và thứ tự là không quan trọng) = 22 1.3. Các phép toán tập hợp Giao (intersection) của 2 tập A và B: là tập các phần tử vừa thuộc vào A vừa thuộc vào B. Ký hiệu: A B A B = x x A x B Nếu giao là tập rỗng, thì A và B được gọi là không giao nhau. Tổng quát: Giao của n tập A1, A2,…,An: A1 A2 …An ((…((A1 A2) …) An) (ghép nhóm và thứ tự là không quan trọng) Ai = A1 A2  …An ¿ { 𝒙 ∨𝒙 ∈ 𝑨𝒊 𝒗 ớ 𝒊 𝒎ọ 𝒊 𝒊=𝟏 ,𝟐 ,.. , 𝒏 } 23 1.3. Các phép toán tập hợp Hiệu (difference) của A và B: là tập hợp các phần tử của A không thuộc vào B. Ký hiệu: A – B hoặc A \ B A – B = x x A B x U A B 24 1.3. Các phép toán tập hợp Hiệu đối xứng (symmetric difference) của A và B: là tập (A – B) (B – A) Ký hiệu: A B U A B 25 1.3. Các phép toán tập hợp Phần bù (complement) của tập A: là tập U – A, trong đó U là tập vũ trụ. phần bù của A là phụ thuộc vào U ! Ký hiệu: = x  A)  (x Cách ký hiệu khác: Ac. U A A A − B = {x | x A và x B} = A ∩ Bc. 26 1.3. Các phép toán tập hợp René Descartes (1596-1650) Tích Đề-các (Cartesian product) của A với B: Là tập bao gồm tất cả các cặp có thứ tự (a, b), trong đó a thuộc A và b thuộc B. Ký hiệu: A  B. Theo định nghĩa A B =  (a, b)aA b B Ví dụ: Cho A = 1, 2, 3  và B = 3, 4 . Khi đó A B =  (1,3), (1,4), (2,3), (2,4), (3,3), (3,4)  B A =  (3,1), (3,2), (3,3), (4,1), (4,2), (4,3)  Thông thường A B  B A |A B| = ? 27 1. Tập hợp 1.1. Các khái niệm cơ bản 1.2. Sơ đồ Venn 1.3. Các phép toán tập hợp 1.4. Các đẳng thức 28 1.4. Các đẳng thức tập hợp Đẳng thức Tên gọi A = A Đồng nhất A U = A (Identity laws) A U = U Trội A =  (Domination laws) A A = A Lũy đẳng A A = A Idempotent laws Bù (Complementation laws) ( A)  A 1.4. Các đẳng thức tập hợp Đẳng thức Tên gọi A B = B A Giao hoán A B = B A Commutative laws A (B C) = (A B) C Kết hợp A (B C) = (A B) C Associative laws A (B C) = (A B) (A C) Phân phối A (B C) = (A B) (A C) Distributive laws A  B A  B Luật De Morgan De Morgan’s laws A  B A  B Phân hoạch Giả sử X1, X2,..., Xm là các tập con của X. Ta nói X1, X2,..., Xm tạo thành một phân hoạch của X (hoặc X được phân hoạch thành các tập X1, X2,..., Xm ) nếu: X = X1 X2 ... Xm ; , i Xi Xj =  j. Xi ≠  , i=1,..,m (Một phân hoạch của tập X là một tập các tập con khác rỗng không giao nhau của X và hợp của chúng là tập X) Ví dụ: X = {1, 2, 3, 4} E = {{1, 2}, {3, 4}} là một phân hoạch của tập X F = {{1, 2, 3}, {3, 4}} không là phân hoạch của tập X Chương 0. Mở đầu 1. Tập hợp 2. Ánh xạ 32 2. Ánh xạ 2.1 Định nghĩa 2.2. Cách xác định ánh xạ 2.3. Một số loại ánh xạ 2. Ánh xạ 2.1 Định nghĩa 2.2. Cách xác định ánh xạ 2.3. Một số loại ánh xạ 2.1. Định nghĩa ánh xạ Ta nói f là ánh xạ từ tập X vào tập Y nếu nó đặt tương ứng mỗi một phần tử x X với một phần tử y Y nào đó. Ký hiệu: f: X Y hoặc y = f(x) x gọi là gốc, y gọi là ảnh. Trong giáo trình giải tích chúng ta đã làm quen với hàm số thực f đặt tương ứng mỗi số thực x R với một giá trị thực y = f(x). 2. Ánh xạ 2.1 Định nghĩa 2.2. Cách xác định ánh xạ 2.3. Một số loại ánh xạ 2.2. Cách xác định ánh xạ Cho hai tập hữu hạn X và Y. Để xác định một ánh xạ f từ X vào Y (f: X Y) ta có thể sử dụng một trong các cách sau: Bảng giá trị đầy đủ Sơ đồ ánh xạ Ma trận ánh xạ Xác định ánh xạ: Bảng giá trị đầy đủ Giả sử X = {x1, x2,..., xm}, Y = {y1, y2,..., yn}, Một ánh xạ f từ X vào Y (f: X Y) có thể xác định bởi bảng giá trị đầy đủ sau đây x x1 x2... xm y=f(x) f(x1) f(x2)... f(xm) Như vậy mỗi ánh xạ từ tập m phần tử X vào tập n phần tử Y hoàn toàn xác định bởi bộ ảnh (f(x1), f(x2),..., f(xm)) Xác định ánh xạ: Sơ đồ ánh xạ Ánh xạ có thể xác định bởi sơ đồ như sau: f X Y f y x y x X Y S ơ đồ Đồ thị hàm số Xác định ánh xạ: Ma trận ánh xạ Giả sử X = {x1, x2,..., xm}, Y = {y1, y2,..., yn}, Một ánh xạ f từ X vào Y (f: XY) có thể xác định bởi ma trận Af = {aij} kích thước m n với các phần tử được xác định theo qui tắc sau đây: 1, nÕu yj lµ phÇn tö t­ ¬ng øng ví i xi qua ¸nh x¹ f aij  0, nÕu tr¸i l¹i  Ví dụ X = { Thắng, Mạnh, Hùng, Cường }; Y = { Mai, Mơ, Mận, Me, Muỗm } Xét ánh xạ f từ X vào Y xác định bởi bảng giá trị đầy đủ sau: x Thắng Mạnh Hùng Cường y=f(x) Mai Mai Mận Muỗm  Ánh xạ nói trên có thể cho bởi sơ đồ và ma trận như sau: Mai Mai M¬MËn Me Muçm Thắng  1 0 0 0 0  Thắng Mơ  Mạnh 1 0 0 0 0  Mạnh Mận Af   0 0 0 1 0  Hùng Hùng Me    0 0 0 0 1  Cường Cường Muỗm Toán rời rạc 2. Ánh xạ 2.1 Định nghĩa 2.2. Cách xác định ánh xạ 2.3. Một số loại ánh xạ 2.3. Một số loại ánh xạ hay dùng Giả sử X, Y là các tập hợp. Đơn ánh: Ánh xạ f : X Y được gọi là đơn ánh (injection hoặc one-to-one) nếu nó đặt tương ứng hai phần tử khác nhau của X với hai phần tử khác nhau của Y. x1, x2 X, x1 x2 f(x1) f(x2)  Ánh xạ f không phải là đơn ánh Ánh xạ g là đơn ánh 2.3. Một số loại ánh xạ hay dùng Giả sử X, Y là các tập hợp. Toàn ánh: Ánh xạ f từ X vào Y được gọi là toàn ánh (surjection hoặc onto) nếu mỗi phần tử của Y đều là ảnh của ít nhất một phần tử nào đó của X qua ánh xạ f.   yY,  xX: y = f(x). Ví dụ: A = {1, 2, 3, 4} và B = {x, y, z}. Ánh xạ: f1 = {(1, z), (2, y), (3, x), (4, y)} ; g={(1, x), (2, x), (3, y), (4, y)} 2.3. Một số loại ánh xạ hay dùng Giả sử X, Y là các tập hợp. Song ánh: Ánh xạ f từ X vào Y được gọi là song ánh (bijection), nếu nó vừa là đơn ánh vừa là toàn ánh.  Ứng dụng Xét bài toán: Đếm số phần tử của tập X. Giả sử Y là tập mà số phần tử của nó là đã biết:  ny = |Y|. Giả sử ta có thể xây dựng được ánh xạ f từ X vào Y. Khi đó Nếu f là đơn ánh, thì ta có |X| ny Nếu f là toàn ánh, thì ta có |X|  ny Nếu f là song ánh, thì ta có |X| = ny Trong tình huống thứ ba ta giải được bài toán đếm đặt ra, nhờ xây dựng được song ánh từ tập các cấu hình tổ hợp cần đếm (tập X) vào tập các cấu hình tổ hợp mà ta đã biết trước số phần tử (tập Y).