Bài giảng toán rời rạc: Lý thuyết tập hợp

University of FloridaDept. of Computer & Information Science & EngineeringCOT 3100Applications of Discrete StructuresDr. Michael P. Frank Slides for a Course Based on the TextDiscrete Mathematics & Its Applications (5th Edition)by Kenneth H. Rosen Bài #3:Lý thuyết tập hợp Rosen 5th ed., §§1.6-1.7 ~43 slides, ~2 lectures Giới thiệu lý thuyết tập hợp (§1.6) Tập hợp là kiểu cấu trúc mới, thể hiện họ không sắp xếp (nhóm) của không hay nhiều hơn các đối tượng khác nhau. Lý thuyết tập hợp nghiên cứu các phép toán trên chúng, các quan hệ giữa chúng và các tính chất về tập hợp. Tập hợp có mặt khắp nơi trong các hệ thống phần mềm máy tính. Mọi thứ trong toán học có thể định nghĩa dưới dạng lý thuyết tập hợp sử dụng logic vị từ. Lý thuyết tập hợp ngây thơ Tiền đề cơ sở: Mọi họ hay lớp các đối tượng mà chúng ta có thể mô tả đều tạo thành tập hợp. Nhưng lý thuyết thu được về mặt logic là không tương thích! Điều đó có nghĩa là tồn tại mệnh đề p của lý thuyết tập hợp ngây thơ sao cho bạn có thể chứng minh rằng cả p và p có thể suy diễn logic từ các tiên đề của lý thuyết đã cho!  Hội của các tiên đề là mâu thuẫn! Lý thuyết như vậy về cơ bản không thú vị, vì mọi khẳng định có thể dễ dàng chứng minh mâu thuẫn! Lý thuyết tập hợp có triết lý hơn sẽ loại bỏ vấn đề này. Khái niệm cơ bản về tập hợp Để ký hiệu tập hợp ta dùng các biến S, T, U, … Ta có thể định nghĩa tập hợp S bằng cách viết liệt kê mọi phần tử của nó trong ngoặc móc: {a, b, c} là tập có 3 đối tượng ký hiệu bởi a, b, c. Định nghĩa xây dựng tập: Với mọi mệnh đề P(x) trên vũ trụ khẳng định nào đó, {x|P(x)} là tập các đối tượng x mà thoả P(x). Các tính chất cơ bản của tập hợp Tập hợp về bản chất là không sắp thứ tự: Không quan trọng đối tượng a, b, và c ký hiệu cái gì, {a, b, c} = {a, c, b} = {b, a, c} ={b, c, a} = {c, a, b} = {c, b, a}. Mọi phần tử là khác nhau (không bằng nhau); liệt kê lặp không có ý nghĩa! Nếu a=b, thì {a, b, c} = {a, c} = {b, c} = {a, a, b, a, b, c, c, c, c}. Tập này chứa (nhiều nhất) 2 phần tử! Định nghĩa sự bằng nhau của tập hợp Hai tập hợp được nói là bằng nhau nếu và chỉ nếu chúng chứa chính xác cùng các phần tử như nhau. Không quan trọng, tập hợp được định nghĩa và ký hiệu như thế nào. Chẳng hạn: Tập hợp {1, 2, 3, 4} = {x | x là số nguyên trong đó x>0 và x0 và |S|, e.g. |P(N)| > |N|.Có kích thước khác nhau cho các tập vô hạn! Tổng kết c¸c ký hiÖu tËp hîp C¸c ®èi t­îng x, y, z; Tập hợp S, T, U. Liệt kª {a, b, c} vµ tËp x©y {x|P(x)}.  PhÐp thuéc, vµ tËp rçng . Quan hÖ tËp hîp =, , , , , , etc. S¬ ®å Venn. Lùc l­îng |S| vµ tËp v« h¹n N, Z, R. TËp mò P(S). Mô tả ngây thơ tập hợp không tương thích Có một số mô tả tập hợp một cách ngây thơ mà dẫn đến cấu trúc không định nghĩa được. (Hay còn gọi là không tương thích với chính nó.) Về mặt toán học các tập hợp này không thể tồn tại. E.g. let S = {x | xx }. Is SS? Như vậy lý thuyết tập hợp tương thích phải hạn chế ngôn ngữ mô tả tập hợp. Trong lớp này chúng ta không quan tâm đến vấn đề này! Bertrand Russell1872-1970 Bộ n phần tử có thứ tự Cũng giống như tập hợp, nhưng khác là có thể lặp và thứ tự tạo ra sự khác biệt. Với mỗi nN, bộ n có thứ tự hay dãy hay danh sách có độ dài n được viết là (a1, a2, …, an). Phần tử thứ nhất là a1, …. Lưu ý rằng (1, 2)  (2, 1)  (2, 1, 1). Contrast withsets’ {} Tích Đề các của tập hợp Đối với các tập A, B, tích Đề các của chúng AB : {(a, b) | aA  bB }. E.g. {a,b}{1,2} = {(a,1),(a,2),(b,1),(b,2)} Đối với các tập hữu hạn A, B, |AB|=|A||B|. Tích Đề các không giao hoán: i.e., AB: AB=BA. Mở rộng A1  A2  …  An... René Descartes (1596-1650) Ôn lại 1.6 Tập hợp S, T, U… Các tập đặc biệt N, Z, R. Ký hiệu tập hợp {a,b,...}, {x|P(x)}… Các phép toán quan hệ trên tập hợp xS, ST, ST, S=T, ST, ST. (Chúng tạo thành mệnh đề) Tập hữu hạn và tập vô hạn. Các phép toán tập hợp |S|, P(S), ST. Tiếp theo §1.5: về các phép toán tập hợp: , , . Bắt đầu từ §1.7: Phép hợp Đối với hai tập A, B, hợp của chúng (nion) AB là tập chứa mọi phần tử mà thuộc hoặc A, hoặc (“”) B (tất nhiên hoặc cả hai). Về hình thức, A,B: AB = {x | xA  xB}. Vậy AB là tập cha của cả hai tập A và B (mà là nhỏ nhất trong các tập cha như vậy):  A, B: (AB  A)  (AB  B) {a,b,c}{2,3} = {a,b,c,2,3} {2,3,5}{3,5,7} = {2,3,5,3,5,7} ={2,3,5,7} Ví dụ phép hợp - Union Examples Think “The United States of America includes every person who worked in any U.S. state last year.” (This is how the IRS sees it...) Phép Giao - Intersection Operator Đối với hai tập hợp A, B, giao của chúng (intersection) AB là tập chứa mọi phần tử mà đồng thời thuộc A và (“”) thuộc B. Về hình thức, A,B: AB={x | xA  xB}. Vậy AB là tập con của cả A và B (trên thực tế là tập con lớn nhất như vậy):  A, B: (AB  A)  (AB  B) {a,b,c}{2,3} = ___ {2,4,6}{3,4,5} = ______ Intersection Examples Think “The intersection of University Ave. and W 13th St. is just that part of the road surface that lies on both streets.”  {4} Tính rời - Disjointedness Hai tập A, B được gọi là rời nhau (disjoint)khi và chỉ khi giao của chúng là rỗng. (AB=) Example: the set of evenintegers is disjoint withthe set of odd integers. Nguyªn lý bao lo¹i trõ:  Inclusion-Exclusion Principle Cã bao nhiªu phÇn tö trong AB? |AB| = |A|  |B|  |AB| VD: Cã bao nhiªu sinh viªn trong danh s¸ch email cña líp? XÐt tËp E  I  M, I = {s | s ghi ®Þa chØ email trong danh s¸ch th«ng tin cña líp}M = {s | s göi ®Þa chØ email cho trî gi¶ng} Mét sè sinh viªn lµm c¶ hai! |E| = |IM| = |I|  |M|  |IM| Hiệu tập hợp - Set Difference Đối với hai tập A, B, hiệu của A với B, viết là AB, là tập tất cả các phần tử trong A nhưng không thuộc B. Một cách hình thức: A  B : x  xA  xB  x  xA  xB  Còn được gọi là: Phần bù của B đối với A. Set Difference Examples {1,2,3,4,5,6}  {2,3,5,7,9,11} = ___________ Z  N  {… , −1, 0, 1, 2, … }  {0, 1, … } = {x | x is an integer but not a nat. #} = {x | x is a negative integer} = {… , −3, −2, −1} {1,4,6} Set Difference - Venn Diagram A−B is what’s left after B“takes a bite out of A” Set A Set B Phần bù tập hợp - Set Complements Vũ trụ đang nói đến cũng được coi là tập hợp, gọi là U. Khi ngữ cảnh xác định rõ ràng U, ta nói rằng đối với bất kỳ AU, phần bù của A, được viết , là tập các phần tử trong U mà không thuộc A, tức là UA. E.g., If U=N, Nói tiếp về phần bù Định nghĩa tương đương, khi U đã rõ: A U Các đẳng thức trên tập hợp Identity: A = A = AU Domination: AU = U , A =  Idempotent: AA = A = AA Double complement: Commutative: AB = BA , AB = BA Associative: A(BC)=(AB)C , A(BC)=(AB)C DeMorgan’s Law for Sets Exactly analogous to (and provable from) DeMorgan’s Law for propositions. Các đồng nhất thức – U là tập hợp tổng thể các đối tượng đang xét Chứng minh các tập bằng nhau Để chứng minh các khẳng định về tập hợp dạng E1 = E2 (vế phải và trái là các biểu thức tập hợp), có ba kỹ thuật có ích sau: 1. Prove E1  E2 and E2  E1 separately. 2. Sử dụng cách xây dựng tập hợp đó và các tương đương logic. 3. Sử dụng bảng thành viên membership table. Method 1: tập con hai chiều Example: Show A(BC)=(AB)(AC). Part 1: Show A(BC)(AB)(AC). Assume xA(BC), & show x(AB)(AC). We know that xA, and either xB or xC. Case 1: xB. Then xAB, so x(AB)(AC). Case 2: xC. Then xAC , so x(AB)(AC). Therefore, x(AB)(AC). Therefore, A(BC)(AB)(AC). Part 2: Show (AB)(AC)  A(BC). … PP2: Dùng luật chứng minh hai tập hợp bằng nhau Method 3: Membership Tables Giống như bảng chân lý cho logic mệnh đề. Các cột cho các biểu thức tập khác nhau. Các hàng cho mọi tổ hợp thành viên (thuộc) của các tập thành phần. Sử dụng “1” để chỉ thành viên của tập đang xét, “0” chỉ không là thành viên. Chứng minh tương đương khi các cột giống nhau. Membership Table Example Prove (AB)B = AB. Membership Table Exercise Prove (AB)C = (AC)(BC). Review of §1.6-1.7 Sets S, T, U… Special sets N, Z, R. Set notations {a,b,...}, {x|P(x)}… Relations xS, ST, ST, S=T, ST, ST. Operations |S|, P(S), , , , , Set equality proof techniques: Mutual subsets. Derivation using logical equivalences. Hợp và giao tổng quát Generalized Unions & Intersections Vì hợp và giao có tính giao hoán, kết hợp, nên ta có thể mở rộng chúng từ cặp có thứ tự (A,B) sang dãy các tập hợp hoặc ngay cả trên tập không sắp thứ tự các tập hợp, X={A | P(A)}. Hợp tổng quát - Generalized Union Phép hợp hai ngôi: AB Phép hợp n ngôi:AA2…An : ((…((A1 A2) …) An)(grouping & order is irrelevant) Ký hiệu “U lớn”: Hoặc cho tập vô hạn các tập hợp: Giao tổng quát – Generalized Intersection Phép giao hai ngôi: AB Phép giao n-ngôi:A1A2…An((…((A1A2)…)An)(nhóm & và thứ tự không quan trọng) Ký hiệu “Giao lớn”: Hoặc đối với tập vô hạn các tập hợp Biểu diễn - Representations Chủ đề chính của môn này là phương pháp biểu diễn một cấu trúc rời rạc bằng cách sử dụng một cấu trúc rời rạc dạng khác. Chẳng hạn có thể biểu diễn các số tự nhiên như sau Sets: 0:, 1:{0}, 2:{0,1}, 3:{0,1,2}, … Bit strings: 0:0, 1:1, 2:10, 3:11, 4:100, … Biểu diễn tập hợp bằng các xâu bit Đối với tập đếm được U với thứ tự x1, x2, …, có thể biểu diễn tập hữu hạn SU bằng xâu bit hữu hạn B=b1b2…bn trong đói: xiS  (i |Pow(X)| = 2 n ? |Z| = |N| = |Q| - đếm được |N| < |R| - không đếm được |pow(N)| = |R| Không có lực lượng nào lớn hơn |N| và nhỏ hơn |R|. Chứng minh các tính chất của các phép toán tập hợp Chứng minh về tập hợp