›
›

Bài giảng Toán rời rạc - Chương III: Quan hệ

pdf 56 trang hapham 5980
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Chương III: Quan hệ", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_toan_roi_rac_chuong_iii_quan_he.pdf

Nội dung text: Bài giảng Toán rời rạc - Chương III: Quan hệ

  1. ChươngLOGO 3 Lê Văn Luyện email: lvluyen@yahoo.com TOÁN RỜI RẠC www.math.hcmus.edu.vn/~lvluyen/trr
  2. Chương 3 QUAN HỆ
  3. 3 I. Quan hệ 1. Định nghĩa và tính chất 2. Biểu diễn quan hệ 3. Quan hệ tương đương. Đồng dư 4. Quan hệ thứ tự, biểu đồ Hass
  4. 4 1. Định nghĩa Một quan hệ hai ngôi từ tập A đến tập B là tập con của tích Đề các R  A x B. Chúng ta sẽ viết a R b thay cho (a, b) R. Quan hệ từ A đến chính nó được gọi là quan hệ trên A R = { (a1, b1), (a1, b3), (a3, b3) }
  5. 5 1. Định nghĩa Ví dụ. A = tập sinh viên; B = các lớp học. R = {(a, b) | sinh viên a học lớp b}
  6. 6 1. Định nghĩa Ví dụ. Cho A = {1, 2, 3, 4}, và R = {(a, b) | a là ước của b} Khi đó R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)} 1 2 3 4 1 2 3 4
  7. 2. Các tính chất của Quan hệ Định nghĩa. Quan hệ R trên A được gọi là phản xạ nếu: a A, a R a Ví dụ. Trên tập A = {1, 2, 3, 4}, quan hệ:  R1 = {(1,1), (1,2), (2,1), (2, 2), (3, 4), (4, 1), (4, 4)} không phản xạ vì (3, 3) R1  R2 = {(1,1), (1,2), (1,4), (2, 2), (3, 3), (4, 1), (4, 4)} phản xạ vì (1,1), (2, 2), (3, 3), (4, 4) R2 7
  8. . Quan hệ trên Z phản xạ vì a a với mọi a Z . Quan hệ > trên Z không phản xạ vì 1 > 1 .Quan hệ“ | ” (“ước số”) trên Z + là phản xạ vì mọi số nguyên a là ước của chính nó . Chú ý. Quan hệ R trên tập A là phản xạ nếu nó chứa đường chéo của A × A : = {(a, a); a A} 4 3 2 1 1 2 3 4 8
  9. 9 2. Các tính chất của Quan hệ Định nghĩa. Quan hệ R trên A được gọi là đối xứng nếu: a A b A (a R b) (b R a) Quan hệ R được gọi là phản xứng nếu  a A b A (a R b)  (b R a) (a = b) Ví dụ.  Quan hệ R1 = {(1,1), (1,2), (2,1)} trên tập A = {1, 2, 3, 4} là đối xứng  Quan hệ trên Z không đối xứng. Tuy nhiên nó phản xứng vì (a b)  (b a) (a = b)
  10. 10 2. Các tính chất của Quan hệ . Quan hệ“ | ” (“ước số”) trên Z +. không đối xứng Tuy nhiên nó có tính phản xứng vì (a | b)  (b | a) (a = b) Chú ý. Quan hệ R trên A là đối xứng nếu nó đối xứng nhau qua đường chéo của A × A. Quan hệ R là phản xứng nếu chỉ có các phần tử nằm trên đường chéo là đối xứng qua của A × A. 4 4 * 3 3 2 2 * * 1 1 1 2 3 4 1 2 3 4
  11. 11 2. Các tính chất của Quan hệ Định nghĩa. Quan hệ R trên A có tính bắc cầu (truyền) nếu a, b,c A,(a R b)  (b R c) (a R c) Ví dụ. Quan hệ R = {(1,1), (1,2), (2,1), (2, 2), (1, 3), (2, 3)} trên tập A = {1, 2, 3, 4} có tính bắc cầu. Quan hệ và “|”trên Z có tính bắc cầu (a b)  (b c) (a c) (a | b)  (b | c) (a | c)
  12. 12 3. Biểu diễn Quan hệ Giới thiệu Ma trận Biểu diễn Quan hệ
  13. 13 Định nghĩa Cho R là quan hệ từ A = {1,2,3,4} đến B = {u,v,w}: R = {(1,u),(1,v),(2,w),(3,w),(4,u)}. Khi đó R có thể biễu diễn như sau u v w Dòng và cột 1 1 1 0 tiêu đề có 2 0 0 1 thể bỏ qua nếu không gây hiểu 3 0 0 1 nhầm. 4 1 0 0 Đây là ma trận cấp 4×3 biễu diễn cho quan hệ R
  14. Biểu diễn Quan hệ Định nghĩa. Cho R là quan hệ từ A = {a1, a2, , am} đến B = {b1, b2, , bn}. Ma trận biểu diễn của R là ma trận cấp m × n MR = [mij] xác định bởi 0 nếu (ai , bj) R mij = 1 nếu (ai , bj) R 1 2 Ví dụ. Nếu R là quan hệ từ A = {1, 2, 3} đến 1 0 0 B = {1, 2} sao cho a R b nếu a > b. Khi 2 1 0 đó ma trận biểu diễn của R là 3 1 1 14
  15. 15 Biểu diễn Quan hệ 1 nếu (ai , bj) R mij = 0 nếu (ai , bj) R Ví dụ. Cho R là quan hệ từ A = {a1, a2, a3} đến B = {b1, b2, b3, b4, b5} được biễu diễn bởi matrận b1 b2 b3 b4 b5 0 1 0 0 0 a1 a2 M R 1 0 1 1 0 a3 1 0 1 0 1 Khi đó R gồm các cặp: {(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)}
  16. 16 Biểu diễn Quan hệ . Cho R là quan hệ trên tập A, khi đó MR là ma trận vuông. . R là phản xạ nếu tất cả các phần tử trên đường chéo của MR đều bằng1: mii = 1 với mọi i u v w u 1 1 0 v 0 1 1 w 0 0 1
  17. 17 Biểu diễn Quan hệ R là đối xứng nếu MR là đối xứng mij = mji for all i, j u v w u 1 0 1 v 0 0 1 w 1 1 0
  18. 18 Biểu diễn Quan hệ R là phản xứng nếu MR thỏa: mij = 0 or mji = 0 if i j u v w u 1 0 1 v 0 0 0 w 0 1 1
  19. 19 3. Quan hệ tương đương Giới thiệu Quan hệ tương đương Biểu diễn số nguyên Lớp tương đương
  20. 20 Định nghĩa Ví dụ. Cho S = {sinh viên của lớp}, gọi R = {(a,b): a có cùng họ với b} Hỏi R phản xạ? Yes Mọi sinh viên có cùng họ R đối xứng? Yes thuộc cùng một nhóm R bắc cầu? Yes .
  21. 3. Quan hệ tương đương Định nghĩa. Quan hệ R trên tập A được gọi là tương đương nếu nó có tính chất phản xạ, đối xứng và bắc cầu : Ví dụ. Quan hệ R trên các chuỗi ký tự xác định bởi aRb nếu a và b có cùng độ dài. Khi đó R là quan hệ tương đương. Ví dụ. Cho R là quan hệ trên R sao cho aRb nếu a – b nguyên. Khi đó R là quan hệ tương đương 21
  22. 3. Quan hệ tương đương Cho a và b là hai số nguyên. A được gọi là ước của b hay b chia hết cho nếu tồn tại số nguyên k sao a = kb Ví dụ. Cho m là số nguyên dương và R quan hệ trên Z sao cho aRb nếu a – b chia hết m, khi đó R là quan hệ tương đương. - Rõ ràng quan hệ này có tính phản xạ và đối xứng. - Cho a, b, c sao cho a – b và b – c chia hết cho m, khi đó a – c = a – b + b – c cũng chia hết cho m. Suy ra R có tính chất bắc cầu. - Quan hệ này được gọi là đồng dư modulo m và chúng ta viết a  b (mod m) thay vì aRb 22
  23. 23 Lớp tương đương Định nghĩa. Cho R là quan hệ tương đương trên A và phần tử a A . Lớp tương đương chứa a được ký hiệu bởi [a]R hoặc [a] là tập [a]R = {b A| b R a}
  24. 24 Lớp tương đương Ví dụ. Tìm các lớp tương đương modulo 8 chứa 0 và 1? Giải. Lớp tương đương modulo 8 chứa 0 gồm tất cả các số nguyên a chia hết cho 8. Do đó [0]8 ={ , – 16, – 8, 0, 8, 16, } Tương tự [1]8 = {a | a chia 8 dư 1} = { , – 15, – 7, 1, 9, 17, }
  25. 25 Lớp tương đương Chú ý. Trong ví dụ cuối, các lớp tương đương [0]8 và [1]8 là rời nhau. Tổng quát, chúng ta có Định lý. Cho R là quan hệ tương đương trên tập A và a, b A, Khi đó (i) a R b nếu [a]R = [b]R (ii) [a]R [b]R nếu [a]R  [b]R =  Chú ý. Các lớp tương đương theo một quan hệ tương đương trên A tạo nên một phân họach trên A, nghĩa là chúng chia tập A thành các tập con rời nhau.
  26. Lớp tương đương 26 Chú ý. Cho {A1, A2, } là phân họach A thành các tập con không rỗng, rời nhau . Khi đó có duy nhất quan hệ tương đương trên A sao cho mỗi Ai là một lớp tương đương. Thật vậy với mỗi a, b A, ta đặt a R b nếu có tập con Ai sao cho a, b Ai . Dễ dàng chứng minh rằng R là quan hệ tương đương trên A và [a]R = Ai nếu a Ai a A A2 1 A3 A b 4 A5
  27. 27 Ví dụ. Cho m là số nguyên dương, khi đó có m lớp đồng dư modulo m là [0]m , [1]m , , [m – 1]m . Chúng lập thành phân họach của Z thành các tập con rời nhau. Chú ý rằng [0]m = [m]m = [2m]m = [1]m = [m + 1]m = [2m +1]m = [m – 1]m = [2m – 1]m = [3m – 1]m = Mỗi lớp tương đương này được gọi là số nguyên modulo m .Tập hợp các số nguyên modulo m được ký hiệu bởi Zm Zm = {[0]m , [1]m , , [m – 1]m}
  28. 28 4. Quan hệ thứ tự. Biểu đồ Hasse Giới thiệu Thứ tự từ điển Biểu đồ Hasse Phần tử tối tiểu, tối đại Chặn trên nhỏ nhất, chặn dưới lớn nhất Sắp xếp topo
  29. 29 Định nghĩa Ví dụ. Cho R là quan hệ trên tập số thực: a R b nếu a b Hỏi:  R phản xạ không? Có R đối xứng không? Không  R phản xứng không? Có R bắc cầu không? Có
  30. 30 Định nghĩa Định nghĩa. Quan hệ R trên tập A là quan hệ thứ tự (thứ tự) nếu nó có tính chất phản xạ, phản xứng và bắc cầu. Người ta thường ký hiệu quan hệ thứ tự bởi Cặp (A, ) đựợc gọi là tập sắp thứ tự hay poset Phản xạ: a a Phản xứng: (a b)  (b a) (a = b) Bắc cầu: (a b)  (b c) (a c)
  31. 31 Định nghĩa Ví dụ. Quan hệ ước số “ | ”trên tập số nguyên dương là quan hệ thứ tự, nghĩa là (Z+, | ) là poset Phản xạ? Có, x | x vì x = 1  x Bắc cầu? Có? a | b nghĩa là b = ka, b | c nghĩa là c = jb. Khi đó c = j(ka) = jka: a | c
  32. 32 Phản xứng? có? a | b nghĩa là b = ka, b | a nghĩa là a = jb. Khi đó a = jka Suy ra j = k = 1, nghĩa là a = b Ví dụ. (Z, | ) là poset? Không phải Phản xứng? 3|-3, và -3|3, Không nhưng 3 -3.
  33. 33 (P(S),  ), ở đây P(S) là tập hợp các con của S, là một poset? Có, là poset. Phản xạ? Có, A  A, A P(S) Bắc cầu? Có A  B, B  C. Suy ra A  C? Phản xứng? Có A  B, B  A. Suy ra A =B?
  34. Định nghĩa 34 Định nghĩa. Các phần tử a và b của poset (S, ) gọi là so sánh được nếu a b hay b a . Trái lại thì ta nói a và b không so sánh được. Cho (S, ), nếu hai phần tử tùy ý của S đều so sánh được với nhau thì ta gọi nó là tập sắp thứ tự toàn phần. Ta cũng nói rằng là thứ tự toàn phần hay thứ tư tuyến tính trên S
  35. Chương 3 Ví dụ Ví dụ. Quan hệ “ ” trên tập số nguyên dương là thứ tự toàn phần. Ví dụ. Quan hệ ước số “ | ”trên tập hợp số nguyên dương không là thứ tự toàn phần, vì các số 5 và 7 là không so sánh được.
  36. 36 Thứ tự tự điển Ví dụ. Trên tập các chuỗi bit có độ dài n ta có thể định nghĩa thứ tự như sau: a1a2 an b1b2 bn nếu ai bi,  i. Với thứ tự này thì các chuỗi 0110 và 1000 là không so sánh được với nhau. Chúng ta không thể nói chuỗi nào lớn hơn. Trong tin học chúng ta thường sử dụng thứ tự toàn phần trên các chuỗi bit . Đó là thứ tự tự điển.
  37. 37 Thứ tự tự điển Cho (A, ) và (B, ’) là hai tập sắp thứ tự toàn phần. Ta định nghĩa thứ tự trên A B như sau : (a1 , b1) (a2, b2) nếu a1 < a2 hay (a1 = a2 và b1 <’ b2) Dễ dàng thấy rằng đây là thứ tự toàn phần trên A B. Ta gọi nó là thứ tự tự điển . Chú ý rằng nếu A và B được sắp tốt bởi và ’ ,tương ứng thì A B cũng được sắp tốt bởi thứ tự Chúng ta cũng có thể mở rộng định nghĩa trên cho tích Descartess của hữu hạn tập sắp thứ tự toàn phần.
  38. 38 Thứ tự tự điển Cho  là một tập hữu hạn (ta gọi là bảng chữ cái). Tập hợp các chuỗi trên , ký hiệu là * , xác định bởi .  *, trong đó  là chuỗi rỗng. . Nếu x , và w *, thì wx *, trong đó wx là kết nối w với x. Ví dụ. Chẳng hạn  = {a, b, c}. Thế thì * = {, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, }
  39. 39 Thứ tự tự điển Giả sử là thứ tự toàn phần trên , khi đó ta có thể định nghĩa thứ tự toàn phần trên * như sau. Cho s = a1 a2 am và t = b1 b2 bn là hai chuỗi trên * Khi đó s t nếu . Hoặc ai = bi đối với 1 i m ,tức là t = a1 a2 am bm +1 bm +2 bn . Hoặc tồn tại k < m sao cho  ai = bi với 1 i k và  ak+1 < bk+1 , nghĩa là s = a1 a2 ak ak +1 ak +2 am t = a1 a2 ak bk +1 bk +2 bn
  40. Thứ tự tự điển 40  Chúng ta có thể kiểm tra là thứ tự toàn phần trên * Ta gọi nó là thứ tự từ điển trên * Ví dụ. Nếu  là bảng chữ cái tiếng Anh với thứ tự: a < b < < z,thì thứ tự nói trên là thứ tự thông thường giữa các từ trong Từ điển. Ví dụ  discreet discrete d i s c r e e t e t d i s c r e t e discreet discreetness d i s c r e e t d i s c r e e t n e s s
  41. 41 Thứ tự tự điển Ví dụ. Nếu  = {0, 1} với 0 < 1, thì là thứ tự toàn phần trên tập tất cả các chuỗi bit * . Ta có  0110 10  0110 01100
  42. 42 Biểu đồ Hasse Mỗi poset có thể biễu diễn bởi đồ thị đặc biệt ta gọi là biểu đồ Hasse Để định nghĩa biểu đồ Hasse chúng ta cần các khái niệm phần tử trội và trội trực tiếp. Định nghĩa. Phần tử b trong poset (S, ) được gọi là phần tử trội của phần tử a trong S nếu a b Chúng ta cũng nói rằng a là được trội bởi b . Phần tử b được gọi là trội trực tiếp của a nếu b là trội của a, và không tồn tại trội c sao cho a c b, a c b
  43. 43 Biểu đồ Hasse . Ta định nghĩa Biểu đồ Hasse của poset (S, ) là đồ thị: Mỗi phần tử của S được biễu diễn bởi một điểm trên mặt phẳng .  Nếu b là trội trực tiếp của a thì vẽ một cung đi từ a đến b . b d a b d, a c a e c
  44. 44 Biểu đồ Hasse Ví dụ. Biểu đồ Hasse của poset ({1,2,3,4}, ) có thể vẽ như sau 4 3 Chú ý . Chúng ta không vẽ 2 mũi tên với qui ước mỗi cung đều đi từ dưới lên trên 1
  45. 45 Ví dụ. Biểu đồ Hasse của P({a,b,c}) và biểu đồ Hasse của các chuỗi bit độ dài 3 với thứ tự tự điển {a,b,c} 111 {a,b} {a,c} {b,c} 110 101 011 {a} {b} {c} 100 010 001  000 Giống nhau không!!!
  46. 46 Phần tử tối đại và phần tử tối tiểu. Xét poset có biểu đồ Hasse như dưới đây:  Mỗi đỉnh màu đỏ là tối đại.  Mỗi đỉnh màu xanh là tối tiểu.  Không có cung nào xuất phát từ điểm tối đại.  Không có cung nào kết thúc ở điểm tối tiểu.
  47. 47 Chú ý. Trong một poset S hữu hạn, phần tử tối đại và phần tử tối tiểu luôn luôn tồn tại.  Thật vậy, chúng ta xuất phát từ điêm bất kỳ a0 S. Nếu a0 không tối tiểu, khi đó tồn tại a1 a0, tiếp tục như vậy cho đến khi tìm được phần tử tối tiểu . Phần tử tối đại tìm được bằng phương pháp tương tự. a0 a1 a2
  48. 48 Ví dụ. Tìm phần tử tối đại, tối tiểu của poset ({2, 4, 5, 10, 12, 20, 25}, | ) ? Giải. Từ biểu đồ Hasse, chúng ta thấy rằng 12, 20, 25 là các phần tử tối đại, còn 2, 5 là các phần tử tối tiểu Như vậy phần tử tối đại, tối tiểu của poset có thể không duy nhất. 12 20 10 4 25 2 5
  49. 49 Ví dụ. Tìm phần tử tối đại, tối tiểu của poset các chuỗi bit độ dài 3? Giải. Từ biểu đồ Hasse, chúng ta thấy rằng 111 là phần tử tối đại duy nhất và 000 là phần tử tối tiểu duy nhất. 111 111 là phần tử lớn nhất và 000 là phần tử nhỏ nhất 011 theo nghĩa: 110 101 000 abc 111 100 010 001 với mọi chuỗi abc 000
  50. 50 Chặn trên, chặn dưới Định nghĩa. Cho (S, ) là poset và A  S . Phần tử chặn trên của A là phần tử x S (có thể thuộc A hoặc không) sao cho  a A, a x. Phần tử chặn dưới của A là phần tử x S sao cho  a A, x a a b Ví dụ. Phần tử chận trên của {g,j} là a. c d Tại sao không phải là b? e f j g h i
  51. Chặn trên, chặn dưới 51 Định nghĩa. Cho (S, ) là poset và A  S. Chặn trên nhỏ nhất của A là phần tử chặn trên x của A sao cho mọi chặn trên y của A, ta đều có y  x Chặn dưới lớn nhất của A là phần tử chặn dưới x của A sao cho mọi chặn dưới y của A, ta có y x Chặn trên nhỏ nhất của : supA Chặn dưới lớn nhất: infA
  52. Chương 3 Chặn trên, chặn dưới Ví dụ Chặn trên nhỏ nhất của {i,j} là d Ví dụ. Chặn dưới chung lớn nhất của a b {g,j} là gì? c d e f j g h i
  53. Chặn trên, chặn dưới 53 Chặn trên nhỏ nhất (nếu có) của A = {a, b} đựơc ký hiệu bởi a  b Chặn dưới lớn nhất (nếu có) của A = {a, b} đựoc ký hiệu bởi a  b a b Ví dụ. i  j = d c d e f j Ví dụ. b  c = f g h i
  54. 54 Sắp xếp topo Chú ý. Mỗi poset hữu hạn đều có phần tử tối tiểu a1. shoes belt jacket Ví dụ shirt là socks trousers cravat watch phần tử tối tiểu uwear shirt  Sau khi loại bỏ phần tử a1 thì tập còn lại vẫn là poset
  55. 55 Sắp xếp topo  Gọi a2 là phần tử tối tiểu của poset mới. shoes belt jacket underwear socks trousers cravat watch phần tử tối tiểu mới uwear shirt Không có chặn trên của a1 và a2
  56. 56 Tiếp tục quá trình này cho đến khi không còn phần tử nào nữa Và cuối cùng chúng ta sẽ có 1 sự sắp xếp a1, a2, , am shoes belt jacket socks trousers Caravat watch uwear shirt Gọi là sắp xếp topo