Bài giảng môn Toán rời rạc - Chương 3: Tập hợp

Nội dung text: Bài giảng môn Toán rời rạc - Chương 3: Tập hợp

1. Tập hợp * 1 of 63
2. Khái niệm • Định nghĩa: Một tập hợp là một bộ sưu tập các vật mà ta còn gọi là các phần tử của tập hợp đó • Ký hiệu: – các chữ in: A, B, C, , X, Y, Z, để chỉ các tập hợp – các chữ nhỏ: a, b, c, , x, y, z, để chỉ các phần tử – ký hiệu x ∈ A để chỉ x là một phần tử của tập hợp A – ký hiệu x ∉ A để chỉ x không là một phần tử của tập hợp A * 2 of 63
3. Biểu diễn một tập hợp • Liệt kê – Các phần tử được chọn tùy ý giữa hai dấu {}. – không có 2 phần tử trùng nhau. – Các phần tử không có trật tự. • Ví dụ: – A = {1, 2, 3, 4} – N = {0, 1, 2, 3, } – Z = {0, ±1, ±2, } * 3 of 63
4. Biểu diễn một tập hợp • Nêu tính chất đặc trưng: Tập hợp sẽ được mô tả như là một bộ sưu tập gồm tất cả các phần tử x thỏa mãn tính chất đặc trưng p(x): • Ví dụ: – Tập hợp A = {x ∈ R | x2 – 4x + 3 = 0} chính là tập hợp A = {1, 3} – Tập hợp các số hữu tỉ được mô tả như sau: * 4 of 63
5. Tập hợp rỗng • Tập hợp rỗng, ký hiệu bởi , là tập hợp không chứa phần tử nào • Ví dụ: – tập hợp A = {x ∈ R | x2 – 4x + 5 = 0} – tập hợp B = {x ∈ Z | 2x – 1 = 0} * 5 of 63
6. Tập hợp con và tập hợp bằng nhau • A là tập hợp con của B, – Ký hiệu A ⊂ B hay B ⊃ A – Nếu mọi phần tử của A đều là các phần tử của B: – A ⊂ B ⇔ ∀x ∈ A, x ∈ B. • A không chứa trong B: AB hay * 6 of 63
7. Tập hợp con và tập hợp bằng nhau • A bằng B, – Ký hiệu A = B – Nếu A là tập hợp con của B và ngược lại – A = B ⇔ (A ⊂ B) và (B ⊂ A). ⇔ (∀x ∈ A, x ∈ B) và (∀x ∈ B, x ∈ A). • Ký hiệu A ≠ B để chỉ A không bằng B. * 7 of 63
8. Tập hợp con và tập hợp bằng nhau • X  Y (x)( x X x Y). • Ví dụ: – A = {x ∈ R | x2 – 4x + 3 = 0} – B = {x ∈ R | x(x –1)(x – 3) = 0} – C = {0; 1; 2}, D = {0; 1; 2; 3} A ⊂ B, B ≠ C, C ⊂ D ? B ⊄ A, D ⊄ C ? * 8 of 63
9. Tập hợp các tập hợp con • Cho tập hợp X. Tập hợp tất cả các tập hợp con của X được ký hiệu là P(X). P(X) = {A | A ⊂ X} • Nếu tập hợp X có đúng n phần tử thì tập hợp tất cả các tập hợp con P(X) của X sẽ có đúng 2n phần tử • Ví dụ: cho X= {a,b,c} P(X) = {∅; {a}; {b}; {c}; {a, b}; {b, c}; {a, c}; {a, b, c}} * 9 of 63
10. TẬP CÁC TẬP CON Tìm tập tất cả tập con của X = {a, b, c} ?. Tập con 0 phần tử : . Tập con 1 phần tử : a {a}, b {b}, c {c}. Tập con 2 phần tử : a, b {a, b}, a, c {a, c}, b, c {b, c}. Tập con 3 phần tử : a, b, c {a, b, c}. Vậy 2X = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. 1/9/2024 10 of 63
11. CÁC TOÁN TỬ CỦA TẬP HỢP Hội : (  ) A  B  (x)( x A hay x B). Giao : (  ) A  B  (x)( x A và x B). Hiệu :( ) A B  (x)( x A và x B). 1/9/2024 11 of 63
12. CÁC TOÁN TỬ CỦA TẬP HỢP Bù : Với A là một tập con của X, phần bù của A trong X, ký hiệu bởi hay CX(A) (đọc là “phần bù của A (trong X)”) là tập hợp X \ A Phép hiệu đối xứng: A ΔB là tập hợp tất cả các phần tử (của X) thuộc A nhưng không thuộc B hay thuộc B nhưng không thuộc A AΔB = {x ∈ X | (x ∈ A và x ∉ B) hay (x ∈ A và x ∉ B) } 1/9/2024 12 of 63
13. TÍNH CHẤT CủA CÁC PHÉP TOÁN * 13 of 63
14. TÍNH CHẤT CủA CÁC PHÉP TOÁN * 14 of 63
15. TÍCH DESCARTES • Cho hai tập hợp A và B. • Tích Descartes của A và B là tập hợp tất cả các cặp (x, y) có thứ tự x trước, y sau, trong đó x thuộc A và y thuộc B. • Ký hiệu: A × B A × B = {(x, y) | x ∈ A và y ∈ B} (x, y) ∈ A × B ⇔ x ∈ A và y ∈ B (x, y) ∉ A × B ⇔ x ∉ A hay y ∉ B * 15 of 63
16. TÍCH DESCARTES • Ví dụ: Cho A = {a, b} và B = {1, 2, 3} – A × B = {(a, 1); (a, 2); (a, 3); (b, 1); (b, 2); (b, 3)} – B × A = {(1, a); (1, b); (2, a); (2, b); (3, a); (3, b)} • Ký hiệu A2 để chỉ tích Descartes A × A A2 = {(x, y) | x ∈ A và y ∈ A} * 16 of 63
17. 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. • A1 = A2 = . . . = An = A thì tập hợp tích A1xA2x n xAn viết là A * 17 of 63
18. Ánh xạ • Cho X và Y là các tập hợp khác rỗng. • Một ánh xạ f từ tập hợp X vào tập hợp Y là phép tương ứng sao cho bởi phép tương ứng nầy mỗi phần tử x của X sẽ có một phần tử duy nhất y của Y tương ứng mà ta ký hiệu là f(x) và gọi là ảnh của x • Hai ánh xạ f và g từ X vào Y được gọi là bằng nhau khi ta có: x X : f(x) = g(x) * 18 of 63
19. Cách xác định một ánh xạ • liệt kê tất cả các ảnh của từng phần tử của X • một công thức để xác định ảnh f(x) của mỗi phần tử x • đưa ra một thủ tục xác định để tính ra (hay tìm ra) được phần tử f(x) ứng với mỗi phần tử x X – f : N N xác định bởi f(n) = 2(n+1). – g : { 0,1} 2 { 0,1} cho bởi g(0,0) = g(0,1) = 1 và g(1,0) = g(1,1) = 0. * 19 of 63
20. Ảnh của tập hợp • Cho f là một ánh xạ từ X vào Y • Giả sử A là một tập hợp con của X • Ảnh của tập A qua ánh xạ f, ký hiệu bởi f(A), là tập hợp con của Y gồm tất cả những phần tử y sao cho y là ảnh của ít nhất một phần tử x thuộc A. f(A) = { f(a) : a A } * 20 of 63
21. Ảnh ngược (hay tạo ảnh) của một tập hợp • Cho f là một ánh xạ từ X vào Y • Giả sử B là một tập hợp con của Y • Ảnh ngược của tập B bởi ánh xạ f, ký hiểu là f-1(B), là tập hợp con của X gồm tất cả những phần tử x sao cho f(x) thuộc B f-1(B) = { x X : f(x) B } • Trong trường hợp tập B chỉ có một phần tử y thì ảnh ngược của B sẽ được viết tắt là f-1(y). * 21 of 63
22. • Cho ánh xạ f : Z N xác định bởi f(n) = n2+1 • A = { -2, -1, 0, 1, 2, 3} • B = { 0, 1, 2, 3, 4, 5} f(A) = { 1, 5, 10} f-1(B) = { -1, 0, 1} * 22 of 63
23. Ánh xạ hợp • Cho 2 ánh xạ – f : X Y – g : Y Z • Ánh xạ hợp h của f và g là ánh xạ từ X vào Z xác định bởi: • Ta viết h = g o f. * 23 of 63
24. Đơn ánh • Ánh xạ f : X Y được gọi là một đơn ánh khi các ảnh của 2 phần tử khác nhau tùy ý thì khác nhau • với mọi x và x' thuộc X ta có: – x x' f(x) f(x') – Hay f(x) = f(x') x = x' * 24 of 63
25. Toàn ánh • Ánh xạ f : X Y được gọi là một toàn ánh khi mọi phần tử của Y đều là ảnh của ít nhất một phần tử x thuộc X, nghĩa là f(X) = Y * 25 of 63
26. Song ánh • Ánh xạ f : X Y được gọi là một song ánh khi nó vừa là đơn ánh vừa là toàn ánh. • Khi ấy với mỗi y Y, có duy nhất phần tử x X sao cho f(x) = y • phép tương ứng liên kết y với x sẽ cho ta một ánh xạ từ Y vào X. Ta gọi ánh xạ nầy là ánh xạ ngược của f và ký hiệu là f-1 f-1 : Y X, xác định bởi f-1(y) = x, với f(x) = y * 26 of 63
27. Ánh xạ gì? • Ánh xạ f : Z N xác định bởi f(n) = n2+1 • Ánh xạ f : N N xác định bởi f(n) = n2+1 • Cho a và b là 2 số thực tùy ý và a 0. Ánh xạ f : R R xác định bởi f(x) = a.x+b * 27 of 63
28. Ánh xạ gì? • Cho P(x) = x2 – 4x + 5 và các ánh xạ – f1 : R → R định bởi f1(x) = P(x); – f2 : [2, +∞) → R định bởi f2(x) = P(x); – f3 : R → [1, +∞) định bởi f3(x) = P(x); – f4 : [2, +∞) → [1, +∞) định bởi f4(x) = P(x); * 28 of 63
29. • Với mỗi y ∈ R, xét phương trình P(x) = y, ta có: P(x) = y ⇔ x2 – 4x + 5 = y; ⇔ x2 – 4x + 5 – y = 0 (1) (1) là một phương trình bậc hai có Δ' = y – 1. Do đó a) Với y 1, (1) có hai nghiệm * 29 of 63
30. 1) f1 không là đơn ánh và cũng không là toàn ánh. Suy ra f1 cũng không là song ánh. 2) f2 là đơn ánh nhưng không là toàn ánh. Suy ra f2 không là song ánh 3) f3 là toàn ánh nhưng không là đơn ánh. Suy ra f3 không là song ánh 4) f4 một song ánh và do đó f4 vừa là đơn ánh vừa là toàn ánh. -1 Hơn nữa, f4 :[1,+∞) → [2, +∞) định bởi: * 30 of 63
31. Một số tính chất 1 • Cho f : X Y. Giả sử A, B là các tập con của X và C, D là các tập con của Y. Khi đó ta có: X = R, Y = R Thử với f: R R A = [-9,9] B = [4,16] x | x2 C = [1,9] D = [4, 25] * 31 of 63
32. Một số tính chất 2 • Cho f : X Y là một song ánh. Khi đó ánh xạ ngược f-1: Y X cũng là một song ánh và ta có: – (f-1) -1 = f -1 – f o f = IdX -1 – f o f = IdY với IdX (tương ứng IdY) là ánh xạ đồng nhất của tập X (tương ứng Y). * 32 of 63
33. Một số tính chất 3 • Cho các ánh xạ f : X Y, g : Y Z. Đặt h = g o f. Ta có – Nếu f và g đều là đơn ánh thì h cũng là đơn ánh – Nếu f và g đều là toàn ánh thì h cũng là toàn ánh – Nếu f và g đều là song ánh thì h cũng là song ánh. Hơn nữa: h-1 = f-1 o g-1 * 33 of 63
34. Phép đếm • 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ử. • Song ánh : A { 1, 2, . . ., n} 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 |. • 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 | = * 34 of 63
35. Nguyên lý cộng • 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 | • 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 | * 35 of 63
36. 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, • Đố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. * 36 of 63
37. Nguyên lý cộng • Ví dụ 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ư * 37 of 63
38. Nguyên lý nhân • 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 | • 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 | * 38 of 63
39. 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 * 39 of 63
40. Nguyên lý nhân • 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 • sau khi chọn cách thực hiện cho T1 ta có n2 cách thực hiện T2 • • 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 * 40 of 63
41. Nguyên lý nhân • Các ghế ngồi trong một hội trường sẽ được ghi nhãn gồm một ký tự (A-Z) 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 * 41 of 63
42. Ví dụ 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 * 42 of 63
43. Ví dụ • Cho S = {0, 1, 2, 3, 4, 5, 6}. a) Có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau từng đôi một được lấy từ S, trong đó có hai chữ số chẵn và ba chữ số lẻ? b) Trong các số ở câu a), có bao nhiêu số chứa chữ số 2? * 43 of 63
44. • Các số x gồm 5 chữ số khác nhau từng đôi một được lấy từ S có dạng: • trong đó a, b, c, d, e ∈ S khác nhau từng đôi, a ≠ 0. * 44 of 63
45. • Để xét các số x như trên có hai chữ số chẵn và ba chữ số lẻ, ta chia hai trường hợp loại trừ lẫn nhau: – Trường hợp 1: a chẵn – Trường hợp 2: a lẻ * 45 of 63
46. Trường hợp 1: a chẵn • Chọn a ∈ {2, 4, 6}. Số cách: 3 • Chọn một ký tự trong {b, c, d, e} (để gán thêm một chữ số chẵn). Số cách: 4. • Chọn thêm một chữ số chẵn trong S\{a} để gán vào ký tự đã chọn. Số cách: 3 • Chọn (có thứ tự) ba chữ số lẻ trong S để gán vào ba ký tự còn lại. Số cách: 6. • Theo nguyên lý nhân, số các số x trong trường hợp này là: 3.4.3.6 = 216 * 46 of 63
47. Trường hợp 2: a lẻ • Chọn a ∈ {1, 3, 5}. Số cách: 3 • Chọn (không kể thứ tự) hai ký tự trong {b,c,d,e} (để gán thêm hai chữ số lẻ). Số cách: 6 • Chọn thêm (có thứ tự) hai chữ số lẻ trong S\{a} để gán vào hai ký tự đã chọn. Số cách: 2 • Chọn (có thứ tự) hai chữ số chẵn trong S để gán vào hai ký tự còn lại. Số cách: 12. • Theo nguyên lý nhân, số các số x trong trường hợp này là: 3.6.2.12 = 432. * 47 of 63
48. • Như vậy, theo nguyên lý cộng ta có số các số x theo yêu cầu là: 216 + 432 = 648 b) Lý luận tương tự như trên nhưng S được thay bằng S’ = {0, 1, 3, 4, 5, 6} ta có số các số x trong câu a) không chứa chữ số 2 là: 312 * 48 of 63
49. Chỉnh hợp • Cho X là một tập hợp gồm n phần tử, và r là một số nguyên dương nhỏ hơn hoặc bằng n. • Mỗi phép chọn r phần tử phân biệt của X theo một thứ tự nào đó sẽ cho ta một chỉnh hợp n chọn r. • Nói cách khác, ta có thể xem một chỉnh hợp như là một dãy hay một bộ gồm r phần tử phân biệt được chọn từ n phần tử cho trước. * 49 of 63
50. Ví dụ • Cho tập hợp S = { 1, 2, 3} • Dãy gồm 2 phần tử 3, 2 là một chỉnh hợp 3 chọn 2 • Sự sắp xếp các phần tử thành dãy 3, 1, 2 cho ta một chỉnh hợp 3 chọn 3 * 50 of 63
51. Chỉnh hợp • Một chỉnh hợp n chọn n được gọi là một hoán vị của n phần tử • Một hoán vị n phần tử là một cách sắp xếp n phần tử theo một thứ tự nào đó * 51 of 63
52. Công thức chỉnh hợp • Số các chỉnh hợp n chọn r là: Số trường hợp lấy 4 người của một lớp gồm 10 người vào 4 vị trí (có thứ tự) đại diện cho lớp * 52 of 63
53. Tổ hợp • Cho X là một tập hợp gồm n phần tử, và r là một số nguyên không âm nhỏ hơn hoặc bằng n. • Mỗi phép chọn r phần tử phân biệt của X mà không phân biệt thứ tự trước sau sẽ cho ta một tổ hợp n chọn r. N • Nói cách khác, ta có thể xem một tổ hợp n chọn r như là một tập hợp con gồm r phần tử của một tập hợp có n phần tử * 53 of 63
54. Tổ hợp Số các tổ hợp n chọn r , với n và r là các số nguyên thỏa 0 ≤ r ≤ n, là • C(n,r) = C(n,n-r) (r<n, n,r là số nguyên không âm) • C(n, k) = C(n-1, k) + C(n-1, k-1) (0 < k < n) • C(n, 0) = 1 C(n, n) = 1 m, n, và r là các số nguyên không âm * r nhỏ hơn hoặc bằng m và n54 of 63
55. Công thức nhị thức Newton • Với x, y ∈ R và n là số nguyên dương ta có: * 55 of 63
56. Chỉnh hợp lặp • Một chỉnh hợp lặp chập k của n phần tử là một bộ có thứ tự gồm k phần tử (không nhất thiết phân biệt) được rút ra từ n phần tử đã cho • Số chỉnh hợp chập k của n phần tử là nk • Các chỉnh hợp chập 2 của 3 phần tử x, y, z là (x,x); (x,y); (x,z); (y,x); (y,y); (y,z); (z,x); (z,y); (z,z) * 56 of 63
57. Hoán vị lặp • Số hoán vị của n phần tử, trong đó có n1 phần tử giống nhau thuộc loại 1, n2 phần tử giống nhau thuộc loại 2, , nk phần tử giống nhau thuộc loại k, là: * 57 of 63
58. Tổ hợp lặp • Một tổ hợp lặp chập k của n loại phần tử (không nhất thiết phải có k ≤ n) là một nhóm không có thứ tự gồm k phần tử phân biệt (có thể cùng loại) thuộc n loại phần tử đã cho • Gọi là số tổ hợp lặp chập k của n lọai phần tử * 58 of 63
59. Hệ quả tổ hợp lặp • Số nghiệm nguyên không âm (x1,x2, ,xn) (mỗi xi đều nguyên không âm) của phương trình x1+ x2+ + xn = k là: • Số cách xếp k vật giống nhau vào n hộp khác nhau là * 59 of 63
60. Ví dụ • Tìm số nghiệm nguyên không âm của phương trình: x1+ x2 + x3 + x4 = 8 * 60 of 63
61. Nguyên lý dirichlet • Giả sử có n vật cần đặt vào k hộp. Khi đó tồn tại ít nhất một hộp chứa từ ⎡ n/k ⎤ vật trở lên. • ⎡ n/k ⎤ số nguyên nhỏ nhất lớn hơn hay bằng n/k * 61 of 63
62. Tóm lại • Khái niệm về tập hợp, ánh xạ. • Tổ hợp (không lăp, không thứ tự), chỉnh hợp (không lặp, có thứ tự), hoán vị. • Nguyên lý cộng, nhân và Dirichlet. * 62 of 63
63. Câu hỏi • Các tính chất của các phép toán trên tập hợp. • Các loại ánh xạ và cho ví dụ. • Có bao nhiêu tập con có 2 phần tử của một tập hợp {a,b,c,d,e,f} • Có bao nhiêu cách chọn 2 trong số 22 giảng viên tin học đi dạy ở Bình Phước. • Có bao nhiêu cách chọn 2 (1 dạy lý thuyết, 1 dạy thực hành) trong số 22 giảng viên tin học đi dạy ở Bình Phước. * 63 of 63