Bài giảng Toán rời rạc - Chương 2: Lý thuyết tập hợp - Bùi Thị Thủy

 TOÁN RỜI RẠC 
(DISCRETE MATHEMATICS) 
 Bùi Thị Thủy 
 Đặng Xuân Thọ 
 Support 
2 
  TS. Đặng Xuân Thọ 
  Mobile: 091.2629.383 
  Email: thodx@hnue.edu.vn 
  Website:  
 Toán rời rạc - ĐHSPHN 
 NỘI DUNG 
3 
  Chương 1. Logic mệnh đề 
  Chương 2. Lý thuyết tập hợp 
  Chương 3. Một số công thức tổ hợp 
  Chương 4. Suy luận và kiểm chứng chương trình 
  Chương 5. Đại số Boole và cấu trúc mạch logic 
  Chương 6. Thuật toán 
  Chương 7. Lý thuyết đồ thị 
 Toán Rời Rạc - ĐHSPHN 
 Chương 2. Lý thuyết tập hợp 
4 
  Thế nào là một tập hợp? 
  Biểu diễn tập hợp? 
  Tập con? 
  Các phép toán của tập hợp? 
  Hợp, giao, trừ, tích đecac 
  Biểu diễn trên máy tính? 
  Quan hệ và ánh xạ? 
  Lực lượng của một tập hợp? 
 Toán Rời Rạc - ĐHSPHN 
 Khái niệm tập hợp 
5 
  Lý thuyết tập hợp được nhà toán học người 
 Đức tên là Cantor xây dựng. 
  Tập hợp là một tổng thể các đối tượng (được 
 gọi là các phần tử của tập hợp) có cùng chung 
 một tính chất chung nào đó. 
  Ký hiệu: 
  Tập hợp ký hiệu bởi chữ in hoa A, Q, N, Z 
  Phần tử ký hiệu bởi chữ in thường a, p, x... 
  a A; p A; 
 Toán Rời Rạc - ĐHSPHN 
 Khái niệm tập hợp 
6 
  Ví dụ: 
  Tập hợp các học sinh trong một lớp học. 
  Tập hợp các cuốn sách trong thư viện. 
  N là tập hợp các số tự nhiên. 
  Z là tập hợp các số nguyên. 
  1 ; 
  ½ ; 
 Toán Rời Rạc - ĐHSPHN 
 Các cách biểu diễn tập hợp 
7 
  Một tập hợp thường được biểu diễn như một 
 phần mặt phẳng được giới hạn bởi một đường 
 cong khép kín. Gọi là biểu đồ Venn. 
  Biểu diễn tập hợp A 
  a A A 
  b A a 
 b 
 Toán Rời Rạc - ĐHSPHN 
 Các cách biểu diễn tập hợp (1/3) 
8 
  Biểu diễn tập hợp bằng cách liệt kê tất cả các 
 phần tử của nó. 
  Liệt kê tất cả các phần tử của tập hợp đã cho 
 bằng cách mở đầu và kết thúc việc kê khai bởi 
 dấu “{“ và “}” 
  Tập A bao gồm 3 phần tử là các số tự nhiên 1,2,3 
  A = {1, 2, 3} 
  Tập B bao gồm 6 số nguyên dương đầu tiên? 
  B = {1, 2, 3, 4, 5, 6} 
 Toán Rời Rạc - ĐHSPHN 
 Các cách biểu diễn tập hợp (2/3) 
9 
  Biểu diễn tập hợp thông qua quy luật đơn 
 giản. 
  Liệt kê các phần tử đầu tiên của tập hợp, và sử 
 dụng ba dấu chấm để thể hiện các phần tử khác 
 mà có thể dễ dàng xác nhận được. 
  Tập hợp các số tự nhiên chẵn 
  A = {0, 2, 4, } 
  Tập hợp các số nguyên? 
  Z = {0, 1, -1, 2, -2, } 
 Toán Rời Rạc - ĐHSPHN 
 Các cách biểu diễn tập hợp (3/3) 
10 
  Biểu diễn tập hợp thông qua quy tắc nhận biết. 
  Đưa ra các quy tắc nhận biết các phần tử của tập 
 hợp mà không cần biết việc kiểm tra tính chất 
 nhận biết được đưa ra có dễ dàng hay không. 
  Tập hợp các số nguyên tố 
  P = {p | p là số nguyên tố} 
  Tập hợp các nghiệm của pt x2 - 2x + 1 = 0? 
  X = {x | x2 - 2x + 1 = 0} 
 Toán Rời Rạc - ĐHSPHN 
11 Tập hợp con và bằng nhau 
 Toán Rời Rạc - ĐHSPHN 
 Tập hợp con 
12 
  Định nghĩa: Cho trước hai tập hợp A và B. Ta 
 nói rằng tập hợp A là tập con của tập hợp B, 
 nếu như mỗi phần tử của tập hợp A là phần tử 
 của tập hợp B. 
  Ký hiệu: A  B 
  A là tập con của tập hợp B 
  Tập hợp B chứa tập hợp A 
 B 
 A 
 Toán Rời Rạc - ĐHSPHN 
 Tập hợp con 
