Bài giảng Toán rời rạc - Chương 4: Quan hệ - Nguyễn Lê Minh

TOÁN RỜI RẠC
Chương 4: QUAN HỆ
GV: NGUYỄN LÊ MINH
Bộ môn Công nghệ thông tin
Nội dung
Định nghĩa và tính chất
Biểu diễn quan hệ
Quan hệ tương đương – Đồng dư
Quan hệ thứ tự - Biểu đồ Hass
Bài tập
2
Định nghĩa
3
Một quan hệ hai ngôi từ tập A đến tập B là tập con của tích
Descart R  A x B. Được viết a R b thay cho (a, b) R.
Quan hệ từ A đến chính nó được gọi là quan hệ trên A
R = { (a1, b1), (a1, b3), (a3, b3) }
Định nghĩa
3
Ví dụ. A = tập sinh viên; B = các lớp học. 
R = {(a, b) | sinh viên a học lớp b}
Định nghĩa
3
Ví dụ. Cho A = {1, 2, 3, 4}, và
R = {(a, b) | a là ước của b}
Khi đó
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)}
1 2 3 4
41 2 3
Các tính chất của quan hệ
3
Định nghĩa. Quan hệ R trên A được gọi là phản xạ nếu: 
a A, a R a
Ví dụ. Trên tập A = {1, 2, 3, 4}, quan hệ:
R1 = {(1,1), (1,2), (2,1), (2, 2), (3, 4), (4, 1), (4, 4)} không phản
xạ vì (3, 3) R1
R2 = {(1,1), (1,2), (1,4), (2, 2), (3, 3), (4, 1), (4, 4)} phản xạ vì
(1,1), (2, 2), (3, 3), (4, 4) R2
Các tính chất của quan hệ
3
Quan hệ trên Z phản xạ vì a a với mọi a Z
Quan hệ > trên Z không phản xạ vì 1 > 1
Chú ý. Quan hệ R trên tập A là phản xạ nếu nó chứa
đường chéo của A × A : 
 = {(a, a); a A}
1
1
2 3
3
4
4
2
Các tính chất của quan hệ
3
Định nghĩa. Quan hệ R trên A được gọi là đối xứng nếu:
a A b A (a R b) (b R a) 
Quan hệ R được gọi là phản xứng nếu
 a A b A (a R b)  (b R a) (a = b)
Ví dụ. 
 Quan hệ R1 = {(1,1), (1,2), (2,1)} trên tập
A = {1, 2, 3, 4} là đối xứng
 Quan hệ trên Z không đối xứng. 
