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

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

1. TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016 Chương 2 TẬP HỢP VÀ ÁNH XẠ lvluyen@hcmus.edu.vn ∼luyen/trr FB: fb.com/trr2015 Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 1/33
2. Nội dung Chương 2. TẬP HỢP VÀ ÁNH XẠ 1. Tập hợp 2. Ánh xạ lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 2/33
3. 2.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 lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 3/33
4. 2.1.1. Khái niệm Tập hợp là một khái niệm cơ bản của Toán họ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ệu x ∈ 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 lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 4/33
5. Lực lượng của tập hợp Số 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 A vô 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| = 4 Cách xác định tập hợp Có 2 cách: 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} lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 5/33
6. Quan hệ giữa các tập hợp a. 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ập hợ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 ∈ B b. Bằng nhau. Hai tập hợp A và B được gọi là bằng nhau nếu A ⊂ B và 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. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 6/33
7. 2.1.2. Các phép toán trên tập hợp a) Hợp Hợ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ột trong 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} lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 7/33
8.  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 ∪ ∅ = A b) Giao Giao 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} lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 8/33
9. Ví 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) lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 9/33
10. c) Hiệu Hiệ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 ∈ B Tí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). lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 10/33
11. d) 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à A Ví 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 lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 11/33
12. Tính chất. A\B = A ∩ B (triệt hiệu) A ∩ A = ∅. 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\C) = (A ∩ B)\(A ∩ C) c) (A\B) ∪ (A\C) = A\(B ∩ C) d) (A\B) ∪ (B\A) = (A ∪ B)\(A ∩ B) e) A ∩ (B\A) = ∅ f) A\B = A\(A ∩ B) = (A ∪ B)\B Ví dụ. Cho các tập hợp A, B và C chứa trong E. Chứng minh (B\C)\(B\A) = (A ∩ B)\C. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 12/33
13. Giải. VT = (B\C)\(B\A) = (B ∩ C)\(B ∩ A) (triệt hiệu) = (B ∩ C) ∩ (B ∩ A) (triệt hiệu) = (B ∩ C) ∩ (B ∪ A) (De Morgan) = C ∩ (B ∩ (B ∪ A)) (kết hợp) = C ∩ ((B ∩ B) ∪ (B ∩ A)) (phân phối) = C ∩ (∅ ∪ (B ∩ A)) (bù) = C ∩ (B ∩ A) (trung hòa) = (A ∩ B) ∩ C (giao hoán, kết hợp) = (A ∩ B)\C = VP (triệt hiệu) Ví dụ.(tự làm) Cho các tập hợp A, B và C ⊂ E. Chứng minh A ∩ (B\C) = (A ∩ B)\(A ∩ C). lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 13/33
14. 2.1.3. Tập các tập con của một tập hợp Định nghĩa. Cho X là một tập hợp. Khi đó tập tất cả các tập con của X được ký hiệu là P (X). Ví dụ. Cho X = {a, b}. Khi đó P (X) = {∅, {a}, {b}, {a, b}} Ví dụ.(tự làm) Cho X = {1, 2, 3}. Tìm tập P (X)? Câu hỏi. Nếu tập X có n phần tử thì tập P (X) có bao nhiêu phần tử? Đáp án. |X| = n ⇒ |P (X)| = 2n. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 14/33
15. 2.1.4. Tích Descartes Định nghĩa. Tích Descartes của tập hợp A với tập hợp B là một tập hợp chứa tất cả các bộ có dạng (x, y) với x là một phần tử của A và y là một phần tử của B, ký hiệu A × B, nghĩa là A × B = {(x, y) | x ∈ A ∧ y ∈ B} Ví dụ. Cho A = {1, 2, 3} và B = {x, y}. Khi đó A × B = {(1, x), (1, y), (2, x), (2, y), (3, x), (3, y)} Câu hỏi. Nếu |A| = n và |B| = m thì |A × B| =? Đáp án. n × m. Khái niệm tích Descartes cũng được mở rộng cho hữu hạn tập hợp, nghĩa là A1 × A2 × · · · × Ak = {(x1, x2, . . . , xk) | xi ∈ Ai, ∀i = 1, k} lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 15/33
16. 2.2. Ánh xạ 1 Định nghĩa ánh xạ 2 Các loại ánh xạ lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 16/33
17. 2.2.1. Định nghĩa Định nghĩa. Một ánh xạ f từ tập X vào tập Y là một phép liên kết từ X vào Y sao cho mỗi phần tử x của X được liên kết với một phần tử duy nhất y của Y, ký hiệu: y = f(x) f : X −→ Y x 7−→ y = f(x). Khi đó X được gọi là tập nguồn, Y được gọi là tập đích. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 17/33
18. Không là ánh xạ Ví dụ. a) Ánh xạ đồng nhất trên X idX : X −→ X x 7−→ x. b) Xét ánh xạ prA : A × B −→ A (a, b) 7−→ a. Khi đó prA được gọi là phép chiếu thứ nhất lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 18/33
19. Định nghĩa. Hai ánh xạ f, g được gọi là bằng nhau khi và chỉ khi chúng có cùng tập nguồn, có cùng tập đích và ∀x ∈ X, f(x) = g(x). Nhận xét. Vậy f 6= g ⇔ ∃x ∈ X, f(x) 6= g(x). 2 Ví dụ. Xét ánh xạ f(x) = (x − 1)(x + 1) và g(x) = x − 1 từ R vào R. Ta có f = g. Ví dụ. Cho f, g : R → R xác định bởi f(x) = 3x + 4 và g(x) = 4x + 3. Hỏi f = g không? Giải. Vì f(0) 6= g(0) nên f 6= g. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 19/33
20. 2.2.2. Ánh xạ hợp Định nghĩa. Cho f : X −→ Y và g : Y −→ Z, lúc đó g◦f : X −→ Z là ánh xạ hợp của g và f, được xác định bởi g◦f(x) = g(f(x)). Ví dụ. Cho f, g : R → R xác định bởi f(x) = x + 2 và g(x) = 3x − 1. Xác định g◦f và f◦g. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 20/33
21. f(x) = x + 2, g(x) = 3x − 1 Giải. i) Với mọi x ∈ R ta có g◦f(x) = g(f(x)) = g(x + 2) = 3(x + 2) − 1 = 3x + 5. Vậy ánh xạ g◦f : R → R được xác định bởi g◦f(x) = 3x + 5. ii) Với mọi x ∈ R ta có f◦g(x) = f(g(x)) = f(3x − 1) = (3x − 1) + 2 = 3x + 1. Vậy ánh xạ f◦g : R → R được xác định bởi f◦g(x) = 3x + 1. 2 Ví dụ.(tự làm) Cho f, g : R → R xác định bởi f(x) = x − 1 và g(x) = 2 − 3x. Xác định g◦f và f◦g. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 21/33
22. 2.2.3. Ảnh và ảnh ngược Định nghĩa. Cho f : X −→ Y , a) Cho A ⊂ X, ảnh của A bởi f là tập f(A) = {f(x) | x ∈ A} ⊂ Y ; b) Cho B ⊂ Y , ảnh ngược của B bởi f là tập f −1(B) = {x ∈ X | f(x) ∈ B} ⊂ X. c) Ta ký hiệu Im(f) = f(X), gọi là ảnh của f. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 22/33
23. 2 Ví dụ. Cho f : R → R được xác định f(x) = x + 1. Hãy tìm a) f([1, 3]); f([−2, −1]); f([−1, 3]); f((1, 5)); b) f −1(1); f −1(2); f −1(−5); f −1([2, 5])? Giải. a) f([1, 3]) = [2, 10]; f([−2, −1]) = [2, 5]; f([−1, 3]) = [1, 10]; f((1, 5)) = (2, 26). b) f −1(1) = {0}; f −1(2) = {−1, 1}; f −1(−5) = ∅; f −1([2, 5]) = [−2, −1] ∪ [1, 2]. ‘ lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 23/33
24. 2.2.4. Các loại ánh xạ Định nghĩa. Cho ánh xạ f : X → Y. Ta nói f đơn ánh nếu “∀x1, x2 ∈ X, x1 6= x2 → f(x1) 6= f(x2)”, nghĩa là hai phần tử khác nhau bất kỳ trong X thì có ảnh khác nhau trong Y. Mệnh đề. Cho ánh xạ f : X → Y. Khi đó: i) f đơn ánh ⇔ “∀x1, x2 ∈ X, f(x1) = f(x2) → x1 = x2”. ii) f không đơn ánh ⇔ “∃x1, x2 ∈ X, x1 6= x2 ∧ f(x1) = f(x2)”. Chứng minh. i) Sử dụng tính chất p → q ⇔ ¬q → ¬p. ii) Sử dụng tính chất ¬(p → q) ⇔ p ∧ ¬q. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 24/33
25. Ví dụ. Cho ánh xạ f : R → R xác định bởi f(x) = x + 3. Xét tính đơn ánh của f. Giải. Với mọi x1, x2 ∈ R, nếu x1 6= x2 thì x1 + 3 6= x2 + 3 nên f(x1) 6= f(x2). Do đó f là đơn ánh. 3 Ví dụ. Cho ánh xạ f : R → R xác định bởi f(x) = x + x. Xét tính đơn ánh của f. Giải. Với mọi x1, x2 ∈ R, 3 3 f(x1) = f(x2) ⇔ x1 + x1 = x2 + x2 3 3 ⇔ x1 − x2 + x1 − x2 = 0 2 2 ⇔ (x1 − x2)(x1 + x1x2 + x2 + 1) = 0 2 2 ⇔ x1 − x2 = 0 (vì x1 + x1x2 + x2 + 1 ≥ 1) ⇔ x1 = x2 Do đó f là đơn ánh. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 25/33
26. 2 Ví dụ. Cho ánh xạ f : R → R xác định bởi f(x) = x + x. Xét tính đơn ánh của f. Giải. Ta có f(−1) = f(0) = 0 mà −1 6= 0. Do đó f không là đơn ánh. Định nghĩa. Cho ánh xạ f : X → Y . Ta nói f toàn ánh nếu “∀y ∈ Y, ∃x ∈ X sao cho y = f(x)”, nghĩa là mọi phần tử thuộc Y đều là ảnh của ít nhất một phần tử thuộc X. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 26/33
27. Ví dụ. 3 a) Cho f : R → R được xác định f(x) = x + 1 là toàn ánh. 2 b) Cho g : R → R được xác định g(x) = x + 1 không là toàn ánh. Mệnh đề. Cho ánh xạ f : X → Y. Khi đó, i) f là toàn ánh ⇔ với mọi y ∈ Y, phương trình y = f(x) có nghiệm ii) f không là toàn ánh ⇔ tồn tại y ∈ Y sao cho phương trình y = f(x) vô nghiệm 2 Ví dụ. Cho f : R → R xác định bởi f(x) = x − 3x + 5. Hỏi f có toàn ánh không? Giải. Với y = 0 ta có phương trình y = f(x) vô nghiệm. Suy ra f không toàn ánh. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 27/33
28. Định nghĩa. Ta nói f : X → Y là một song ánh nếu f vừa là đơn ánh vừa là toàn ánh nghĩa là ∀y ∈ Y, ∃! x ∈ X : f(x) = y Ví dụ. 3 a) f : R → R được xác định f(x) = x + 1 là song ánh 2 b) g : R → R được xác định g(x) = x + 1 không là song ánh Ví dụ. Cho f : R → R xác định bởi f(x) = x + 3. Hỏi f có song ánh không? lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 28/33
29. Giải. Với mọi y ∈ R, ta có y = f(x) ⇔ y = x + 3 ⇔ x = y − 3. Như vậy, với mọi y ∈ R, tồn tại x = y − 3 ∈ R để y = f(x). Do đó f là toàn ánh. Hơn nữa f là đơn ánh. Vậy, f là song ánh. Ví dụ.(tự làm) Cho f : N → N xác định bởi f(x) = 2x + 1. Hỏi f có song ánh không? Ví dụ.(tự làm) Cho f : Z → Z xác định bởi f(x) = x + 5. Hỏi f có song ánh không? Tính chất. Cho ánh xạ f : X → Y và g : Y → Z. Khi đó (i) f, g đơn ánh ⇒ g◦f đơn ánh ⇒ f đơn ánh; (ii) f, g toàn ánh ⇒ g◦f toàn ánh ⇒ g toàn ánh; (iii) f, g song ánh ⇒ g◦f song ánh ⇒ f đơn ánh, g toàn ánh. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 29/33
30. 2.2.5. Ánh xạ ngược Định nghĩa. Cho f : X → Y là một song ánh. Khi đó, với mọi y ∈ Y , tồn tại duy nhất một phần tử x ∈ X thỏa f(x) = y. Do đó tương ứng y 7→ x là một ánh xạ từ Y vào X. Ta gọi đây là ánh xạ ngược của f và ký hiệu f −1. Như vậy: f −1 : Y −→ X y 7−→ x với f(x) = y. Ví dụ. Cho f là ánh xạ từ R vào R xác định bởi f(x) = x + 4. Chứng tỏ f song ánh và tìm f −1? Đáp án. f −1(y) = y − 4. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 30/33
31. Ví dụ. Cho f : [0; 2] −→ [0; 4] x 7−→ x2 thì f −1 : [0; 4] −→ [0; 2] √ y 7−→ y Định lý. Cho ánh xạ f : X → Y. Khi đó, nếu ∀y ∈ Y , phương trình f(x) = y (theo ẩn x) có duy nhất một nghiệm thì f là song ánh. Hơn −1 nữa, nếu nghiệm đó là x0 thì f (y) = x0. Ví dụ. Cho f : R → R xác định bởi f(x) = 5x − 3. Hỏi f có song ánh không? Giải. Với mọi y ∈ R, ta xét phương trình ẩn x sau y + 3 y = f(x) ⇔ y = 5x − 3 ⇔ x = . 5 Như vậy, phương trình có nghiệm duy nhất, suy ra f là song ánh. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 31/33
32. Hơn nữa y + 3 x + 3 f −1(y) = hay f −1(x) = 5 5 Ví dụ.(tự làm) Cho ánh xạ f : X = (2, +∞) → Y = R định bởi f(x) = 4ln(5x − 10) + 3, ∀x ∈ X. Chứng minh f là một song ánh và viết ánh xạ ngược f −1. 3 Ví dụ.(tự làm) Cho f : R → R xác định bởi f(x) = x + 1. Hỏi f có song ánh không? Nếu có, tìm ảnh ngược của f Ví dụ.(tự làm) Cho f : R → R với −x x f(x) = 2e − 5e + 3 ∀x ∈ R. Chứng minh f là một song ánh và viết ánh xạ ngược f −1(x). lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 32/33
33. Mệnh đề. Cho f : X → Y và g : Y → Z là hai song ánh. Khi đó: (i) f −1 cũng là một song ánh và (f −1)−1 = f; −1 −1 −1 (ii) (g◦f) = f ◦ g Mệnh đề. Ánh xạ g : Y → X là nghịch đảo của f : X → Y khi và chỉ khi g◦f = IdX , f◦g = IdY . Nhận xét. Cho A và B là các tập hữu hạn và ánh xạ f : A → B. Khi đó (i) Nếu f đơn ánh thì |A| ≤ |B|; (ii) Nếu f toàn ánh thì |A| ≥ |B|; (iii) Nếu f song ánh thì |A| = |B|. lvluyen@hcmus.edu.vn Chương 2. Tập hợp và ánh xạ 02/11/2015 33/33