Bài giảng Toán rời rạc - Chương 6: Quan hệ
Baøi giaûng moân
Raïc
Quan heä hai ngoâi
Nguyeãn Anh
Thi
Ñònh nghóa
Moät quan heä hai ngoâi R treân taäp A = ∅ laø moät taäp con khaùc
ngoâi
roãng cuûa taäp tích A × A.
Khi (x; y) ∈ R, ta ghi xRy, neáu khoâng, ta ghi xRy.
ñöông.
Ví duï
töï.
•
•
A = {1; 2; 3},
R = {(1; 1); (1; 2); (2; 1); (2; 2); (2; 3); (3; 3)}.
Ta coù 1R2, 2R1, 2R3, vaø 3R2
Quan heä ” = ” treân moät taäp hôïp A baát kyø:
(aRb) ⇔ a = b
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Quan heä hai ngoâi
Nguyeãn Anh
Thi
Ví duï
•
Quan heä ” ≤ ” treân Z, Q hay R:
(aRb) ⇔ a ≤ b
ngoâi
ñöông.
töï.
•
Goïi L laø taäp hôïp caùc ñöôøng thaúng trong maët phaúng. Quan
heä song song ñöôïc ñònh nghóa bôûi:
(dRd0) ⇔ d//d0
Quan heä ñoàng dö modulo n:
(aRb) ⇔ a ≡ b( mod n)
•
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Nguyeãn Anh
Thi
Ví duï
ngoâi
•
Quan heä ” = ” treân moät taäp hôïp baát kyø, quan heä ” ≤ ”
ñöông.
treân Z, Q, R, quan heä ñoàng dö treân Z laø phaûn xaï.
Caùc quan heä ” =, ≡, //” laø caùc quan heä ñoái xöùng.
Caùc quan heä ” =, ≡, //, ≤ ” laø caùc quan heä baéc caàu.
töï.
•
•
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Quan heä töông ñöông
Nguyeãn Anh
Thi
ngoâi
Ñònh nghóa
ñöông.
Quan heä hai ngoâi R treân taäp A ñöôïc goïi laø moät quan heä töông
ñöông khi vaø chæ khi R coù caùc tính chaát phaûn xa,ï ñoái xöùng, baéc
caàu.
töï.
Ví duï
Caùc quan heä ” =, ≡, //” laø caùc quan heä töông ñöông.
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Ñònh nghóa
Cho R laø moät quan heä töông ñöông treân A. Lôùp töông ñöông
Nguyeãn Anh
Thi
cuûa phaàn töû x ∈ A laø taäp con x = {t ∈ A|tRx}.
Tính chaát
ngoâi
i. ∀x ∈ A, x = ∅;
ii. z ∈ x ⇒ z = x;
ñöông.
töï.
iii. ∀x, y ∈ A, x ∩ y = ∅ hoaëc x = y (nghóa laø: x = y thì
x ∩ y = ∅).
Ñònh nghóa
Cho R laø moät quan heä töông ñöông treân A. taäp hôïp caùc lôùp
töông ñöông (khaùc nhau) cuûa A ñöôïc goïi laø taäp thöông cuûa A
treân R, kyù hieäu A/R. Nhö vaäy, phaàn töû cuûa A/R laø moät taäp con
cuûa A.
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Quan heä ñoàng dö
Nguyeãn Anh
Thi
Ñònh nghóa
Cho tröôùc n ∈ N, ta ñònh nghóa quan heä ñoàng dö modulo n (kyù
ngoâi
∼
hieäu (mod n )) treân taäp Z, nhö sau:
=
ñöông.
∼
x
y(mod n) ⇔ n|(x − y)
=
töï.
Ñònh nghóa
Treân Zn ta ñònh nghóa moät caùch töï nhieân caùc pheùp toaùn + vaø .
nhö sau:
x + y = x + y
x.y = x.y, ∀x, y ∈ Zn
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Quan heä thöù töï
Nguyeãn Anh
Thi
Ñònh nghóa
ngoâi
Moät quan heä S treân taäp A = ∅ ñöôïc goïi laø moät quan heä thöù töï
khi vaø chæ khi S coù caùc tính chaát phaûn xaï, phaûn xöùng, baéc caàu.
Khi ñoù A ñöôïc goïi laø moät taäp ñöôïc saép (coù thöù töï boä phaän).
Neáu ∀x, y ∈ A, luoân luoân coù xSy hoaëc ySx thì taäp ñöôïc saép
(A, S) ñöôïc goïi laø taäp thöù töï toaøn phaàn.
ñöông.
töï.
Ví duï
Caùc quan heä ≥, ≤ (theo nghóa thoâng thöôøng) laø nhöõng quan
heä thöù töï (toaøn phaàn) treân N, Z, Q, R.
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Ñònh nghóa
Nguyeãn Anh
Thi
Cho (A, S) laø moät taäp ñöôïc saép, ∅ = B ⊆ A
a. Phaàn töû M ∈ B laø phaàn töû lôùn nhaát cuûa B khi vaø chæ khi
∀x ∈ B, xSM.
ngoâi
b. Phaàn töû m ∈ B laø phaàn töû nhoû nhaát cuûa B khi vaø chæ khi
∀x ∈ B, mSx.
ñöông.
töï.
c. Phaàn töû a ∈ B laø phaàn töû toái tieåu cuûa B khi vaø chæ khi
khoâng coù x ∈ B, x = a vaø xSa. (Hay noùi caùch khaùc,
∀x ∈ B, xSa ⇒ x = a).
d. Phaàn töû b ∈ B laø phaàn töû toái ñaïi cuûa B khi vaø chæ khi khoâng
coù x ∈ B, x = b vaø bSx. (Hay noùi caùch khaùc,
∀x ∈ B, bSx ⇒ x = b).
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Ñònh lyù
Phaàn töû lôùn nhaát, phaàn töû nhoû nhaát cuûa moät taäp ñöôïc saép
(neáu coù) laø duy nhaát.
Nguyeãn Anh
Thi
Nhaän xeùt
ngoâi
Trong moät taäp ñöôïc saép, phaàn töû lôùn nhaát (neáu coù) seõ laø phaàn
töû toái ñaïi duy nhaát, phaàn töû nhoû nhaát (neáu coù) seõ laø phaàn töû
toái tieåu duy nhaát.
ñöông.
töï.
Ñònh lyù
(A, S) laø taäp ñöôïc saép höõu haïn thì
a. Moïi phaàn töû a ∈ A ñeàu bò chaän treân bôûi moät phaàn töû toái ñaïi,
bò chaän döôùi bôûi moät phaàn töû toái tieåu.
b. A coù phaàn töû toái ñaïi, phaàn töû toái tieåu.
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Nguyeãn Anh
Thi
Ñònh nghóa
Cho (A, S) laø moät taäp ñöôïc saép, khi xSy ta baûo x bò troäi bôûi y, y
troäi x. Khi xSy vaø khoâng toàn taïi z sao cho xSz vaø zSy, ta noùi y
laø troäi tröïc tieáp cuûa x.
ngoâi
ñöông.
Ñònh nghóa
töï.
Ta bieåu dieãn moät taäp thöù töï (A, S) höõu haïn bôûi moät giaûn ñoà,
goàm nhöõng ñieåm lieân keát vôùi nhöõng phaàn töû cuûa A vaø nhöõng
cung coù höôùng noái x vôùi y khi y laø troäi tröïc tieáp cuûa x; giaûn ñoà
treân ñöôïc goïi laø bieåu ñoà Hasse.
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Topo hoùa moät quan heä thöù töï baùn
phaàn
Nguyeãn Anh
Thi
ngoâi
ñöông.
Ñònh nghóa
töï.
Cho (A, S) laø moät taäp thöù töï baùn phaàn. Topo hoùa T cuûa S laø
moät quan heä thöù töï toaøn phaàn treân A sao cho
x, y ∈ A, xSy ⇒ xTy (nghóa laø khoâng coù x = y sao cho xTy maø
ySx).
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Giaûi thuaät tìm topo hoùa T cuûa S
khi A laø taäp höõu haïn, |A| = n
Nguyeãn Anh
Thi
Ta thöïc hieän theo caùc böôùc sau:
i. Choïn x1 laø moät phaàn töû toái tieåu cuûa A.
ngoâi
ii. Choïn x2 laø moät phaàn töû toái tieåu cuûa A\{x1}
iii. Sau khi choïn ñöôïc x1, x2, . . . , xk, ta choïn xk+1 laø moät phaàn
töû toái tieåu cuûa A\{x1, x2, . . . , x − k}
ñöông.
töï.
Khi ñaõ coù daõy x1, x2, . . . , xn, ta ñaët xiTxj khi vaø chæ khi i ≤ j
Chuù yù
Vì coù theå coù nhieàu caùch choïn löïa trong moãi böôùc, neân seõ coù
nhieàu topo hoùa khaùc nhau cho cuøng moät taäp thöù töï.
Ví duï
Topo hoùa taäp ñöôïc saép A = (U30, |).
Nguyeãn Anh Thi
18 trang
15/01/2024
6800
Free
Bạn đang xem tài liệu "Bài giảng Toán rời rạc - Chương 6: Quan hệ", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_chuong_6_quan_he.pdf
