资源描述
离散数学复习（2014.6）第11章一、命题及命题的符号化例：(1) 下列语句不是命题的是 。A：11+1=100； B：地球外的星球上有人；C：朝鲜的首都是汉城； D：我在撒谎。 （2）如果我上街，我就去书店看看，除非我很累。 P：我上街，Q：我去书店看看，R：我很累 (3) 他要么是山东人，要么是东北人。 P：他是山东人，Q：他是东北人 （3.1）他不可能既是山东人又是东北人。 （4）小张和小王至多只有一人能获奖。二、判断命题公式的类型例：判断下列公式的类型(永真，永假，可真可假（可满足公式）)。（PQ）（PQ）Q（PQ）P三、命题公式及其应用（主析取范式的求法及其应用）。要从P，Q，R这3人中挑出几位选手参加围棋比赛，但必须满足下列3个条件：(1) P和Q仅一个人参加；（2）Q和R至多参加一个人；（3）若R不参加，则P也不参加。问有几种选择方案？分别选哪些人？ 四、永真蕴含式及其在推理中的应用（1）只要小王曾经到过失窃者的房间并且11点前没有离开，小王就犯了盗窃罪。小王曾经到过失窃者的房间。如果小王在11点前离开，看门会看到他。看门人没有看到他。所以小王犯了罪。五、谓词演算（概念，命题定律和永真蕴含式，推理规则）（1）凡是有理数都可表示成分数Q(x)：x是有理数，F(x)：x可表示成分数（2）没有不吃饭的人P(x) ：x是人，E(x)：x吃饭（3）有些实数是有理数R(x) ：x是实数，Q(x)：x是有理数（4）有些人没有去过北京P(x) ：x是人，B(x)：x去过北京（5）素数不全是奇数P(x) ：x是素数，O(x)：x是奇数（6）推理（P240,11）六、递推关系的求解（1）特征方程有两相异的根（2）特征方程有两等根。（3）非齐次递推关系的求解。P241：27，29, 30（叠加原理）七、生成函数P232-233：表11.24有用的生成函数。P230：例11.78P234，例11.86：求的解的个数，其中是非负整数，满足。242：34把10个相同的球分给4个孩子，如果每个孩子至少得到2个球，使用生成函数确定不同的分法数。补充例子：分水果例子。第12章一、 集合的相关概念P256: 9. 正确的证明，错误的举反例P256: 13. A=2,3，2,3，则（1）A-2,3= （2）2,3-A= （3）A-= （4）A-= 补充例题：设，则 ； ， ， ， 。 二、 集合的幂集幂集的概念：某集合的幂集元素个数与该集合元素之间的关系。（P250：Th12.1）P256:10P256:11P282: 2. 设A=1,2，求2AA。2A=，1，2，A2AA=(，1)，(1，1)，(2，1)，(A，1)，(，2)，(1，2)，(2，2)，(A，2)补充例题：A=,求2AA。三、 集合的笛卡尔乘积P256：17. 一天之内的时间可用 时分表示。试用笛卡尔乘积表示它们的全体。 设 H=0,1，23； M=0,1,2，59 一天之内的时间可表示成：HM=（h，m）|hHmM 。18. 若A=0, 1，B=1, 2，试求下列集合： （1）A1B；（2）A2BA1B=（0,1,1），（0,1,2）,（1,1,1）,（1,1,2）A2B=(0,0,1)，(0,0,2)，(0,1,1)，(0,1,2)，(1,0,1)，(1,0,2)，(1,1,1)，(1,1,2)四、 容斥原理P256:15，16第13章 关系一、关系的相关概念表示方法：集合表示法，关系矩阵，关系图逆关系：关系的复合（与函数的复合的区别）求关系的定义域和值域：P282， 3P282：1、设A=1,2,3,4,用列举法表示R。（1） R=(x,y)| x是y的倍数R=(1,1)，(2,2)，(2,1)，(3,3)，(3,1) ，(4,4)，(4,1)， (4,2) （3）R=(x,y)| x/y是素数R= (2,1)， (3,1) ， (4,2) P282： 3、（1）DR=1,2,4（2）V=2,3,4补充例题：R=(a,b)，(a,b)，(,)，(,),求DR，V，R2，P282: 5设， ，求R的各次幂。二、关系的判定自反反自反对称反对称可传递集合表示RIAR=关系矩阵MR主对角元全为1主对角元全为0中不含负值关系图G每个顶点有自环每个顶点都无自环若两结点有边，则必为双向边若两结点间有边，必是单向边若xixj有边，xjxk有边，则xixk有边P282：7,8,9（R是定义在A上的二元关系）7.关系自反反自反R1R2R38. 关系对称反对称R1R2R3R49. 关系可传递性R1R2R3三、等价关系自反，对称，可传递性（证明）同余关系（P264，例13.11）等价类（P265，例13.12）等价类与集合划分之间的关系（1） 已知等价关系R，求出由R所导出的等价划分A/R。（2） 给定集合以及该集合的一个划分，给出相应等价关系，并证明确为等价关系（Th13.3）补充作业：设，试问A上可定义多少个不同的等价关系？（利用P266，定理13.3）补充例题：A=a,b,c,d, R是定义在A上的关系，R=(a,a)，(b,b)，(a,b)，(b,a)，(c,c)，(d,d),求出由R导出的等价划分A/R。（P256-266）四、偏序关系定义：自反，反对称，可传递全序：任何2个元素都可比。哈斯图（已知哈斯图，写出偏序关系； 已知偏序关系，写出哈斯图）P282：12. 答案：decbafgh R=(b,d)，(b,e)，(d,f) ,(b,f)，(c,d)，(c,e)，(c,f)，(e,f) (g,h)IA(P269，例13.21) 设，画出偏序集的哈斯图。五、闭包（P269-270）自反闭包：对称闭包s（R）：可传递闭包t（R）(P270,Th13.4)：P283： 13设给定集合，规定X上的不同关系，试求t(R1), t(R2)，并画出相应的关系图。 答案：t(R1)=(a,b)，(b,a)，(a,c)，(c,a)，(b,c)，(c,b) IXt(R2)=(a,b)， (a,c)， (b,c)，(c,c) 六、函数与鸽舍原理函数的复合P283:18：以下存在逆函数的是 ，其逆函数是 。 ； ，函数的复合：设函数；，则复合函数 。鸽舍原理：P283:16设第i个人的朋友个数为mi (i=1,2,.,n)，则0min-1 (i=1,2,.,n)。分析：0和n-1不可能同时取得。1、如果存在某个mi =0，即有人一个朋友都没有，那么其他人就不可能有n-1个朋友，即不会有mi = n-1；2、如果有一个人有n-1个朋友，则其他人必然至少有一个朋友，即不会有mi =0。所以：m1，m2，mn只能有n-1种取法。即0,1,2，n-2；或者1,2，n-1。根据鸽舍原理，这n个数中，必有2个数彼此相等。即必有2个人具有相同数目的朋友。补充1：证明在边长为2的正六边形中任取13个点，则至少有三个点连成的三角形面积不超过。（参考教材P274 例13.26）补充2：某工人在m天内加工若干零件，试证明一定能在连续k天（k=m）加工零件数是m的整数倍。（见书P275 例13.28）
展开阅读全文