Bài giảng "Toán rời rạc - Chương 3: Phương pháp đếm" cung cấp cho người học các kiến thức: Tập hợp và hàm số, các nguyên lý đếm, lý thuyết tổ hợp, nguyên lý Dirichlet, hệ thức truy hồi. nội dung chi tiết. | Bài giảng Toán rời rạc: Chương 3 - Nguyễn Lê Minh TOÁN RỜI RẠC Chương 3: PHƯƠNG PHÁP ĐẾM GV: NGUYỄN LÊ MINH Bộ môn Công nghệ thông tin Nội dung Tập hợp và hàm số Các nguyên lý đếm Lý thuyết tổ hợp Nguyên lý Dirichlet Hệ thức truy hồi 2 Tập hợp Định nghĩa: Là một trong những khái niệm cơ bản của toán học, làm cơ sở cho các định nghĩa toán học. Đó là những đối tượng được nhóm lại theo một tính chất nào đó Ví dụ: Tập hợp các bài tập toán rời rạc Tập hợp số sinh viên lớp CNTT K59 Hệ các phương trình tuyến tính (Tập hợp đồng nghĩa với họ, hệ, lớp .) 3 Tập hợp Những yếu tố tạo thành một tập hợp gọi là phần tử (hay điểm) của tập hợp Kí hiệu: Nếu a là phần tử của A a∈A (a thuộc A) 3 Diễn tả tập hợp Có 2 cách diễn tả tập hợp: Nêu tính chất đặc trưng các phần tử tạo thành tập hợp Liệt kê các phần tử của tập hợp Ví dụ: A = ∈ | à ố ê ố A = 1 ;2 ;3 ;4 ;5 3 Tập hợp Các tập hợp số: N = −> tập hợp số tự nhiên ∗ = −> tập hợp số tự nhiên khác 0 Z = −> tập hợp các số nguyên Q = −> tập hợp các số hữu tỉ R = −> tập hợp các số thực C = −> tập hợp các số phức 3 Tập hợp - Tập hợp A có n phần tử |A| = n - Tập hợp A có vô số phần tử |A| = +∞ - Tập hợp không có phần tử nào ( tập hợp rỗng) |A| = ∅ ( Lưu ý: Tập hợp rỗng ≠ tập hợp có phần tử 0) 3 Tập hợp Nếu mọi phần tử của tập hợp A đều là phần tử của tập hợp B thì A là tập hợp con của B A B Ngoài ra: A A A Nếu A B và B A thì A = B Nếu ≠ thì A B hay B A 3 Tập hợp Mối quan hệ giữa hai tập hợp được biểu diễn bằng biểu đồ Venn 3 Các phép toán trên tập hợp • Phép giao: ∩ = ∈ |( ∈ ) ( ∈ ) • Phép hợp: ∪ = ∈ |( ∈ ) ( ∈ ) • Phần bù: A U \ A x U | x A 3 Tính chất của các phép toán Với A, B, C là các tập con tùy ý của U 3 Tích Descartes của các tập hợp Tích Descartes của hai tập hợp A, B (ký hiệu AxB) là tập các cặp .
