tailieunhanh - 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,. . | T 1 1 A - Ấ Chương 2. Phương pháp đêm I. TẬP HỢP 1. 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 G 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à 0 . Tập hợp bằng nhau A B V x G A thì x G B và V x G B thì x G A XÁC ĐINH 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ệu ngoặc và . Ví dụ A a b c Cách nêu đặc trưng của ph b A x G 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 e N n là số nguyên tố B n G 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 o B hay B o A V x G A thì x G B Ví dụ 0 1 2 c n e N n 10 Các tập hợp số. N e Z e Q e R e 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ủa nó là một tập hợp con của X. Ví dụ X 0 1 2 Thì P X 0 0 1 2 0 l 0 2 l 2 0 l 2 Tính chất 0 c A và A c A với mọi tập hợp A. A G B A B G A A B a c b a b c c A c C X c Y P X c P Y Nếu tập hợp X có n phần tử n G N thì tập hợp P X có 2n phần .