「离散数学」期末综合复习资料知识点复习考点归纳总结

离散数学期末综合复习资料考点归纳总结一、判断题电大考试电大小抄电大复习资料1. （ ）命题联结词，是最小联结词组。2. （ ）（pq）p为矛盾式。3. （ ）（pq）（qr）（pr）为重言式。4. （ ）a、b、c是任意命题公式，如果acbc，一定有ab。5. （ ）若集合a上的二元关系r是对称的，rc一定是对称的。6. （ ）r是a上的二元关系，r是自反的，当且仅当r(r)=r。7. （ ）集合a上的等价关系确定了a的一个划分。8. （ ）有理数集是可数的。9. （ ）若函数f，g为入射则其复合函数也为入射。10. （ ）r是集合a上的关系，r有传递性的充要条件是rorr。11. （ ）设是一个代数系统，且集合a中元素的个数大于1。如果该代数系统中存在幺元e和零元q，则eq。12. （ ）交换群必是循环群。13. （ ）一个群可以有多个等幂元。14. （ ）模格一定是分配格。15. （ ）每个有向图中，结点入度数总和等于结点出度总和。16. （ ）图g的邻接矩阵a，al中的i行j列表示结点vi到vj长度为l路的数目。17. （ ）任何图中必有偶数个度数为奇数的结点。18. （ ）有向图中，它的每一个结点位于且只位于一个单侧分图中。19. （ ）任意平面图最多是四色的。20. （ ）不存在既有欧拉回路又有汉密尔顿回路的图。二、填空题1 设p：“天下雨”，q：“他骑自行车上班”，r：“他乘公共汽车上班”。则命题“除非下雨，否则他就骑自行车上班”可符号化为 。“他或者骑自行车，或者乘公共汽车上班”可符号化为 2 设n(x)：x是自然数；j(x)：x是奇数；q(x)：x是偶数，用谓词公式符号化命题“任何自然数不是偶数就是奇数”。3 设p(x)：x是运动员，q(x)：x是教练。则命题“不是所有运动员都是教练”可符号化为。4 设d=a,b；p(a,a)=p(b,b)=t；p(a,b)=p(b,a)=f。则公式(x)($y)(p(x,y)p(y,x)的真值是。5 集合a=,的幂集p(a)为6 集合a=1,2，b=a,b,c,d，c=c,d,e，则a(b-c)为7 试用空集构成集合a（a）= 和b= ，使得ab且ab都成立。并且ab=。8 设a=1,2,3，r=,，传递闭包t(r)为 。9 设a=1,2,3，b=x,y，f：ab，则不同的函数个数为 个。10 q为有理数集，q上定义运算*为a*b=a+b-ab，则的幺元为 。11 代数系统，其中sk=x|xzx=k，+为普通加法，则是一个半群的必要条件是 。12 设g为v个结点e条边的连通平面图，则面r等于 。13 一棵树有n2个结点度数为2，n3个结点度数为3，nk个结点度数为k，则度数为1的结点的个数为 。14 设t为根树，若每个结点的出度都小于等于m，则t称为 树，若除 外，每个结点的出度都等于m，则t称为完全m叉树。15 设是偏序集，如果a中任意两个元素都有 和 ，则称为格。三、解答题1. 将公式(pq) (qr)(pr)化成与之等价且仅含、的公式。2. 将下列命题符号化：（1）他虽聪明但不用功。（2）除非你努力否则你将失败。（3）我们不能既划船又跑步（4）仅当你走我才留下。3. 用谓词表达式符号化下列命题：（1）所有老的国家选手都是运动员。（2）某些教练是年老的，但是健壮的。（3）任何自然数不是偶数就是奇数。（4）不是所有运动员都是教练。4. 求命题公式(pq)的主合取范式。5. 求命题公式p(pq)的主析取范式。6. 设集合a1, 2, 3，a上的关系r, （1）画出r的关系图；（2）写出r的关系矩阵；（2）问r具有关系的哪几种性质(自反、反自反、对称、反对称、传递)。7. 构造一非空偏序集，它存在一子集有上界，但没有最小上界。它还有一子集，存在最大下界但没有最小元。8. 以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。a) f: zn, f(x)=x2+1b) f: nq, f(x) = 1/xc) f: 1,2,3a,b,c, f=,d) f: nn, f(x)=2xe) f: rrrr, f(x,y)=9. 设s=1,2,3,4,6,12，d为s上的整除关系，（1）试写出该关系并画出哈斯图；（2）设子集b=2,3,6，试求b的最大元、最小元、极大元和极小元；（3）试求b的上界、上确界、下界和下确界。10. 设集合a有m个元素，b有n个元素，则a到b的关系有多少个？a到b的函数有多少个？11. 判定下列代数系统是否为群，请说明原因。（1），其中r为实数集，+为普通加法；（2），其中i为整数集，为普通乘法 12. 设群的运算表如下：*eabeeabaabebbea试写出的所有子群，及其相应的左陪集。13. 设g=，v=v1,v2,v3,v4的邻接矩阵：0 1 0 11 0 1 1 1 1 0 0 1 0 0 0 a(g)=（1）试画出该图。（2）v2的入度d-(v2)和出度d+(v2)是多少？（3）从v2到v4长度为2的路有几条？v1v3v2v5v414. 试求下面有向图的强分图、单侧分图和弱分图15. （1）画一个有欧拉回路和一条汉密尔顿回路的图。（2）画一个有欧拉回路，但没有汉密尔顿回路的图。（3）画一个没有欧拉回路，但有汉密尔顿回路的图。v1v2v3v4v54325112216. 下图给出的赋权图表示五个城市及对应两个城镇间公路的长度。是给出一个最优的设计方案使各城市间有公路连通。17. 设有一组权3、4、13、5、6、12，（1）求相应的最优树（要求构造的过程中，每个分支点的左儿子的权小于右儿子的权）。（2）设上述权值分别对应英文字母b、d、e、g、o、y，试根据求得的最优树构造前缀码，并对二进制序列0100110110010001011译码。四、证明题1. a (bc),(ef)c,b(as)be2. 试证明命题公式为永真式。3. 试证明：(pq) (pr) (qs) sr4. 用推理规则证明：(x)(p(x)q(x) ($x) p(x)($y)(p(y)q(y)5. 对所有集合a、b和c，有(ab)c=a(bc)，当且仅当ca。6. 若r和s是集合a上的等价关系，试证明rs也是a上的等价关系。7. 证明集合0,1和(0,1)是等势的。8. 设f: x-y和g: y-z是函数，使得gf是一个满射，且g是一个入射。证明f是满射。9. 设,是两个群，在g1g2上定义运算为：=，证明是一个群。10. f是群到群的同态映射，e是g中的幺元则，f的同态核k=x|xg且f(x)=e构成的代数系统是的子群。11. 证明在格中，若abc，则（1）ab=bc（2）(ab)(bc)=b=(ab)(ac)12. 若有n个人，每个人恰有三个朋友，证明n必为偶数。13. 证明当且仅当g的一条边e不包含在g的回路中时，e才是g的割边。14. 画出k3,3图，并证明其不是欧拉图，也不是平面图。15. 设g为连通图，证明当且仅当边e是g的割边时，e才在g的每颗生成树中。16. 设t是非平凡的无向树，t中度数最大的结点有2个，它们的度数为k（k=2），证明：t中至少有2k-2片树叶。17. 设g=有11个结点，m条边，证明g或者其补图g是非平面图。部分参考