13/04/2010
1
Chương II
Ệ
QUAN H
Ệ
Cho tậphợpX≠∅.Một quan hệhai ngôi trên X
là
một
tập
hợp
con
ℜ
của
2
Nếu
(x y)
∈ℜ
ta
1. Định nghĩa và ký hiệu
là
một
tập
hợp
con
ℜ
của
.
Nếu
(x
,
y)
∈ℜ
,
ta
viếtxℜy. Nếu (x,y)∉ℜ,ta viết.
Ví dụ1:
Cho
=
{
1
2
3
4
}
và
ℜ
=
{(
1
1
)
(
1
3
)
(
2
1
)
x
y
ℜ
Cho
=
{
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ưng , , ...
13/04/2010 2
12
ℜ
22
ℜ
23
ℜ
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
Quan
hệ
có
cùng
trị
tuyệt
đối
trên
tập
hợp
các
số
thựcRlà một quan hệhai ngôi ℜtrên tậphợ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
Quan
hệ
nhỏ
hơn
hay
bằng
trên
tập
các
số
hữu
tỉ
Qlà 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ướcm
ộ
tsốn
g
u
y
ên dươn
g
n
,
ta đ
ị
nh n
g
hĩam
ộ
t
1. Định nghĩa và ký hiệu
ộ
gy
g
,
ị
g
ộ
quan hệhai ngôi trên Znhưsau:
∀x, y ∈Z, xℜy ⇔x – y chia hết cho n.
Quan hệnày đượcgọi là quan hệđồng dưmodulo n.
Nếuxℜytaviết:
x ≡
y
(
mod n
)
y( )
Chẳng hạn, vớin=7tacó9≡2(mod7)và3≡10
(mod 7) nhưng 3 ≅6(mod7).
13/04/2010 5
Cho tậphợphữuhạnX={x
1,x
2, ..., xn}. Khi
đó
mỗi
quan
hệ
hai
ngôi
ℜ
trên
có
thể
được
2. Ma trận biểu diễn quan hệ hai ngôi
đó
,
mỗi
quan
hệ
hai
ngôi
ℜ
trên
có
thể
được
biểudiễnbởimộtmatrận vuông cấpn,kýhiệu
là M(ℜ), trong đó:
M(
ℜ
)
=
r
ij
với
1
0
ij
ij
x
x
r
ℜ
⎧
⎪
=
⎨
ℜ
⎪
M(
ℜ
)
r
ij
với
13/04/2010 6
0
ij
ij
r
x
x
ℜ
⎪
⎩
Ví dụ:
Xé
t
X=
{
1
,
2
,
3
,
4
}
và
q
uan h
ệ
hai n
g
ôi
ℜ
như
2. Ma trận biểu diễn quan hệ hai ngôi
{
,
,
,
}
q
ệ
g
trong Ví dụ1ởtrên. Ma trậnbiểudiễncủaℜlà:
()
1010
1000
1000
M
⎛⎞
⎜⎟
⎜⎟
ℜ=
⎜⎟
⎜⎟
13/04/2010 7
0000
⎜⎟
⎝⎠
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
3
.
1
.
Tính
phản
xạ
:
Ta nói quan hệhai ngôi ℜcó tính phảnxạnếu
vớimọix∈X, x luôn luôn có quan hệℜvớix.
Nhưvậy:
ℜ
p
hản xạ
⇔
∀
x
∈
X, x
ℜ
x
p
Suy ra:
ℜkhông phản xạ ⇔∃x ∈X, x x
13/04/2010 8
ℜ
13/04/2010
3
3.1. Tính phảnxạ:
•G
ọ
iΔ
X
là đườn
g
chéo chính củaX
2:
3. Tính chất của quan hệ hai ngôi
ọ
X
g
ΔX= {(x, x) |x ∈X}
Khi ấyquanhệℜtrên X là phảnxạkhi và chỉ
khi ℜ⊃Δ
X.
1
13/04/2010 9
123 4
4
3
2
1
3.1. Tính phảnxạ:
•NếuXhữuhạnthìℜphảnxạkhi và chỉkhi
ể
ễ
ố
3. Tính chất của quan hệ hai ngôi
ma trận
b
i
ể
udi
ễ
nM(
ℜ
) có các hệs
ố
trên
đường chéo đềulà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
3
.
2
.
Tính
đối
xứng
:
Ta nói quan hệhai ngôi ℜcó tính đốixứng khi
vớimọix,y∈X, nếu x có quan hệℜvớiythìy
cũng có quan hệℜvớix.Nhưvậy:
ℜđối xứn
g
⇔
(
∀x,
y
∈X, x
ℜ
y
⇒
y
ℜ
x
)
.
g
(
y
y
y
)
Suy ra:
ℜkhông đối xứng ⇔(∃x,y∈X, xℜy và y x)
13/04/2010 11
ℜ
3.2. Tính đốixứng:
•Quanhệℜtrên Alà đốixứng khi và chỉkhi
ố
3. Tính chất của quan hệ hai ngôi
nó đ
ố
ixứng nhau qua đường chéo
Δ
củaA×
A.
3
2
1
13/04/2010 12
1234
4
3
13/04/2010
4
3.2. Tính đốixứng:
•NếuXhữuhạnthìℜđốixứng khi và chỉkhi
ể
ễ
ố
3. Tính chất của quan hệ hai ngôi
ma trận
b
i
ể
udi
ễ
nM(ℜ)làmộtmatrậ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
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
3
.
3
.
Tính
phả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
thểxảyrađồng thời x có quan hệℜvớiyvàycóquan
hệℜvớix.Nhưvậy:
ℜ
phảnđốixứng
⇔
(
∀
x, y
∈
X, x
≠
yvàx
ℜ
y
⇒
yx)
ℜ
ℜ
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đốixứng:
•Quanhệℜlà phảnxứng khi và chỉkhi chỉcó
ầ
ằ
ố
3. Tính chất của quan hệ hai ngôi
các ph
ầ
ntửn
ằ
mtrênđường chéo là đ
ố
ixứng
qua ΔcủaA×A.
3
2
1
13/04/2010 15
1234
4
3
3.3. Tính phảnđốixứng:
•VớiXhữuhạnthìℜphảnđốixứng khi và chỉ
ể
ễ
3. Tính chất của quan hệ hai ngôi
khi ma trận
b
i
ể
udi
ễ
nM(
ℜ
)=(
r
ij)thỏa:
∀1 ≤i ≠j ≤n, rji = 1 ⇒rij = 0.
Ví dụ:
Quan hệ ≤trên Zphả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
3
.
4
.
Tính
bắc
cầu
:
Ta nói quan hệhai ngôi ℜcó tính bắccầu khi đốivới
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:
Rbắccầu
⇔
(
∀
xyz
∈
Xx
ℜ
yvày
ℜ
z
⇒
x
ℜ
z)
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ắccầ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ậpA= {1, 2, 3, 4} có tính bắccầu.
•Quanhệ≤và “|”trên Zcó tính bắccầu
(
≤
b
)
(
b
≤
)
(
≤
)
(
a
≤
b
)
∧
(
b
≤
c
)
→
(
a
≤
c
)
(a |b) ∧(b |c) →(a |c)
13/04/2010 18
4.1. Định nghĩa:
Mộtquanhệℜtrên tậphợpXđượcgọilà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
đương
nếu
ℜ
thỏa
các
tính
chất
phản
xạ
,
đối
xứng
và
bắc
cầu
.
Ví dụ:
1) Quan hệbằng nhau trên mộttậphợpX≠∅bấtkỳlà một
quan hệtương đương X.
2) Quan hệnhỏhơnhaybằng thông thường trên các tậphợpsố
không phảilàmột quan hệtương đương.
ề
3) Qua
n
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
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
ấ
ylớptương đương chứax,kýhiệu
bởi hay [x], là tậphợpgồmtấtcảcác phầntửy
của X có quan hệℜvớix.Nhưvậy:
= {y ∈X |yℜx}
x
x
13/04/2010 20