Toán học - Tập hợp

Tập hợpDate1Khá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ợpcá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 Aký hiệu x ∉ A để chỉ x không là một phần tử của tập hợp ADate2Biểu diễn một tập hợpLiệ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, ...} Date3Biểu diễn một tập hợpNê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: Date4Tập hợp rỗngTập hợp rỗng, ký hiệu bởi , là tập hợp không chứa phần tử nàoVí dụ:tập hợp A = {x ∈ R | x2 – 4x + 5 = 0} tập hợp B = {x ∈ Z | 2x – 1 = 0} Date5Tập hợp con và tập hợp bằng nhauA 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 hayDate6Tập hợp con và tập hợp bằng nhauA bằng B, Ký hiệu A = B Nếu A là tập hợp con của B và ngược lạiA = 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.Date7Tập hợp con và tập hợp bằng nhauX  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 ?Date8Tập hợp các tập hợp conCho 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}} Date9TẬ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}}.Date10CÁC TOÁN TỬ CỦA TẬP HỢPHộ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).Date11CÁC TOÁN TỬ CỦA TẬP HỢPBù : 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 AAΔB = {x ∈ X | (x ∈ A và x ∉ B) hay (x ∈ A và x ∉ B) } Date12TÍNH CHẤT CủA CÁC PHÉP TOÁNDate13TÍNH CHẤT CủA CÁC PHÉP TOÁNDate14TÍ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 Date15TÍ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} Date16Tích Descartes của nhiều tập hợpCho 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 xAn viết là AnDate17Á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 xHai á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)Date18Cá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 Xmộ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  Xf : 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.Date19Ảnh của tập hợpCho f là một ánh xạ từ X vào YGiả 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 } Date20Ảnh ngược (hay tạo ảnh) của một tập hợpCho f là một ánh xạ từ X vào YGiả 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).Date21Cho ánh xạ f : Z  N xác định bởi f(n) = n2+1A = { -2, -1, 0, 1, 2, 3}B = { 0, 1, 2, 3, 4, 5}f(A) = { 1, 5, 10} f-1(B) = { -1, 0, 1} Date22Ánh xạ hợpCho 2 ánh xạf : X  Yg : 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.Date23Đơ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 nhauvới mọi x và x' thuộc X ta có: x  x'  f(x)  f(x')Hay f(x) = f(x')  x = x'Date24Toà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) = YDate25Song á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) = yphé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) = yDate26Á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+1Cho 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+bDate27Á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);Date28Vớ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)là một phương trình bậc hai có Δ' = y – 1. Do đóVới y 1, (1) có hai nghiệm Date29f1 không là đơn ánh và cũng không là toàn ánh. Suy ra f1 cũng không là song ánh.f2 là đơn ánh nhưng không là toàn ánh. Suy ra f2 không là song ánhf3 là toàn ánh nhưng không là đơn ánh. Suy ra f3 không là song ánhf4 một song ánh và do đó f4 vừa là đơn ánh vừa là toàn ánh. Hơn nữa, f4-1 :[1,+∞) → [2, +∞) định bởi: Date30Một số tính chất 1Cho 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ó:Thử với f: R  R x | x2X = R, Y = RA = [-9,9] B = [4,16]C = [1,9] D = [4, 25]Date31Một số tính chất 2Cho 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 = ff-1 o f = IdXf o f-1 = IdYvới IdX (tương ứng IdY) là ánh xạ đồng nhất của tập X (tương ứng Y).Date32Một số tính chất 3Cho 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 ánhNếu f và g đều là toàn ánh thì h cũng là toàn ánhNế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-1Date33Phép đếmCho 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 ATập hợp rỗng có số phần tử là 0, và cũng được xem là tập hữu hạnSố 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 | = Date34Nguyên lý cộngCho 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 |Date35Nguyên lý cộngGiả 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.Date36Nguyên lý cộngVí 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ư Date37Nguyên lý nhânCho 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 |Date38Nguyên lý nhânGiả 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 n2Date39Nguyên lý nhânGiả sử một thủ tục bao gồm m công việc kế tiếp nhau T1, T2, . . ., TmNếu công việc T1 có thể được thực hiện theo n1 cáchsau khi chọn cách thực hiện cho T1 ta có n2 cách thực hiện T2khi 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 TmVậy ta có n1.n2. ... .nm cách để thực hiện thủ tụcDate40Nguyên lý nhânCá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êuDate41Ví 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 Date42Ví dụCho S = {0, 1, 2, 3, 4, 5, 6}. 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ẻ?Trong các số ở câu a), có bao nhiêu số chứa chữ số 2? Date43Cá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. Date44Để 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ẵnTrường hợp 2: a lẻDate45Trường hợp 1: a chẵnChọn a ∈ {2, 4, 6}. Số cách: 3Chọ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: 3Chọ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 Date46Trường hợp 2: a lẻChọn a ∈ {1, 3, 5}. Số cách: 3Chọ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: 6Chọ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: 2Chọ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. Date47Như vậy, theo nguyên lý cộng ta có số các số x theo yêu cầu là: 216 + 432 = 648b) 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à: 312Date48Chỉnh hợpCho 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.Date49Ví 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 2Sự 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 3Date50Chỉnh hợpMộ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 đóDate51Công thức chỉnh hợpSố 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 Date52Tổ hợpCho 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. NNó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ửDate53Tổ hợpSố 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) = 1m, n, và r là các số nguyên không âm r nhỏ hơn hoặc bằng m và nDate54Công thức nhị thức NewtonVới x, y ∈ R và n là số nguyên dương ta có:Date55Chỉnh hợp lặpMộ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ử đã choSố chỉnh hợp chập k của n phần tử là nkCá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) Date56Hoán vị lặpSố 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à:Date57Tổ hợp lặpMộ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ử đã choGọi là số tổ hợp lặp chập k của n lọai phần tửDate58Hệ quả tổ hợp lặpSố 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àDate59Ví dụTìm số nghiệm nguyên không âm của phương trình: x1+ x2 + x3 + x4 = 8 Date60Nguyên lý dirichletGiả 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/kDate61Tóm lạiKhá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.Date62Câu hỏiCá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. Date63