复旦大学 计算机院 赵一鸣 离散数学(中文课件)16

《复旦大学 计算机院 赵一鸣 离散数学(中文课件)16》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.集合，S1={a},S2={{a}},S3={a,{a}}aS3,S1S3{a}S3,S2S3,S1S3,S1S2,集合的运算2.关系A上二元关系性质自反，反自反，对称，反对称，传递T1={(1,2),(1,3)}是传递的T2={(1,1)}传递T3={(1,2),(2,3),(1,3)}传递T4={(1,2),(2,3),(1,3),(2,1),(1,1)}?因为(2,1)T4,(1,2)T4,而(2,2)T4所以T4不是传递的等价关系,偏序关系自反,对称,传递闭包要求

2、掌握:(1)正确判定是否为自反，反自反，对称，反对称，传递,等价关系,偏序关系,等价类,划分,划分的和与积.(2)计算闭包(3)画Hasse图（难度不低于习题2.39)(4)证明:如讲过的例子和做过的作业及定理;讨论rst(R),srt(R),rts(R),trs(R),tsr(R),str(R)它们的关系;证明给定的是划分3.函数概念,满射,入射,双射,象集.复合函数要求掌握(1)判别是否为函数,满射,入射,双射(2)有关证明.(3)构造双射4.无限集无限集的基本特征,子集的基数=集合的基数可列

3、集,不可列集要求掌握:定理4.16(康托尔定理),定理4.10,定理4.14,定理4.9和“定理:设F是[0,1]上一切实函数集,则F的基数不是0,也不是c(1).”对于一切有限集,其幂集也是有限集，

4、P(A)

5、=2

6、A

7、可列集是基数最小的无限集可列集之间的差是否仍是可列集无限集之间的差是否仍是无限集证明基数相等的方法:构造双射分别构造两个内射5.鸽笼原理,关键是构造鸽子和笼子6.排列与组合注意区分有序和无序选取环排列多重集的排列与组合的求解方法:公式,包含排斥原理,生成函数方法利用包含排斥原

8、理求有限制条件的排列组合问题有序划分和无序划分求方程整数解与组合问题的联系,注意化到标准形式ex=1+x+x2/2!+…+xn/n!+…;x+x2/2!+…+xn/n!+…=ex-1;e-x=1-x+x2/2!+…+(-1)nxn/n!+…;1+x2/2!+…+x2n/(2n)!+…=(ex+e-x)/2;x+x3/3!+…+x2n+1/(2n+1)!+…=(ex-e-x)/2;7.递推关系建立递推关系用特征根方法和生成函数方法求递推关系1.设f是集合A到集合A的内射，但不是满射，求A的最小基数,

9、说明理由。2.一个人步行了11小时，共走了45公里，已知他第一小时走6公里，而最后一小时只走了3公里，用鸽笼原理证明：一定存在连续3个小时，使得在这3个小时内至少走了12公里.