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
9 trang |
Chia sẻ: trungkhoi17 | Lượt xem: 882 | Lượt tải: 0
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:
- bai_giang_toan_roi_rac_chuong_2_quan_he.pdf