tailieunhanh - Bài giảng Cấu trúc rời rạc: Chương 2 - ĐH Công nghệ Thông tin

Bài giảng "Cấu trúc rời rạc - Chương 2: Các phương pháp đếm" cung cấp cho người học các kiến thức: Tập hợp các tập hợp con, biểu diễn tập hợp trên máy tính, các phép toán tập hợp và các tính chất liên quan, tập hợp tích Descartes, nguyên lý cộng, nguyên lý nhân, nguyên lý chuồng bồ câu. . | TOÁN RỜI RẠC CHƯƠNG II: CÁC PHƯƠNG PHÁP ĐẾM 1 CÁC PHƯƠNG PHÁP ĐẾM Tập hợp các tập hợp con. Biểu diễn tập hợp trên máy tính. Các phép toán tập hợp và các tính chất liên quan. Tập hợp tích Descartes. Nguyên lý cộng. Nguyên lý nhân. Nguyên lý chuồng bồ câu. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức Newton. Hoán vị và tổ hợp lặp. 2 TẬP HỢP 1. Khái niệm 2. Quan hệ giữa các tập hợp 3. Các cách xác định tập hợp 4. Tập hợp các tập hợp con (Tập hợp lũy thừa) 3 Chương 2: Các phương pháp đếm. 3 Một tụ tập của vô hạn hay hữu hạn các đối tượng có một tính chất chung nào đó gọi là một 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 đó. Tập hợp thường gọi vắn tắt là tập. Định nghĩa tập hợp: KHÁI NIỆM 4 Chương 2: Các phương pháp đếm. 4 Ví dụ: R là tập các số thực. Z là tập các số nguyên. N là tập các số tự nhiên. Ghi chú: x ∈ A để chỉ x là phần tử của tập A x ∉ A để chỉ x không phải là phần tử của tập A ∅ (tập rỗng): là tập không chứa bất kì phần tử nào KHÁI NIỆM 5 Tập hợp bằng nhau: Hai tập hợp A và B được gọi là bằng nhau khi và chỉ khi chúng có cùng các phần tử, tức là mỗi phần tử thuộc A đều là phần tử thuộc B và ngược lại. Kí hiệu: A=B. Ví dụ: {1, 3, 5} và {3, 5, 1} Tập con: Tập A được gọi là tập con của tập B khi và chỉ khi mọi phần tử của A đều là phần tử của B. Kí hiệu: A B. Nhận xét: (A B) x (x A x B) là đúng QUAN HỆ GIỮA CÁC TẬP HỢP 6 Ví dụ: Tập các số nguyên dương lẻ nhỏ hơn 10 là một tập con của tập các số nguyên dương nhỏ hơn 10 . Ghi chú: Khi muốn nhấn mạnh tập A là tập con của tập B nhưng A≠B, ta viết A⊂B và nói rằng A là tập con thật sự của B. Nhận xét: Nếu A⊆B và B⊆A thì A=B. Tập rỗng là con của mọi tập hợp. Mọi tập hợp đều là tập con của chính nó. QUAN HỆ GIỮA CÁC TẬP HỢP 7 Chương 2: Các phương pháp đếm. 7 Một tập hợp có thể được xác định bằng cách liệt kê tất cả các phần tử của nó. Chúng ta sẽ dùng ký hiệu trong đó tất cả các phần tử của một tập hợp được liệt kê ở giữa hai dấu móc. Ví dụ: V = {a, e, i o, u} O = . | TOÁN RỜI RẠC CHƯƠNG II: CÁC PHƯƠNG PHÁP ĐẾM 1 CÁC PHƯƠNG PHÁP ĐẾM Tập hợp các tập hợp con. Biểu diễn tập hợp trên máy tính. Các phép toán tập hợp và các tính chất liên quan. Tập hợp tích Descartes. Nguyên lý cộng. Nguyên lý nhân. Nguyên lý chuồng bồ câu. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức Newton. Hoán vị và tổ hợp lặp. 2 TẬP HỢP 1. Khái niệm 2. Quan hệ giữa các tập hợp 3. Các cách xác định tập hợp 4. Tập hợp các tập hợp con (Tập hợp lũy thừa) 3 Chương 2: Các phương pháp đếm. 3 Một tụ tập của vô hạn hay hữu hạn các đối tượng có một tính chất chung nào đó gọi là một 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 đó. Tập hợp thường gọi vắn tắt là tập. Định nghĩa tập hợp: KHÁI NIỆM 4 Chương 2: Các phương pháp đếm. 4 Ví dụ: R là tập các số thực. Z là tập các số nguyên. N là tập các số tự nhiên. Ghi chú: x ∈ A để chỉ x là phần tử của tập A x ∉ A để chỉ x không phải là phần tử của tập A ∅ (tập rỗng): là tập không chứa bất kì phần tử nào KHÁI NIỆM 5