Tuy nhiên nó phản xứng vì
(a b)  (b a) (a = b)
Các tính chất của quan hệ
3
Chú ý. Quan hệ R trên A là đối xứng nếu nó đối xứng nhau
qua đường chéo của A × A. 
Quan hệ R là phản xứng nếu chỉ có các phần tử nằm trên
đường chéo là đối xứng qua của A × A.
Các tính chất của quan hệ
3
1 2 3 4
1
2
3
4
1 2 3 4
1
2
3
4
*
*
*
Các tính chất của quan hệ
3
Định nghĩa. Quan hệ R trên A có tính bắc cầu (truyền) nếu
a, b,c A,(a R b)  (b R c) (a R c)
Ví dụ. 
Quan hệ R = {(1,1), (1,2), (2,1), (2, 2), (1, 3), (2, 3)}
trên tập A = {1, 2, 3, 4} có tính bắc cầu.
Tóm lại
3
R phản xạ : aRa
R đối xứng: aRb bRa
R phản xứng: aRb và bRa a=b
R bắc cầu: aRb và bRc aRc
Quan hệ tương đương
3
Ví dụ.
Xét quan hệ trên tập {1,2,3,4}
Các quan hệ sau, quan hệ nào là phản xạ, đối xứng, bắc cầu
Quan hệ tương đương
3
Ví dụ.
Xét quan hệ sau trên tập số nguyên
Quan hệ nào là phản xạ, đối xứng, bắc cầu ?
Quan hệ tương đương
3
Định nghĩa. Quan hệ R trên tập A được gọi là tương đương
nếu nó có tính chất phản xạ, đối xứng và bắc cầu :
Ví dụ. Quan hệ R trên các chuỗi ký tự xác định bởi aRb nếu
a và b có cùng độ dài. Khi đó R là quan hệ tương đương.
Ví dụ. Cho R là quan hệ trên R sao cho aRb nếu a – b 
nguyên. Khi đó R là quan hệ tương đương
Quan hệ tương đương
3
Cho a và b là hai số nguyên. a được gọi là ước của b hay b 
chia hết cho a nếu tồn tại số nguyên k sao cho b = ka
Ví dụ. Cho m là số nguyên dương và R quan hệ trên Z sao
cho aRb nếu a – b chia hết cho m, khi đó R là quan hệ
tương đương.
- Rõ ràng quan hệ này có tính phản xạ và đối xứng.
- Cho a, b, c sao cho a – b và b – c chia hết cho m, khi đó a 
– c = a – b + b – c cũng chia hết cho m. Suy ra R có tính chất
bắc cầu.
- Quan hệ này được gọi là đồng dư modulo m và được viết
viết
a  b (mod m) 
thay vì aRb
Lớp tương đương
3
Định nghĩa. Cho R là quan hệ tương đương trên A và phần
tử x A . Lớp tương đương chứa x được ký hiệu bởi [x]R
hoặc [x] là tập hợp con
[x]R = {b A| x R a}
Lớp tương đương
3
Ví dụ. Tìm các lớp tương đương modulo 8 chứa 0 và 1? 
Giải. Lớp tương đương modulo 8 chứa 0 gồm tất cả các số
nguyên a chia hết cho 8. Do đó
[0]8 ={ , – 16, – 8, 0, 8, 16,  }
Tương tự
[1]8 = {a | a chia 8 dư 1} 
= { , – 15, – 7, 1, 9, 17,  }
Lớp tương đương
3
Chú ý. Trong ví dụ cuối, các lớp tương đương [0]8 và [1]8 là
rời nhau.
Tổng quát, chúng ta có
Định lý. Cho R là quan hệ tương đương trên tập A và
a, b A, Khi đó
(i) a R b nếu [a]R = [b]R
(ii) [a]R [b]R nếu [a]R  [b]R = 
Chú ý. Các lớp tương đương theo một quan hệ tương
đương trên A tạo nên một phân họach trên A, nghĩa là chúng
chia tập A thành các tập con rời nhau. 
Lớp tương đương
3
Chú ý. Cho {A1, A2,  } là phân họach A thành các tập con 
không rỗng, rời nhau. Khi đó có duy nhất quan hệ tương
đương trên A sao cho mỗi Ai là một lớp tương đương.
A1
A2 A3
A4 A5
a
b
Lớp tương đương
3
Ví dụ. Cho m là số nguyên dương, khi đó có m lớp đồng dư
modulo m là [0]m , [1]m , , [m – 1]m .
Chúng lập thành phân họach của Z thành các tập con rời
nhau. Chú ý rằng
[0]m = [m]m = [2m]m = 
[1]m = [m + 1]m = [2m +1]m = 
[m – 1]m = [2m – 1]m = [3m – 1]m = 
Mỗi lớp tương đương này được gọi là số nguyên modulo 
m
.Tập hợp các số nguyên modulo m được ký hiệu bởi Zm
Zm = {[0]m , [1]m , , [m – 1]m}
Lớp tương đương
3
Ví dụ. Cho A = {0; 1; 2; 3; 4; 5; 6; 9; 11; 23; 24; 39}
Xét quan hệ tương đương (mod 5), ta có:
[0] = {0,5} = [5]
[1] = {1,6,11} = [6] = [11]
[2] = {2}
[3] = {3,23} = [23]
[4] = {4,9,24,39} = [9] = [24] = [39]
Tập A bao gồm 5 lớp tương đương rời nhau từng đôi một là
{2}, {0,5}, {3,23}, {1,6,11}, {4,9,24,39}
Quan hệ thứ tự
3
Ví dụ. Cho R là quan hệ trên tập số thực:
a R b nếu a b
Hỏi:
 R phản xạ không?
