Bài giảng môn Toán rời rạc - Chương 2: Tập hợp và ánh xạ

Bài giảng môn Toán rời rạc - Chương 2: Tập hợp và ánh xạ, cung cấp những kiến thức như khái niệm tập hợp; các phép toán trên tập hợp; tập các tập con của một tập hợp; tích descartes; định nghĩa ánh xạ; ánh xạ hợp; ảnh và ảnh ngược; các loại ánh xạ; ánh xạ ngược. 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 môn Toán rời rạc - Chương 2: Tập hợp và ánh xạ TOÁN RỜI RẠC Chương 2 TẬP HỢP VÀ ÁNH XẠToán Rời Rạc Chương 2. Tập hợp và ánh xạ O c 2020 LVL 1/35Nội dungChương 2. TẬP HỢP VÀ ÁNH XẠ 1. Tập hợp 2. Ánh xạ Toán Rời Rạc Chương 2. Tập hợp và ánh xạ O c 2020 LVL 2/352.1. Tập hợp 1 Khái niệm 2 Các phép toán trên tập hợp 3 Tập các tập con của một tập hợp 4 Tích Descartes Toán Rời Rạc Chương 2. Tập hợp và ánh xạ O c 2020 LVL 3/352.1.1. Khái niệmTập hợp là một khái niệm cơ bản của Toánhọc, dùng để chỉ một nhóm các đối tượng nàođó mà chúng ta quan tâm.Khi phần tử x thuộc tập hợp A ta ký hiệux ∈ A, ngược lại ta ký hiệu x ∈ A. /Ví dụ.- Tập hợp sinh viên của một trường đại học.- Tập hợp các số nguyên.- Tập hợp các trái táo trên một cây.Để minh họa tập hợp thì chúng ta dùng sơ đồVen Toán Rời Rạc Chương 2. Tập hợp và ánh xạ O c 2020 LVL 4/35Lực lượng của tập hợpSố phần tử của tập hợp A được gọi là lực lượng của tập hợp, kí hiệu|A|. Nếu A có hữu hạn phần tử, ta nói A hữu hạn. Ngược lại, ta nói Avô hạn.Ví dụ.• |∅| = 0• N, Z, Q, R, là các tập vô hạn• X = {1, 3, 4, 5} là tập hữu hạn với |X| = 4Cách xác định tập hợpCó 2 cách phổ biến: 1 Liệt kê tất cả các phần tử của tập hợp A = {1, 2, 3, 4, a, b} 2 Đưa ra tính chất đặc trưng B = {n ∈ N | n chia hết cho 3} Toán Rời Rạc Chương 2. Tập hợp và ánh xạ O c 2020 LVL 5/35Quan hệ giữa các tập hợpa. Bao hàm. Nếu mọi phần tử của tập hợp A đều là phần tử của tậphợp B thì tập hợp A được gọi là tập hợp con của tập hợp B, ký hiệu làA ⊂ B, nghĩa là A ⊂ B ⇔ ∀x, x ∈ A → x ∈ Bb. Bằng nhau. Hai tập hợp A và B được gọi là bằng nhau nếu A ⊂ Bvà B ⊂ A, ký hiệu A = B.Ví dụ. Cho A = {1, 3, 4, 5}, B = {1, 2, 3, 4, 5, 6, 7, 8} vàC = {x ∈ Z | 0 < x < 9}. Khi đó A ⊂ B và B = C. Toán Rời Rạc Chương 2. Tập hợp và ánh xạ O c 2020 LVL 6/352.1.2. Các phép toán trên tập hợpa) HợpHợp của A và B là tập hợp gồm tất cả các phần tử thuộc ít nhất mộttrong hai tập hợp A và B, ký hiệu A ∪ B, nghĩa là A ∪ B = {x | x ∈ A ∨ x ∈ B}Ví dụ. Cho A = {a, b, c, d} và B = {c, d, e, f }. Khi đó A ∪ B = {a, b, c, d, e, f } Toán Rời Rạc Chương 2. Tập hợp và ánh xạ O c 2020 LVL 7/35 x∈A x∈A /Nhận xét. x ∈ A ∪ B ⇔ x∈A∪B ⇔ / x∈B x∈B /Tính chất. 1 Tính lũy đẳng A ∪ A = A 2 Tính giao hoán A ∪ B = B ∪ A 3 Tính kết hợp (A ∪ B) ∪ C = A ∪ (B ∪ C) 4 Hợp với tập rỗng A ∪ ∅ = Ab) GiaoGiao của A và B là tập hợp gồm tất cả các phần tử vừa thuộc A vàthuộc B, ký hiệu A ∩ B, nghĩa là A ∩ B = {x | x ∈ A ∧ x ∈ B} Toán Rời Rạc Chương 2. Tập hợp và ánh xạ O c 2020 LVL 8/35Ví dụ. Cho A = {a, b, c, d} và B = {c, d, e, f }. Khi đó A ∩ B = {c, d}. x∈A x∈A /Nhận xét. x ∈ A ∩ B ⇔ x∈A∩B ⇔ / x∈B x∈B /Tính chất. 1 Tính lũy đẳng A ∩ A = A 2 Tính giao hoán A ∩ B = B ∩ A 3 Tính kết hợp (A ∩ B) ∩ C = A ∩ (B ∩ C) 4 Giao với tập rỗng A ∩ ∅ = ∅Tính chất. Tính phân phối của phép hợp và giao 1 A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) 2 A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) Toán Rời Rạc Chương 2. Tập hợp và ánh xạ O c 2020 LVL 9/35c) HiệuHiệu của hai tập hợp A và B là tập hợp tạo bởi tất cả các phần tửthuộc tập A mà không thuộc tập B ký hiệu A\B, nghĩa là A\B = {x | x ∈ A ∧ x ∈ B} / x∈A x∈A /Nhận xét. x ∈ A\B ⇔ x ∈ A\B ⇔ / x∈B / x∈BTính chất. Cho A, B, C là các tập hợp. Khi đó 1 A\(B ∩ C) = (A\B) ∪ (A\C); 2 A\(B ∪ C) = (A\B) ∩ (A\C). Toán Rời Rạc Chương 2. Tập hợp và ánh xạ O c 2020 LVL 10/35d) Tập bùKhi A ⊂ U thì U \A gọi là tập bù của A trong U. Ký hiệu CU A hayđơn giản là AVí dụ. Cho A = {1, 3, 4, 6} và U = {1, 2, 3, 4, 5, 6, 7, 8}. Khi đó A = {2, 5, 7, 8}Tính chất. Luật De Morgan 1 A∩B =A∪B 2 A∪B =A∩B Toán Rời Rạc Chương 2. Tập hợp và ánh xạ Oc 2020 LVL 11/35Tính chất. A\B = A ∩ B (triệt hiệu) A ∩ A = ∅. A=A A ∪ A = U.Ví dụ. Cho A, B, C là các tập hợp. Chứng minh rằng: a) A\(A\B) = A ∩ B b) (A\B) ∪ (A\C) = A\(B ∩ C) c) (A\B) ∪ (B\A) = (A ∪ B)\(A ∩ B) d) A ∩ (B\A) = ∅ e) A\B = A\(A ...