Bài giảng 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 TOÁN RỜI RẠC Chương 2: Lý thuyết tập hợp Toán rời rạc: 2011-2012 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. Chương 2: Lý thuyết tập hợp 2 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Giới thiệu Tập hợp Chương 2: Lý thuyết tập hợp 3 TOPIC 1 Toán rời rạc: 2011-2012 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. Chương 2: Lý thuyết tập hợp 4 Toán rời rạc: 2011-2012 Định nghĩa Tập hợp (set) Chương 2: Lý thuyết tập hợp 5 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 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 } Chương 2: Lý thuyết tập hợp 6 Toán rời rạc: 2011-2012 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} Chương 2: Lý thuyết tập hợp 7 Toán rời rạc: 2011-2012 Biểu đồ Venn John Venn (1834 - 1923) Không gian (universe):  Hình chữ nhật.  Thường kí hiệu: U. Các tập hợp:  Hình tròn, hoặc  Các hình khép kín khác. Các phần tử:  Điểm. Chương 2: Lý thuyết tập hợp 8 Tên tập hợp T Toán rời rạc: 2011-2012 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. Chương 2: Lý thuyết tập hợp 9 Toán rời rạc: 2011-2012 Lượng số (Cardinality)  Tập vô hạn (infinite)?  Ví dụ: Chương 2: Lý thuyết tập hợp 10 Toán rời rạc: 2011-2012 Tập con (Subset) Chương 2: Lý thuyết tập hợp 11 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 Tập lũy thừa (Power set) Chương 2: Lý thuyết tập hợp 12 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. Power set: tổ hợp tất cả các phần tử. Toán rời rạc: 2011-2012 Tập lũy thừa (Power set)  Lượng số của tập lũy thừa: |P(S)| = 2|S| Chương 2: Lý thuyết tập hợp 13 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Tích Descartes (Cartesian product) Chương 2: Lý thuyết tập hợp 14 TOPIC 2 Toán rời rạc: 2011-2012 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) Chương 2: Lý thuyết tập hợp 15 Toán rời rạc: 2011-2012 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)} Chương 2: Lý thuyết tập hợp 16 Toán rời rạc: 2011-2012 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 = ? Chương 2: Lý thuyết tập hợp 17 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Các phép toán tập hợp Chương 2: Lý thuyết tập hợp 18 TOPIC 3 Toán rời rạc: 2011-2012 Union  Phép tuyển: A ∪ B A ∪ B = {x|x  A  x  B} Chương 2: Lý thuyết tập hợp 19 Toán rời rạc: 2011-2012 Intersection  Phép hội: A ∩ B A ∩ B = {x|x  A  x  B} Chương 2: Lý thuyết tập hợp 20 Toán rời rạc: 2011-2012 Examples Ví dụ: Cho 2 tập A = {1,3,5} và B = {1,2,3}. A ∪ B = {1,2,3,5} A ∩ B = {3} Cho tập C = {4,5}. B ∩ C = ∅ Chương 2: Lý thuyết tập hợp 21  Hai tập hợp được gọi là tách rời nhau (disjoint) nếu Intersection của chúng là ∅. Toán rời rạc: 2011-2012 Lượng số (Cardinality)  |A ∪ B| = |A| + |B| − |A ∩ B|  |A ∩ B| = ? Chương 2: Lý thuyết tập hợp 22 Toán rời rạc: 2011-2012 Tổng quát hóa Chương 2: Lý thuyết tập hợp 23 Toán rời rạc: 2011-2012 Phép hiệu và Phần bù Phép hiệu (Difference): A−B = {x|x ∈ A ∧ x ∉ B} Phần bù (Complement): A={x|x ∉ A} Chương 2: Lý thuyết tập hợp 24 Toán rời rạc: 2011-2012 Phép hiệu và Phần bù Ví dụ: A = {1,3,5} và B = {1,2,3} Universal set U = {x|x ∈ Z+ ∧ x < 10} A−B = {1,5} A = {2,4,6,7,8,9} Chương 2: Lý thuyết tập hợp 25 Toán rời rạc: 2011-2012 Các công thức tập hợp Chương 2: Lý thuyết tập hợp 26 Công thức Tên A ∪ ∅=A A ∩ U=A Luật đồng nhất A ∪ U=U A ∩ ∅=∅ Luật trội A ∪ A=A A ∩A=A Luật không đổi (A) =A Luật bù Công thức Tên A∪B=B∪A A∩B=B∩A Luật giao hoán A∪(B∪C) = (A∪B)∪C A∩(B∩C) = (A∩B)∩C Luật kết hợp A∩(B∪C) = (A∪B)∩(A∪C) A∪(B∩C) = (A∩B)∪(A∩C) Luật phân phối A∪B=A∩B A∩B=A∪B Luật De Morgan Toán rời rạc: 2011-2012 Exercises 1. Cho A = {1,2,3,4,5} và B = {0,3,6}. Tìm: a) A∪B b) A∩B c) A – B d) B – A 2. Cho A = {a,b,c,d,e} và B = {a,b,c,d,e,f,g,h}. Tìm: a) A∪B b) A∩B c) A – B d) B – A 3. Liệt kê tất cả các phần tử của A×B×C, với: A={shirt, pull}, B={jean, trouser, sport}, C={yellow, blue} Chương 2: Lý thuyết tập hợp 27