›
›

Tài liệu Cấu trúc rời rạc cho khoa học máy tính - Chapter 4: Relations

Download
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH  
TRƯỜNG ĐẠI HỌC BÁCH KHOA  
KHOA KHOA HỌC - KỸ THUẬT MÁY TÍNH  
CẤU TRÚC RỜI RẠC CHO KHMT (CO1007)  
Nhóm:18-TDTT —- Homework  
CHAPTER 4  
Relations  
GVHD: Nguyễn An Khương  
SV thực hiện: Đinh Minh Tân – 1613074  
Trương Minh Tiến – 1613544  
Vũ Đào Anh Tuấn – 1613938  
Nguyễn Thị Trà My – 51305086  
Tp. Hồ Chí Minh, Tháng 11/2016  
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 1.  
a) transitive  
b) reflexive, symmetric, transitive  
c) symmetric  
d) antisymmetric  
e) reflexive, antisymmetric, transitive  
f) nothing  
Exercise 2.  
a) symmetric  
b) reflexive, symmetric, transitive  
c) reflexive, symmetric, transitive  
d) antisymmetric  
e) reflexive, symmetric, transitive  
f) symmetric  
g) antisymmetric, transitive  
h) symmetric  
i) reflexive, symmetric, transitive  
Exercise 3.  
a) R1 ∪ R2 = {(1, 2), (2, 3), (3, 4), (1, 1), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3)}  
b) R1 ∩ R2 = {(1, 2), (2, 3), (3, 4)}  
c) R1 − R2 = ∅  
d) R2 − R1 = {(1, 2), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3)}  
Exercise 4.  
a) R1 ∪ R2 = {(a, b)|a ≡ b(mod3) ∨ a ≡ b(mod4)}  
b) R1 ∩ R2 = {(a, b)|a ≡ b(mod12)}  
c) R1 − R2 = {(a, b)|a − b = 12k + i, k ∈ Z, i ∈ {3, 6, 9}}  
d) R2 − R1 = {(a, b)|a − b = 12k + i, k ∈ Z, i ∈ {4, 8}}  
Chương 4: Homework  
Trang 1/5  
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 5.  
a) R = {(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (3, 1), (3, 4), (3, 5), (4, 2), (4, 5), (5, 1), (5, 2), (5, 4)}  
b) R2 = R◦R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 4), (2, 5), (2, 2), (3, 1), (3, 2), (3, 3), (3, 5), (3, 4), (4, 3), (4, 4), (  
c) R3 = R2◦R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 4), (2, 5), (2, 2), (3, 1), (3, 2), (3, 3), (3, 5), (3, 4), (4, 3), (4, 4),  
Exercise 6.  
a) R1 ◦ R2 = {(4, 2), (2, 2), (2, 3), (3, 2), (3, 3)}  
R1 ◦ R3 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}  
R1 ◦ R4 = {(1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}  
R1 ◦ R5 = {(4, 1), (4, 2), (1, 1), (1, 2), (2, 2), (3, 3)}  
R1 ◦ R6 = {(1, 2)}  
b) R2 ◦ R3 ◦ R4 ◦ R6 = {(1, 2), (1, 4), 1, 3)}  
c) (R3)2 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}  
d) (R3)4 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}  
e) {(4, 2), (2, 4), (2, 2), (2, 3), (3, 2), (3, 3), (4, 4), (1, 1), (5, 5)}  
f) {(4, 2), (2, 2), (2, 3), (3, 2), (3, 3), (2, 4)}  
g) {(1, 2)}  
Exercise 7.  
a) {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1), (1, 3), (3, 1)}  
b) {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2)}  
c) {(1, 1), (1, 2), (2, 1), (2, 2)}  
Exercise 8.  
a) 216  
b) 216 − 215  
Exercise 9.  
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)}  
Chương 4: Homework  
Trang 2/5  
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.  
a
b
d
c
Exercise 11.  
a) If there is a city c such that there is a direct non-stop airline flight from a to c and there is a  
direct non-stop airline flight from c to b.  
b) If there are two citys c,d such that there is a direct non-stop airline flight from a to c,there is  
a direct non-stop airline flight from c to d and there is a direct non-stop airline flight from d  
to b  
Exercise 12.  
a) Reflexive closure of R:  
{(0, 1), (1, 1), (1, 2), (2, 0), (2, 2), (3, 0), (0, 0), (3, 3)}  
b) Symmetric closure of R:  
{(0, 1), (1, 1), (1, 2), (2, 0), (2, 2), (3, 0), (1, 0), (2, 1), (0, 2), (0, 3)}  
c) Transitive closure of R:  
{(0, 1), (1, 1), (1, 2), (2, 0), (2, 2), (3, 0), (0, 2), (1, 0), (0, 0), (2, 1), (3, 1), (3, 2)}  
Exercise 13.  
Symmetric closure of R:  
{(a, b) | a|b or b|a}  
Exercise 14.  
a) {(1, 2), (1, 4), (3, 3), (4, 1), (1, 1), (4, 4), (4, 2), (2, 2)}  
b) {(1, 2), (1, 4), (3, 3), (4, 1), (2, 1), (1, 1), (2, 2), (4, 2), (4, 4), (2, 4)}  
c) {(1, 2), (1, 4), (3, 3), (4, 1), (2, 1), (1, 1), (2, 2), (4, 2), (4, 4), (2, 4)}  
Chương 4: Homework  
Trang 3/5  
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 15.  
a) Equivalence relation  
b) Not reflexive, not transitive  
c) Equivalence relation  
d) Not transitive  
Exercise 16.  
a) NO  
b) YES  
c) YES  
d) NO  
Exercise 17.  
a) R = {(0, 0), (1, 2), (1, 1), (2, 1), (2, 2), (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 5), (5, 4), (5, 3)}  
b) R = {(0, 0), (0, 1), (1, 1), (1, 0), (2, 3), (2, 2), (3, 2), (3, 3), (4, 5), (4, 4), (5, 4), (5, 5)}  
Exercise 18.  
a) R is an equivalence relation.  
Proof: We have a-a=0 is an integer for all real numbers.So R is reflexive.If aRb  
and bRC then a-b is an interger, b-c is an integer.So a-b+b-c=a-c is also an inte-  
ger.Hence,aRc.Therefore, R is trasitive.Suppose that aRb.Then a-b is an integer, so b-a is  
also an interger. Hence bRa.R is symmetric.  
Thus, R is an equivalence relation.  
b) Z  
1
2
c) {x + |x ∈ Z}  
Exercise 19.  
a) R an equivalence relation. Proof:  
We have a+b=b+a for all a,b ∈ A.Hence (a,b)R(a,b).So, R is reflexive.Suppose  
that (a,b)R(c,d).Then a+b=c+d,so c+d=a+b.Hence,(c,d)R(a,b).Therefore, R is symmet-  
ric.If (a,b)R(x,y) and (x,y)R(c,d)then a+b=x+y and x+y=c+d. So a+b=c+d.Hence  
(a,b)R(c,d).Thus,R is transitive.  
In conclusion, R an equivalence relation.  
b) [(1, 3)] = {(3, 1), (1, 3), (2, 2)}  
[(2, 4)] = {(2, 4), (1, 5), (5, 1), (3, 3), (4, 2)}  
[(1, 1)] = {(1, 1)}  
c) [(1, 3)] = {(3, 1), (1, 3), (2, 2)}  
[(2, 4)] = {(2, 4), (1, 5), (5, 1), (3, 3), (4, 2)}  
[(1, 1)] = {(1, 1)}  
[(1, 2)] = {(1, 2), (2, 1)}  
Chương 4: Homework  
Trang 4/5  
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, 3)] = {(1, 4), (4, 1), (3, 2), (2, 3)}  
[(3, 4)] = {(3, 4), (4, 3), (2, 5), (5, 2)}  
[(4, 4)] = {(4, 4), (5, 3), (3, 5)}  
[(4, 5)] = {(4, 5), (5, 4)}  
[(5, 5)] = {(5, 5)}  
Exercise 20.  
1. YES  
2. NO. Because it is not transitive and not antisymmetric  
3. YES  
4. YES  
5. NO. Because it is not antisymmetric and not transitive  
Exercise 21.  
a) YES  
b) NO. Because relation R on Z is not transitive,not antisymmetric and not reflexive,so it is  
not a partial ordering.  
c) YES  
d) NO. Because relation R on Z is not transitive,not antisymmetric and not reflexive,so it is  
not a partial ordering.  
Chương 4: Homework  
Trang 5/5  
 
pdf 6 trang baolam 19180 Free
Download
Bạn đang xem tài liệu "Tài liệu Cấu trúc rời rạc cho khoa học máy tính - Chapter 4: Relations", để 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:

  • pdftai_lieu_cau_truc_roi_rac_cho_khoa_hoc_may_tinh_chapter_4_re.pdf