Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 2: Phương pháp đếm

Chương 2 trình bày về phương pháp đếm. Các nội dung chính được trình bày trong chương này gồm có: Khái niệm tập hợp, cách xác định một tập hợp, quan hệ "bao hàm trong" và tập hợp con, các phép toán tập hợp, ánh xạ, các nguyên lý đếm,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 2: Phương pháp đếm Chương 2. Phương pháp đếmI. TẬP HỢP1. KHÁI NIỆM TẬP HỢP Để chỉ một tập hợp ta dùng chữ in hoa, chẳng hạn như A, B, C,….,X,Y,Z. Để chỉ một phần tử ta dùng chữ thường, chẳng hạn như a, b, c,….,x,y,z. Để 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. Ký hiệu x  A Tập vũ trụ: Tập A nằm trong tập U thì U gọi là một vũ trụ của A. Tập hợp rỗng: Tập hợp không có phần tử nào được gọi là tập hợp rỗng,và được ký hiệu là  . Tập hợp bằng nhau:A = B  x  A thì x  B và  x  B thì x  A2.CÁCH XÁC ĐỊNH MỘT TẬP HỢP. Cách liệt kê: Ta liệt kê tất cả các phần tử của tập hợp giữa 2 ký hiệungoặc  và  .Ví dụ: aA =  a, b, c  b c Cách nêu đặc trưng của phần tử:A =  x  U / p(x) với U là tập vũ trụ của tập A.hay vắn tắt (khi hiểu ngầm tập vũ trụ U): A =  x / p(x) Ví dụ:A =  n  N / n là số nguyên tố  B =  n  N / có một số tự nhiên m sao cho n = m2 3. QUAN HỆ bao hàm trong VÀ TẬP HỢP CON Định nghĩa: A  B (hay B  A)  x  A thì x  BVí dụ: 0, 1, 2   n  N : n < 10 Các tập hợp số.N  Z  Q  R  C, trong đó  N là tập hợp các số tự nhiên,  Z là tập hợp các số nguyên,  Q là tập hợp các số hữu tỉ,  R là tập hợp các số thực,  C là tập hợp các số phức. Cho X là một tập hợp. Sưu tập tất cả các tập hợp con của X được kýhiệu là P(X). Nói một cách khác, P(X) là một tập hợp mà mỗi phần tử củanó là một tập hợp con của X.Ví dụ: X= 0, 1, 2Thì P(X)= 0, 1, 2 Tính chất:   A và A  A, với mọi tập hợp A. (A  B)  (B  A)  (A = B) (A  B)  (B  C)  (A  C) X  Y  P(X)  P(Y) Nếu tập hợp X có n phần tử (n  N) thì tập hợp P(X) có 2n phần tử.4.CÁC PHÉP TÓAN TẬP HỢP. Giao.A  B =  x : (x  A)  (x  B)  Hợp.A  B =  x : (x  A)  (x  B)  Hiệu.A - B =  x : (x  A)  (x  B)  Phần bù.Ac = U – A Tích Descartes của 2 tập hợp.A x B =  (a,b) : a  A  b  B Trong trường hợp B = A, ta kỳ hiệu A x A = A2.Các tính chất của các phép toán: Tính giao hoán: AB=BA AB=BA Tính kết hợp: A  (B  C) = (A  B)  C A  (B  C) = (A  B)  C Tính phân bố: A  (B  C) = (A  B)  (A  C) A  (B  C) = (A  B)  (A  C) Luật De Morgan: (A  B)c = Ac  Bc (A  B)c = Ac  Bc Phần tử trung hòa: A=A AU=A Phần bù: A  Ac = U A  Ac =  Tính thống trị: AU=U A=II. ÁNH XẠ2.1 Định nghĩa á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ậphợp Y là phép tương ứng sao cho bởi phép tương ứng nầy mỗi phần tử xcủ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. Ta viếtf:XYx f(x) Ta thường minh họa ánh xạ f bởi sơ đồ sau đây: 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) Cách xác định một ánh xạ.Ta có thể xác định ánh xạ f từ X vào Y bằng nhiều cách, chẳng hạn nhưcách liệt kê tất cả các ảnh của từng phần tử của X, cách cho một côngthức để xác định ảnh f(x) của mỗi phần tử x, hoặc ta có thể đưa ra mộtthủ tục xác định để tính ra (hay tìm ra) được phần tử f(x) ứng với mỗiphần tử x  X.Ví dụ:f : N  N xác định bởi f(n) = 2(n+1).Thìf(1)=4f(2)=6….2.2 Ảnh và ảnh ngược Ả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. Ảnhcủ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  Ả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. Aûnhngượ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ồmtấ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 vắn tắt là f-1(y).Ví dụ:Cho ánh xạ f : Z  N xác định bởi f(n) = n2+1. Đặt A =  -2, -1, 0, 1, 2, 3và B =  0, 1, 2, 3, 4, 5 . Ta có :f(A) =  1, 2, 5, 10f-1(B) =  -2,-1, 0, 1,22.3 Các ánh xạ đặc biệt Đơ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, nghĩa là 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 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. Song ánh:Aù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. Như thế phép tương ứng liên kết y với x sẽ cho ta một ánh xạ từ Y vàoX. Ta gọi ánh xạ nầy là ánh xạ ngược của f và ký hiệu là f-1. Vậy ta cóf-1 : Y  X, xác định bởi f-1(y) = x, với f(x) = y.Ví dụ:Ánh xạ f : Z  N xác định bởi f(n) = n2+1 không phải là một đơn ánh vìf(-1) = f(1) = 2 mà -1  1.Ánh xạ f : N  N xác định bởi f(n) = n2+1 là một đơn ánh vì ta có thểthấy rằng với mọi n và n thuộc N ta có: nếu f(n) = f(n) thì n = n.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 là một song ánh vì với mọi số thực y thì phương trình ax + b = ycó nghiệm thực x duy nhất là x = (y-b) / a. Từ đó ta cũng có ánh xạ ngượcđược xác định bởi f-1(y) = (y-b) / a.III. CÁC NGUYÊN LÝ ĐẾM.3.1 Phép Đếm Định nghĩa: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ạnvà A có n phần tử.Khi đó song ánh f : A   1, 2, . . ., n được xem là một phép đếm tậphợ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| (còn gọi là ...