Giáo trình Cấu trúc rời rạc - Bài tập chương 5: Quan hệ
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Bài tập chương 5
Quan hệ
1 Dẫn nhập
Trong bài tập dưới đây, chúng ta sẽ làm quen với các kiến thức liên quan đến lý thuyết tập hợp (bao
gồm quan hệ, quan hệ tương đương và quan hệ thứ tự). Sinh viên cần ôn lại lý thuyết của chương 5
trước khi làm bài tập bên dưới.
2 Bài tập mẫu
Câu 1.
Cho quan hệ R = {(1, 1), (2, 3), (3, 2)} trên tập X = {1, 2, 3}. Hãy xác định nếu R là
a) phản xạ
b) đối xứng
c) bắc cầu
Lời giải.
a) Quan hệ R không có tính chất phản xạ vì (2, 2) ∈/ R;
b) Quan hệ R có tính chất đối xứng đối xứng vì R−1 = R;
c) Quan hệ R không có tính chất bắc cầu vì (3, 2) ∈ R và (2, 3) ∈ R, nhưng (3, 3) ∈/ R.
2
Câu 2.
Quan hệ R trên N được định nghĩa bởi “n R m nếu và chỉ nếu m = n + 1” là
a) đối xứng?
b) phản xạ?
c) bắc cầu?
Lời giải.
a) Nếu R có tính chất đối xứng, ta sẽ có m = n + 1 ⇐⇒ n = m + 1 (vô lý!).
b) Nếu R có tính chất phản xạ, thì n = n + 1 (vô lý!).
c) Nếu R có tính chất bắc cầu, thì ta sẽ có m = n + 1 và p = m + 1 =⇒ p = n + 1 (vô lý!)
2
Câu 3.
Vẽ ma trận và đồ thị có hướng tương ứng với quan hệ R trong câu 1
Giáo trình Cấu Trúc Rời Rạc
Trang 1/8
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Lời giải.
1 0 1
• Ma trận : 0 0 1
0 1 0
1
2
3
• Đồ thị :
2
3 Bài tập cần giải
Câu 4.
Cho Z là tập hợp các số nguyên, L là tập hợp các đường thẳng trong mặt phẳng. Xác định các quan
hệ sau có tính phản xạ, đối xứng, phản đối xứng, bắc cầu, tương đương hay không? Giải thích.
a) Trên tập {1, 2, 3, 4} , các quan hệ sau:
R1 = {(1, 1), (2, 2), (3, 3)}
R2 = {(4, 2), (2, 4), (2, 2), (2, 3), (3, 2), (3, 3), (4, 4)}
R3 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
R4 = {(1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 4)}
R5 = {(4, 4), (4, 1), (4, 2), (1, 4), (1, 1), (1, 2), (2, 4), (2, 2), (3, 3)}
R6 = {(1, 2)}
b) Trên tập Z, các quan hệ: “=”, “≡”, “≤”, “=”
c) Trên tập L, các quan hệ: “//”, “⊥”, “cắt nhau”, “chéo nhau”.
d) Trên tập Z, các quan hệ sau:
R7 : xRy ⇔ (x + y) chẵn
R8 : xRy ⇔ (x − y) chẵn
R9 : xRy ⇔ (x2 + y2) chẵn
e) Trên tập R, các quan hệ sau:
R10 : xRy ⇔ |x| = |y|
R11 : xRy ⇔ sin2 x + cos2 y = 1
f) Trên tập ZxZ, quan hệ R12 : (a, b)R(c, d) ⇔ a ≤ c
Câu 5.
Vẽ ma trận và đồ thị có hướng tương ứng với quan hệ Rx(1 ≤ x ≤ 6) trong câu 4a
Giáo trình Cấu Trúc Rời Rạc
Trang 2/8
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Câu 6.
Cho các ma trận và đồ thị có hướng tương ứng với một quan hệ Rx trên tập {1, 2, 3, 4}. Xác định các
quan hệ Rx có tính phản xạ, đối xứng, phản đối xứng, bắc cầu, tương đương hay không? Giải thích.
0 0 0 0
0 1 1 1
0 1 1 1
0 0 0 0
a)
b)
c)
1 1 0 0
1 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 1 0 0
0 0 1 0
0 0 0 4
0 0 0 0
d)
1
2
3
4
e)
2
4
1
3
f)
Câu 7.
Hãy tìm một quan hệ trên A = {1, 2, 3, 4} sao cho nó có tính chất:
a) Phản xạ và đối xứng nhưng không bắc cầu.
b) Phản xạ và bắc cầu nhưng không đối xứng.
c) Bắc cầu và đối xứng nhưng không phản xạ.
Câu 8.
Trên tập {1, 2, 3, 4}, cho các quan hệ sau:
R1 = {(1, 1), (2, 2), (3, 3)}
R2 = {(4, 2), (2, 4), (2, 2), (2, 3), (3, 2), (3, 3), (4, 4)}
Giáo trình Cấu Trúc Rời Rạc
Trang 3/8
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
R3 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
R4 = {(1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 4)}
R5 = {(4, 4), (4, 1), (4, 2), (1, 4), (1, 1), (1, 2), (2, 4), (2, 2), (3, 3)}
R6 = {(1, 2)}
Tìm:
a) R1 ◦ R2, R1 ◦ R3, R1 ◦ R4, R1 ◦ R5, R1 ◦ R6
b) R2 ◦ R3 ◦ R4 ◦ R6
c) (R3)2
d) (R3)4
e) Bao đóng phản xạ của R2
f) Bao đóng đối xứng của R1 ◦ R2
g) Bao đóng bắc cầu của R6
Câu 9.
Liệt kê các cặp trong quan hệ tương đương được tạo bởi các phân hoạch sau của {0, 1, 2, 3, 4, 5}.
1. {0}, {1,2}, {3,4,5}
2. {0,1}, {2,3}, {4,5}
3. {0,1,2}, {3,4,5}
4. {0}, {1}, {2}, {3}, {4}, {5}
Câu 10.
Quan hệ trên tập {0,1,2,3} nào sau đây là thứ tự bộ phận? Nếu không có thứ tự bộ phận, xác định
các tính chất của một thứ tự bộ phận mà quan hệ đó còn thiếu.
1. {(0,0), (1,1), (2,2), (3,3) }
2. {(0,0), (1,1), (2,0), (2,2), (2,3), (3,2), (3,3)}
3. {(0,0), (1,1), (1,2), (2,2), (3,3)}
4. {(0,0), (1,1), (1,2), (1,3), (2,2), (2,3), (3,3)}
5. {(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,2), (3,3)}
Câu 11.
Trả lời các câu hỏi sau đối với poset ({2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72}, |).
1. Tìm phần tử cực đại.
2. Tìm phần tử cực tiểu.
3. Có phần tử lớn nhất hay không?
4. Có phần tử nhỏ nhất hay không?
5. Tìm tất cả cận trên của {2,9}.
6. Tìm cận trên nhỏ nhất của {2,9}, nếu có.
7. Tìm tất cả cận dưới của {60,72}.
Giáo trình Cấu Trúc Rời Rạc
Trang 4/8
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
8. Tìm cận dưới lớn nhất của {60,72}, nếu có.
Câu 12.
Cho quan hệ R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4), (4, 5), (5, 4), (5, 5), (6, 6)} trên tập A = {1, 2, 3, 4, 5, 6}
a) R có phải là một quan hệ tương đương không? Vì sao?
b) Tìm các lớp tương đương [1], [2], [3], [4], [5], [6]
c) Tìm phân hoạch của A thành các lớp tương đương ở câu b.
Câu 13.
Cho A = {1, 2, 3, 4, 5} × {1, 2, 3, 4, 5} và R là quan hệ trên A sao cho:
(a, b)R(c, d) ⇔ a + b = c + d
a) R có phải là một quan hệ tương đương không? Vì sao?
b) Tìm các lớp tương đương [(1,3)], [(2,4)], [(1,1)]
c) Tìm phân hoạch của A thành các lớp tương đương ở câu b.
Câu 14.
Quan hệ nào sau đây là poset?
a) (Z, =)
b) (Z, =)
c) (Z, ≥)
d) (Z, -)
Câu 15.
Các cặp phần tử nào trong đây là so sánh được trong poset (Z+, |)?
1. 5, 15
2. 6, 9
3. 8, 16
4. 7, 7
Câu 16.
Một tập hợp có thứ tự bộ phận (poset) trên tập hợp A được nói là có thứ tự bộ phận tốt nếu mọi tập
hợp khác ∅ của A đều có phần tử bé nhất. Khi ấy ta nói (A, p) được sắp tốt. Cho biết trong các tập
hợp dưới đây, tập hợp nào sắp thứ tự tốt?
a) (N, ≤)
b) (Z, ≤)
c) (Q, ≤)
d) (Q+, ≤)
e) (P, ≤) trong đó P là tập hợp các số nguyên tố.
f) (A, ≤) trong đó A = ∅) là một tập con hữu hạn của Z.
Giáo trình Cấu Trúc Rời Rạc
Trang 5/8
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Câu 17.
a) Cho ví dụ của một tập hợp sắp tốt không có phần tử lớn nhất.
b) Cho ví dụ của một tập hợp sắp tốt có phần tử lớn nhất.
c) Chứng minh rằng mọi tập có thứ tự bộ phận tốt đều là tập có thứ tự toàn phần.
d) Điều ngược lại của câu c có đúng không?
4 Bài tập thêm
Câu 18.
Trong các quan hệ sau trên tập {1, 2, 3, 4}, xác định xem nó có phản xạ, đối xứng, phản đối xứng và
bắc cầu hay không
1. {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}
2. {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
3. {(2, 4), (4, 2)}
4. {(1, 2), (2, 3), (3, 4)}
5. {(1, 1), (2, 2), (3, 3), (4, 4)}
6. {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}
Câu 19.
Quan hệ R trên N được định nghĩa bởi “n R m nếu và chỉ nếu m và n có cùng ước số chung lớn hơn
1” là
a) đối xứng?
b) phản xạ?
c) bắc cầu?
Câu 20.
Xác định quan hệ R trên tập tất cả mọi người là phản xạ, đối xứng, phản đối xứng hay bắc cầu. Biết
rằng (a, b) ∈ R nếu và chỉ nếu
a) a cao hơn b;
b) a và b sinh cùng ngày;
c) a và b có cùng ông bà nội.
Câu 21.
Liệt kê các cặp có thứ tự trong quan hệ trên tập {1, 2, 3, 4} tương ứng với ma trận sau (trong đó hàng
và cột tương ứng với số nguyên liệt kê theo thứ tự tăng dần)
1 1 0 1
1 0 1 0
0 1 1 1
1 0 1 1
a)
Giáo trình Cấu Trúc Rời Rạc
Trang 6/8
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
1 1 1 0
0 1 0 0
0 0 1 1
1 0 0 1
b)
c)
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
Câu 22.
Xác định các quan hệ trong bài trên có phản xạ, đối xứng, phản đối xứng và bắc cầu hay không.
Câu 23.
Vẽ đồ thị có hướng từ 3 ma trận ở Bài 4 và dựa vào đó, vẽ đồ thị có hướng của bao đóng phản xạ, và
vẽ đồ thị có hướng của bao đóng đối xứng.
Câu 24.
Cho R là quan hệ {(a, b) | a = b} trên tập số nguyên. Bao đóng phản xạ của R là gì?
Câu 25.
Tìm thứ tự của các chuỗi sau theo chữ cái tiếng Anh:
1. quack, quick, quicksilver, quicksand, quacking
2. open, opener, opera, operand, opened
3. zoo, zero, zoom, zoology, zoological
Câu 26.
Xác định xem quan hệ R trên tập tất cả các trang Web là phản xạ, đối xứng, phản đối xứng, hay bắc
cầu, trong đó (a, b) ∈ R khi và chỉ khi
1. Tất cả những ai đã xem trang Web a cũng xem trang Web b.
2. Tại cả hai trang Web a và b không có liên kết nào giống nhau.
3. Có ít nhất một liên kết giống nhau trên trang Web a và trang Web b.
4. Có một trang Web có chứa liên kết đến cả trang Web a lẫn trang Web b.
Câu 27.
Cho R là một quan hệ trên tập {1, 2, 3, 4, 5} có chứa các cặp (1,1), (1,2), (1,3), (2,3), (2,4), (3,1), (3,4),
(3,5), (4,2), (4,5), (5,1), (5,2) và (5,4). Tìm
a) R2.
b) R3.
c) R4
d) R5.
Câu 28.
Cho R là quan hệ trên tập {0,1,2,3} có chứa các cặp (0,1), (1,1), (1,2), (2,0), (2,2) và (3,0). Tìm
a) bao đóng phản xạ của R.
b) bao đóng đối xứng của R.
c) bao đóng bắc cầu của R.
Giáo trình Cấu Trúc Rời Rạc
Trang 7/8
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Câu 29.
Cho ma trận quan hệ trên tập {a, b, c, d} như sau (trong đó hàng và cột tương ứng với chữ cái liệt kê
theo thứ tự tăng dần)
0 1 1 0
1 0 0 0
0 0 0 1
0 1 1 0
1.
2.
3.
1 1 0 0
0 0 1 0
1 0 0 0
0 0 0 0
0 1 1 1
1 0 0 1
1 0 0 0
0 1 0 0
Vẽ đồ thị có hướng từ 3 ma trận trên và dựa vào đó, vẽ đồ thị có hướng của bao đóng phản xạ, và vẽ
đồ thị có hướng của bao đóng đối xứng.
Câu 30.
Các quan hệ sau trên {0, 1, 2, 3}, quan hệ nào là tương đương. Nếu không phải, hãy chỉ ra tính chất
còn thiếu để nó trở thành tương đương. Nếu là tương đương, hãy chỉ ra các lớp đương tương của nó.
a) {(0, 0), (1, 1), (2, 2), (3, 3)}
b) {(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}
c) {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
d) {(0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}
e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 2), (3, 3)}
5 Bài tập nâng cao
Câu 31.
Gọi R là một quan hệ phản xạ. Chứng minh rằng Rn cũng là một quan hệ phản xạ với mọi số nguyên
dương n.
Câu 32.
Làm thế nào để xác định trên ma trận quan hệ R trên tập A là phi phản xạ? Với định nghĩa một
quan hệ R trên tập A là phi phản xạ nếu với mọi a ∈ A, (a, a) ∈/ R.
Câu 33.
Làm thế nào để xác định trên ma trận quan hệ R trên tập A là phi đối xứng? Với định nghĩa một
quan hệ R được gọi là phi đối xứng nếu (a, b) ∈ R nghĩa là (b, a) ∈/ R.
Câu 34.
Cho R là quan hệ {(a, b) | a là ước của b} trên tập số nguyên. Bao đóng đối xứng của R là gì?
6 Tổng kết
Thông qua các bài tập trong phần này, chúng ta đã hiểu rõ hơn và làm quen với lý thuyết về quan hệ
(bao gồm quan hệ tương đương và quan hệ thứ tự) mà chi tiết về lý thuyết đã được trình bày trong
slide chương 5.
Giáo trình Cấu Trúc Rời Rạc
Trang 8/8
8 trang
26/04/2022
6120
Bạn đang xem tài liệu "Giáo trình Cấu trúc rời rạc - Bài tập chương 5: Quan hệ", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_cau_truc_roi_rac_bai_tap_chuong_5_quan_he.pdf
