Bài giảng Toán rời rạc: Chương 2 - ThS. Trần Quang Khải

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

Thêm vào BST

Báo xấu

62
lượt xem 4
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 2 Lý thuyết tập hợp, cung cấp cho người học những kiến thức như: Giới thiệu tập hợp; Tích Descartes; Các phép toán tập hợp. Mời các bạn cùng tham khảo!

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 2 - ThS. Trần Quang Khải

TOÁN RỜI RẠC Chương 2: Lý thuyết tập hợp Giảng viên: ThS. Trần Quang Khải
Nội dung 1. Giới thiệu tập hợp. 2. Tích Descartes. 3. Các phép toán tập hợp. 4. Hỏi đáp. 5. Bài tập. Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 2
TOPIC 1 Giới thiệu Tập hợp Giảng viên: ThS. Trần Quang Khải Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 3
Giới thiệu  Tập hợp (set):  Cấu trúc rời rạc cơ bản  các cấu trúc rời rạc khác.  Mục đích:  Nhóm (group) các đối tượng lại với nhau.  Các đối tượng thường có tính chất tương tự nhau.  Ví dụ:  Các sinh viên trong lớp Toán Rời Rạc.  Các con cọp thích ăn chay. Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 4
Định nghĩa Tập hợp (set) Một tập hợp là một “nhóm” (collection) các đối tượng. (Discrete Mathematics and Its Applications) Các đối tượng trong tập hợp:  phần tử, hoặc  thành viên/thành phần (elements, members) Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 5
Biểu diễn  Kiểu liệt kê: S = {a,b,c,d } : tập hợp các ký tự a,b,c,d. a  S : a là một phần tử S. e  S : e không phải là một phần tử của S. ∅ hoặc {} : tập rỗng.  Kiểu kí hiệu builder (xây dựng tập hợp):  = {x | x là số thực } Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 6
Tập hợp “bằng nhau”  Equality: 2 tập hợp A và B là bằng nhau nếu và chỉ nếu chúng có các phần tử giống nhau. A = B ⇔ ∀x(x ∈A ↔ x ∈B)  Ví dụ: {1,4,5} = {4,1,5} {1,3,5,5,1} = {1,3,5} Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 7
Biểu đồ Venn John Venn (1834 - 1923) Không gian (universe):  Hình chữ nhật. Tên tập hợp  Thường kí hiệu: U. Các tập hợp:  Hình tròn, hoặc T  Các hình khép kín khác. Các phần tử:  Điểm. Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 8
Lượng số (Cardinality) Nếu tập S có chính xác n (n ≥0, n Z) phần tử phân biệt nhau thì:  S là tập hữu hạn (finite).  Lượng số của S là n.  Kí hiệu: |S| = n.  Ví dụ:  A là tập các số tự nhiên lẻ nhỏ hơn 10: |A| = ?  B là tập các sinh viên lớp Toán Rời Rạc: |B| = ?  |∅| = 0. Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 9
Lượng số (Cardinality)  Tập vô hạn (infinite)?  Ví dụ: Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 10
Tập con (Subset) Tập A là con của tập B nếu mọi phần tử của A cũng là phần tử của B. Kí hiệu: A  B Nếu A  B và A là tập con của B thì A  B. Ví dụ: {1,3,5,5,1}  {1,3,5} {a, b, c}  {a, x, y, b, d, c, e} Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 11
Tập lũy thừa (Power set) Power set: tổ hợp tất cả các phần tử. Cho tập S, tập lũy thừa của S là tập tất cả các tập con của S. Ký hiệu: P(S) hay 2S. Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 12
Tập lũy thừa (Power set)  Lượng số của tập lũy thừa: |P(S)| = 2|S| Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 13
TOPIC 2 Tích Descartes (Cartesian product) Giảng viên: ThS. Trần Quang Khải Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 14
Tập có thứ tự  Ordered n-tuples (n-bộ): A = (a1, a2, …, an) a1 là phần tử thứ NHẤT. a2 là phần tử thứ HAI. … an là phần tử thứ n.  Nếu thay đổi thứ tự, A không còn là A.  Hai tập có thứ tự bằng nhau? A = (a1, a2, …, an) và B = (b1, b2, …, bn) Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 15
Tích Descartes  René Descartes (1596-1650).  Cartesian Product: Cho 2 tập A, B. tích Descartes của 2 tập A và B được định nghĩa như sau: A × B = {(a,b)|a ∈ A, b ∈ B}  Ví dụ: A = {0,1} và B = {a, b, c} A × B = {(0, a), (0, b), (0, c), (1, a), (1, b),(1, c)} Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 16
Tích Descartes  Tích Descartes của n tập hợp: A1×A2×...×An= {(a1, a2, …, an)| a1A1, a2A2,…, anAn }  Ví dụ: A = {0,1}, B = {1, 2}, C = {0,1,2) A×B×C=? Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 17
TOPIC 3 Các phép toán tập hợp Giảng viên: ThS. Trần Quang Khải Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 18
Union  Phép tuyển: A ∪ B A ∪ B = {x|x  A  x  B} Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 19
Intersection  Phép hội: A ∩ B A ∩ B = {x|x  A  x  B} Toán rời rạc: 2011-2012 Chương 2: Lý thuyết tập hợp 20