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

13/04/2010 Chương II 1. Định nghĩa và ký hiệu Cho tậphợpX≠∅.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 QUAN HỆ viếtxℜy. Nếu (x,y)∉ℜ,ta viết.xℜy Ví dụ 1: Cho X = {1, 2, 3, 4} và ℜ = {(1,1), (1,3), (2, 1), (3,1)}. Ta thấy ℜ là một quan hệ trên X và 1ℜ1, 1ℜ3, 2ℜ1, 3ℜ1nhưng12ℜ ,22ℜ ,23ℜ ... 13/04/2010 2 1. Định nghĩa và ký hiệu 1. Định nghĩa và ký hiệu Ví dụ 2: Ví dụ 3: Quan hệ có cùng trị tuyệt đối trên tập hợp các số Quan hệ nhỏ hơn hay bằng trên tập các số hữu tỉ thực R là một quan hệ hai ngôi ℜ trên tậphợp Q là một quan hệ hai ngôi trên Q: R: ∀x, y ∈ Q, x ℜ y ⇔ x ≤ y ∀x, y ∈ R, xℜy ⇔|x| = |y| 13/04/2010 3 13/04/2010 4 1 13/04/2010 1. Định nghĩa và ký hiệu 2. Ma trận biểu diễn quan hệ hai ngôi Ví dụ 4: Cho tậphợphữuhạnX={x1,x2, ..., xn}. Khi Cho trướcmộtsố nggyuyên dương n, ta định nghĩamột đó, mỗi quan hệ hai ngôi ℜ trên X có thể được quan hệ hai ngôi trên Z như sau: ∀x, y ∈ Z, xℜy ⇔ x – y chia hết cho n. biểudiễnbởimộtmatrận vuông cấpn,kýhiệu Quan hệ này đượcgọi là quan hệ đồng dư modulo n. là M(ℜ), trong đó: Nếuxℜytaviết: ⎧1 ℜ ⎪ xijx x ≡ yy( (mod n ) = ⎨ M(ℜ) = rij với r ij 0 ℜ ⎪ xijx Chẳng hạn, vớin=7tacó9≡ 2(mod7)và3≡ 10 ⎩ (mod 7) nhưng 3 ≅ 6(mod7). 13/04/2010 5 13/04/2010 6 2. Ma trận biểu diễn quan hệ hai ngôi 3. Tính chất của quan hệ hai ngôi Ví dụ: Cho ℜ là một quan hệ hai ngôi trên X. Xét X={1, 2, 3, 4} và quan hệ hai ngôi ℜ như 3.1. Tính phản xạ: trong Ví dụ 1 ở trên. Ma trậnbiểudiễncủa ℜ là: Ta nói quan hệ hai ngôi ℜ có tính phảnxạ nếu ⎛⎞1010 vớimọix∈ X, x luôn luôn có quan hệ ℜ vớix. ⎜⎟ 1000 Như vậy: M ()ℜ=⎜⎟ ⎜⎟1000 ℜ phản xạ ⇔ ∀x ∈ X, xℜx ⎜⎟ ⎝⎠0000 Suy ra: ℜ không phản xạ ⇔∃x ∈ X, x ℜ x 13/04/2010 7 13/04/2010 8 2 13/04/2010 3. Tính chất của quan hệ hai ngôi 3. Tính chất của quan hệ hai ngôi 3.1. Tính phảnxạ: 3.1. Tính phảnxạ: •Gọi Δ là đường chéo chính củaX2: •NếuXhữuhạnthìℜ phảnxạ khi và chỉ khi X ma trận biểudiễnM(ℜ) có các hệ số trên Δ = {(x, x) | x ∈ X} X đường chéo đềulà1. Khi ấyquanhệ ℜ trên X là phảnxạ khi và chỉ khi ℜ⊃ΔX. 1 2 3 4 123 4 13/04/2010 9 13/04/2010 10 3. Tính chất của quan hệ hai ngôi 3. Tính chất của quan hệ hai ngôi Cho ℜ là một quan hệ hai ngôi trên X. 3.2. Tính đốixứng: •Quanhệ ℜ trên A là đốixứng khi và chỉ khi 3.2. Tính đối xứng: nó đốixứng nhau qua đường chéo Δ của A × Ta nói quan hệ hai ngôi ℜ có tính đốixứng khi A. vớimọix,y∈ X, nếu x có quan hệ ℜ vớiythìy cũng có quan hệ ℜ vớix.Như vậy: 1 ℜ đối xứng ⇔ (∀x, y ∈ X, xℜy ⇒ yℜx). 2 3 Suy ra: 4 ℜ không đối xứng ⇔ (∃x,y∈X, xℜy và yℜ x) 1234 13/04/2010 11 13/04/2010 12 3 13/04/2010 3. Tính chất của quan hệ hai ngôi 3. Tính chất của quan hệ hai ngôi 3.2. Tính đốixứng: Cho ℜ là một quan hệ hai ngôi trên X. •NếuXhữuhạnthìℜ đốixứng khi và chỉ khi 3.3. Tính phản đối xứng: ma trận biểudiễnM(ℜ)làmộtmatrận đối xứng. Ta nói quan hệ hai ngôi ℜ có tính phản đốixứng nếu đốivớihaiphầntử khác nhau bấtkỳ x, y ∈ X không Ví dụ thể xảyrađồng thời x có quan hệ ℜ vớiyvàycóquan hệ ℜ vớix.Như vậy: Quan hệ ℜ1 = {(1,1), (1,2), (2,1)} trên tập A={1,2,3,4} là đối xứng. ℜ phản đốiix xứng ⇔ (∀x, y ∈ X, x ≠ yvàxy và xℜy ⇒ yx)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 13 13/04/2010 14 3. Tính chất của quan hệ hai ngôi 3. Tính chất của quan hệ hai ngôi 3.3. Tính phản đốixứng: 3.3. Tính phản đốixứng: •Quanhệ ℜ là phảnxứng khi và chỉ khi chỉ có •VớiXhữuhạnthìℜ phản đốixứng khi và chỉ các phầntử nằmtrênđường chéo là đốixứng khi ma trận biểudiễnM(ℜ)=(rij)thỏa: qua Δ của A × A. ∀1 ≤ i ≠ j ≤ n, rji = 1 ⇒ rij = 0. 1 Ví dụ: 2 Quan hệ ≤ trên Z phản xứng vì: 3 (a ≤ b) ∧ (b ≤ a) → (a = b) 4 1234 13/04/2010 15 13/04/2010 16 4 13/04/2010 3. Tính chất của quan hệ hai ngôi 3. Tính chất của quan hệ hai ngôi Cho ℜ là một quan hệ hai ngôi trên X. 3.4. Tính bắccầu: Ví dụ 3.4. Tính bắc cầu: •Quan hệ ℜ ={(1,1),(1,2),(2,1),(2,2),(1,3),(2,3)} Ta nói quan hệ hai ngôi ℜ có tính bắccầu khi đốivới trên tập A = {1, 2, 3, 4} có tính bắccầu. các phầntử bấtkỳ x, y, z ∈ X, nếuxcóquanhệ ℜ với yvàycóquanhệ ℜ vớizthìxcũng có quan hệ ℜ với z. Như vậy: •Quanhệ ≤ và “|”trên Z có tính bắccầu RbR bắccc cầu ⇔ (∀xyzx, y, z ∈ XxX, xℜyvàyy và yℜz ⇒ xℜz) (a ≤ b) ∧ (b ≤ c) → (a ≤ c) Suy ra: (a | b) ∧ (b | c) → (a | c) R không bắc cầu ⇔ (∃x,y,z ∈ X, xℜy và yℜz và x ℜ z). 13/04/2010 17 13/04/2010 18 4. Quan hệ tương đương 4. Quan hệ tương đương 4.1. Định nghĩa: 4.2. Định nghĩa: Mộtquanhệ ℜ trên tậphợpXđượcgọilàmột quan hệ tương Giả sử ℜ là một quan hệ tương đương trên X và đương nếu ℜ thỏa các tính chất phản xạ, đối xứng và bắc cầu. x ∈ X. Khi ấylớptương đương chứax,kýhiệu Ví dụ: 1) Quan hệ bằng nhau trên mộttậphợpX≠∅bấtkỳ là một bởix hay [x], là tậphợpgồmtấtcả các phầntử y quan hệ tương đương X. của X có quan hệ ℜ vớix.Như vậy: 2) Quan hệ nhỏ hơnhaybằng thông thường trên các tậphợpsố x = {y ∈ X | yℜx} không phảilàmột quan hệ tương đương. 3) Quan hệ “tương đương logic” trên tậphợpcácdạ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ộtquanhệ tương đương trên Z. 13/04/2010 19 13/04/2010 20 5 13/04/2010 4. Quan hệ tương đương 5. Quan hệ thứ tự 4.3. Định lý: 5.1. Định nghĩa: Giả sử ℜ là một quan hệ tương đương trên X. Mộtquanhệ ℜ trên tậphợpXđượcgọilà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. Khi đó: Khi ấy ta nói X là mộttậphợpsắpthứ tự (hay có thứ tự). •∀x ∈ X, x ∈ x. Ví dụ: •∀x, y ∈ X, xℜy ⇔ x = y 1) Quan hệ nhỏ hơnhaybằng thông thường trên các tậphợpsố là một quan hệ thứ tự. •∀x, y ∈ X, x ∩≠∅⇔y x = y 2) Cho tậphợpE≠∅.TrêntậphợpP(E)tacóquanhệ: ∀A, B ∈ P(E), A ℜ B ⇔ A ⊆ B 3) Trên tập N các số tự nhiên ta định nghĩaquanhệướcsố:xℜy ⇔ x|y. Quan hệ thứ tự trên vẫn đượckýhiệubởix|y. 13/04/2010 21 13/04/2010 22 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.2. Định nghĩa: 5.3. Định nghĩa: Mộtquanhệ thứ tự ≺trên X đượcgọi là toàn phầnnếuhaiphần tử bất kỳ đều so sánh được với nhau, nghĩa là: Xét một tập hợp có thứ tự (X, ≺ ) và x, y là 2 ∀x, y ∈ X, x ≺ y hay y ≺ x. phầntử bấtkỳ củaX.Khiđó ta nói: Trong trường hợpngượclại, ta nói≺ là mộtquanhệ thứ tự bộ phận. Nói cách khác, quan hệ thứ tự ≺ là bộ phậnnếutồntạihai phầntử không so sánh đượcvới nhau, nghĩalà:∃x, y ∈ X, x≺ y 1) y là trội xhayxđượctrội bởiynếux≺ y. và y≺ x. Ví dụ: 2) y là trội trực tiếp của x nếu y ≠ x, y trội x và 1) N, Z, Q, R vớithứ tự ≤ thông thường là những tậphợpsắp không tồntạimộttrộizcủa x sao cho x≺ z y. thứ tự toàn phần. ≺ 2) (P(E), ⊆)làtập đượcsắpthứ tự bộ phậnnếuEcóítnhất2 phầntử. 13/04/2010 23 13/04/2010 24 6 13/04/2010 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.4. Định nghĩa: 5.4. Định nghĩa: Biểu đồ Hasse củamộttậphợphữuhạncóthứ Ví dụ: tự (X,≺ ) bao gồm: 1) Biểu đồ Hasse củaU12={x∈ N | x|n} với 1) Mộttậphợp các điểmtrongmặtphẳng tương quan hệ “ | ” đượcchobởi: ứng1–1vớiX,gọi là các đỉnh. 2) Mộttậphợp các cung có hướng nốimộtsố đỉnh: hai đỉnh x, y được nối lại bởi một cung có hướng từ xtớiynếu y là trộitrựctiếpcủax. 13/04/2010 25 13/04/2010 26 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.4. Định nghĩa: 5.4. Định nghĩa: Ví dụ: Ví dụ: 2) Với E = {a, b, c} thì biểu đồ Hasse của(P(E), 3) Biểu đồ Hasse của {1, 2, 3, 4, 5} vớithứ tự ⊆)códạng: thông thường có dạng củamột dây chuyền: 13/04/2010 27 13/04/2010 28 7 13/04/2010 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.5. Định nghĩa: 5.5. Định nghĩa: Xét (X,≺ ) là mộttập đượcsắpvàa,b∈ X. Ta nói: 2) b là phầntử tốitiểu(tương ứng, phầntử tối đại) của 1)alàphầntử nhỏ nhất(tương ứng phầntử lớnnhất) X, nếu b là không là trộithựcsự của(tương ứng không củaX,kýhiệubởiminX(tương ứng, bởimaxX),nếu đượctrộithựcsự bởi) phầntử nào củaX.Như vậy: anhỏ hơnhaybằng (tương ứng, lớnhơnhaybằng) mọi blàphầntử tốitiểucủaX⇔ (∀x ∈ X, x≺ b ⇒ x=b); phần tử trong X. Như vậy: blàphầntử tối đạicủaX ⇔ (∀x ∈ X, b≺ x ⇒ x=b). a = min X ⇔∀x ∈ X, a ≺ x; a = max X ⇔∀x ∈ X, x ≺ a. 13/04/2010 29 13/04/2010 30 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.5. Định nghĩa: 5.6. Định lý: Chú ý: Nếu(X,≺ )làmộttập đượcsắpthứ tự toàn phần Trong một tập hợp sắp thứ tự X, phầntử nhỏ thìkháiniệmtốitiểu trùng vớikháiniệmnhỏ nhất, và nhấta=minX,nếutồntại, là phầntử tốitiểu khái niệmtối đại trùng với khái niệmlớnnhất. duy nhất.Suyraacũng là phầntử nhỏ nhất duy nhất. Kếtluậntương tự cho phầntử lớnnhấtvà phầntử tối đại. 13/04/2010 31 13/04/2010 32 8 13/04/2010 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.7. Định lý: 5.8. Thứ tự tựđiển: Trong một tập hợp sắp thứ tự hữuhạntacó: Cho (A,≺ ) là mộttậphữuhạn, khác rỗng, có thứ tự toàn phần, gọilàtậpmẫutự.GọiSlàtậphợp 1) Mọiphầntử trội(tương ứng, đượctrộibởi) tấtcả các chuỗikítự có dạng s = a1a2 ... an với n ∈ N và a ,a , ..., a ∈ A(vớin=0tacóchuỗi mộtphầntử tốitiểu(tương ứng, tối đại). 1 2 n rỗng ∅ khôngcókýtự nào). Trong S ta qui ước: 2) Nếu a là phần tử tối tiểu (tương ứng, tối đại) vớis=a1a2 ... an và t = b1b2 ... bm: s = t ⇔ (n = m và a = b , i = 1, n ) duy nhấtcủa X thì a là phầntử nhỏ nhất(tương i i Trên S ta định nghĩa quan hệ ≺ như sau: ứng, phầntử lớnnhất). 13/04/2010 33 13/04/2010 34 5. Quan hệ thứ tự 5.8. Thứ tự tựđiển: 1) ∀s ∈ S , ∅ ≺ s; 2) ∀s, t ∈ S,s=a1a2 ... an và t = b1b2 ... bm ⎡ nmabi≤==,,1,; n st≺ ⇔ ⎢ ii ⎣∃≤knmabababmin{ , },11 = ,...,kkkk−− 1 = 1 , < Khi đó ≺ là quan hệ thứ tự toàn phần trên S. Ta gọi đây là thứ tự tựđiểntrênSứng vớitậpmẫu tự (A,≺ ). 13/04/2010 35 9