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 - HK2 - NĂM 2015-2016 Chương 2 TẬP HỢP VÀ ÁNH XẠ luyen.hutech@gmail.com ∼luyen/trrhutech FB: fb.com/trrhutech Trường Đại Học Công Nghệ TP Hồ Chí Minh luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 1/32
2. Nội dung Chương 2. TẬP HỢP VÀ ÁNH XẠ 1. Tập hợp 2. Ánh xạ luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 2/32
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 luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 3/32
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 luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 4/32
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} luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 5/32
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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 6/32
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} luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 7/32
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} luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 8/32
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) luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 9/32
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). luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 10/32
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 luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 11/32
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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 12/32
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). luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 13/32
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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 14/32
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} luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 15/32
16. 2.2. Ánh xạ 1 Định nghĩa ánh xạ 2 Ánh xạ hợp 3 Ảnh và ảnh ngược 4 Các loại ánh xạ 5 Ánh xạ ngược luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 16/32
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 duy nhất một phần 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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 17/32
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 luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 18/32
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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 19/32
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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 20/32
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. Ví dụ. Cho f, g : R → R xác định bởi f(x) = 4x + 1 và f◦g(x) = 3 − 2x. Hãy xác định g(x)? luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 21/32
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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 22/32
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]. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 23/32
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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 24/32
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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 25/32
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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 26/32
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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 27/32
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? luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 28/32
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? luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 29/32
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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 30/32
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. luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 31/32
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? luyen.hutech@gmail.com Chương 2. Tập hợp và ánh xạ 07/03/2016 32/32