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

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.
Nội dung trích xuất từ tài liệu:
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 ...