13 
  Ví dụ: 
  Tập hợp các số tự nhiên N là tập hợp con thực 
 sự của tập hợp các số nguyên Z. 
  Tập hợp  được quy định là tập hợp con của tất 
 cả các tập hợp. 
  Mỗi tập hợp bất kỳ cũng là tập hợp con của chính 
 nó. 
 Toán Rời Rạc - ĐHSPHN 
 Tập hợp con 
14 
  Cho trước tập hợp A, ta ký hiệu tập hợp tất cả 
 các tập hợp con của A là P(A). 
  Ví dụ: với A = {1, 2} 
  P(A) = {, {1}, {2}, {1, 2}} 
  Tính chất: Quan hệ “chứa nhau” () của tập 
 hợp là một quan hệ có tính chất phản xạ và 
 bắc cầu: 
  Với mọi tập hợp A ta có A  A 
  Nếu A  B và B  C thì A  C 
 Toán Rời Rạc - ĐHSPHN 
 Tập hợp bằng nhau 
15 
  Định nghĩa: cho trước hai tập hợp A và B là 
 hai tập hợp bằng nhau khi và chỉ khi A là tập 
 hợp con của tập hợp B và B là tập hợp con 
 của tập hợp A. 
  Ký hiệu: A = B 
  Nếu A  B và B  A thì A = B 
  Ví dụ: 
  A = {1, 2} 
  B = {x | x2 – 3x + 2 = 0} 
 Toán Rời Rạc - ĐHSPHN 
 Tập hợp bằng nhau 
16 
  Tính chất: quan hệ “bằng nhau” của tập hợp 
 là quan hệ tương đương: 
  Với mọi tập hợp A ta có A = A (tính phản xạ) 
  Nếu A = B thì B = A (tính đối xứng) 
  Nếu A = B và B = C thì A = C (tính bắc cầu) 
 Toán Rời Rạc - ĐHSPHN 
 Luyện tập 
17 
  Cho trước tập hợp A = {1,2,3} và B = {1,3,5,7}. 
 Hãy liệt kê tất cả các tập hợp vừa là tập con 
 của A vừa là tập hợp con của B. 
  Xác định mỗi quan hệ giữa các tập hợp sau: 
  A={1,2,3} và B={1,3,5,7} 
  A={1,2,3} và B={1,3,5,2,7} 
  Xác định tập hợp P({1,2,3})? 
 Toán Rời Rạc - ĐHSPHN 
18 Các phép toán của tập hợp 
 Toán Rời Rạc - ĐHSPHN 
 Phép hợp 
19 
  Định nghĩa: cho trước tập hợp A và tập hợp 
 B. Hợp của tập hợp A và tập hợp B là tập hợp 
 chứa tất cả các phần tử thuộc A hoặc thuộc B, 
 và chỉ những phần tử đó mà thôi. 
  Hợp của tập hợp A và tập hợp B được ký hiệu 
 bởi A  B. 
  A  B = {x | x A hoặc x B} 
 Toán Rời Rạc - ĐHSPHN 
 Phép hợp 
20 
  Tính chất: 
  Luật đồng nhất: A   = A với mọi tập hợp A 
  Luật nuốt: A  U = U với mọi tập hợp A  U 
  Luật lũy đẳng: A  A = A với mọi tập hợp A 
  Luật giao hoán: A  B = B  A với mọi tập hợp A,B 
  Luật kết hợp: (A  B)  C = A  (B  C) với mọi 
 tập hợp A, B, C 
 Toán Rời Rạc - ĐHSPHN 
 Phép hợp 
21 
  Bảng thuộc tính 
  Để chỉ một phần tử thuộc một tập hợp, dùng số 1 
  Để chỉ phần tử không thuộc một tập hợp, dùng 0 
 Toán Rời Rạc - ĐHSPHN 
 Phép giao 
22 
  Định nghĩa: cho trước tập hợp A và tập hợp 
 B. Giao của tập hợp A và tập hợp B là tập hợp 
 chứa tất cả các phần tử vừa thuộc A vừa 
 thuộc B, và chỉ những phần tử đó mà thôi. 
  Ký hiệu: A  B 
  A  B = {x | x A và x B} 
 Toán Rời Rạc - ĐHSPHN 
 Phép giao 
23 
  Tính chất: 
  Luật nuốt: A   =  với mọi tập hợp A 
  Luật đồng nhất: A  U = A với mọi tập hợp A  U 
  Luật lũy đẳng: A  A = A với mọi tập hợp A 
  Luật giao hoán: A  B = B  A với mọi tập hợp A,B 
  Luật kết hợp: (A  B)  C = A  (B  C) với mọi 
 tập hợp A, B, C 
  A  (B  C) = (A  B)  (A  C) 
  A  (B  C) = (A  B)  (A  C) 
  Lập bảng thuộc tính? 
 Toán Rời Rạc - ĐHSPHN 
 Phép trừ 
