《复旦大学 计算机院 赵一鸣 离散数学(中文课件)16》由会员分享，可在线阅读，更多相关《复旦大学 计算机院 赵一鸣 离散数学(中文课件)16（9页珍藏版）》请在金锄头文库上搜索。
1、 1.集合 ， S1=a,S2=a,S3=a,a aS3, S1 S3 aS3,S2 S3, S1S3, S1S2, 集合的运算 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不是传递的 等价关系,偏序关系 自反,对称,传递闭包 要求掌握: (1)正确判定是否为自反，反自反，对称，反对 称，传递,等价关系,偏序关系, 等价类,划分,划
2、分的和与积. (2)计算闭包 (3)画Hasse图（难度不低于习题2.39) (4)证明:如讲过的例子和做过的作业及定理; 讨论rst(R),srt(R),rts(R),trs(R), tsr(R), str(R)它 们的关系; 证明给定的是划分 3.函数 概念,满射,入射,双射,象集.复合函数 要求掌握 (1)判别是否为函数,满射,入射,双射 (2) 有关证明. (3)构造双射 4.无限集 无限集的基本特征,子集的基数=集合的基数 可列集,不可列集 要求掌握: 定理4.16(康托尔定理),定理4.10,定理4.14,定 理4.9和“定理:设F是0,1上一切实函数集,则 F的基数不是0,也不是
3、c(1).” 对于一切有限集,其幂集也是有限集， |P(A)|=2|A| 可列集是基数最小的无限集 可列集之间的差是否仍是可列集 无限集之间的差是否仍是无限集 证明基数相等的方法: 构造双射 分别构造两个内射 5. 鸽笼原理,关键是构造鸽子和笼子 6.排列与组合 注意区分有序和无序选取 环排列 多重集的排列与组合的求解方法: 公式,包含排斥原理,生成函数方法 利用包含排斥原理求有限制条件的排列组合问题 有序划分和无序划分 求方程整数解与组合问题的联系,注意化到标准 形式 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的最小基数,说明理由 。 2.一个人步行了11小时，共走了45公里 ，已知他第一小时走6公里，而最后一小 时只走了3公里，用鸽笼原理证明：一定 存在连续3个小时，使得在这3个小时内 至少走了12公里.
