电大《离散数学》期末综合复习资料.docx

《电大《离散数学》期末综合复习资料.docx》由会员分享，可在线阅读，更多相关《电大《离散数学》期末综合复习资料.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -电大离散数学期末综合复习资料小抄一、判定题1. （）命题联结词， 是最小联结词组。2. （）（ P Q）P 为冲突式。3. （）（P Q）（ QR）（ PR）为重言式。4. （）A 、B 、C 是任意命题公式，假如ACBC，肯定有AB。C5. （）如集合A 上的二元关系R 是对称的， R 肯定是对称的。6. （） R 是 A 上的二元关系，R 是自反的，当且仅当rR=R 。7. （）集合 A 上的等价关系确定了A 的一个划分。8. （）有理数集是可数的。9. （）如函数f， g 为入射就其复合函数也为入射

2、。10. （ ）R 是集合 A 上的关系， R 有传递性的充要条件是RoRR。11. （）设 是一个代数系统，且集合A 中元素的个数大于1。假如该代数系统中存在幺元e 和零元，就e。12. （）交换群必是循环群。13. （）一个群可以有多个等幂元。14. （）模格肯定是安排格。15. （）每个有向图中，结点入度数总和等于结点出度总和。16. （）图 G 的邻接矩阵A ，A l 中的 i 行 j 列表示结点v i 到 vj 长度为 l 路的数目。17. （）任何图中必有偶数个度数为奇数的结点。18. （ ）有向图中，它的每一个结点位于且只位于一个单侧分图中。19. （ ）任意平面图最多是四色的。

3、20. （）不存在既有欧拉回路又有汉密尔顿回路的图。二、填空题1 设 P：“天下雨”，Q：“他骑自行车上班” ， R：“他乘公共汽车上班” 。就命题“除非下雨，否就他就骑自行车上班”可符号化为。 “他或者骑自行车，或者乘公共汽车上班”可符号化为2 设 Nx ： x 是自然数。 Jx ： x 是奇数。 Qx ： x 是偶数，用谓词公式符号化命题“任何自然数不是偶数就是奇数”。3 设 Px ： x 是运动员， Qx ： x 是教练。就命题“不是全部运动员都是教练”可符号化为。4 设 D=a,b 。 Pa,a=Pb,b=T 。Pa,b=Pb,a=F 。就公式 xyPx,yPy,x 的真值是。5 集合

4、 A=, 的幂集 PA 为6 集合 A=1,2 ， B=a,b,c,d ， C=c,d,e ，就 AB-C 为7 试用空集构成集合 A （A）=和 B=，使得 AB 且 AB 都成立。并且AB= 。8 设 A=1,2,3 ， R=,，传递闭包tR 为 。9 设 A=1,2,3 ， B=x,y， f： AB，就不同的函数个数为个。10Q 为有理数集， Q 上定义运算 *为 a*b=a+b-ab ，就 的幺元为。11代数系统 ，其中 Sk =x|xZx=K ，+为一般加法，就 是一个半群的必要条件是。12设 G 为 v 个结点 e 条边的连通平面图，就面r 等于。13一棵树有n2 个结点度数为2，

5、n3 个结点度数为3， nk 个结点度数为k ，就度数为1 的结点的个数为。14设 T 为根树，如每个结点的出度都小于等于m，就 T 称为树，如除外，每个结点的出度都等于m，就 T称为完全m 叉树。15设是偏序集，假如A 中任意两个元素都有和，就称为格。三、解答题1. 将公式 PQQRPR 化成与之等价且仅含、 的公式。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 4 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - -

6、 - - -2. 将以下命题符号化： （ 1）他虽聪慧但不用功。 （ 2）除非你努力否就你将失败。（3）我们不能既划船又跑步（ 4）仅当你走我才留下。3. 用谓词表达式符号化以下命题：（ 1）全部老的国家选手都是运动员。（ 2）某些教练是年老的，但是健壮的。（ 3）任何自然数不是偶数就是奇数。（ 4）不是全部运动员都是教练。4. 求命题公式PQ 的主合取范式。5. 求命题公式P PQ 的主析取范式。6.设集合 A 1, 2, 3 ，A 上的关系R ,（ 1）画出 R 的关系图。（ 2）写出 R 的关系矩阵。（ 2）问 R 具有关系的哪几种性质自反、反自反、对称、反对称、传递 。7. 构造一非空

