Phương pháp đếm

25/03/2010 1 Chương I PHƯƠNG PHÁP ĐẾM KHÁI NIỆMVỀ TẬP HỢP 1.1. Định nghĩa: 1. Nhắc lại về tập hợp và ánh xạ Một tập hợp là một bộ sưu tập các vật mà ta còn gọi là các phần tử của tập hợp đó. 25/03/2010 3 KHÁI NIỆMVỀ TẬP HỢP 1.2. Ký hiệu: Ta dùng 1. Nhắc lại về tập hợp và ánh xạ – các chữ in: A, B, C, ..., X, Y, Z, ... để chỉ các tập hợp. – các chữ nhỏ: a, b, c, ..., x, y, z, ... để chỉ các phần tử. ể ầ– ký hiệu x ∈ A đ chỉ x là một ph n tử của tập hợp A. Ký hiệu x ∉ A để chỉ x không phải là một phần tử của tập hợp A. 25/03/2010 4 KHÁI NIỆMVỀ TẬP HỢP 1.3. Biểu diễn một tập hợp: 1. Nhắc lại về tập hợp và ánh xạ 1)Liệt kê: Các phần tử của tập hợp sẽ được liệt kê đúng một lần giữa hai dấu { }; giữa hai phần tử khác nhau sẽ có dấu ngăn cách (thường là dấu phẩy , hay chấm phẩy ;) nhưng thứ tự giữa các phần tử này là không quan trọng. Ví dụ: A = {1, 2, 3, 4}, N = {0, 1, 2, 3, ...}, Z = {0, ±1, ±2, ...}, ... 25/03/2010 5 25/03/2010 2 KHÁI NIỆMVỀ TẬP HỢP 1.3. Biểu diễn một tập hợp: 1. Nhắc lại về tập hợp và ánh xạ 2) Nêu tính chất đặc trưng: Tập hợp sẽ được mô tả như là một bộ sưu tập gồm tất cả các phần tử x thỏa mãn tính chất đặc trưng p(x) nào đó dưới dạng: A = {x | p(x)} hay A = {x ∈ B | p(x)}. Ví dụ: 1) Tập hợp A = {x ∈ R | x2 – 4x + 3 = 0} chính là tập hợp A = {1, 3}. 2) Tập hợp các số hữu tỉ được mô tả như sau: Q = { Z, n ≠ 0} 25/03/2010 6 KHÁI NIỆMVỀ TẬP HỢP 1.4. Tập hợp rỗng: 1. Nhắc lại về tập hợp và ánh xạ Tập hợp rỗng, ký hiệu bởi ∅, là tập hợp không chứa phần tử nào. Ví dụ: Các tập hợp A = {x ∈ R | x2 – 4x + 5 = 0} và B = {x ∈ Z | 2x – 1 = 0} đều là các tập hợp rỗng. 25/03/2010 7 KHÁI NIỆMVỀ TẬP HỢP 1.5. Tập hợp con và tập hợp bằng nhau: 1. Nhắc lại về tập hợp và ánh xạ Cho hai tập hợp A và B. Ta nói: 1) A là tập hợp con của B, ký hiệu A ⊂ B hay B ⊃ A nếu mọi phần tử của A đều là các phần tử của B. Như vậy, theo định nghĩa, ta có: A ⊂ B⇔∀x ∈ A, x ∈ B. Ký hiệu A ⊄ B hay B A để chỉ A không phải là tập con của B. 25/03/2010 8 KHÁI NIỆMVỀ TẬP HỢP 1.5. Tập hợp con và tập hợp bằng nhau: 1. Nhắc lại về tập hợp và ánh xạ 2) A bằng B, ký hiệu A = B, nếu A là tập hợp con của B và ngược lại. Như vậy, theo định nghĩa, ta có: A = B ⇔ (A ⊂ B) và (B ⊂ A) ⇔ (∀x ∈ A, x ∈ B) và (∀x ∈ B, x ∈ A). Ký hiệu A ≠ B để chỉ A không bằng B. Ví d Xé á ậ hụ: t c c t p ợp A = {x ∈ R | x2 – 4x + 3 = 0}, B = {x ∈ R | x(x –1)(x – 3) = 0}, C = {0; 1; 2}, D = {0; 1; 2; 3}. Ta thấy A ⊂ B, B ≠ C, C ⊂ D, nhưng B ⊄ A, D ⊄ C. 25/03/2010 9 25/03/2010 3 KHÁI NIỆMVỀ TẬP HỢP 1.6. Tập hợp các tập hợp con: 1. Nhắc lại về tập hợp và ánh xạ Cho tập hợp X. Tập hợp tất cả các tập hợp con của X được ký hiệu là P(X). Như vậy: P(X) = {A | A ⊂ B} Ví dụ: Cho X = {a, b, c}. Ta có: P(X) = {∅; {a}; {b}; {c}; {a, b}; {b, c}; {a, c}; {a, b, c}}. 25/03/2010 10 KHÁI NIỆMVỀ TẬP HỢP 1.7. Số phần tử của tập hợp hữu hạn: 1. Nhắc lại về tập hợp và ánh xạ Cho A là tập hợp hữu hạn. Số phần tử của tập A ký hiệu là |A|. Ta có: 1) |A∪B| = |A|+ |B| - |A∩B| . 2) |A×B| = |A| |B| 3) |P (A)| = 2 |A|, P(A) là tập các tập con của A. 25/03/2010 11 CÁC PHÉP TOÁN TẬP HỢP Cho A và B là hai tập hợp con của tập hợp X. 1. Nhắc lại về tập hợp và ánh xạ 1.8 Phép giao: Phần giao của A và B, ký hiệu bởi A ∩ B, là tập hợp tất cả các phần tử của X vừa thuộc A vừa thuộc B. Như vậy, theo định nghĩa, ta có: A ∩ B = {x ∈ X | x ∈ A và x ∈ B}. Nói cách khác ∀x ∈ X, x ∈ A ∩ B ⇔ x ∈ A và x ∈ B. Suy ra ∀x ∈ X, x ∉ A ∩ B ⇔ x ∉ A hay x ∉ B.25/03/2010 12 CÁC PHÉP TOÁN TẬP HỢP 1.9. Phép hợp: 1. Nhắc lại về tập hợp và ánh xạ Phần hợp của A và B, ký hiệu bởi A ∪ B, là tập hợp tất cả các phần tử (của X) thuộc A hay thuộc B. Như vậy, theo định nghĩa, ta có: A ∪ B = {x ∈ X | x ∈ A hay x ∈ B}. Nói cách khác ∀x ∈ X, x ∈ A ∪ B ⇔ x ∈ A hay x ∈ B. Suy ra ∀x ∈ X, x ∉ A ∪ B ⇔ x ∉ A và x ∉ B. 25/03/2010 13 25/03/2010 4 CÁC PHÉP TOÁN TẬP HỢP 1.10. Phép hiệu: 1. Nhắc lại về tập hợp và ánh xạ Phần hiệu của A và B, ký hiệu bởi A \ B, là tập hợp tất cả các phần tử (của X) thuộc A nhưng không thuộc B. Như vậy, theo định nghĩa, ta có: A \ B = {x ∈ X | x ∈ A và x ∉ B}. Nói cách khác ∀x ∈ X, x ∈ A \ B ⇔ x ∈ A và x ∉ B. Suy ra ∀x ∈ X, x ∉ A \ B ⇔ x ∉ A hay x ∈ B. 25/03/2010 14 CÁC PHÉP TOÁN TẬP HỢP 1.11. Phép bù: 1. Nhắc lại về tập hợp và ánh xạ Với A là một tập con của X, phần bù của A trong X, ký hiệu bởi hay CX(A), là tập hợp X\A. Như vậy, theo định nghĩa, ta có: = X\A = {x ∈ X | x ∉ A}. Nói cách khác A A ∀x ∈ X, x ∈ ⇔ x ∉ A. Suy ra ∀x ∈ X, x ∉ ⇔ x ∈ A. 25/03/2010 15 A A CÁC PHÉP TOÁN TẬP HỢP Ví dụ: 1. Nhắc lại về tập hợp và ánh xạ Xét các tập hợp X = {0; 1; 2; 3; 4; 5; 6}; A = {0; 1; 2; 3}; B = {1; 2; 4; 5}. Ta có: A ∩ B = {1 2};, A ∪ B = {0; 1; 2; 3; 4; 5}; A \ B = {0; 3}; B \ A = {4; 5}; CX(A) = {4; 5; 6}; CX(B) = {0; 3; 6}. 25/03/2010 16 CÁC PHÉP TOÁN TẬP HỢP 1.12. Định lý (tính chất của các phép toán): 1. Nhắc lại về tập hợp và ánh xạ Cho A, B, C là các tập hợp con của tập hợp X. Khi đó ta có: 1) Tính lũy đẳng: A ∩ A = A và A ∪ A = A 2) Tính giao hoán: A ∩ B = B ∩ A và A ∪ B = B ∪ A. 3) Tính kết hợp: (A ∩ B) ∩ C = A ∩ (B ∩ C) và (A ∪ B) ∪ C = A ∪ (B ∪ C) 25/03/2010 17 25/03/2010 5 CÁC PHÉP TOÁN TẬP HỢP 1.12. Định lý (tính chất của các phép toán): 1. Nhắc lại về tập hợp và ánh xạ 4) Tính phân phối: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) và A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) 5) Công thức De Morgan: &A B A B A B A B∩ = ∪ ∪ = ∩ 6) Các công thức 25/03/2010 18 & \A A A B A B= = ∩ CÁC PHÉP TOÁN TẬP HỢP 1.13. Mở rộng: 1. Nhắc lại về tập hợp và ánh xạ Cho {Ai}i∈I là một họ các tập hợp. Ta định nghĩa phần giao và phần hợp của họ {Ai}i∈I như sau: { , }i i i I A x i I x A ∈ = ∀ ∈ ∈ 25/03/2010 19 { , }i i i I A x i I x A ∈ = ∃ ∈ ∈ CÁC PHÉP TOÁN TẬP HỢP 1.13. Mở rộng: 1. Nhắc lại về tập hợp và ánh xạ Khi đó ta có công thức De Morgan suy rộng như sau: i i i I i I A A ∈ ∈ = A A 25/03/2010 20 i i i I i I∈ ∈ = TÍCH DESCARTRES 1.14. Định nghĩa: 1. Nhắc lại về tập hợp và ánh xạ Cho hai tập hợp A và B. Tích Descartes của A và B, ký hiệu bởi A × B, là tập hợp tất cả các cặp (x, y) có thứ tự x trước, y sau, trong đó x thuộc A và y thuộc B. Như vậy, theo định nghĩa, ta có: A × B = {(x, y) | x ∈ A và y ∈ B}. Nói cách khác (x, y) ∈ A × B ⇔ x ∈ A và y ∈ B. Suy ra (x, y) ∉ A × B ⇔ x ∉ A hay y ∉ B. 25/03/2010 21 25/03/2010 6 TÍCH DESCARTRES 1.14. Định nghĩa: 1. Nhắc lại về tập hợp và ánh xạ Ta có: (x, y) = (x', y') ⇔ x = x' và y = y'. Do đó: (x, y) ≠ (x', y') ⇔ x ≠ x' hay y ≠ y'. Ký hiệu A2 để chỉ tích Descartes A × A. Tức là: A2 {( ) | A à A}= x, y x ∈ v y ∈ 25/03/2010 22 TÍCH DESCARTRES 1.15. Tích Descartes của n tập hợp: 1. Nhắc lại về tập hợp và ánh xạ Cho là một dãy gồm n tập hợp. Ta định nghĩa tích Descartres của như sau: A1 × A2 × ... × An = {(x1, x2, ..., xn) | ∀1 ≤ i ≤ n, xi ∈ Ai} Ta còn ký hiệu tích Descartes của bởi bởi . Ký hiệu An để chỉ tích Descartes A × A × × A (n lần) { } 1ni iA = { } 1ni iA = { } 1ni iA = 1 n i i A = ∏ ... . Tức là: An = {(x1, x2, ..., xn) | ∀1 ≤ i ≤ n, xi ∈ A} 25/03/2010 23 TÍCH DESCARTRES 1.16. Mở rộng: 1. Nhắc lại về tập hợp và ánh xạ Cho là một họ các tập hợp. Ta định nghĩa tích Descartes của họ như sau: { }( ) ,i i i I i i i I A x i I x A∈ ∈ = ∀ ∈ ∈∏ { } 1ni iA = { } 1ni iA = 25/03/2010 24 VỊ TỪ VÀ LƯỢNG TỪ 1.17. Định nghĩa: 1. Nhắc lại về tập hợp và ánh xạ Cho A là một tập hợp khác rỗng. Giả sử, ứng với mỗi x = a ∈ A ta có một mệnh đề p(a). Khi đó, ta nói p = p(x) là một vị từ theo một biến (xác định trên A). Tổng quát, cho A1, A2, A3…là n tập hợp khác rỗng. Giả sử rằng ứng với mỗi (x1,x2,...,xn) = (a1,a2,...,an)∈A1×A2× ... ×An, ta có một mệnh đề p(a1,a2,.,an). Khi đó ta nói p = p(x1,x2,.,xn) là một vị từ theo n biến (xác định trên A1×A2× ... ×An) 25/03/2010 25 25/03/2010 7 VỊ TỪ VÀ LƯỢNG TỪ Ví dụ 1: 1. Nhắc lại về tập hợp và ánh xạ Xét p(n) = “n > 2” là một vị từ một biến xác định trên tập các số tự nhiên N. Ta thấy với n = 3, 4 ta được các mệnh đề đúng p(3), p(4), còn với n = 0, 1 ta được mệnh đề sai p(0), p(1). Ví dụ 2: Xét p(x,y) = “x2 + y = 1” là một vị từ theo hai biến xác định trên R2, ta thấy p(0,1) là một mệnh đề đúng, trong khi p(1,1) là một mệnh đề sai. 25/03/2010 26 VỊ TỪ VÀ LƯỢNG TỪ 1.18. Định nghĩa: 1. Nhắc lại về tập hợp và ánh xạ Cho trước các vị từ p(x), q(x) theo một biến x ∈ A. Khi ấy, i. Phủ định của vị từ p(x) ký hiệu là ¬p(x) là vị từ mà khi thay x bởi 1 phần tử cố định của A thì ta được mệnh đề ¬(p(a)). ii. Phép nối liền (tương ứng nối rời, kéo theo…) của p(x) và q(x) được ký hiệu bởi p(x)∧q(x) (tương ứng là p(x)∨q(x), p(x)→q(x)) là vị từ theo biến x mà khi thay x bởi phần tử cố định a ∈ A ta được mệnh đề p(a)∧q(a) ( tương ứng là p(a) ∨q(a), p(a)→q(a)). 25/03/2010 27 VỊ TỪ VÀ LƯỢNG TỪ 1.19. Định nghĩa: 1. Nhắc lại về tập hợp và ánh xạ Cho p(x) là một vị từ theo một biến xác định trên A. Ta định nghĩa các mệnh đề lượng từ hóa của p(x) như sau: i. Mệnh đề “Với mọi x thuộc A, p(x)”, ký hiệu bởi “∀x ∈ A, p(x)”, là mệnh đề được định bởi “∀x ∈ A, p(x)” đúng khi và chỉ khi p(a) luôn đúng với mọi giá trị a ∈ A. ii. Mệnh đề “Tồn tại (ít nhất) (hay có (ít nhất)) một x thuộc A, p(x))” ký hiệu bởi “∃x ∈ A, p(x)”, là mệnh đề được định bởi “∃x ∈ A, p(x)” đúng khi và chỉ khi có ít nhất một giá trị x = a0 nào đó sao cho mệnh đề p(a0) đúng. 25/03/2010 28 VỊ TỪ VÀ LƯỢNG TỪ 1.20. Định lý: 1. Nhắc lại về tập hợp và ánh xạ Cho p(x, y) là một vị từ theo hai biến x, y xác định trên A×B, các mệnh đề sau là đúng: i. [∀x ∈ A,∀y ∈ B, p(x, y)]↔ [∀y ∈ B, ∀x ∈ A, p(x, y)] ii [∃ A ∃ B ( )] [∃ B ∃ A ( )]. x ∈ , y ∈ , p x, y ↔ y ∈ , x ∈ , p x, y iii. [∃x ∈ A, ∀y ∈ B, p(x, y)]→ [∀y ∈ B, ∃x ∈ A, p(x, y)] 25/03/2010 29 25/03/2010 8 VỊ TỪ VÀ LƯỢNG TỪ 1.21. Định lý: 1. Nhắc lại về tập hợp và ánh xạ Trong một mệnh đề lượng từ hoá từ một vị từ theo nhiều biến độc lập, nếu ta hoán vị hai lượng từ đứng cạnh nhau thì: i. Mệnh đề mới vẫn còn tương đương logic với mệnh đề cũ nếu hai lượng từ này cùng loại. ii. Mệnh đề mới này sẽ là một hệ quả logic của mệnh đề cũ nếu hai lượng từ trước khi hoán vị có dạng ∃ ∀ 25/03/2010 30 VỊ TỪ VÀ LƯỢNG TỪ 1.22. Định lý: 1. Nhắc lại về tập hợp và ánh xạ i. Với p(x) là một vị từ theo một biến xác định trên A, ta có: ii Phủ định của mệnh đề lượng từ hóa từ vị từ p(x x ( ) ( ), ,x A p x x A p x∀ ∈ ⇔ ∃ ∈ ( ) ( ), ,x A p x x A p x∃ ∈ ⇔∀ ∈ . 1, 2, ..., xn) có được bằng cách thay lượng từ ∀ bằng lượng từ ∃ và ngược lại, và thay vị từ p(x1, x2, ..., xn) bằng vị từ 25/03/2010 31 ( )1 2, , . . . , np x x x VỊ TỪ VÀ LƯỢNG TỪ 1.23. Quy tắc đặc biệt hóa phổ dụng: 1. Nhắc lại về tập hợp và ánh xạ Nếu một mệnh đề đúng có dạng lượng từ hóa trong đó một biến x ∈ A bị buộc bởi lượng từ phổ dụng ∀, khi ấy nếu thay thế x bởi a ∈ A ta sẽ được một mệnh đề đúng. 25/03/2010 32 VỊ TỪ VÀ LƯỢNG TỪ 1.24. Quy tắc tổng quát hóa phổ dụng: 1. Nhắc lại về tập hợp và ánh xạ Nếu trong một mệnh đề lượng từ hóa, khi thay một biến buộc bởi lượng từ ∀ bằng một phần tử cố định nhưng tùy ý của tập hợp tương ứng mà mệnh đề nhận được có chân trị 1 thì bản thân mệnh đề lượng từ hoá ban đầu cũng có chân trị 1. 25/03/2010 33 25/03/2010 9 ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ 1.25. Định nghĩa: 1. Nhắc lại về tập hợp và ánh xạ Cho hai tập hợp X, Y ≠ ∅. Một ánh xạ f từ X vào Y là quy tắc cho ứng với mỗi phần tử x của X một phần tử duy nhất y của Y mà ta ký hiệu là f(x) và gọi là ảnh của x qua ánh xạ f. Ta viết: f : X → Y x f(x) 1.26. Định nghĩa: Hai ánh xạ f và g từ X vào Y được gọi là bằng nhau nếu: ∀x ∈ X, f(x) = g(x) 25/03/2010 34 ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ 1.27. Ảnh và ảnh ngược: 1. Nhắc lại về tập hợp và ánh xạ Cho ánh xạ f từ X vào Y và A ⊂ X, B ⊂ Y. Ta định nghĩa: 1) Ảnh của A qua f là tập hợp: f(A) = {y ∈ Y | ∃x ∈ A, y = f(x)} Ta cũng viết: f(A) = {f(x) | x ∈ A} Như vậy theo định nghĩa, ta có: ∀y ∈ Y, y ∈ f(A) ⇔ ∃x ∈ A, y = f(x); ∀y ∈ Y, y ∉ f(A) ⇔∀x ∈ A, y ≠ f(x). 25/03/2010 35 ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ 1.27. Ảnh và ảnh ngược: 1. Nhắc lại về tập hợp và ánh xạ 2) Ảnh ngược hay tạo ảnh của B bởi f là tập hợp: f–1(B) = {x ∈ X | f(x) ∈ B} Như vậy theo định nghĩa, ta có: ∀x ∈ X, x ∈ f–1(B)⇔ f(x) ∈ B; ∀x ∈ X, x ∉ f–1(B)⇔ f(x) ∉ B. 25/03/2010 36 ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ 1.27. Ảnh và ảnh ngược: 1. Nhắc lại về tập hợp và ánh xạ Chú ý: 1) Ta thường dùng ký hiệu Imf để chỉ tập hợp f(X) và còn gọi là ảnh của f. 2) Với y ∈ B ta dùng ký hiệu f–1(y) thay cho f–1({y}). Đó chính là tập hợp các phần tử x ∈ X thỏa f(x) = y (ta thường ấgọi đây là tập hợp t t cả các nghiệm x trong X của phương trình f(x) = y). Lưu ý rằng tập hợp f–1(y) có thể rỗng hay khác rỗng (gồm một hay nhiều phần tử). 25/03/2010 37 25/03/2010 10 ĐỊNH NGHĨA VÀ KÝ HIỆU ÁNH XẠ 1.28 Định lý: 1. Nhắc lại về tập hợp và ánh xạ Giả sử f là một ánh xạ từ X vào Y. Với A1 và A2 là hai tập hợp con tùy ý của X, B1 và B2 là hai tập con tùy ý của Y. Ta có: 1. f(A1 ∪ A2) = f(A1) ∪ f(A2); 2. f(A1 ∩ A2) ⊂ f(A1) ∩ f(A2); 3. f(A1 \ A2) ⊃ f(A1) \ f(A2); 4. f–1(B1 ∪ B2) = f–1(B1)∪ f–1(B2); 5. f–1(B1 ∩ B2) = f–1(B1)∩ f–1(B2); 6. f–1(B1 \ B2) = f–1(B1) \ f–1(B2). 25/03/2010 38 PHÂN LOẠI ÁNH XẠ Xét ánh xạ f : X → Y. 1 29 Đơn ánh: 1. Nhắc lại về tập hợp và ánh xạ . . Ta nói f : X→ Y là một đơn ánh nếu hai phần tử khác nhau bất kỳ của X đều có ảnh khác nhau, nghĩa là: ∀x, x' ∈ X, x ≠ x' ⇒ f(x) ≠ f(x') Những tính chất sau được suy trực tiếp từ định nghĩa. f : X→ Y là một đơn ánh ⇔ (∀x, x' ∈ X, f(x) = f(x')⇒ x = x'). ⇔ (∀y ∈ Y, f–1(y) có nhiều nhất một phần tử). ⇔ (∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) có nhiều nhất một nghiệm x ∈ X. 25/03/2010 39 PHÂN LOẠI ÁNH XẠ Xét ánh xạ f : X → Y. 1 29 á h 1. Nhắc lại về tập hợp và ánh xạ . . Đơn n : Suy ra: f : X→ Y không là một đơn ánh ⇔ (∃x, x' ∈ X, x ≠ x' và f(x) = f(x')). ⇔ (∃y ∈ Y, phương trình f(x) = y (y được xem như tham số) có ít nhất hai nghiệm x ∈ X. 25/03/2010 40 PHÂN LOẠI ÁNH XẠ Xét ánh xạ f : X → Y. 1 30 à á h 1. Nhắc lại về tập hợp và ánh xạ . . To n n : Ta nói f : X→ Y là một toàn ánh nếu Imf = Y. Những tính chất sau được suy trực tiếp từ định nghĩa. f : X→ Y là một toàn ánh ⇔ (∀y ∈ Y, ∃x ∈ X, y = f(x)) ⇔ (∀y ∈ Y, f–1(y) ≠ ∅); ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) có nghiệm x ∈ X. 25/03/2010 41 25/03/2010 11 PHÂN LOẠI ÁNH XẠ Xét ánh xạ f : X → Y. 1 30 à á h 1. Nhắc lại về tập hợp và ánh xạ . . To n n : Suy ra: f : X→ Y không là một toàn ánh ⇔ (∃y ∈ Y, ∀x ∈ X, y ≠ f(x)); ⇔ (∃y ∈ Y, f–1(y) =∅); ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) vô nghiệm trong X. 25/03/2010 42 PHÂN LOẠI ÁNH XẠ Xét ánh xạ f : X → Y. 1 31 S á h à á h 1. Nhắc lại về tập hợp và ánh xạ . . ong n v n xạ ngược: Ta nói f : X→ Y là một song ánh hay là một tương ứng 1-1 nếu f vừa là đơn ánh vừa là toàn ánh. Những tính chất sau được suy trực tiếp từ định nghĩa. f : X→ Y là một song ánh ⇔ (∀y ∈ Y, ∃!x ∈ X, y = f(x)); ⇔ (∀y ∈ Y, f–1(y) có đúng một phần tử); ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) có duy nhất một nghiệm x ∈ X. 25/03/2010 43 PHÂN LOẠI ÁNH XẠ Xét ánh xạ f : X → Y. 1 31 S á h à á h 1. Nhắc lại về tập hợp và ánh xạ . . ong n v n xạ ngược: Suy ra: f : X→ Y không là một song ánh ⇔ f không là một đơn ánh hay không là một toàn ánh; ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham số) vô nghiệm hoặc có ít nhất hai nghiệm x ∈ X. 25/03/2010 44 PHÂN LOẠI ÁNH XẠ Xét ánh xạ f : X → Y. 1 31 S á h à á h 1. Nhắc lại về tập hợp và ánh xạ . . ong n v n xạ ngược: Xét f : X→ Y là một song ánh. Khi đó, theo tính chất trên, 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 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 f–1(y) = x với f(x) = y. 25/03/2010 45 25/03/2010 12 TÍCH CÁC ÁNH XẠ 1.32. Định nghĩa: Cho hai ánh xạ 1. Nhắc lại về tập hợp và ánh xạ f : X → Y và g : Y' → Z trong đó Y ⊂ Y'. Ánh xạ tích h của f và g là ánh xạ từ X vào Z xác định bởi: h : X → Z x h(x) = g(f(x)) Ta viết: h = g o f : X → Y → Z x f(x) h(x) = g(f(x)) 25/03/2010 46 TÍCH CÁC ÁNH XẠ 1.33. Định lý: 1. Nhắc lại về tập hợp và ánh xạ Xét f : X→ Y là một song ánh. Khi đó: f o f–1 = IdY f–1 o f = IdX trong đó ký hiệu IdX để chỉ ánh xạ đồng nhất X → X định bởi Id (x) = x ∀x ∈ X; ta gọi Id là ánh xạ đồngX , X nhất trên X, tương tự IdY là ánh xạ đồng nhất trên Y. 25/03/2010 47 NGUYÊN LÝ CỘNG & NGUYÊN LÝ NHÂN 2.1. Nguyên lý Cộng: 2. Phép đếm Giả sử để một hiện tượng xảy ra, có k trường hợp lớn loại trừ lẫn nhau. Biết rằng ở mỗi trường hợp lớn thứ j lại có nj trường hợp nhỏ. Khi đó, số trường hợp nhỏ nói chung để hiện tượng trên xảy ra là: n = n1 + n2 + … + nk. 25/03/2010 48 NGUYÊN LÝ CỘNG & NGUYÊN LÝ NHÂN 2.2. Nguyên lý Nhân: 2. Phép đếm Giả sử để hoàn thành một công việc ta phải tiến hành theo trình tự k bước có tác dụng độc lập. Biết rằng: – Có n1 cách thực hiện buớc 1. – Sau khi thực hiện bước 1 xong, dù bằng bất cứ cách nào, luôn luôn có một số lượng không đổi n2 cách để thực hiện bước 2. – ………… – Cuối cùng, sau khi thực hiện xong bước thứ k-1, luôn luôn có một số lượng không đổi nk cách để thực hiện bước thứ k. Khi đó, số cách để hoàn thành công việc đã cho là: n = n1n2… nk. 25/03/2010 49 25/03/2010 13 GIẢI TÍCH TỔ HỢP 2.3. Hoán vị: 2. Phép đếm Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ tự n phần tử của A được gọi là một hoán vị của n phần tử. Số các hoán vị của n phần tử ký hiệu là Pn Pn = n! Định lý. Số hoán vị của n phần tử, trong đó có n1 phần tử giống nhau thuộc loại 1, n2 phần tử giống nhau thuộc loại 2,…, nk phần tử giống nhau thuộc loại k, là: 25/03/2010 50 1 2 ! ! !... !k n n n n GIẢI TÍCH TỔ HỢP 2.4. Chỉnh hợp: 2. Phép đếm Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phần tử (1 ≤ k ≤n) sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử. Số các chỉnh hợp chập k của n ký hiệu là 25/03/2010 51 ( ) ! ! k n nA n k = − k nA GIẢI TÍCH TỔ HỢP 2.5. Tổ hợp: 2. Phép đếm Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử. Số các tổ hợp chập k của n phần tử đựơc ký hiệu là 25/03/2010 52 k nC ( ) ! ! ! k n nC k n k = − GIẢI TÍCH TỔ HỢP 2.5. Tổ hợp: 2. Phép đếm Nhận xét: Từ kết quả trên ta suy ra số tập con gồm k phần tử của tập hợp gồm n phần tử là Định lý: a) với mọi 0 ≤ k ≤ n; b) với mọi 1 ≤ k ≤ n k nC n k k n nC C − = 1k k k Công thức nhị thức Newton: Với x, y ∈ R và n là số nguyên dương ta có: 25/03/2010 53 1n n nC C C − ++ = 0 ( ) n n k n k k n k x y C x y− = + = ∑ 25/03/2010 14 GIẢI TÍCH TỔ HỢP 2.6. Tổ hợp lặp: 2. Phép đếm Có thể xem một tổ hợp lặp chập k của n loại phần tử a1, a2,…, an là một nhóm không thứ tự gồm k phần tử có thể trùng nhau được rút ra từ tập {a1, a2,…, an}. Gọi là số tổ hợp lặp chập k của n loại phần tử Ta cókK . công thức: 25/03/2010 54 n 1 k k n n kK C + −= GIẢI TÍCH TỔ HỢP 2.6. Tổ hợp lặp: 2. Phép đếm Hệ quả: Số nghiệm nguyên không âm (x1,x2,…,xn) (mỗi xi đều nguyên không âm) của phương trình x1+ x2+…+ xn= k là: 25/03/2010 55 1 k k n n kK C + −= 2.7. Nguyên lý Dirichlet Giả sử có n vật cần đặt vào k hộp. Khi đó tồn tại 2. Phép đếm ít nhất một hộp chứa từ vật trở lên, trong đó là số nguyên nhỏ nhất lớn hơn hay bằng n/k. Hơn nữa, là số nguyên lớn nhất thỏa tính chất trên. /n k⎡ ⎤⎢ ⎥ /n k⎡ ⎤⎢ ⎥ /n k⎡ ⎤⎢ ⎥ 25/03/2010 56 3. Hệ thức đệ quy Một hệ thức đệ quy tuyến tính cấp k là một hệ thức có dạng: xn = a1xn-1 +… + akxn-k + fn (1) trong đó: – ak ≠ 0, a1,…, ak-1 là các hệ số thực – {fn} là một dãy số thực cho trước – {xn} là dãy ẩn nhận các giá trị thực. 25/03/2010 57 25/03/2010 15 3. Hệ thức đệ quy Trường hợp dãy fn= 0 với mọi n thì (1) trở thành: xn = a1xn-1 +… +akxn-