›
›

Bài tập Cấu trúc rời rạc - Chương 4: Relation

Download
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 4  
Relation  
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 quan hệ.  
Sinh viên cần ôn lại lý thuyết của Chương 4 trước khi làm bài tập bên dưới.  
2 Bài tập cần giải  
It is recommended that you should do as much as possible all the Problems in Rosen’s  
Chapter 9 (7th ed.), and related Problems in Bender and Williamson’s book.  
The following exercises are minimal requirement for understanding relations at basic  
level.  
Exercise 1.  
For each of these relations on the set {1, 2, 3, 4}, decide whether it is reflexive, whether it  
is symmetric, whether it is antisymmetric, and whether it is transitive.  
a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}  
b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}  
c) {(2, 4), (4, 2)}  
d) {(1, 2), (2, 3), (3, 4)}  
e) {(1, 1), (2, 2), (3, 3), (4, 4)}  
f) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}  
Exercise 2.  
Determine whether the relation R on the set of all real numbers is reflexive, symmetric,  
antisymmetric, and/or transitive, where (x, y) ∈ R if and only if  
a) x + y = 0  
b) x = ±y  
c) x − y is a rational number.  
d) x = 2y  
Giáo trình Cấu Trúc Rời Rạc  
Trang 1/6  
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh  
Khoa Khoa Học và Kỹ Thuật Máy Tính  
e) xy ≥ 0  
f) xy = 0  
g) x = 1  
h) x = 1 or y = 1  
i) x ≡ y (mod 7)  
Exercise 3.  
Let R1 = {(1, 2), (2, 3), (3, 4)} and R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (3, 4)}  
be relations from {1, 2, 3} to {1, 2, 3, 4}. Find  
a) R1 ∪ R2  
b) R1 ∩ R2  
c) R1 − R2  
d) R2 − R1  
Exercise 4.  
Let R1 and R2 be the "congruent modulo 3" and the "congruent modulo 4" relations,  
respectively, on the set of integers. That is, R1 = {(a, b)|a ≡ b( mod 3)} and R2  
=
{(a, b)|a ≡ b( mod 4)}. Find  
a) R1 ∪ R2  
b) R1 ∩ R2  
c) R1 − R2  
d) R2 − R1  
Exercise 5.  
Let R be the relation on the set {1, 2, 3, 4, 5} containing the ordered pairs (1,1), (1,2), (1,3),  
(2,3), (2,4), (3,1), (3,4), (3,5), (4,2), (4,5), (5,1), (5,2) and (5,4). Find R2, R3.  
Exercise 6.  
For each of these relations on the set {1,2,3,4}, let  
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)}.  
Find  
Giáo trình Cấu Trúc Rời Rạc  
Trang 2/6  
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) R1 ◦ R2, R1 ◦ R3, R1 ◦ R4, R1 ◦ R5, R1 ◦ R6  
b) R2 ◦ R3 ◦ R4 ◦ R6  
c) (R3)2  
d) (R3)4  
e) reflexive closure của R2  
f) symmetric closure của R1 ◦ R2  
g) transitive closure của R6  
Exercise 7.  
Give an example of a relation on a set {1,2,3,4} that is  
a) reflexive and symmetric, but not transitive.  
b) reflexive and transitive, but not symmetric.  
c) transitive and symmetric, but not reflexive.  
Exercise 8.  
a) How many relations are there on the set {a, b, c, d}?  
b) How many relations are there on the set {a, b, c, d} that contain the pair (a, a)?  
Exercise 9.  
List the ordered pairs in the relations on {1, 2, 3, 4} corresponding to these matrices (where  
the rows and columns correspond to the integers listed in increasing order).  
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  
Giáo trình Cấu Trúc Rời Rạc  
Trang 3/6  
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh  
Khoa Khoa Học và Kỹ Thuật Máy Tính  
Exercise 10.  
Draw the directed graph that represents the relation {(a, a), (a, b), (b, c), (c, b), (c, d), (d, a), (d, b)}  
Exercise 11.  
Let R be the relation that contains the pair (a, b) if a and b are cities such that there is a  
direct non-stop airline flight from a to b. When is (a, b) in  
a) R2 ?  
b) R3 ?  
Exercise 12.  
Let R be the relation on the set {0, 1, 2, 3} containing the ordered pairs (0,1), (1,1), (1,2),  
(2,0), (2,2) and (3,0). Find the  
a) reflexive closure of R.  
b) symmetric closure of R.  
c) transitive closure of R.  
Exercise 13.  
Let R be the relation {(a, b)|a divides b} on the set of integers. What is the symmetric  
closure of R?  
Exercise 14.  
Find the smallest relation containing the relation {(1, 2), (1, 4), (3, 3), (4, 1)} that is  
a) reflexive and transitive  
b) symmetric and transitive  
c) reflexive, symmetric and transitive  
Exercise 15.  
Which of these relations on {0, 1, 2, 3} are equivalence relations? Determine the properties  
of an equivalence relation that the others lack.  
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)}  
Exercise 16.  
Which of these collections of subsets are partitions of {1, 2, 3, 4, 5, 6}?  
Giáo trình Cấu Trúc Rời Rạc  
Trang 4/6  
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) {1,2}, {2,3,4}, {4,5,6}  
b) {1}, {2, 3, 6}, {4}, {5}  
c) {2,4,6}, {1,3,5}  
d) {1,4,5}, {2,6}  
Exercise 17.  
List the ordered pairs in the equivalence relations produced by these partitions of {0, 1, 2,  
3, 4, 5}.  
a) {0}, {1,2}, {3,4,5}  
b) {0,1}, {2,3}, {4,5}  
Exercise 18.  
Let R be the relation on the set of real numbers such that aRb if and only if a − b is an  
integer.  
a) Is R an equivalence relation?  
b) What is the equivalence class of 1 for this equivalence relation?  
c) What is the equivalence class of 1/2 for this equivalence relation?  
Exercise 19.  
Let R be the relation on the set A = {1, 2, 3, 4, 5} such that  
(a, b)R(c, d) ⇔ a + b = c + d  
a) Is R an equivalence relation?  
b) What is the equivalence class of [(1,3)], [(2,4)], [(1,1)]?  
c) Find the partition of set A formed by the equivalence classes of part b.  
Exercise 20.  
Which of these relations on {0, 1, 2, 3} are partial orderings? Determine the properties of  
a partial ordering that the others lack.  
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)}  
Giáo trình Cấu Trúc Rời Rạc  
Trang 5/6  
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh  
Khoa Khoa Học và Kỹ Thuật Máy Tính  
5. {(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,2), (3,3)}  
Exercise 21.  
Which of these are posets?  
a) (Z, =)  
b) (Z, =)  
c) (Z, ≥)  
d) (Z, -)  
Giáo trình Cấu Trúc Rời Rạc  
Trang 6/6  
pdf 6 trang baolam 22440 Free
Download
Bạn đang xem tài liệu "Bài tập Cấu trúc rời rạc - Chương 4: Relation", để 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:

  • pdfbai_tap_cau_truc_roi_rac_chuong_4_relation.pdf