Giáo trình Toàn rời rạc 1 - 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ý!).
Giáo trình Toán Rời Rạc 1
Trang 1/9
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) 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
3 Bài tập cần giải
Câu 3.
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)}
Lời giải.
1. Không phản xạ (thiếu (1,1)), không đối xứng (có (2,4) nhưng không có (4,2)), không
phản đối xứng (có (2,3) và (3,2) nhưng 2 = 3), có bắc cầu
2. Có phản xạ, có đối xứng, không phản đối xứng (có (1,2) và (2,1) nhưng 2 = 1), có
bắc cầu
3. Không phản xạ, có đối xứng, không có phản đối xứng, không có bắc cầu
4. Không phản xạ, không có đối xứng, có phản đối xứng, không có bắc cầu
5. Có phản xạ, có đối xứng, có phản đối xứng, có bắc cầu
6. Không có phản xạ, không có đối xứng, không có phản đối xứng, không có bắc cầu
2
Câu 4.
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à
Giáo trình Toán Rời Rạc 1
Trang 2/9
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
a) đối xứng?
b) phản xạ?
c) bắc cầu?
Lời giải.
a) Để R có tính chất đối xứng, thì với mọi m, n ∈ N, nếu (m, n) ∈ R thì (n, m) ∈ R. Giả
sử (m, n) có ước số chung là k > 1 thì rõ ràng (n, m) cũng có ước số chung là k. Vậy
quan hệ này đối xứng.
b) Để R có tính chất phản xạ, thì với mọi m ∈ N, (m, m) ∈ R. Trong các số tự nhiên, ta
tìm thấy cặp (1, 1) ∈/ R vì chúng có ước số chung là 1. Vậy R không có tính phản xạ.
c) Để R có tính chất bắc cầu, thì với mọi m, n, p ∈ N, nếu (m, n) ∈ R và (n, p) ∈ R thì
(m, p) ∈ R. Tìm thấy một cặp (2, 6) ∈ R và (6, 9) ∈ R nhưng rõ ràng (2, 9) ∈/ R. Vậy
nó không có bắc cầu.
2
Câu 5.
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.
Lời giải.
a) Đây là quan hệ không phản xạ (một người không thể cao hơn chính mình), không đối
xứng, có phản đối xứng (vì không thể tìm được 2 người mà người này cao hơn người kia,
và người kia cao hơn người này) và có bắc cầu.
b) Đây là quan hệ phản xạ, đối xứng, không có phản đối xứng và có tính bắc cầu.
c) Quan hệ này là quan hệ phản xạ, đối xứng, không có phản đối xứng và có tính bắc cầu.
2
Câu 6.
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}
Giáo trình Toán Rời Rạc 1
Trang 3/9
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
2. {0,1}, {2,3}, {4,5}
3. {0,1,2}, {3,4,5}
4. {0}, {1}, {2}, {3}, {4}, {5}
Lời giải.
a) {(0,0), (1,1), (2,2), (1,2), (2,1), (3,3), (4,4), (5,5), (3,4), (4,3), (3,5), (5,3), (4,5),
(5,4)}
b) {(0,0), (1,1), (0,1), (1,0), (2,2), (3,3), (2,3), (3,2), (4,4), (5,5), (4,5), (5,4)}
c) {(0,0), (1,1), (2,2), (0,1), (1,0), (0,2), (2,0), (1,2), (2,1), (3,3), (4,4), (5,5), (3,4),
(4,3), (3,5), (5,3), (4,5), (5,4)}
d) {(0,0), (1,1), (2,2), (3,3), (4,4), (5,5)}
2
Câu 7.
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)}
Lời giải.
a) Là thứ tự bộ phận
b) Không là thứ tự bộ phận (không phản đối xứng)
c) Là thứ tự bộ phận
d) Là thứ tự bộ phận
e) Không phải thứ tự bộ phận (không phản đối xứng, không bắc cầu)
Giáo trình Toán Rời Rạc 1
Trang 4/9
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
2
Câu 8.
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}.
8. Tìm cận dưới lớn nhất của {60,72}, nếu có.
Lời giải.
a) 27, 48, 60, 72
b) 2, 9
c) Không
d) Không
e) 18, 36, 72
f) 18
g) 12, 6, 4, 2
h) 12
2
Câu 9.
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)
Giáo trình Toán Rời Rạc 1
Trang 5/9
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 0 1
1 0 1 0
0 1 1 1
1 0 1 1
a)
b)
c)
1 1 1 0
0 1 0 0
0 0 1 1
1 0 0 1
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
Lời giải.
a) {(1,1), (1,2), (1,4), (2,1), (2,3), (3,2), (3,3), (3,4), (4,1), (4,3), (4,4)}
b) {(1,1), (1,2), (1,3), (2,2), (3,3), (3,4), (4,1), (4,4)}
c) {(1,2), (1,4), (2,1), (2,3), (3,2), (3,4), (4,1), (4,3)}
2
Câu 10.
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.
Lời giải.
a) Không phản xạ, đối xứng, không phản đối xứng, không bắc cầu
b) Phản xạ, không đối xứng, có phản đối xứng, không bắc cầu
c) Không phản xạ, đối xứng, không phản đối xứng, không bắc cầu
2
Câu 11.
Vẽ đồ thị có hướng từ 3 ma trận ở Bài 3 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.
Lời giải. Sinh viên tự thực hiện
2
Câu 12.
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ì?
Lời giải. Z × Z
2
Giáo trình Toán Rời Rạc 1
Trang 6/9
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
4 Bài tập nâng cao
Câu 13.
Quan hệ nào sau đây là poset?
a) (Z, =)
b) (Z, =)
c) (Z, ≥)
d) (Z, -)
Câu 14.
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 15.
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 16.
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 17.
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
Giáo trình Toán Rời Rạc 1
Trang 7/9
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
a) R2.
b) R3.
c) R4
d) R5.
Câu 18.
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 19.
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 20.
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 21.
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.
Câu 22.
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ì?
Câu 23.
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.
1 1 0 0
0 0 1 0
1 0 0 0
0 0 0 0
Giáo trình Toán Rời Rạc 1
Trang 8/9
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
0 1 1 1
1 0 0 1
3.
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 24.
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)}
Câu 25.
Cho R là quan hệ trên tập gồm các cặp số nguyên dương sao cho ((a, b), (c, d)) ∈ R nếu và
chỉ nếu a + d = b + c.
a) Chứng minh rằng R là một quan hệ tương đương.
b) Lớp tương đương của (1,2) với quan hệ tương đương R là gì?
c) Hãy biểu diễn bằng lời các lớp tương đương của quan hệ tương đương R.
5 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 Toán Rời Rạc 1
Trang 9/9
9 trang
18040
Free
Bạn đang xem tài liệu "Giáo trình Toàn rời rạc 1 - 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_toan_roi_rac_1_bai_tap_chuong_5_quan_he.pdf
