zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán rời rạc: Chương 1 - Phương pháp đếm

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:27

Báo xấu

198
lượt xem 25
download

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

Bài giảng Toán rời rạc: Chương 1 - Phương pháp đếm trình bày về tập hợp và ánh xạ; phép đếm; hệ thức đệ quy; nguyên lý bù trừ; nguyên lý quy nạp; phương pháp phản ứng. Bài giảng phục vụ cho các bạn chuyên ngành Toán học và những bạn quan tâm tới lĩnh vực này.

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 rời rạc: Chương 1 - 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 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: – các chữ in: A, B, C, ..., X, Y, Z, ... để chỉ các 1)Liệt kê: Các phần tử của tập hợp sẽ được liệt kê đúng tập hợp. 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 – 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 4 25/03/2010 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: 2) Nêu tính chất đặc trưng: Tập hợp sẽ được mô tả như Tập hợp rỗng, ký hiệu bởi ∅, là tập hợp không 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)}. Ví dụ: Các tập hợp 1) Tập hợp A = {x ∈ R | x2 – 4x + 3 = 0} chính là tập A = {x ∈ R | x2 – 4x + 5 = 0} hợp A = {1, 3}. và B = {x ∈ Z | 2x – 1 = 0} 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 6 25/03/2010 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: Cho hai tập hợp A và B. Ta nói: 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ó: 1) A là tập hợp con của B, ký hiệu A ⊂ B hay B ⊃ A A=B ⇔ (A ⊂ B) và (B ⊂ A) 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ụ: d Xét Xé các á tập ậ hợp h 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 8 25/03/2010 9 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 của X được ký hiệu là P(X). Như vậy: ký hiệu là |A|. Ta có: P(X) = {A | A ⊂ B} 1) |A∪B| = |A|+ |B| - |A∩B| . Ví dụ: Cho X = {a, b, c}. Ta có: 2) |A×B| = |A| |B| 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 10 25/03/2010 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 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) thuộc A hay thuộc B. Như vậy, cả các phần tử của X vừa thuộc A vừa thuộc B. Như theo định nghĩa, ta có: vậy, theo định nghĩa, ta có: A ∪ B = {x ∈ X | x ∈ A hay x ∈ B}. A ∩ B = {x ∈ X | x ∈ A và x ∈ B}. Nói cách khác Nói cách khác ∀x ∈ X, x ∈ A ∪ B ⇔ x ∈ A hay x ∈ B. ∀x ∈ X, x ∈ A ∩ B ⇔ x ∈ A và x ∈ B. Suy ra Suy ra ∀x ∈ X, x ∉ A ∪ B ⇔ x ∉ A và x ∉ B. 25/03/2010 ∀x ∈ X, x ∉ A ∩ B ⇔ x ∉ A hay x ∉ B. 12 25/03/2010 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ý cả các phần tử (của X) thuộc A nhưng không thuộc B. hiệu bởi A hay CX(A), là tập hợp X\A. Như vậy, theo 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 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 14 25/03/2010 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 đó A = {0; 1; 2; 3}; ta có: B = {1; 2; 4; 5}. 1) Tính lũy đẳng: Ta có: A ∩ A = A và A ∪ A = A 2) Tính giao hoán: A ∩ B = {1, {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 16 25/03/2010 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 A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) giao và phần hợp của họ {Ai}i∈I như sau: 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 18 25/03/2010 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ư i∈I i∈I vậy, theo định nghĩa, ta có: A × B = {(x, y) | x ∈ A và y ∈ B}. Ai = Ai i∈I i∈I 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 20 25/03/2010 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 Ta có: (x, y) = (x', y') ⇔ x = x' và y = y'. Cho { Ai }i =1là một dãy gồm n tập hợp. Ta định nghĩa tích n Do đó: (x, y) ≠ (x', y') ⇔ x ≠ x' hay y ≠ y'. Descartres của { Ai }i =1 như sau: A1 × A2 × ... × An = {(x1, x2, ..., xn) | ∀1 ≤ i ≤ n, xi ∈ Ai} n n Ký hiệu A2 để chỉ tích Descartes A × A. Tức là: Ta còn ký hiệu tích Descartes của bởi { Ai }i =1 bởi ∏i =1 Ai . {( y)) | x ∈ A vàà y ∈ A} A2 = {(x, Ký hiệu A để chỉ tích Descartes A × A × ... × A (n lần). n lần) Tức là: An = {(x1, x2, ..., xn) | ∀1 ≤ i ≤ n, xi ∈ A} 25/03/2010 22 25/03/2010 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 24 25/03/2010 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 Ta thấy với n = 3, 4 ta được các mệnh đề đúng p(3), thay x bởi 1 phần tử cố định của A thì ta được mệnh đề p(4), còn với n = 0, 1 ta được mệnh đề sai p(0), p(1). ¬(p(a)). ụ 2: Ví dụ 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à 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 26 25/03/2010 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: 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)” i. [∀x ∈ A,∀y ∈ B, p(x, y)] ↔ [∀y ∈ B, ∀x ∈ A, p(x, y)] đúng khi và chỉ khi p(a) luôn đúng với mọi giá trị a ∈ A. ii ii. [∃x ∈ A, A ∃y ∈ B, B p(x, )] ↔ [∃y ∈ B, ( y)] B ∃x ∈ A, A p(x, ( y)] )] 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 28 25/03/2010 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ó: 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 ∃x ∈ A, p ( x ) ⇔ ∀x ∈ A, p ( x ) ợ g từ nàyy cùngg loại. đề cũ nếu hai lượng ạ ii Phủ định của mệnh đề lượng từ hóa từ vị từ p(x1, x2, ii. ii. Mệnh đề mới này sẽ là một hệ quả logic của mệnh ..., xn) có được bằng cách thay lượng từ ∀ bằng đề cũ nếu hai lượng từ trước khi hoán vị có dạng ∃ lượng từ ∃ và ngược lại, và thay vị từ p(x1, x2, ..., ∀ xn) bằng vị từ p ( x 1 , x 2 , . .. , x n ) 25/03/2010 30 25/03/2010 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. đú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 32 25/03/2010 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} 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 34 25/03/2010 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 Như vậy theo định nghĩa, ta có: gọi là ảnh của f. ∀x ∈ X, x ∈ f–1(B) ⇔ f(x) ∈ B; 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 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 36 25/03/2010 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: 1.29. 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); 6. f–1(B1 \ B2) = f–1(B1) \ f–1(B2). ⇔ (∀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 38 25/03/2010 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.29. á h 1 30 Toàn 1.30. à ánh: á h Suy ra: Ta nói f : X → Y là một toàn ánh nếu Imf = Y. 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 40 25/03/2010 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 1.30. à ánh: á h 1 31 Song 1.31. S á h và ánh à ánh á h xạ ngược: Suy ra: Ta nói f : X → Y là một song ánh hay là một tương ứng 1-1 f : X → Y không là một toàn ánh nếu f vừa là đơn ánh vừa là toàn ánh. ⇔ (∃y ∈ Y, ∀x ∈ X, y ≠ f(x)); Những tính chất sau được suy trực tiếp từ định nghĩa. ⇔ (∃y ∈ Y, f–1(y) = ∅); f : X → Y là một song ánh ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham ⇔ (∀y ∈ Y, ∃!x ∈ X, y = f(x)); số) vô nghiệm trong 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 42 25/03/2010 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 1.31. S á h và ánh à ánh á h xạ ngược: 1 31 Song 1.31. S á h và ánh à ánh á h xạ ngược: Suy ra: Xét f : X → Y là một song ánh. Khi đó, theo tính chất trên, f : X → Y không là một song ánh 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 không là một đơn ánh hay không là một toàn ánh; = 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: ⇔ ∀y ∈ Y, phương trình f(x) = y (y được xem như tham f–11 : Y → X số) vô nghiệm hoặc có ít nhất hai nghiệm x ∈ X. y f–1(y) = x với f(x) = y. 25/03/2010 44 25/03/2010 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 x h(x) = g(f(x)) x ∀x ∈ X; ta gọi IdX là ánh xạ đồng định bởi IdX(x) = x, Ta viết: nhất trên X, tương tự IdY là ánh xạ đồng nhất trên Y. h=gof:X→Y→Z x f(x) h(x) = g(f(x)) 25/03/2010 46 25/03/2010 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ử để một hiện tượng xảy ra, có k trường hợp 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: 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 48 25/03/2010 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 tử. Số các hoán vị của n phần tử ký hiệu là Pn phần tử (1 ≤ k ≤n) sắp thứ tự của tập hợp A được 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 tử giống nhau thuộc loại 1, n2 phần tử giống nhau thuộc các chỉnh hợp chập k của n ký hiệu là Ank loại 2,…, nk phần tử giống nhau thuộc loại k, là: n! n! A nk = n1 ! n 2 !...n k ! ( n − k )! 25/03/2010 50 25/03/2010 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: Cho tập hợp A gồm n phần tử. Mỗi tập con gồ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à Cnk k phần tử của A được gọi là một tổ hợp chập k Định lý: của n phần tử. Số các tổ hợp chập k của n phần a) C n−k = C k với mọi 0 ≤ k ≤ n; n n b) Cnk + Cnk −1 = Cnk+1 với mọi 1 ≤ k ≤ n 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 ( x + y)n = ∑C k =0 k n x n−k y k 25/03/2010 52 25/03/2010 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ử. tử Ta có là: công thức: K nk = Cnk+ k −1 K nk = Cnk+k −1 25/03/2010 54 25/03/2010 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: ạ g í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ãyy số thực ự cho trước – {xn} là dãy ẩn nhận các giá trị thực. 25/03/2010 56 25/03/2010 57 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ở thành: • Mỗi dãy {xn} thỏa (1) được gọi là một nghiệm 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 đệệ q quyy tuyến y tính • Họ dãy số {xn = xn(C1, C2,…,CCk)} 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 58 25/03/2010 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 k 1 = yk-1 k1 ((*)) 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 60 25/03/2010 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. 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 62 25/03/2010 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 Khi đó, cầu thang còn n n-2 2 bậc nên số cách đi cấp p 2: hết cầu thang trong trường hợp này là xn-2. Theo nguyên lý cộng, số cách đi hết cầu thang ⎧ xn = xn−1 + xn−2 là xn-1 + xn-2 . Do đó ta có: ⎨ xn = xn-1 + xn-2 ⎩ x1 = 1, x2 = 2. 25/03/2010 64 25/03/2010 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 Có 3 cọc A, B, C và n đĩa (có lỗ để đặt vào cọc) 264= 18446744073709551615 (500 billion years) 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. g Vấn đề đặt ặ ra là chuyển y 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 66 25/03/2010 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.C Cuối C ối cùng ù ta chuyển h ể n-1 1 đĩa đĩ từ cọc B sang cọc C. Số lần chuyển n-1 đĩa đó ⎧ xn = 2 xn −1 + 1; ⎨ lại là xn-1. ⎩ x1 = 1. 25/03/2010 68 25/03/2010 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 70 25/03/2010 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 ⎧ 2 xn − 3 xn −1 = 0; là λ0 = 3/2 ⎨ ⎩ 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 1 ⎛3⎞ xn = C ⎜ ⎟ ⎝2⎠ 25/03/2010 72 25/03/2010 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 Từ điều kiện ệ ban đầu x1 = 1,, ta có : Trường hợp k = 2: Phương trình đặc trưng (*) trở thành: 3 λ2 - a1λ - a2 = 0 (*) C ∗ =1 2 Suy ra: 2 a) Nếu (*) có hai nghiệm thực phân biệt λ1 C= 3 và λ2 thì (2) có nghiệm tổng quát là : Do đó nghiệm của hệ thức đệ quy đã cho là: xn = Aλ1n + Bλ2n n −1 ⎛3⎞ xn = ⎜ ⎟ ⎝2⎠ 25/03/2010 74 25/03/2010 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ó nghiệm tổng quát là: λ = r (cos ϕ ± i sin ϕ ) 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 76 25/03/2010 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 Giải các hệ thức đệ quy sau: Ví dụ 1: Ví dụ 1 2 xn − 3 xn −1 + xn −2 = 0 2 xn − 3 xn −1 + xn−2 = 0 (1) Phương trình đặc trưng của (1) là: Ví dụ 2 ⎧ 4 xn +1 − 12 xn + 9 xn −1 = 0; 2λ2 - 3λ + 1 = 0 (*) ⎨ ⎩ x0 = 2; x1 = 4.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 n = A + B⎜ ⎟ ⎝2⎠ 25/03/2010 78 25/03/2010 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 4λ2 - 12λ + 9 = 0 Suy ra A = 2 và B = 2 có nghiệm thực kép là λ0 = 3/2. Do đó nghiệm Vậy nghiệm của (2) là: tổng quát của (2) là: n ⎛3⎞ n −1 ⎛3⎞ x = (3 + n ) ⎜ ⎟ x n = ( A + n B )⎜⎟ n ⎝2⎠ ⎝2⎠ 25/03/2010 80 25/03/2010 81 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.