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

Chương 3
QUAN HỆ
1
1. Định nghĩa và tính chất
2. Biểu diễn quan hệ
I. Quan hệ
2
3. Quan hệ tương đương. Đồng dư
4. Quan hệ thứ tự, biểu đồ Hass
1. Đị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 Đề 
các R ⊆ A x B. Chúng ta sẽ 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) }
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}
4
1. Định nghĩa
1. Định nghĩa
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)}
5
1 2 3 4
1 2 3 4
2. Các tính chất của Quan hệ
Đị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
6
 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
Quan hệ“ | ” (“ước số”) trên Z + là phản xạ vì mọi số
nguyên a là ước của chính nó .
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 : 
1 2 3 4
1
2
3
4
∆ = {(a, a); a ∈ A}
7
2. Các tính chất của Quan hệ
Đị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ụ. 
8
 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)
(a | b) ∧ (b | a) → (a = b)
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ệ“ | ” (“ước số”) trên Z +. không đối xứng
Tuy nhiên nó có tính phản xứng vì
9
2. Các tính chất của Quan hệ
1 2 3 4
1
2
3
4
1 2 3 4
1
2
3
4
*
*
*
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.
2. Các tính chất của Quan hệ
Đị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)}
10
trên tập A = {1, 2, 3, 4} có tính bắc cầu.
Quan hệ ≤ và “|”trên Z có tính bắc cầu
(a ≤ b) ∧ (b ≤ c) → (a ≤ c)
(a | b) ∧ (b | c) → (a | c)
Tóm lại

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
11
Giới thiệu
Quan hệ tương đương 
3. Quan hệ tương đương
12
Lớp tương đương
Định nghĩa
Ví dụ.
Cho S = {sinh viên của lớp}, gọi
R = {(a,b): a có cùng họ với b}
Hỏi
13
Yes
Yes
Yes
Mọi sinh viên
có cùng họ 
thuộc cùng một 
nhóm.
R phản xạ?
R đối xứng?
R bắc cầu?
Đị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
3. Quan hệ tương đương
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
14
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 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
3. Quan hệ tương đươ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à chúng 
ta viết
a ≡ b (mod m) 
thay vì aRb
15
Lớp tương đương
Định nghĩa. Cho R là quan hệ tương đương trên A và 
phần tử a ∈ A . Lớp tương đương chứa a được ký hiệu 
bởi [a]R hoặc [a] là tập
16
[a]R = {b ∈ A| b R a}
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] ={ , – 16, – 8, 0, 8, 16,  }
17
Lớp tương đương
8
Tương tự 
[1]8 = {a | a chia 8 dư 1} 
= { , – 15, – 7, 1, 9, 17,  }
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 đó
18
Lớp tương đương
(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. 
Chú ý. Cho {A1, A2, p } 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.
19
Lớp tương đương
A1 A2 A3
A4 A5
a
b
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 = p
20
[1]m = [m + 1]m = [2m +1]m = p
ppppppppppppp
[m – 1]m = [2m – 1]m = [3m – 1]m = p
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 , p, [m – 1]m}
4. Quan hệ thứ tự. Biểu đồ Hasse
21
Giới thiệu
Biểu đồ Hasse
Phần tử tối tiểu, tối đại
Chặn trên nhỏ nhất, chặn dưới lớn nhất
Định nghĩa
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?
22
Có
Có
Không

 R phản xứng không?
R đối xứng không?
R bắc cầu không? Có
Đị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. 
pCặp (A, ) đựợc gọi là tập sắp thứ tự hay poset
Người ta thường ký hiệu quan hệ thứ tự bởi p
23
Định nghĩa
Phản xạ: a ap
Phản xứng: (a b) ∧ (b a) → (a = b)pp
pBắc cầu: (a b) ∧ (b c) → (a c)pp
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
24
Định nghĩa
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
Phản xứng?
a | b nghĩa là b = ka, b | a nghĩa là a = jb. 
Khi đó a = jka
có?
25
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
(P(S), ⊆ ), ở đây P(S) là tập hợp các con của S, là một poset?
Có, A ⊆A, ∀A∈ P(S)Phản xạ?
Bắc cầu? A ⊆ B, B ⊆ C. Suy ra A ⊆ C?Có
Có, là poset.
26
Phản xứng? A ⊆ B, B ⊆A. Suy ra A =B?Có
Đị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 . 
p
p p
pCho (S, ), nếu hai phần tử tùy ý của S đều so sánh 
được với nhau thì ta gọi nó là tập sắp thứ tự toàn phần
Trái lại thì ta nói a và b không so sánh được.
27
Định nghĩa
.
Ta cũng nói rằng là thứ tự toàn phần hay thứ tư tuyến tính
trên S
p
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.
Ví dụ
28
Biểu đồ Hasse
Mỗi poset có thể biễu diễn bởi đồ thị đặc biệt ta gọi
là biểu đồ Hasse 
Để định nghĩa biểu đồ Hasse chúng ta 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à 
29
Chúng ta 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
phần tử trội của phần tử a trong S nếu a b
p
p
bcabca ≠≠,pp
Biểu đồ Hasse
 Ta đị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 .
p
 Nếu b là trội trực tiếp của a thì vẽ một cung đi từ 
30
a
b
c
d
e
cadba ppp ,
a đến b .
Biểu đồ Hasse
Ví dụ. Biểu đồ Hasse của poset ({1,2,3,4}, ≤) có 
thể vẽ như sau
4
31
Chú ý . Chúng ta không vẽ
mũi tên với qui ước mỗi 
cung đều đi từ dưới lên trên
3
2
1
Ví dụ. Biểu đồ Hasse của P({a,b,c})
{a,b,c}
{a,b} {a,c} {b,c}
32
{a} {b} {c}
∅
Phần tử tối đại và phần tử tối tiểu.
Xét poset có biểu đồ Hasse như dưới đây:
 Mỗi đỉnh màu đỏ là tối đại.
 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.
 Mỗi đỉnh màu xanh là tối tiểu.
33
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, chúng ta xuất phát từ điêm bất kỳ a0 ∈ S. 
Phần tử tối đại tìm được bằng phương pháp tương tự.
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 .
p
34
a0
a1
a2
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.
35
2
4
12 20
10
5
25
Chặn trên, chặn dưới
Đị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.
p
p
Phần tử chặn dưới của A là phần tử x ∈ S sao cho
∀ a ∈ A, x ap
36
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?
Đị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
p
f
Chặn dưới lớn nhất của A là phần tử chặn dưới x
37
Chặn trên, chặn dưới
của A sao cho mọi chặn dưới y của A, ta có
y xp
Chặn trên nhỏ nhất của : supA
Chặn dưới lớn nhất: infA
a b
dc
Ví dụ. Chặn dưới chung lớn nhất của 
{a,b} là gì?
Ví dụ Chặn trên nhỏ nhất của {i,j} là d
Chặn trên, chặn dưới
jf
ih
e
g
38
a b
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
39
Chặn trên, chặn dưới
d
jf
ih
e
c
g
Ví dụ. b ∧ c = f
Ví dụ. i ∨ j = d