Chương II Phép đếm

Chương II: Phép Đếm. * TẬP HỢP Định nghĩa tập hợp: Các tập hợp dùng để nhóm các đối tượng lại với nhau. Thông thường, các đối tượng trong tập hợp có các tính chất tương tự nhau. Chú ý: thuật ngữ đối tượng được dùng ở đây không chỉ rõ cụ thể một đối tượng nào, sự mô tả một tập hợp nào đó hoàn toàn mang tính trực giác về các đối tượng. Chương II: Phép Đếm. * TẬP HỢP Các đối tượng trong một tập hợp được gọi là các phần tử của tập hợp. Kí hiệu: Các tập hợp thường được ký hiệu bởi những chữ cái in hoa đậm như A, B, X, Y ... , các phần tử thuộc tập hợp hay được ký hiệu bởi các chữ cái in thường như a, b, c, l, g, t... Ví dụ: Tập MAT04 gồm các sinh viên trong lớp toán rời rạc. Tập A = {a,b,c}. Tập các số tự nhiên N. Tập B = {1, xe hơi, Binladen, mây}. Chương II: Phép Đếm. * Để chỉ a là phần tử của tập hợp A ta viết a ∈ A, trái lại nếu a không thuộc A ta viết a ∉A. Một tập hợp không có bất kì phần tử nào được gọi là tập hợp rỗng, kí hiệu là , hay {}. TẬP HỢP Chương II: Phép Đếm. * TẬP HỢP Tập Hợp Con Định nghĩa: Tập A được gọi là một tập con của tập hợp B khi và chỉ khi mỗi phần tử của A là một phần tử của B. Hay A ⊆ B khi và chỉ khi lượng từ : ∀ x ((x∈ A) → (x ∈ B)) cho ta giá trị đúng. Khi đó, ta kí hiệu : A ⊆ B. Nếu A là tập con của tập B và tồn tại ít nhất 1 phần tử b thuộc B mà b không thuộc A thì khi đó A được gọi là tập con thật sự của B. Kí hiệu là A⊂ B. Chương II: Phép Đếm. * TẬP HỢP Ví dụ: Tập MAT04 gồm các sinh viên trong lớp toán rời rạc là tập con của tập UIT là tập gồm các sinh viên trong trường. S = {a,b} là tập con của tập P = {a,b,c,l,g,t}. Tập số hữu tỉ Q là tập con của số thực R. Chương II: Phép Đếm. * TẬP HỢP Tập Hợp Bằng Nhau Định nghĩa: A và B được xem là 2 tập hợp bằng nhau nếu mỗi phần tử của A đều thuộc B và ngược lại. Hay mệnh đề : ∀ x (x∈ A → x∈ B ) ∨ ∀ x ( x ∈ B → x ∈ A) cho ta giá trị đúng. Khi đó, ta kí hiệu : A = B. Ví dụ: Tập A = {a,b,c} bằng tập B = {a,b,c} (hay A=B). Tập hợp các quốc gia tham dự Seagames 26 bằng tập hợp các quốc gia thuộc khu vực Đông Nam Á. Chương II: Phép Đếm. * TẬP HỢP Chương II: Phép Đếm. * Tập các tập con của một tập hợp Định nghĩa: Tập các tập con của tập hợp A được kí hiệu là P(A), tức là: P(A) = {B | B  A} Ví dụ: P(A = {a, b, c}) = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. P() = {}. P(P()) = {, {}}. TẬP HỢP Tính Chất : Tập rỗng là tập con của A và A cũng là tập con của A với mọi tập A. Tập A là con của tập B và tập B là con của tập A thì suy ra A = B. Tập A là con của tập B và tập B là con của tập C thì suy ra A là con C. Tập A là con của tập B thì P(A) là con của P(B). Nếu A có n phần tử thì P(A) có 2n phần tử. Chương II: Phép Đếm. * BIỂU DIỄN TẬP HỢP Chương II: Phép Đếm. * Các cách biểu diễn tập hợp: Xác định bằng lời: Tập hợp A gồm các giáo viên trong trường UIT. Tập hợp B gồm 4 số nguyên tố đầu tiên. Liệt kê các phần tử trong cập dấu {} Tập hợp C = {4, 2, 1, 3}. Tập hợp D = {đỏ, trắng, xanh}. Với các tập có nhiều phần tử có thể chỉ liệt kê một số phần tử. E = {1, 2, 3, …, 1000}. Nêu đặc trưng của các phần tử: F = {x | x  Z  “x chia hết cho 2”}. BIỂU DIỄN TẬP HỢP Chương II: Phép Đếm. * Các cách biểu diễn tập hợp: Biểu diễn dưới dạng ảnh của một tập hợp khác: A = { f(x) | (x  A’) }. Với f là một ánh xạ f : A’ -> A. VD: G = {x2 | x  Z và -10 5}. C-D = {0, 2, 4} Hiệu của tập các quốc gia Đông Nam Á và tập các quốc gia WTO là tập {Lào, Đông-Timo} CÁC PHÉP TOÁN VÀ TÍNH CHẤT 4. Phần bù: Định nghĩa: Phần bù của tập A kí hiệu là Ā là tập các phần tử x không thuộc A. Công thức: Ā = {x | x ∉ A}. Ví dụ: Cho A={a, b, c, x, y, z}. Phần bù của A là Ā = {d, e, f, g, h, i, k, l, m, n, o, p, q, r, s, t, u, v, w, }. (với tập vũ trụ là tập các chữ cái tiếng Anh) Phần bù của tập các số âm là tập các số dương và số 0. (với tập vũ trụ là tập các số thực) Chương II: Phép Đếm. * CÁC PHÉP TOÁN VÀ TÍNH CHẤT Tính chất của các phép toán trên tập hợp Chương II: Phép Đếm. * CÁC PHÉP TOÁN VÀ TÍNH CHẤT Tính chất của các phép toán trên tập hợp Chương II: Phép Đếm. * Tích Descartes Tích Descartes của 2 tập hợp: Định nghĩa: Cho 2 tập hợp A và B tích Descartes của 2 tập hợp A và B ký hiệu là A x B. Là tất cả các cặp (a, b) sao cho a thuộc A và b thuộc B. Công thức: A x B = {(a, b) | a  A  b  B} Trong trường hợp tập A bằng tập B thì ta ký hiệu : A x B = A x A=A2. Chương II: Phép Đếm. * Tích Descartes Tích Descartes của nhiều tập hợp: Định nghĩa: 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 A1 x A2 x … x An . Là tập gồm tất cả các bộ phần tử (a1, a2, …, an) với ai thuộc Ai với mọi i từ 1 đến n. Công thức : A1 x A2 x … x An = {(a1, a2, …, an) | ai  Ai, i = }. Trong trường hợp: A1 = A2 = … = An = A thì tập hợp tích A1 x A2 x … x An = A x A x … x A = An. Chương II: Phép Đếm. * Tích Descartes Tính chất: Với A , B là tập hữu hạn. |A x B| = |A| x |B| . Tương tự, với A1, A2, … , An là các tập hữu hạn thì : |A1 x A2 x … x An| = |A1| x |A2| x … x |An|. |An| = |A|n. Chương II: Phép Đếm. * CÁC NGUYÊN LÝ ĐẾM Chương II: Phép Đếm. * Nguyên lý cộng. Nguyên lý nhân. Nguyên lý chuồng bồ câu. Chương II: Phép Đếm. * Cơ sở tập hợp: Cho A và B là 2 tập hữu hạn sao cho A∩B =  khi đó |A  B| = |A|+|B|. Tổng quát: Nếu A1, A2, …, An là các tập hữu hạn nhau tức là giao của 2 tập hợp rời bất kỳ trong n tập hợp đó thì đều bằng  thì ta có: |A1  A2  …  An| = |A1| + |A2| + … + |An| NGUYÊN LÝ CỘNG Cở sở tập hợp: Ví dụ: Lớp học có 10 sinh viên nam và 5 sinh viên nữ. Khi đó lớp học có bao nhiêu sinh viên ? Giải: Gọi A là tập hợp các sinh viên nam trong lớp. B là tập hợp các sinh viên nữ trong lớp. Khi đó, tập hợp các sinh viên trong lớp X = A  B, do đó số sinh viên trong lớp là: |X| = |A  B| = |A| + |B| = 15. (vì A và B là tập rời nhau). Chương II: Phép Đếm. * NGUYÊN LÝ CỘNG Nguyên lý cộng: Định nghĩa : Giả sử ta phải thực hiện 1 công việc và để thực hiện công việc này ta có thể chọn 1 trong 2 biện pháp khác nhau theo nghĩa: cách thực hiện biện pháp thứ 1 luôn khác cách thực hiện biện pháp thứ 2 và biện pháp thứ 1 cách thực hiện có n, và biện pháp thứ 2 có m cách thực hiện. Vậy ta có n + m cách thực hiện công việc. Mở rộng: Giả sử ta thực hiện 1 công việc có n biện pháp khác nhau là A1, A2, … , An các biện pháp này đôi 1 khác nhau. Để thực hiện biện pháp Ai có ni cách vậy số cách thực hiện công việc trên là: n1 + n2 + … + ni cách. Chương II: Phép Đếm. * NGUYÊN LÝ CỘNG Nguyên lý cộng: Ví dụ: An có 2 cách để đi đến trường là đi bộ và đi xe buýt. Nếu đi bộ thì có 3 con đường để An đến trường. Nếu đi xe buýt thì có 8 chuyến xe buýt đi từ nhà An đến trường. Khi đó, An có 8 + 3 = 11 cách để đi đến trường. Chương II: Phép Đếm. * NGUYÊN LÝ NHÂN Cơ sở tập hợp: Cho 2 tập A và B hữu hạn khi đó, ta có: |A x B| = |A|.|B|. Mở rộng, với n tập hợp A1, A2, …, An cho trước. Khi đó, ta có: |A1 x A2 x … An| = |A1| . |A2| . … . |An|. Chương II: Phép Đếm. * NGUYÊN LÝ NHÂN Cơ sở tập hợp Ví dụ: Một lớp có 10 sinh viên nam và 5 sinh viên nữ. Tính số cách chọn ra 1 sinh viên nam và 1 sinh viên nữ để tham gia văn nghệ cho trường ? Giải: Gọi A là tập các sinh viên nam trong lớp. Gọi B là tập các sinh viên nữ trong lớp. Khi đó, số cặp gồm 1 sinh viên nam và 1 sinh viên nữ để tham gia văn nghệ cho trường là tập X = A x B. Do đó, số cách là |X| = |A x B| = |A| . |B| = 10.5 = 50. Chương II: Phép Đếm. * NGUYÊN LÝ NHÂN Nguyên lý nhân: Định nghĩa: Giả sử thực hiện 1 thủ tục gồm 2 công việc kế tiếp nhau, công việc thứ 1 có thể thực hiện n cách, công việc thứ 2 có thể thực hiện m cách. Khi đó, thủ tục trên có thể thực hiện bằng n.m cách. Mở rộng: Cho 1 thủ tục gồm n công việc kế tiếp nhau, công việc A1 có n1 cách, công việc A2 có n2 cách, … công việc An có ni cách. Khi đó, thủ tục trên có thể thực hiện bằng n1 . n2 . … . ni cách. Chương II: Phép Đếm. * NGUYÊN LÝ NHÂN Nguyên lý nhân: Ví dụ: Để đi đến trường Tuyến phải đi qua 3 trạm xe buýt. Ở trạm thứ nhất, có 3 tuyến xe buýt đi đến trạm thứ hai. Ở trạm thứ 2 có 4 tuyến xe buýt đi đến trạm thứ ba. Ở trạm thứ 2 có 2 tuyến xe buýt đi từ trạm thứ ba đến trường. Khi đó số cách đi đến trường của Tuyến là: 3.4.2 = 24 (cách). Chương II: Phép Đếm. * NGUYÊN LÝ CHUỒNG BỒ CÂU Gọi x là số nguyên nhỏ nhất lớn hơn hay bằng x. Định nghĩa :Giả sử có n chim bồ câu ở trong k chuồng. Khi đó tồn tại ít nhất một chuồng chứa từ n/k bồ câu trở lên. Ví dụ: Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít nhất 1 chuồng có 3 con bồ câu trở lên. Chương II: Phép Đếm. *