Toán học - Chương II: Quan hệ

13/04/2010 1 Chương II ỆQUAN H Cho tập hợp X ≠ ∅. Một quan hệ hai ngôi trên X là một tập hợp con ℜ của X2 Nếu (x y)∈ℜ ta 1. Định nghĩa và ký hiệu . , , viết xℜy. Nếu (x,y)∉ℜ,ta viết . Ví dụ 1: Cho X = {1 2 3 4} và ℜ = {(1 1) (1 3) (2 1) x yℜ , , , , , , , , , (3,1)}. Ta thấy ℜ là một quan hệ trên X và 1ℜ1, 1ℜ3, 2ℜ1, 3ℜ1 nhưng , , ... 13/04/2010 2 1 2ℜ 2 2ℜ 2 3ℜ Ví dụ 2: Quan hệ có cùng trị tuyệt đối trên tập hợp các số 1. Định nghĩa và ký hiệu thực R là một quan hệ hai ngôi ℜ trên tập hợp R: ∀x, y ∈ R, xℜy ⇔ |x| = |y| 13/04/2010 3 Ví dụ 3: Quan hệ nhỏ hơn hay bằng trên tập các số hữu tỉ 1. Định nghĩa và ký hiệu Q là một quan hệ hai ngôi trên Q: ∀x, y ∈ Q, x ℜ y ⇔ x ≤ y 13/04/2010 4 13/04/2010 2 Ví dụ 4: Cho trước một số nguyên dương n, ta định nghĩa một 1. Định nghĩa và ký hiệu quan hệ hai ngôi trên Z như sau: ∀x, y ∈ Z, xℜy ⇔ x – y chia hết cho n. Quan hệ này được gọi là quan hệ đồng dư modulo n. Nếu xℜy ta viết: x ≡ y (mod n) Chẳng hạn, với n = 7 ta có 9 ≡ 2 (mod 7) và 3 ≡ 10 (mod 7) nhưng 3 ≅ 6 (mod 7). 13/04/2010 5 Cho tập hợp hữu hạn X = {x1, x2, ..., xn}. Khi đó mỗi quan hệ hai ngôi ℜ trên X có thể được 2. Ma trận biểu diễn quan hệ hai ngôi , biểu diễn bởi một ma trận vuông cấp n, ký hiệu là M(ℜ), trong đó: M(ℜ) = rij với 1 0 i j ij x x r ℜ⎧⎪= ⎨ ℜ⎪ 13/04/2010 6 i jx x⎩ Ví dụ: Xét X = {1, 2, 3, 4} và quan hệ hai ngôi ℜ như 2. Ma trận biểu diễn quan hệ hai ngôi trong Ví dụ 1 ở trên. Ma trận biểu diễn của ℜ là: ( ) 1 0 1 0 1 0 0 0 1 0 0 0 M ⎛ ⎞⎜ ⎟⎜ ⎟ℜ = ⎜ ⎟⎜ ⎟ 13/04/2010 7 0 0 0 0⎝ ⎠ Cho ℜ là một quan hệ hai ngôi trên X. 3.1. Tính phản xạ: 3. Tính chất của quan hệ hai ngôi Ta nói quan hệ hai ngôi ℜ có tính phản xạ nếu với mọi x ∈ X, x luôn luôn có quan hệ ℜ với x. Như vậy: ℜ phản xạ ⇔∀x ∈ X, xℜx Suy ra: ℜ không phản xạ ⇔ ∃x ∈ X, x x 13/04/2010 8 ℜ 13/04/2010 3 3.1. Tính phản xạ: • Gọi ΔX là đường chéo chính của X2: 3. Tính chất của quan hệ hai ngôi ΔX = {(x, x) | x ∈ X} Khi ấy quan hệ ℜ trên X là phản xạ khi và chỉ khiℜ ⊃ ΔX. 1 13/04/2010 9 1 2 3 4 4 3 2 3.1. Tính phản xạ: • Nếu X hữu hạn thì ℜ phản xạ khi và chỉ khi ể ễ ố 3. Tính chất của quan hệ hai ngôi ma trận bi u di n M(ℜ) có các hệ s trên đường chéo đều là 1. 13/04/2010 10 Cho ℜ là một quan hệ hai ngôi trên X. 3.2. Tính đối xứng: 3. Tính chất của quan hệ hai ngôi Ta nói quan hệ hai ngôi ℜ có tính đối xứng khi với mọi x, y ∈ X, nếu x có quan hệ ℜ với y thì y cũng có quan hệ ℜ với x. Như vậy: ℜ đối xứng ⇔ (∀x, y ∈ X, xℜy ⇒ yℜx). Suy ra: ℜ không đối xứng ⇔ (∃x,y∈X, xℜy và y x) 13/04/2010 11 ℜ 3.2. Tính đối xứng: • Quan hệ ℜ trên A là đối xứng khi và chỉ khi ố 3. Tính chất của quan hệ hai ngôi nó đ i xứng nhau qua đường chéo Δ của A × A. 3 2 1 13/04/2010 12 1 2 3 4 4 13/04/2010 4 3.2. Tính đối xứng: • Nếu X hữu hạn thì ℜ đối xứng khi và chỉ khi ể ễ ố 3. Tính chất của quan hệ hai ngôi ma trận bi u di n M(ℜ) là một ma trận đ i xứng. Ví dụ Quan hệ ℜ1 = {(1,1), (1,2), (2,1)} trên tập A={1 2 3 4} là đối xứng, , , . 13/04/2010 13 Cho ℜ là một quan hệ hai ngôi trên X. 3.3. Tính phản đối xứng: 3. Tính chất của quan hệ hai ngôi Ta nói quan hệ hai ngôi ℜ có tính phản đối xứng nếu đối với hai phần tử khác nhau bất kỳ x, y ∈ X không thể xảy ra đồng thời x có quan hệ ℜ với y và y có quan hệ ℜ với x. Như vậy: ℜ phản đối xứng⇔ (∀x, y ∈ X, x ≠ y và xℜy⇒ y x)ℜ ⇔ (∀x, y ∈ X, x ℜ y và yℜx ⇒ x = y). Suy ra: R không phản đối xứng ⇔ (∃x, y ∈ X, x ≠ y và xℜy và yℜx). 13/04/2010 14 3.3. Tính phản đối xứng: • Quan hệ ℜ là phản xứng khi và chỉ khi chỉ có ầ ằ ố 3. Tính chất của quan hệ hai ngôi các ph n tử n m trên đường chéo là đ i xứng qua Δ của A × A. 3 2 1 13/04/2010 15 1 2 3 4 4 3.3. Tính phản đối xứng: • Với X hữu hạn thì ℜ phản đối xứng khi và chỉ ể ễ 3. Tính chất của quan hệ hai ngôi khi ma trận bi u di n M(ℜ) = (rij) thỏa: ∀1 ≤ i ≠ j ≤ n, rji = 1 ⇒ rij = 0. Ví dụ: Quan hệ ≤ trên Z phản xứng vì: (a ≤ b) ∧ (b ≤ a) → (a = b) 13/04/2010 16 13/04/2010 5 Cho ℜ là một quan hệ hai ngôi trên X. 3.4. Tính bắc cầu: 3. Tính chất của quan hệ hai ngôi Ta nói quan hệ hai ngôi ℜ có tính bắc cầu khi đối với các phần tử bất kỳ x, y, z ∈ X, nếu x có quan hệ ℜ với y và y có quan hệ ℜ với z thì x cũng có quan hệ ℜ với z. Như vậy: R bắc cầu⇔ (∀x y z ∈ X xℜy và yℜz⇒ xℜz) , , , Suy ra: R không bắc cầu ⇔ (∃x,y,z ∈ X, xℜy và yℜz và x z). 13/04/2010 17 ℜ 3.4. Tính bắc cầu: Ví dụ 3. Tính chất của quan hệ hai ngôi •Quan hệ ℜ ={(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 ( ≤ b) (b ≤ ) ( ≤ )a ∧ c → a c (a | b) ∧ (b | c) → (a | c) 13/04/2010 18 4.1. Định nghĩa: Một quan hệ ℜ trên tập hợp X được gọi là một quan hệ tương đương nếu ℜ thỏa các tính chất phản xạ đối xứng và bắc cầu 4. Quan hệ tương đương , . Ví dụ: 1) Quan hệ bằng nhau trên một tập hợp X ≠ ∅ bất kỳ là một quan hệ tương đương X. 2) Quan hệ nhỏ hơn hay bằng thông thường trên các tập hợp số không phải là một quan hệ tương đương. ề3) Quan hệ “tương đương logic” trên tập hợp các dạng mệnh đ là một quan hệ tương đương. 4) Quan hệ đồng dư modulo n (n nguyên dương) là một quan hệ tương đương trên Z. 13/04/2010 19 4.2. Định nghĩa: Giả sử ℜ là một quan hệ tương đương trên X và ấ 4. Quan hệ tương đương x ∈ X. Khi y lớp tương đương chứa x, ký hiệu bởi hay [x], là tập hợp gồm tất cả các phần tử y của X có quan hệ ℜ với x. Như vậy: = {y ∈ X | yℜx} x x 13/04/2010 20 13/04/2010 6 4.3. Định lý: Giả sử ℜ là một quan hệ tương đương trên X. 4. Quan hệ tương đương Khi đó: •∀x ∈ X, x ∈ . •∀x, y ∈ X, xℜy ⇔ = •∀x, y ∈ X, ∩ ≠ ∅⇔ = x x y x y yx 13/04/2010 21 5.1. Định nghĩa: Một quan hệ ℜ trên tập hợp X được gọi là một quan hệ thứ tự nếuℜ thỏa các tính chất phản xạ phản xứng và bắc cầu 5. Quan hệ thứ tự , . Khi ấy ta nói X là một tập hợp sắp thứ tự (hay có thứ tự). Ví dụ: 1) Quan hệ nhỏ hơn hay bằng thông thường trên các tập hợp số là một quan hệ thứ tự. 2) Cho tập hợp E ≠ ∅. Trên tập hợp P(E) ta có quan hệ: ∀A, B ∈ P(E), A ℜ B⇔ A ⊆ B 3) Trên tập N các số tự nhiên ta định nghĩa quan hệ ước số: xℜy ⇔ x|y. Quan hệ thứ tự trên vẫn được ký hiệu bởi x|y. 13/04/2010 22 5.2. Định nghĩa: Một quan hệ thứ tự trên X được gọi là toàn phần nếu hai phần tử bất kỳ đều so sánh được với nhau nghĩa là: 5. Quan hệ thứ tự ≺ , ∀x, y ∈ X, x y hay y x. Trong trường hợp ngược lại, ta nói là một quan hệ thứ tự bộ phận. Nói cách khác, quan hệ thứ tự là bộ phận nếu tồn tại hai phần tử không so sánh được với nhau, nghĩa là: ∃x, y ∈ X, x y và y x. Ví d ≺ ≺ ≺ ≺ ≺≺ ụ: 1) N, Z, Q, R với thứ tự ≤ thông thường là những tập hợp sắp thứ tự toàn phần. 2) (P(E), ⊆) là tập được sắp thứ tự bộ phận nếu E có ít nhất 2 phần tử. 13/04/2010 23 5.3. Định nghĩa: Xét một tập hợp có thứ tự (X, ) và x, y là 2 5. Quan hệ thứ tự ≺ phần tử bất kỳ của X. Khi đó ta nói: 1) y là trội x hay x được trội bởi y nếu x y. 2) 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. 13/04/2010 24 ≺ ≺ 13/04/2010 7 5.4. Định nghĩa: Biểu đồ Hasse của một tập hợp hữu hạn có thứ ồ 5. Quan hệ thứ tự tự (X, ) bao g m: 1) 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. 2) 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. 13/04/2010 25 5.4. Định nghĩa: Ví dụ: 5. Quan hệ thứ tự 1) Biểu đồ Hasse của U12 = {x ∈ N | x|n} với quan hệ “ | ” được cho bởi: 13/04/2010 26 5.4. Định nghĩa: Ví dụ: 5. Quan hệ thứ tự 2) Với E = {a, b, c} thì biểu đồ Hasse của (P(E), ⊆) có dạng: 13/04/2010 27 5.4. Định nghĩa: Ví dụ: 5. Quan hệ thứ tự 3) 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: 13/04/2010 28 13/04/2010 8 5.5. Định nghĩa: Xét (X, ) là một tập được sắp và a, b ∈ X. Ta nói: 5. Quan hệ thứ tự ≺ 1) a là phần tử nhỏ nhất (tương ứng phần tử lớn nhất) của X, ký hiệu bởi min X (tương ứng, bởi max X), nếu a nhỏ hơn hay bằng (tương ứng, lớn hơn hay bằng) mọi phần tử trong X. Như vậy: a = min X ⇔∀x ∈ X, a x; a = max X ⇔∀x ∈ X, x a. 13/04/2010 29 ≺ ≺ 5.5. Định nghĩa: 2) b là phần tử tối tiểu (tương ứng, phần tử tối đại) của 5. Quan hệ thứ tự X, nếu b là không là trội thực sự của (tương ứng không được trội thực sự bởi) phần tử nào của X. Như vậy: b là phần tử tối tiểu của X⇔ (∀x ∈ X, x b⇒ x = b);≺ b là phần tử tối đại của X ⇔ (∀x ∈ X, b x⇒ x = b). 13/04/2010 30 ≺ 5.5. Định nghĩa: Chú ý: Nếu (X, ) là một tập được sắp thứ tự toàn phần 5. Quan hệ thứ tự ≺ thì khái niệm tối tiểu trùng với khái niệm nhỏ nhất, và khái niệm tối đại trùng với khái niệm lớn nhất. 13/04/2010 31 5.6. Định lý: Trong một tập hợp sắp thứ tự X, phần tử nhỏ 5. Quan hệ thứ tự nhất a = min X, nếu tồn tại, là phần tử tối tiểu duy nhất. Suy ra a cũng là phần tử nhỏ nhất duy nhất. Kết luận tương tự cho phần tử lớn nhất và phần tử tối đại. 13/04/2010 32 13/04/2010 9 5.7. Định lý: Trong một tập hợp sắp thứ tự hữu hạn ta có: 5. Quan hệ thứ tự 1) Mọi phần tử trội (tương ứng, được trội bởi) một phần tử tối tiểu (tương ứng, tối đại). 2) Nếu a là phần tử tối tiểu (tương ứng tối đại), duy nhất của X thì a là phần tử nhỏ nhất (tương ứng, phần tử lớn nhất). 13/04/2010 33 5.8. Thứ tự tự điển: Cho (A, ) là một tập hữu hạn, khác rỗng, có thứ ầ ẫ 5. Quan hệ thứ tự ≺ tự toàn ph n, gọi là tập m u tự. Gọi S là tập hợp tất cả các chuỗi kí tự có dạng s = a1a2 ... an với n ∈ N và a1, a2, ..., an ∈ A (với n = 0 ta có chuỗi rỗng ∅ không có ký tự nào). Trong S ta qui ước: với s = a1a2 ... an và t = b1b2 ... bm: s = t ⇔ (n = m và ai = bi, i = ) Trên S ta định nghĩa quan hệ như sau: 13/04/2010 34 1,n ≺ 5.8. Thứ tự tự điển: 1) ∀s ∈ S , ∅ s; 5. Quan hệ thứ tự ≺ 2) ∀s, t ∈ S , s = a1a2 ... an và t = b1b2 ... bm Khi đó là quan hệ thứ tự toàn phần trên S Ta 1 1 1 1 , , 1, ; min{ , }, ,..., , i i k k k k n m a b i ns t k n m a b a b a b− − ⎡ ≤ = =⇔ ⎢∃ ≤ = = <⎣ ≺ ≺ . gọi đây là thứ tự tự điển trên S ứng với tập mẫu tự (A, ). 13/04/2010 35 ≺