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

 .
Ví dụ 1:
Cho X = {1 2 3 4} và ℜ = {(1 1) (1 3) (2 1)
x yℜ
, , , , , , , , ,
(3,1)}. Ta thấy ℜ là một quan hệ trên X và 1ℜ1,
1ℜ3, 2ℜ1, 3ℜ1 nhưng , , ...
13/04/2010 2
1 2ℜ 2 2ℜ 2 3ℜ
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
thực R là một quan hệ hai ngôi ℜ trên tập hợ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
Q là 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ước một số nguyên dương n, ta định nghĩa một
1. Định nghĩa và ký hiệu
quan hệ hai ngôi trên Z như sau:
∀x, y ∈ Z, xℜy ⇔ x – y chia hết cho n.
Quan hệ này được gọi là quan hệ đồng dư modulo n.
Nếu xℜy ta viết:
x ≡ y (mod n)
Chẳng hạn, với n = 7 ta có 9 ≡ 2 (mod 7) và 3 ≡ 10
(mod 7) nhưng 3 ≅ 6 (mod 7).
13/04/2010 5
Cho tập hợp hữu hạn X = {x1, x2, ..., xn}. Khi
đó mỗi quan hệ hai ngôi ℜ trên X có thể được
2. Ma trận biểu diễn quan hệ hai ngôi
,
biểu diễn bởi một ma trận vuông cấp n, ký hiệu
là M(ℜ), trong đó:
M(ℜ) = rij với
1
0
i j
ij
x x
r
ℜ⎧⎪= ⎨ ℜ⎪
13/04/2010 6
i jx x⎩
Ví dụ: 
Xét X = {1, 2, 3, 4} và quan hệ hai ngôi ℜ như
2. Ma trận biểu diễn quan hệ hai ngôi
trong Ví dụ 1 ở trên. Ma trận biểu diễn của ℜ là:
( )
1 0 1 0
1 0 0 0
1 0 0 0
M
⎛ ⎞⎜ ⎟⎜ ⎟ℜ = ⎜ ⎟⎜ ⎟
13/04/2010 7
0 0 0 0⎝ ⎠
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
Ta nói quan hệ hai ngôi ℜ có tính phản xạ nếu
với mọi x ∈ X, x luôn luôn có quan hệ ℜ với x.
Như vậy:
ℜ phản xạ ⇔∀x ∈ X, xℜx
Suy ra:
ℜ không phản xạ ⇔ ∃x ∈ X, x x
13/04/2010 8
ℜ
13/04/2010
3
3.1. Tính phản xạ:
• Gọi ΔX là đường chéo chính của X2:
3. Tính chất của quan hệ hai ngôi
ΔX = {(x, x) | x ∈ X}
Khi ấy quan hệ ℜ trên X là phản xạ khi và chỉ
khiℜ ⊃ ΔX.
1
13/04/2010 9
1 2 3 4
4
3
2
3.1. Tính phản xạ:
• Nếu X hữu hạn thì ℜ phản xạ khi và chỉ khi
ể ễ ố
3. Tính chất của quan hệ hai ngôi
ma trận bi u di n M(ℜ) có các hệ s trên
đường chéo đều là 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
Ta nói quan hệ hai ngôi ℜ có tính đối xứng khi
với mọi x, y ∈ X, nếu x có quan hệ ℜ với y thì y
cũng có quan hệ ℜ với x. Như vậy:
ℜ đối xứng ⇔ (∀x, y ∈ X, xℜy ⇒ yℜx).
Suy ra:
ℜ không đối xứng ⇔ (∃x,y∈X, xℜy và y x)
13/04/2010 11
ℜ
3.2. Tính đối xứng:
• Quan hệ ℜ trên A là đối xứng khi và chỉ khi
ố
3. Tính chất của quan hệ hai ngôi
nó đ i xứng nhau qua đường chéo Δ của A ×
A.
3
2
1
13/04/2010 12
1 2 3 4
4
13/04/2010
4
3.2. Tính đối xứng:
• Nếu X hữu hạn thì ℜ đối xứng khi và chỉ khi
ể ễ ố
3. Tính chất của quan hệ hai ngôi
ma trận bi u di n M(ℜ) là một ma trậ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, , , .
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
Ta nói quan hệ hai ngôi ℜ có tính phản đối xứng nếu
đối với hai phần tử khác nhau bất kỳ x, y ∈ X không
thể xảy ra đồng thời x có quan hệ ℜ với y và y có quan
hệ ℜ với x. Như vậy:
ℜ 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 đối xứng:
• Quan hệ ℜ là phản xứng khi và chỉ khi chỉ có
ầ ằ ố
3. Tính chất của quan hệ hai ngôi
các ph n tử n m trên đường chéo là đ i xứng
qua Δ của A × A.
3
2
1
13/04/2010 15
1 2 3 4
4
3.3. Tính phản đối xứng:
• Với X hữu hạn thì ℜ phản đối xứng khi và chỉ
ể ễ
3. Tính chất của quan hệ hai ngôi
khi ma trận bi u di n M(ℜ) = (rij) thỏa:
∀1 ≤ i ≠ j ≤ n, rji = 1 ⇒ rij = 0.
Ví dụ:
Quan hệ ≤ trên Z phả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
Ta nói quan hệ hai ngôi ℜ có tính bắc cầu khi đối với
các phần tử bất kỳ x, y, z ∈ X, nếu x có quan hệ ℜ với
y và y có quan hệ ℜ với z thì x cũng có quan hệ ℜ với
z. Như vậy:
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ắc cầ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ậ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
( ≤ b) (b ≤ ) ( ≤ )a ∧ c → a c
(a | b) ∧ (b | c) → (a | c)
13/04/2010 18
4.1. Định nghĩa:
Một quan hệ ℜ trên tập hợp X được gọi là 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
, .
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. Như vậy:
= {y ∈ X | yℜx}
x
x
13/04/2010 20
13/04/2010
6
4.3. Định lý:
Giả sử ℜ là một quan hệ tương đương trên X.
4. Quan hệ tương đương
Khi đó:
•∀x ∈ X, x ∈ .
•∀x, y ∈ X, xℜy ⇔ = 
•∀x, y ∈ X, ∩ ≠ ∅⇔ = 
x
x y
x y yx
13/04/2010 21
5.1. Định nghĩa:
Một quan hệ ℜ trên tập hợp X được gọi là 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
5. Quan hệ thứ tự
, .
Khi ấy ta nói X là một tập hợp sắp thứ tự (hay có thứ tự).
Ví dụ:
1) Quan hệ nhỏ hơn hay bằng thông thường trên các tập hợp số
là một quan hệ thứ tự.
2) Cho tập hợp E ≠ ∅. Trên tập hợp P(E) ta có quan hệ: ∀A, B ∈
P(E), A ℜ B⇔ A ⊆ B
3) Trên tập N các số tự nhiên ta định nghĩa quan hệ ước số: xℜy
⇔ x|y. Quan hệ thứ tự trên vẫn được ký hiệu bởi x|y.
13/04/2010 22
5.2. Định nghĩa:
Một quan hệ thứ tự trên X được gọi là toàn phần nếu hai phần
tử bất kỳ đều so sánh được với nhau nghĩa là:
5. Quan hệ thứ tự
≺
,
∀x, y ∈ X, x y hay y x.
Trong trường hợp ngược lại, ta nói là một quan hệ thứ tự bộ
phận. Nói cách khác, quan hệ thứ tự là bộ phận nếu tồn tại hai
phần tử không so sánh được với nhau, nghĩa là: ∃x, y ∈ X, x y
và y x.
Ví d
≺
≺
≺ ≺
≺≺
ụ:
1) N, Z, Q, R với thứ tự ≤ thông thường là những tập hợp sắp
thứ tự toàn phần.
2) (P(E), ⊆) là tập được sắp thứ tự bộ phận nếu E có ít nhất 2
phần tử.
13/04/2010 23
5.3. Định nghĩa:
Xét một tập hợp có thứ tự (X, ) và x, y là 2
5. Quan hệ thứ tự
≺
phần tử bất kỳ của X. Khi đó ta nói:
1) y là trội x hay x được trội bởi y nếu x y.
2) y là trội trực tiếp của x nếu y ≠ x y trội x và
≺
,
không tồn tại một trội z của x sao cho x z y.
13/04/2010 24
≺ ≺
13/04/2010
7
5.4. Định nghĩa:
Biểu đồ Hasse của một tập hợp hữu hạn có thứ
ồ
5. Quan hệ thứ tự
tự (X, ) bao g m:
1) Một tập hợp các điểm trong mặt phẳng tương
ứng 1 – 1 với X, gọi là các đỉnh.
2) Một tập hợp các cung có hướng nối một số
đỉnh: hai đỉnh x y được nối lại bởi một cung có
≺
,
hướng từ x tới y nếu y là trội trực tiếp của x.
13/04/2010 25
5.4. Định nghĩa:
Ví dụ:
5. Quan hệ thứ tự
1) Biểu đồ Hasse của U12 = {x ∈ N | x|n} với
quan hệ “ | ” được cho bởi:
13/04/2010 26
5.4. Định nghĩa:
Ví dụ:
5. Quan hệ thứ tự
2) Với E = {a, b, c} thì biểu đồ Hasse của (P(E),
⊆) có dạng:
13/04/2010 27
5.4. Định nghĩa:
Ví dụ:
5. Quan hệ thứ tự
3) Biểu đồ Hasse của {1, 2, 3, 4, 5} với thứ tự
thông thường có dạng của một dây chuyền:
13/04/2010 28
13/04/2010
8
5.5. Định nghĩa:
Xét (X, ) là một tập được sắp và a, b ∈ X. Ta nói:
5. Quan hệ thứ tự
≺
1) a là phần tử nhỏ nhất (tương ứng phần tử lớn nhất)
của X, ký hiệu bởi min X (tương ứng, bởi max X), nếu
a nhỏ hơn hay bằng (tương ứng, lớn hơn hay bằng) mọi
phần tử trong X. Như vậy:
a = min X ⇔∀x ∈ X, a x;
a = max X ⇔∀x ∈ X, x a.
13/04/2010 29
≺
≺
5.5. Định nghĩa:
2) b là phần tử tối tiểu (tương ứng, phần tử tối đại) của
5. Quan hệ thứ tự
X, nếu b là không là trội thực sự của (tương ứng không
được trội thực sự bởi) phần tử nào của X. Như vậy:
b là phần tử tối tiểu của X⇔ (∀x ∈ X, x b⇒ x = b);≺
b là phần tử tối đại của X ⇔ (∀x ∈ X, b x⇒ x = b).
13/04/2010 30
≺
5.5. Định nghĩa:
Chú ý: Nếu (X, ) là một tập được sắp thứ tự toàn phần
5. Quan hệ thứ tự
≺
thì khái niệm tối tiểu trùng với khái niệm nhỏ nhất, và
khái niệm tối đại trùng với khái niệm lớn nhất.
13/04/2010 31
5.6. Định lý:
Trong một tập hợp sắp thứ tự X, phần tử nhỏ
5. Quan hệ thứ tự
nhất a = min X, nếu tồn tại, là phần tử tối tiểu
duy nhất. Suy ra a cũng là phần tử nhỏ nhất duy
nhất. Kết luận tương tự cho phần tử lớn nhất và
phần tử tối đại.
13/04/2010 32
13/04/2010
9
5.7. Định lý:
Trong một tập hợp sắp thứ tự hữu hạn ta có:
5. Quan hệ thứ tự
1) Mọi phần tử trội (tương ứng, được trội bởi)
một phần tử tối tiểu (tương ứng, tối đại).
2) Nếu a là phần tử tối tiểu (tương ứng tối đại),
duy nhất của X thì a là phần tử nhỏ nhất (tương
ứng, phần tử lớn nhất).
13/04/2010 33
5.8. Thứ tự tự điển:
Cho (A, ) là một tập hữu hạn, khác rỗng, có thứ
ầ ẫ
5. Quan hệ thứ tự
≺
tự toàn ph n, gọi là tập m u tự. Gọi S là tập hợp
tất cả các chuỗi kí tự có dạng s = a1a2 ... an với
n ∈ N và a1, a2, ..., an ∈ A (với n = 0 ta có chuỗi
rỗng ∅ không có ký tự nào). Trong S ta qui ước:
với s = a1a2 ... an và t = b1b2 ... bm:
s = t ⇔ (n = m và ai = bi, i = )
Trên S ta định nghĩa quan hệ như sau:
13/04/2010 34
1,n
≺
5.8. Thứ tự tự điển:
1) ∀s ∈ S , ∅ s;
5. Quan hệ thứ tự
≺
2) ∀s, t ∈ S , s = a1a2 ... an và t = b1b2 ... bm
Khi đó là quan hệ thứ tự toàn phần trên S Ta
1 1 1 1
, , 1, ;
min{ , }, ,..., ,
i i
k k k k
n m a b i ns t
k n m a b a b a b− −
⎡ ≤ = =⇔ ⎢∃ ≤ = = <⎣
≺
≺ .
gọi đây là thứ tự tự điển trên S ứng với tập mẫu
tự (A, ).
13/04/2010 35
≺