Bài giảng Toán: Chương I. PHƯƠNG PHÁP ĐẾM

Chia sẻ: Ngô Thanh Nhật | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

60
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán: Chương I. PHƯƠNG PHÁP ĐẾM

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