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

TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016
Chương 5
QUAN HỆ
lvluyen@hcmus.edu.vn
∼luyen/trr
FB: fb.com/trr2015
Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh
lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 1/39
Nội dung
Chương 5. QUAN HỆ
1. Quan hệ hai ngôi
2. Quan hệ tương đương
3. Quan hệ thứ tự
lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 2/39
5.1. Quan hệ hai ngôi
1 Định nghĩa
2 Các tính chất của quan hệ
lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 3/39
5.1.1. Định nghĩa
Định nghĩa. Một quan hệ hai ngôi từ tập A đến tập B là tập con
R của tích Descartes A×B.
Quan hệ từ A đến chính nó được gọi là quan hệ hai ngôi (hay quan
hệ ) trên A.
Ví dụ. Cho A = {0, 1, 2} và B = {a, b}. Khi đó
R = {(0, a), (0, b), (1, a), (2, b)}
là một quan hệ từ A vào B. Quan hệ này được mô tả bằng
lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 4/39
Ví dụ. Cho A = {1, 2, 3, 4}, và R = {(a, b) | a là ước của b}. Khi đó R
là một quan hệ trên A. Hãy tìm R?
Giải. R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.
Ví dụ. Cho A = {1, 2, 3, 4}. Hỏi ta có thể xây dựng được bao nhiêu
qua hệ trên A?
Giải. Vì |A| = 4 nên |A×A| = 16. Do mỗi quan hệ trên A là một tập
con của |A×A| nên số quan hệ trên A là 216.
Ví dụ.(tự làm) Cho A = {1, 2, 3}. Hãy tìm số quan hệ hai ngôi trên A
a) chứa (1, 1).
b) có đúng 5 phần tử.
c) có ít nhất 7 phần tử.
lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 5/39
Định nghĩa. Cho R là quan hệ trên A và x, y ∈ A. Ta nói:
i) x quan hệ R với y nếu (x, y) ∈ R, ký hiệu xRy.
ii) x không quan hệ R với y nếu (x, y) /∈ R , ký hiệu xRy.
Ví dụ. Cho A = {1, 2, 3} và R = {(1, 1), (1, 2), (2, 3), (1, 3)} là một
quan hệ trên A. Khi đó
1R1, 1R2, 2R3, 1R3, 2R1, 2R2, . . .
Ví dụ. Cho A = {1, 2, 3, 4, 5, 6, 7, 8}. Một quan hệ R trên A được xác
định như sau:
xRy ⇔ x− y chia hết cho 4.
Ta có:
1R5, 5R1, 7R7, 1R2, 3R6, . . .
lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 6/39
5.1.2. Các tính chất của Quan hệ
Định nghĩa. Cho R là quan hệ trên A. Ta nói
i) R phản xạ ⇔ ∀x ∈ A, xRx.
ii) R đối xứng ⇔ ∀x, y ∈ A, xRy → yRx.
iii) R phản xứng ⇔ ∀x, y ∈ A, xRy ∧ yRx→ x = y.
iv) R bắc cầu (hay còn gọi là truyền) ⇔
∀x, y, z ∈ A, xRy ∧ yRz → xRz.
Nhận xét. Cho R là quan hệ trên A. Khi đó:
i) R không phản xạ ⇔ ∃x ∈ A, xRx.
ii) R không đối xứng ⇔ ∃x, y ∈ A, xRy ∧ yRx.
iii) R không phản xứng ⇔ ∃x, y ∈ A, xRy ∧ yRx ∧ x 6= y.
iv) R không bắc cầu ⇔ ∃x, y, z ∈ A, xRy ∧ yRz ∧ xRz.
lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 7/39
Ví dụ. Trên tập hợp số nguyên, ta xét những quan hệ sau:
R1 = {(a, b) | a ≤ b},
R2 = {(a, b) | a > b},
R3 = {(a, b) | a = b hay a = −b},
R4 = {(a, b) | a = b+ 1},
R5 = {(a, b) | a+ b ≤ 3}.
Hỏi những quan hệ trên có tính chất nào?
Ví dụ. Trên tập hợp A = {1, 2, 3, 4}, ta xét những quan hệ sau:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
Hỏi những quan hệ trên có tính chất nào?
lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 8/39
Ví dụ.(tự làm) Cho S = {1, 2, 3} và quan hệ hai ngôi
R = {(2, 2), (1, 3), (3, 3), (1, 2), (1, 1), (2, 1)}
trên S. Xét các tính chất phản xạ, đối xứng, phản xứng và bắc cầu của
quan hệ R?
Ví dụ.(tự làm) Cho S = {1, 2, 3} và
R = {(1, 1); (1, 2); (2, 3); (3, 2); (3, 3)}
là một quan hệ hai ngôi trên S. Xét các tính chất phản xạ, đối xứng,
phản xứng và bắc cầu của R.
Ví dụ.(tự làm) Cho S = {1, 2, 3}. Đặt
∀x, y ∈ S, xRy ⇔ 3(x+ y) = xy + 9.
Liệt kê tất cả (x, y) ∈ S2 thỏa xRy và xét 4 tính chất phản xạ, đối
xứng, phản xứng và bắc cầu của R.
lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 9/39
Ví dụ. Cho R là quan hệ trên Z, được xác định bởi
∀x, y ∈ Z, xRy ⇔ x+ y chẵn.
Xác định các tính chất của R.
Giải.
(i) ∀x ∈ Z, vì x+ x = 2x chẵn nên xRx. Do đó R phản xạ.
(ii) ∀x, y ∈ Z, nếu xRy thì x+ y chẵn nên y + x cũng chẵn, nghĩa là
yRx. Do đó R đối xứng.
(iii) Ta có 1R3 và 3R1, nhưng 1 6= 3. Do đó R không phản xứng.
(iv) ∀x, y, z ∈ Z, nếu xRy và yRz thì x+ y và y + z chẵn. Mà
x+ z = (x+ y) + (y + z)− 2y,
nên x+ z cũng là số chẵn, nghĩa là xRz. Do đó R bắc cầu.
Vậy R thỏa mãn các tính chất phản xạ, đối xứng và bắc cầu, nhưng
không phản xứng.
lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 10/39
5.2. Biểu diễn quan hệ bằng ma trận
Ví dụ. Cho R là quan hệ từ A = {1, 2, 3, 4} đến B = {u, v, w},
R = {(1, u), (1, v), (2, w), (3, w), (4, u)}.
Khi đó R có thể biễu diễn như sau
Dòng và cột tiêu đề có thể bỏ qua nếu không gây hiểu nhầm.
lvluyen@hcmus.edu.vn Chương 5. Quan hệ 14/12/2015 11/39
Định nghĩa. Cho R là quan hệ từ A = {a1, a2, . . . , am} đến
B = {b1, b2, . . . , bn}. Ma trận biểu diễn của R là ma trận cấp m× n
MR = (mij) xác định bởi
mij =
{
0 nếu (ai, bj) /∈ R
1 nếu (ai, bj) ∈ R
Ví dụ. Nếu R l