24 
  Định nghĩa: cho trước tập hợp A và B. Hiệu 
 của tập hợp A với tập hợp B là tập hợp chứa 
 tất cả các phần tử thuộc A mà không thuộc B, 
 và chỉ những phần tử đó mà thôi. 
  Ký hiệu: A \ B hoặc A – B 
  A - B = {x | x A và x B} 
 Toán Rời Rạc - ĐHSPHN 
 Phép trừ 
25 
  Định nghĩa: cho trước tập hợp A và tập hợp U 
 chứa tập hợp A. Khi đó ta nói hiệu U – A là 
 phần bù của tập hợp A trong tập hợp U và ký 
 hiệu U – A bởi CA(U) hoặc 푈 và nếu không 
 xảy ra hiểu lầm thì có thể viết ngắn gọn 
  Ví dụ: 
  A = {0, 1, 2, 3}; U = N 
  = {4, 5, } 
 Toán Rời Rạc - ĐHSPHN 
 Phép trừ 
26 
  Tính chất: 
  Luật bù: = 
  Luật De Morgan cho giao: ∩ = ∪ 
  Luật De morgan cho hợp: ∪ = ∩ 
  Lập bảng thuộc tính? 
 Toán Rời Rạc - ĐHSPHN 
 Phép trừ 
27 
  Định nghĩa: Hiệu đối xứng của hai tập hợp A 
 và B là tập hợp chứa các phần tử chỉ thuộc 
 đúng một trong hai tập hợp A và B (hoặc thuộc 
 tập hợp A hoặc thuộc tập hợp B), và chỉ chứa 
 đúng các phần tử này mà thôi. 
  Ký hiệu: ∆ hoặc ⊕ 
  ⊕ = (A − B)⋃ ( − ) 
 Toán Rời Rạc - ĐHSPHN 
 Hằng đẳng thức đáng nhớ 
28 
 A   = A Luật đồng A  (B  C) = (A  B)  (A  C) Luật phân 
 nhất phối 
 A  U = A A  (B  C) = (A  B)  (A  C) 
 A  U = U Luật nuốt (A  B)  C = A  (B  C) Luật kết 
 hợp 
 A   =  (A  B)  C = A  (B  C) 
 A  A = A Luật lũy ∩ = ∪ Luật De 
 đẳng Morgan 
 A  A = A ∪ = ∩ 
 A  B = B  A Luật giao = Luật bù 
 hoán 
 A  B = B  A 
 Toán Rời Rạc - ĐHSPHN 
 Chứng minh đẳng thức của tập hợp 
29 
  Ví dụ: chứng minh luật De Morgan ∩ = ∪ 
 ∩ = ∉ ⋂ 
 = ( ∈ ⋂ ) 
 = ( ∈ ⋀ ∈ )} 
 = ( ∈ ) ⋁( ∈ )} 
 = ( ∉ ) ⋁( ∉ )} 
 = ∈ ⋁ ∈ 
 = ∈ ⋃ 
 = ⋃ 
 Toán Rời Rạc - ĐHSPHN 
 Tích Đêcac (Descartes) 
30 
  Định nghĩa: Cho A và B là hai tập hợp. Tích 
 Đêcac của A và B là tập hợp tất cả các cặp 
 (a,b) với ∈ và ∈ . 
  × = , | a ∈ , ∈ 
  A =  hoặc B =  thì A x B =  
  Lưu ý: tích Đêcác không có tính chất giao 
 hoán như nhiều phép toán khác của tập hợp. 
 Toán Rời Rạc - ĐHSPHN 
 Biểu diễn tập hợp trên máy tính 
31 
  Xét 1 tập U đủ lớn để chứa các tập hợp đã 
 cho, ví dụ là hợp của các tập hợp cho trước. 
  Biểu diễn tập hợp A ứng với xâu a1a2..an với: 
  n là số phần tử của U 
  ai = 0 nếu phần tử thứ i không thuộc A 
  ai = 1 nếu phần tử thứ i thuộc A 
  Dễ thấy  là xâu gồm toàn các bit 0 
  và U là xâu gồm toàn các bit 1 
 Toán Rời Rạc - ĐHSPHN 
 Biểu diễn tập hợp trên máy tính 
32 
  Ví dụ: 
  A = {1,2,4} và B = {1,3,5} 
  U = {1,2,3,4,5} n = 5 
  Biểu diễn xâu A: a1a2a3a4a5? 
  Cách biểu diễn tập hợp bằng các xâu bit 
 chúng ta dễ dàng thực hiện được các phép 
 toán hợp, giao, và trừ của tập hợp. 
 Toán Rời Rạc - ĐHSPHN 
 Luyện tập 
33 
  Bằng bảng thuộc tính hãy chứng minh: 
  A  (B  C) = (A  B)  (A  C) 
  A  (B  C) = (A  B)  (A  C) 
  Cho A={+,-}; B={a,b,c}; C={1,2,3}. Hãy xác 
 định: 
  A x B x C 
  A x C x B 
  B x C x A 
 Toán Rời Rạc - ĐHSPHN 
THANK YOU!