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

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

1. Quan hệ
2. Quan hệ 2 ngôi • Cho một tập hợp X khác rỗng. • Một quan hệ 2 ngôi trên X là một tập hợp con R của X2. • Cho 2 phần tử x và y của X, ta nói x có quan hệ R với y khi và chỉ khi (x,y) R, và viết là x R y x R y (x,y) R • Khi x không có quan hệ R với y, ta viết:
3. Ví dụ • Trên tập hợp X = { 1,2,3,4} , xét quan hệ 2 ngôi R được định nghĩa bởi: R = { (1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)} • Trên tập hợp các số nguyên Z ta định nghĩa một quan hệ 2 ngôi R như sau: x R y nếu và chỉ nếu x-y là số chẳn. (R = { (x,y) Z2 : x-y = 2k với k Z } ) • ∀x, y ∈ R, xRy ⇔ |x| = |y| • ∀x, y ∈ Q, xRy ⇔ x ≤ y • ∀x, y ∈ Z, xRy ⇔ a – b chia hết cho n x ≡ y (mod n).
4. Quan hệ • Người ta còn định nghĩa một quan hệ (2 ngôi) giữa một tập hợp A và một tập hợp B là một tập hợp con của AxB. • Tổng quát hơn, ta có thể định nghĩa một quan hệ giữa các tập hợp A1, A2, . . ., An là một tập hợp con của A1 x A2 x . . . x An. Như vậy, khi R là một quan hệ giữa các tập A1, A2, . . ., An thì mỗi phần tử của R là một bộ n (a1, a2, . . ., an) với ai Ai (i=1, , n).
5. Xác định một quan hệ • Liệt kê: liệt kê tất cả các cặp hay bộ phần tử có quan hệ R (tức là thuộc R) • Nêu tính chất đặc trưng cho quan hệ R, tức là tính chất hay tiêu chuẩn để xác định các phần tử thuộc R hay không
6. Các tính chất của quan hệ 2 ngôi • Giả sử R là một quan hệ 2 ngôi trên một tập hợp X • Ta nói quan hệ R có tính phản xạ (reflexive) nếu và chỉ nếu x R x với mọi x X. • Ta nói quan hệ R có tính đối xứng (symmetric) nếu và chỉ nếu x R y y R x với mọi x,y X • Ta nói quan hệ R có tính phản xứng (antisymmetric) nếu và chỉ nếu (x R y và y R x) x = y với mọi x,y X. • Ta nói quan hệ R có tính truyền hay bắc cầu (transitive) nếu và chỉ nếu (x R y và y R z) x R z với mọi x,y,z X
7. Ví dụ • Quan hệ trên tập hợp các số thực • Trên tập hợp X = { 1,2,3,4} , xét quan hệ 2 ngôi R được định nghĩa bởi: R = { (1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)} • Trên tập hợp các số nguyên Z ta định nghĩa một quan hệ 2 ngôi R như sau: x R y nếu và chỉ nếu x-y là số chẳn
8. Biểu diễn quan hệ 2 ngôi dưới dạng ma trận • Giả sử R là một quan hệ 2 ngôi giữa một tập hợp hữu hạn A = { a1, a2, , am} và một tập hữu hạn B = { b1, b2, , bm} • Quan hệ R có thể được biểu diễn bởi ma trận MR = [mij] gồm m dòng và n cột (tức là ma trận cấp mxn): – mij = 1 nếu (ai , bj) R – mij = 0 nếu (ai , bj) Ï R
9. Quan hệ tương đương • Một quan hệ 2 ngôi R trên một tập hợp X được gọi là một quan hệ tương đương nếu và chỉ nếu nó thỏa 3 tính chất: phản xạ, đối xứng, truyền.
10. Lớp tương đương và tập hợp thương • Với mỗi phần tử x X, ta định nghĩa lớp tương đương chứa x, ký hiệu , là tập hợp tất cả những phần tử (thuộc X) có quan hệ R với x • Tập hợp các lớp tương đương của quan hệ tương đương R trên X này (là một tập con của P(X)) được gọi là tập hợp thương (của quan hệ tương đương R trên X)
11. Quan hệ thứ tự • Một quan hệ 2 ngôi R trên một tập hợp X (khác rỗng) được gọi là một quan hệ thứ tự (hay vắn tắt, là một thứ tự) nếu và chỉ nếu nó có 3 tính chất: phản xạ, phản xứng, truyền • Khi đó ta cũng nói tập hợp X là một tập có thứ tự • Nếu có thêm tính chất: với mọi x, y X ta có xRy hay yRx thì ta nói R là một quan hệ thứ tự toàn phần trên X.
12. Quan hệ thứ tự • Nếu trên X có nhiều quan hệ thứ tự thì khi xét đến thứ tự trên X ta phải nói rõ thứ tự nào, và ta thường viết tập hợp X có thứ tự dưới dạng một cặp (X,R); trong đó R là quan hệ thứ tự đang xét trên X • Nếu (X,R) là một tập hợp có thứ tự và A  X thì quan hệ thứ R thu hẹp trên tập A, cũng được ký hiệu là R (nếu không gây ra nhầm lẫn), là một quan hệ thứ tự trên A (X,R) thứ tự và A  X (A,R) thứ tự
13. Ví dụ • Quan hệ nhỏ hơn hay bằng ≤ • Cho tập hợp E ≠ ∅. Trên tập hợp P(E) ta xét quan hệ: ∀A, B ∈ P(E), A R B ⇔ A ⊂ B • Trên tập N các số tự nhiên ta định nghĩa quan hệ ước số xRy ⇔ x|y x|y có nghĩa x là một ước của y, hay y chia hết cho x
14. Ví dụ • Un= {a N: a|n} với quan hệ R: xRy x|y • Un={ } • R={ .}
15. Ví dụ • Un= {a N: a|n} với quan hệ R: xRy x|y • U12={ 1,2,3,4,6,12} • R={{1,1},{1,2} ,{1,3} ,{1,4} ,{1,6} ,{1,12}, {2,2},{2,4},{2,6},{2,12},{3,3},{3,6}, {3,12},{4,4},{4,12},(6,6}{6,12}, {12,12}}
16. Trội, trội trực tiếp Xét một tập hợp có thứ tự (X, ) và x, y là 2 phần tử bất kỳ của X. Khi đó ta nói: – y trội x hay x được trội bởi y nếu x ≤ y – y là trội trực tiếp của x nếu y ≠ x, y trội x và không tồn tại một trội z của x sao cho x < z < y
17. Quan hệ thứ tự • Cho (X, ) là một tập hợp có thứ tự, và A  X – a A là một phần tử nhỏ nhất của tập hợp A x A ta có : a x – a A là một phần tử lớn nhất của tập hợp A x A ta có : x a – a A là một phần tử tối tiểu của tập hợp A không tồn tại x A sao cho x a và x a – a A là một phần tử tối đại của tập hợp A không tồn tại x A sao cho x a và a x
18. Quan hệ thứ tự • Xet tập A = {1,2,3,4} với quan hệ R: xRy x|y • Phần tử nhỏ nhất là 1 (vì 1 là ước của tất cả các phần tử của A) • Phần tử tối tiểu là 1 (vì không có phần tử nào là ước của 1) • Phần tử tối đại là 3, 4 (vì 3, 4 không là ước của phần tử nào khác nó trong A) • Phần tử lớn nhất không có
19. Ví dụ • xét tập hợp X = { 1,2,3} với quan hệ 2 ngôi r được cho bởi r = { (1,1), (2,2), (3,3), (1,2), (3,2)} • Trong tập hợp có thứ tự (Z , ), tập hợp A = { m Z| m2 < 100} • Trong tập hợp có thứ tự (R, ), tập hợp A = { x R| x2 < 100}
20. Quan hệ thứ tự • Phần tử nhỏ nhất (lớn nhất) của một tập hợp, nếu có, là duy nhất.Ta ký hiệu phần tử nhỏ nhất của một tập hợp A là min A hay min (A), và ký hiệu phần tử lớn nhất của A là max A hay max (A). • Phần tử tối tiểu (tối đại) của một tập hợp có thứ tự không nhất thiết là duy nhất • Phần tử lớn nhất (nhỏ nhất) của một tập hợp, nếu có, là phần tử tối đại (tối tiểu) duy nhất của tập hợp đó
21. Quan hệ thứ tự - chận dưới • Cho (X, ) là một tập hợp có thứ tự, và A  X – Ta gọi một phần tử x X là một chận dưới của tập hợp A nếu và chỉ nếu với mọi a A ta có : x a – Chận dưới lớn nhất (nếu có), tức là phần tử lớn nhất trong tập hợp tất cả những chận dưới của A được ký hiệu là inf (A)
22. Quan hệ thứ tự - chận trên • Cho (X, ) là một tập hợp có thứ tự, và A  X – Ta gọi một phần tử x X là một chận trên của tập hợp A nếu và chỉ nếu với mọi a A ta có : a x – Chận trên nhỏ nhất (nếu có), tức là phần tử nhỏ nhất trong tập hợp tất cả những chận trên, của A được ký hiệu là sup (A)
23. Thứ tự tốt • Một tập hợp có thứ tự được gọi là có thứ tự tốt (hay được sắp tốt) nếu và chỉ nếu mọi tập con khác rỗng đều có phần tử nhỏ nhất. – Tập hợp có thứ tự (N, ) là một tập hợp được sắp tốt. – Tập hợp có thứ tự (Z, ) không phải là một tập hợp được sắp tốt vì Z không có phần tử nhỏ nhất.
24. Biểu đồ Hasse • Biểu đồ Hasse của một tập hợp hữu hạn có thứ tự (X, ≤) bao gồm: – Một tập hợp các điểm trong mặt phẳng tương ứng 1-1 với X, gọi là các đỉnh. – Một tập hợp các cung có hướng nối một số đỉnh: hai đỉnh x, y được nối lại bởi một cung có hướng từ x tới y nếu y là trội trực tiếp của x
25. • Biểu đồ Hasse của U12 = {x ∈ N : x|n}
26. • Với E = {a, b, c} thì biểu đồ Hasse của (P(E), ⊂) có dạng:
27. • Biểu đồ Hasse của {1, 2, 3, 4, 5} với thứ tự thông thường có dạng của một dây chuyền:
28. Dàn • Cho (L, ) là một tập hợp có thứ tự. Ta nói (L, ) là một dàn nếu và chỉ nếu với mọi a, b L, tập hợp { a,b} có chận dưới lớn nhất và có chận trên nhỏ nhất; tức là tồn tại sup(a,b) và inf(a,b) • Ký hiệu ab và a  b để chỉ sup(a,b) và inf(a,b) – a  b = sup(a,b) – a  b = inf(a,b)
29. Ví dụ • Tập hợp có thứ tự toàn phần là một dàn, với a  b = max(a,b) và a  b = min(a,b). • Trong dàn (L, ), phần tử sup(a,b) = a  b được đặc trưng bởi 2 tính chất sau: – a a  b và b a  b –  c L : (a c và b c) (a  b c) • Trong dàn (L, ), phần tử inf(a,b) = a  b được đặc trưng bởi 2 tính chất sau: – a  b a và a  b b –  c L : (c a và c b) (c a  b )
30. Ví dụ • Cho E là một tập hợp • Tập hợp (P(E),  ) là một dàn. • Với mọi A, B P(E), ta thấy A B và A B lần lượt chính là chận trên nhỏ nhất và chận dưới lớn nhất theo thứ tự  A  B = A B A  B = A B
31. Ví dụ • (N,| ) là một tập hợp có thứ tự (|: chia hết) • Với 2 số tự nhiên a và b: – chận trên nhỏ nhất chính là bội số chung nhỏ nhất của chúng – chận dưới lớn nhất chính là ước số chung lớn nhất của chúng • Vậy (N,| ) là một dàn
32. Ví dụ 3 • Các tập hợp có thứ tự được biểu diễn bởi các biểu đồ Hasse trong hình dưới đây có phải là dàn hay không:
33. Dàn con • Cho (L, ) là một dàn và B là một tập hợp con của L • B là một dàn con của L khi và chỉ khi với mọi a,b B ta có a  b B và a  b B
34. Ví dụ • Xem dàn L có biểu đồ Hasse như sau:
35. Đồng cấu dàn • Cho (L, ) và (M, ) là các dàn • Một ánh xạ f : L M được gọi là một đồng cấu dàn nếu và chỉ nếu " x,y L : x y f(x) f(y) • Trường hợp f có thêm tính chất song ánh thì ta nói f là một đẳng cấu dàn • f : L M là một đẳng cấu dàn thì với mọi x, y L: – f (x  y) = f(x)  f(y) – f (x  y) = f(x)  f(y)
36. Ví dụ • Xem hai dàn L và M có biểu đố Hasse: • Ánh xạ f : L M được định nghĩa bởi : f(1) = b, f(2) = e, f(3) = c, f(4) = v là một đồng cấu dàn.
37. • Ánh xạ g : L M được định nghĩa bởi : – g(1) = a, g(2) = b, g(3) = d, g(4) = v – không phải là một đồng cấu dàn vì g(2)  g(3) = b  d = c, mà g(23) = g(4) = v c.
38. Tính chất của dàn 1 • Với mọi phần tử x, y, z thuộc dàn (L, ) ta có 1. x  x = x , x  x = x (tính lũy đẳng) 2. x  y = y  x , x  y = y  x (tính giao hoán) 3. x  (y  z) = (x  y)  z (tính kết hợp) x  (y  z) = (x  y)  z 4. x y (x  y = y) (x  y = x) 5. x  (x  y) = x = x  (x L y)
39. Tính chất của dàn 2 • Với mọi phần tử a, b, c, d thuộc dàn (L, ) ta có 1. (a b) (a  c b  c và a  c b  c) 2. (a b và c d) (a  c b  d và a  c b  d)
40. Tính chất của dàn 3 • Với mọi phần tử x, y, z thuộc dàn (L, ) ta có : 1. x  (y  z)  (x  y)  (x  z) x  (y  z) (x  y)  (x  z) 2. (x z)  x (y  z) (x  y)  z
41. Tóm lại • Một quan hệ 2 ngôi trên X là một tập hợp con R của X2 • Quan hệ tương đương: phản xạ, đối xứng và truyền hay bắc cầu. • Quan hệ thứ tự: phạn xạ, phản xứng và bắc cầu. • Cho (L, ) là một tập hợp có thứ tự. Ta nói (L, ) là một dàn nếu và chỉ nếu với mọi a, b L, tập hợp { a,b} có chận dưới lớn nhất và có chận trên nhỏ nhất; tức là tồn tại sup(a,b) và inf(a,b)
42. Câu hỏi • Tập các số tự nhiên N với quan hệ đồng dư có phải là quan hệ tương đương hay không tại sao? • U12= {a N: a|12} với quan hệ R: xRy x|y có phải là tập sắp thứ tự hay không tại sao? • Vẽ biều đồ Hasse của tập hợp U12 trên. • Cho biết tập hợp U12 trên có phải là một dàn không tại sao?