第13讲 习题课 北京大学计算机系离散数学讲义(ppt版).pptVIP

《集合论与图论》第13讲 第13讲 习题课 1. 作业讲解 2. 习题课 习题讲解(#5) p83, 习题二, 27, 28, 29 27. OK. 利用fldR1?fldR2=? ? R1○R2=?, R2○R1=?, R1i○R2j=?, R2i○R1j=?, i,j?N+. 习题讲解(#5) 28. (“m?n”应改为“mn”, 否则m=n=0) m=0,n=15. (许多人m=1,n=16, 忘记了R0=IA) 利用27题, 周期15 = lcm(3,5) 习题讲解(#5) 29. r( R )=R?{d,d,c,c} s( R )=R?{b,a,d,c} t( R )=R 习题讲解(#6) p84, 习题二, 35,39,47,50,52 35. R对称: xRy ? xRy ? xRx (R自反) ? yRx R传递: xRy ? yRz ? yRx ? yRz (R对称) ? xRz 习题讲解(#6) 39. 题目: A={1,2,3,4}, ?={ {1,2,3},{4} }. (1) R?=E{4}?E{1,2,3} ={1,1,2,2,3,3,4,4,1,2 , 2,1 ,2,3 ,3,2 ,1,3 ,3,1} (2) ?1= { {1},{2,3},{4} }, R?1=…, A/R?1=?1, ?2= { {2},{1,3},{4} }, ?3= { {3},{1,2},{4} } ?4= { {1},{2},{3},{4} }, ?5=?. # 习题讲解(#6) 47.最长链长度为5, 有4条: {1,2,6,18,54}, {1,3,6,18,54}, {1,3,9,18,54}, {1,3,9,27,54}, 至少划分为5个不相交的反链: {{54},{18,27},{6,9},{2,3},{1}} 至多划分为8个不相交的反链: {{1},{2},{3},{6},{9},{18},{27},{54}} 习题讲解(#6) 50. (1) R自反: ?x?A, ?y?B, x?A ? y?B ? xR1x ? yR2y ? x,yRx,y 习题讲解(#6) 50. (2) R反对称: ?x1,x2?A, ?y1,y2?B, x1,y1Rx2,y2 ? x2,y2Rx1,y1 ? x1R1x2 ? y1R2y2 ? x2R1x1 ? y2R2y1 ? x1=x2 ? y1=y2 ? x1,y1=x2,y2 注意: 非对称 ? 反对称 xRy?yRx?x=y ? xRy?x?y??yRx 习题讲解(#6) 50. (3) R传递: ?x1,x2,x3 ?A, ?y1,y2 ,y3 ?B, x1,y1Rx2,y2 ? x2,y2Rx1,y1 ? x3,y3Rx3,y3 ? x1R1x2 ? y1R2y2 ? x2R1x3 ? y2R2y3 ? x1R1x3 ? y1R2y3 ? x1,y1Rx3,y3. # 习题讲解(#6) 52. 利用哈斯图. 5类19种. 1 + 6 + 6 + 3 + 3 = 19 作业讲解(#7) p104, 习题三, 11,15,16,19,20 11.(25.) g(b)=f -1({b}) ? f满射 ? g(b)??. b1?b2 ? g(b1)?g(b2)=? ? g(b1)?? ? g(b2)?? ? g(b1)?g(b2) ? g单射. # 作业讲解(#7) 15. (1) N/R1 = { {n} | n?N } N/R2 = { {2k|k?N}, {2k+1|k?N} } N/R3 ={ {3k|k?N},{3k+1|k?N},{3k+2|k?N} } N/R4 = { {6k+j | k?N} | j=0,1,…,5 } # 注意: N/R2 = { {2k}, {2k+1} | k?N }是错误写法! (2) 作业讲解(#7) (3) f1(H) = H f2(H) = {0} f3(H) = {0,1,2} f4(H) = {0,2,4} # 作业讲解(#7) 16. g○f:R?R, g○f(x)=x2+2, 非单,非满 f○g:R?R, g○f(x)=x2+8x+14,