R đối xứng không?
 R phản xứng không?
R bắc cầu không?
Có
Không
Có
Có
Quan hệ thứ tự
3
Định nghĩa. Quan hệ R trên tập A là quan hệ thứ tự (thứ tự)
nếu nó có tính chất phản xạ, phản xứng và bắc cầu.
Người ta thường ký hiệu quan hệ thứ tự bởi
Cặp (A, ) đựợc gọi là tập sắp thứ tự hay poset
Phản xạ: a a 
Phản xứng: (a b)  (b a) (a = b) 
 Bắc cầu: (a b)  (b c) (a c) 
Quan hệ thứ tự
3
Ví dụ. Quan hệ ước số “ | ”trên tập số nguyên dương là quan hệ thứ
tự, nghĩa là (Z+, | ) là poset
Phản xạ? Có, x | x vì x = 1  x
Bắc cầu? Có?
a | b nghĩa là b = ka, b | c nghĩa là c = jb. 
Khi đó c = j(ka) = jka: a | c
Quan hệ thứ tự
3
Phản xứng? có?
a | b nghĩa là b = ka, b | a nghĩa là a = jb. 
Khi đó a = jka
Suy ra j = k = 1, nghĩa là a = b 
Ví dụ. (Z, | ) là poset?
Phản xứng?
Không
3|-3, và -3|3, 
nhưng 3 -3.
Không phải
Quan hệ thứ tự
3
(P(S),  ), ở đây P(S) là tập hợp các con của S, là một
poset?
Phản xạ? Có, A A, A P(S)
Bắc cầu? A  B, B  C. Suy ra A  C?
Phản xứng? A  B, B A. Suy ra A =B?Có
Có
Có, là poset.
Quan hệ thứ tự
3
Định nghĩa. Các phần tử a và b của poset (S, ) gọi là so 
sánh được nếu a b hay b a . 
Trái lại thì ta nói a và b không so sánh được
Cho (S, ), nếu hai phần tử tùy ý của S đều so sánh được
với nhau thì gọi nó là tập sắp thứ tự toàn phần.
Ta cũng nói rằng là thứ tự toàn phần hay thứ tư tuyến tính
trên S
Quan hệ thứ tự
3
Ví dụ. Quan hệ “ ” trên tập số nguyên dương là thứ tự toàn
phần. 
Ví dụ. Quan hệ ước số “ | ”trên tập hợp số nguyên dương
không là thứ tự toàn phần, vì các số 5 và 7 là không so sánh
được.
Biểu đồ Hasse
3
Mỗi poset có thể biễu diễn bởi đồ thị đặc biệt gọi là biểu đồ
Hasse
Để định nghĩa biểu đồ Hasse cần các khái niệm phần tử trội
và trội trực tiếp.
Định nghĩa. Phần tử b trong poset (S, ) được gọi là phần
tử trội của phần tử a trong S nếu a b
Hoặc cũng nói rằng a là được trội bởi b . Phần tử b được
gọi là trội trực tiếp của a nếu b là trội của a, và không tồn
tại trội c sao cho
bcabca , 
Biểu đồ Hasse
3
 Định nghĩa Biểu đồ Hasse của poset (S, ) là đồ thị:
 Mỗi phần tử của S được biễu diễn bởi một điểm trên mặt
phẳng
 Nếu b là trội trực tiếp của a thì vẽ một cung đi từ a đến
b .
cadba ,
a
b
c
d
e
Biểu đồ Hasse
3
Ví dụ. Biểu đồ Hasse của poset ({1,2,3,4}, ) có thể vẽ như
sau
4
3
2
1
Chú ý : Không vẽ
mũi tên với qui ước mỗi
cung đều đi từ dưới lên trên
Biểu đồ Hasse
3
Ví dụ: Biểu đồ Hasse của P({a,b,c})
{a,b,c}
{a,b} {a,c} 
{b,c}
{a}
{b} {c}

