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

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

pdf9 trang | Chia sẻ: trungkhoi17 | Lượt xem: 882 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu Bài giảng Toán rời rạc - Chương 2: Quan hệ, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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

Các file đính kèm theo tài liệu này:

  • pdfbai_giang_toan_roi_rac_chuong_2_quan_he.pdf
Tài liệu liên quan