7、偏序集，它存在一子集有上界，但没有最小上界。它仍有一子集，存在最大下界但没有最小元。8. 以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。a) f: ZN, fx=x 2+1b) f: NQ, fx = 1/xcf: 1,2,3a,b,c, f=,xdf: NN, fx=2ef: RRRR, fx,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

8、 个元素，就A 到 B 的关系有多少个？A 到 B 的函数有多少个？11. 判定以下代数系统是否为群，请说明缘由。（ 1），其中 R 为实数集， +为一般加法。 （ 2），其中 I为整数集，为一般乘法12. 设群 的运算表如下：*eabeeabaabebbea试写出 的全部子群，及其相应的左陪集。13.设 G= ，V=V1,V2,V3,V4的邻接矩阵：01011011AG=1100（ 1）试画出该图。1000（ 2） V2 的入度 d-+V2 和出度 d V2 是多少？（ 3）从 V2 到 V4 长度为 2 的路有几条？14. 试求下面有向图的强分图、单侧分图和弱分图v4v5v1v2v315.

9、 （ 1）画一个有欧拉回路和一条汉密尔顿回路的图。（ 2）画一个有欧拉回路，但没有汉密尔顿回路的图。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 4 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -（ 3）画一个没有欧拉回路，但有汉密尔顿回路的图。16. 下图给出的赋权图表示五个城市及对应两个城镇间大路的长度。是给出一个最优的设计方案使各城市间有公可编辑资料 - - - 欢迎下载精品名师归纳总结路连通。1

10、7. 设有一组权3、4、13、 5、6、12，V1342V3V252211V5V4可编辑资料 - - - 欢迎下载精品名师归纳总结（ 1）求相应的最优树（要求构造的过程中，每个分支点的左儿子的权小于右儿子的权）。（ 2）设上述权值分别对应英文字母b 、d、 e、g 、 o、 y ，试依据求得的最优树构造前缀码，并对二进制序列0100110110010001011 译码。四、证明题1. ABC,EFC,BASBE2. 试证明命题公式 PQ QR PR 为永真式。3. 试证明： P Q PR QSS R4.用推理规章证明：xPxQx x Px yPyQy5. 对全部集合A 、B 和 C，有 ABC

11、=ABC，当且仅当CA 。6. 如 R和 S 是集合 A 上的等价关系，试证明RS 也是 A 上的等价关系。7. 证明集合 0,1 和0,1是等势的。8. 设 f: X-Y和 g: Y-Z 是函数，使得g f 是一个满射，且g 是一个入射。证明f 是满射。9.设,是两个群， 在 G1 G2 上定义运算为：=，证明 是一个群。10. f 是群 到群 的同态映射， e是 G中的幺元就， f 的同态核 K=x|xG 且 fx=e构成的代数系统是的子群。11. 证明在格中，如a b c，就（ 1） ab=bc（ 2） abbc=b=abac12. 如有 n 个人，每个人恰有三个伴侣，证明n 必为偶数。

12、13. 证明当且仅当G 的一条边e 不包含在G 的回路中时， e 才是 G 的割边。14. 画出 K 3,3 图，并证明其不是欧拉图，也不是平面图。15. 设 G 为连通图，证明当且仅当边e 是 G 的割边时， e 才在 G 的每颗生成树中。16. 设 T 是非平凡的无向树，T 中度数最大的结点有2 个，它们的度数为k（ k=2 ），证明： T 中至少有2k-2 片树叶。17. 设 G= 有 11 个结点， m 条边，证明G 或者其补图G是非平面图。部分参考答案一、判定题1. （错误）2. （正确）3. （正确）可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - -

13、 - - - - - -第 3 页，共 4 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -4. （错误）5. （正确）6. （正确）7. （正确）8. （正确）9. （正确）10. （正确）11. （正确）12. （错误）13. （错误）14. （错误）15. （正确）16. （正确）17. （正确）18. （正确）19. （正确）20. （错误）可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 4 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载