Phần tử tối đại và phần tử tối tiểu
3
Xét poset có biểu đồ Hasse như dưới đây:
 Mỗi đỉnh màu đỏ là tối đại.
 Mỗi đỉnh màu xanh là tối tiểu.
 Không có cung nào
xuất phát từ điểm
tối đại. 
 Không có cung nào
kết thúc ở điểm tối
tiểu.
Phần tử tối đại và phần tử tối tiểu
3
Chú ý. Trong một poset S hữu hạn, phần tử tối đại và phần tử
tối tiểu luôn luôn tồn tại.
 Thật vậy, xuất phát từ điểm bất kỳ a0 S. 
Nếu a0 không tối tiểu, khi đó tồn tại a1 a0, 
tiếp tục như vậy
cho đến khi tìm
được phần tử tối
tiểu .
a0
a1
a2
Phần tử tối đại và phần tử tối tiểu
3
Ví dụ. Tìm phần tử tối đại, tối tiểu của poset ({2, 4, 5, 10, 12, 
20, 25}, | ) ?
Giải. Từ biểu đồ Hasse, chúng ta thấy rằng 12, 20, 25 là
các phần tử tối đại, còn 2, 5 là các phần tử tối tiểu
Như vậy phần tử tối đại, tối tiểu của poset có thể không
duy nhất.
2
4
12 20
10
5
25
Chặn trên – Chặn dưới
3
Định nghĩa. Cho (S, ) là poset và A  S . Phần tử chặn
trên của A là phần tử x S (có thể thuộc A hoặc không) 
sao cho  a A, a x.
Phần tử chặn dưới của A là phần tử x S sao cho  a A, 
x a
Ví dụ. Phần tử chặn trên của
{g,j} là a. 
a b
d
jf
ih
e
c
g
Tại sao không phải là b?
Chặn trên – Chặn dưới
3
Định nghĩa. Cho (S, ) là poset và A  S. Chặn trên nhỏ
nhất của A là phần tử chặn trên x của A sao cho mọi
chặn trên y của A, ta đều có y x
Chặn dưới lớn nhất của A là phần tử chặn dưới x của A 
sao cho mọi chặn dưới y của A, ta có y x

Chặn trên nhỏ nhất của : supA
Chặn dưới lớn nhất: infA
Chặn trên – Chặn dưới
3
Ví dụ Chặn trên nhỏ nhất của {i,j} là d
Ví dụ. Chặn dưới chung lớn nhất của
{a,b} là gì?
a b
d
jf
ih
e
c
g
Chặn trên – Chặn dưới
3
Chặn trên nhỏ nhất (nếu có) của A = {a, b} đựơc ký hiệu bởi
a  b
Chặn dưới lớn nhất (nếu có) của A = {a, b} đựoc ký hiệu bởi
a  b
Ví dụ. i  j = da b
d
jf
ih
e
c
g
Ví dụ. b  c = f
Bao đóng của quan hệ
3
Giả sử P là tập hợp một số tính chất của các quan hệ, bao
đóng P (P - closure) của một quan hệ R trên tập S là quan hệ
nhỏ nhất có chứa tất cả các cặp của R thoả mãn các tính
chất trong P.
Bao đóng bắc cầu R+ của R được xác định như sau :
1. Nếu (a,b) thuộc R thì (a,b) thuộc R+.
2. Nếu (a,b) thuộc R+ và (b,c) cũng thuộc R thì (a,c) thuộc 
R+.
3. Không còn gì thêm trong R+.
Bao đóng của quan hệ
3
Bao đóng phản xạ và bắc cầu R* của R được xác định như 
sau :
R* = R+ {(a, a) | a ∈ S}
Ví dụ:
Cho quan hệ R = {(1, 2), (2, 2), (2, 3)} trên tập hợp S = {1, 2,
3}
Khi đó ta có :
R+ = {(1, 2), (2, 2), (2, 3), (1, 3)}
R* = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}
Bài tập
3