2022年《计算机数学基础》――离散数学期末复习参考 .pdf

优秀学习资料欢迎下载计算机数学基础 ( 一)离散数学期末复习参考一、关于期末考试1. 本学期的结业考核由形成性考核和期末考核构成。形成性考核由平时作业成绩构成，占结业考核成绩的20%, 期末考核成绩占结业考核成绩的80% 。 2.期末考核实行全国统一考核，根据本课程考试说明，由中央电大统一命题，统一考核时间，制定统一评分标准。开办试点的地方电大组织考核。期末考核的考核内容和要求以考核说明为准；采用闭卷笔试，试卷满分100 分；时限120 分钟。试题类型及分数： 单项选择题和填空题，分数约占25。解答与计算题， 分数约占 56；证明题，分数约占19。3, 考核试卷分数分布：第1 编数理逻辑约30 分，第 2 编集合论约30 分，第 3 编图论约 25 分，第 4 编代数系统约15。4. 易、中、较难题目在试卷中占的比例是4：4： 2。二、各章重点考核内容第 1 章命题逻辑1命题联结词真值真值表简单命题符号化2. 命题公式永真式永假式可满足式3. 公式等值演算( 必须掌握公式基本等值式) 4. 求范式（用各种方法求合取范式、析取范式，尤其是主析取范式，主合取范式等）5. 掌握逻辑推理的方法。第 2 章谓词逻辑1. 谓词量词个体词个体域变元 ( 约束变元、自由变元) 简单命题符号化2. 判别简单谓词公式的类型( 永真式、永假式、可满足式) 3. 求前束范式4. 有限个体域中，求给定解释下的公式真值。第 3 章集合及其运算1. 集合元素全集空集幂集2. 集合的关系与运算3. 有序对和笛卡儿积第 4 章关系与函数1. 二元关系及其表示方法集合方法、矩阵和图2. 关系的运算和复合关系、逆关系3. 二元关系的性质 ( 5 条性质 )4. 等价关系 ( 等价类 ) 与偏序关系 ( 哈斯图极大 ( 小) 元 最大 ( 小 ) 元5. 函数复合函数单射满射和双射，求反函数名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 优秀学习资料欢迎下载第 5 章图的基本概念1. 图结点边有向图无向图简单图多重图完全图子图与生成子图结点度数握手定理及其推论2. 通路通路的长度初级 ( 简单 ) 通路回路初级 ( 简单 ) 回路点割集与割点边割集与桥连通图强( 单测、弱 ) 连通3. 关联矩阵邻接矩阵第 6 章几种特殊图1. 欧拉通路 ( 回路 ) 欧拉图哈密顿通路 ( 回路 ) 哈密顿图2. 平面图面的次数平面图相关定理( 定理 6 8) 3. 树无向树有向树最小生成树根树最优树二叉树第 7 章群1. 代数运算以及运算性质单位元、逆元 , 代数系统，2. 半群群及其性质子群3. 循环群交换群n元置换及置换群4. 群的同态与同构第 8 章其它代数系统1. 环与域，环. 2. 格有界格有余格分配格3. 布尔代数三、 各章基本问题第 1 章命题逻辑1. 命题符号化，是否命题判断或求真值。2. 命题公式赋值，及类型判别。3. 命题公式等值判别或证明。方法有真值表法、等值演算法和主范式法. 4. 求范式和主范式。5. 蕴含式 ( 推理理论 ) 证明：方法有：真值表法、等值演算法、主析取范式法、构造证明法直接法、附加前提证明法和反证法。第 2 章谓词逻辑1. 命题符号化。2. 求辖域、约束变元、自由变元。3. 给定解释求谓词公式的真值(多为个体域有限的情形)。4. 判断谓词公式是否重言式(用代换实例 )、永假式？5. 求前束范式。第3章集合及其运算1. 求集合表达式(列举法或描述法)。2. 判断集合与元素、集合与集合的关系，用，？名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 优秀学习资料欢迎下载3. 求幂集。4. 包含或相等的化简或证明。5. 求笛卡儿积，或某些等式证明。第 4 章二元关系与函数1. 求关系的表达式，关系矩阵、关系图，Dom(R),Ran(R). 2. 验证或证明关系的性质。3. 关系计算：求，4. 求复合关系、逆关系及其矩阵。5. 求自反闭包或对称闭包。6. 验证或证明关系R 是等价关系或偏序关系。7. 作偏序关系的哈斯图，求极大(小)元、最大 (小)元。8. 验证是否是函数，是满射、单射、双射？第 5 章图的基本概念1. 图 G 与 G互求。2. 判断简单图、多重图、完全图。3. 求子图或生成子图。4. 求结点度数或用握手定理求结点数，或判断是否度数序列。5. 判断是否同构，主要用必要条件判断不同构。会作2 或 3 个结点非同构的生成子图。6. 用定理 1(握手定理 )或 2 以及推理进行推理或计算。7. 求图中通路、回路、长度或通路、回路的数目(主要用定理8) 8.判断是否连通、强连通、单侧连通或弱连通。9. 求点割集、割点和边割集、割边(比较简单的图 )。10. 求有向图的邻接矩阵和可达矩阵。第 6 章几种特殊的图1.判断或作欧拉图，求欧拉通路、回路。2. 判断或作哈密顿图，求哈密顿通路、回路，说明不是哈密顿图。3. 判断是否可平面图，将可平面图改画为平面图。4. 求连通平面图的面、边界和次数。5. 用定理 6， 7 作某些证明或计算。如求二元完全树中树叶个数与分支点数之关系。6. 判断是否树。7. 求树的结点与边的关系。8. 求最小生成树和权。第 7 章群1. 验证代数运算f 在 A 上封闭，即 是代数系统。2. 验证代数运算有结合律，交换律等。3. 验证代数运算f，g 有无分配律，吸收律等。4. 求运算的单位元，逆元.。5. 判断是否半群、群、交换群、循环群，求生成元和循环群的子群。. 7. 在群中进行计算、化简等。8. 求复合置换、逆置换等。名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 优秀学习资料欢迎下载9. 证明群同态、同构，找同态(同构 )映射。第 8 章其它代数系统1. 验证是否为环？2. 给出偏序集，判断是否为格？3. 在格中进行计算、化简或证明等。4. 布尔代数式的化简、求值或证明.四、自我练习题一、单项选择题1. 给定无向图如图1 所示，下面给出的顶点集的子集中，不是点割集的为（）(A) b,d (B) d (C) a,c (D) e,g 2. 无向完全图K3的不同构的生成子图有（）个(A) 6 (B) 5 (C) 4 (D) 3 3. 在自然数集合N 上，下列运算可结合的是（）A.),max(yxyxB.yxyx2C.22yxyxD. yxyx4. 设 N 为自然数集合，在下面 4 种运算下不构成代数系统的是（）(A) xy = x+y 2xy(B) xy = x+y(C) x y = xy(D) xy = |x|+|y| (其中， +、分别为普通加法和减法) 5. 已知偏序集的哈斯图，如图2 所示，是格的为( ) (A) (B) (C) (D) 图 2 二、填空题6. 若命题变元P，Q，R 赋值为 (1,0,1)，则命题公式G)()(QPRQP的真值是7. 设 N(x)：x 是自然数， Z(y)；y 是整数，则命题“自然数都是整数，而有的整数不是自然数”符号化为8. 设 A,， B 为任意集合，命题A B的真值为9. 设 A，B 为有限集，且m,n,那末 A与 B 间存在双射，当且仅当10. 在有向图的邻接矩阵中，第i 行元素之和 ,第 j 列元素之和分别为三、化简解答题11. 做命题公式)()(PQPQP的真值表，并判断该公式的类型12.化简集合表达式：(ABC)(AC)(C(C B)A) 13. （1）将命题公式)(PRQP化为只含和的尽可能简单的等值式(2) 求谓词公式)()(afRxQPx的真值其中 P：4 3，Q（x） ：x 1，R（x） ：x 2，f(0)=0，f(4)=4a：4个体域 D=0 ，4四、计算解答题14. (1) 设 R 和 S是集合 A1,2,3 上的二元关系，g afdbe c 图 1 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 优秀学习资料欢迎下载R, S =, 求 R S，写出它的矩阵MR S(2) 求布尔表达式cbcbacbaE)(),(的对偶式，并求当 a,b,c 取值 0,0,1 时，E(a,b,c)以及其对偶式的真值。15. 指出谓词公式)(),()(),()(xSyxxHxPzxGxFx中x 和 x的辖域，并指出该公式的约束变元和自由变元以及约束出现次数和自由出现次数16. 已知带权图G，如图 3 所示试求图G 的最小生成树，并计算该生成树的权17. 设简单连通无向图G 有 12 条边， G 中有 1 度结点 2 个， 2 度结点 2 个， 4 度结点 3 个，其余结点度数不超过3求 G 中至少有多少个结点试作一个满足该条件的简单无向图图 3五、证明题18. 证明如果R和 S是非空集合A 上的等价关系，则SR也是 A 上的等价关系19. 设 R*是非 0 实数集，在R*上定义集合S为,00*RbabaS证明(S，*) 是代数系统，满足结合律，交换律，存在单位元，S 的每个元素有逆元。其中*是矩阵的乘法运算五、自我练习题解答一、单项选择题1. B 2. C 3. A 4. A 5. D 二、填空题6. 1 7. x(N(x)Z(x)x(Z(x)N(x) 8. 0 9. m=n10. 结点 vi的出度和结点vj的入度三、化简解答题11. . 命题公式)()(PQPQP的真值表PQPQQPPQP)()()(PQPQP0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 原式为可满足式. 12. (ABC)(AC)(C(CB)A) (AC)（ CA）(两次用吸收律) =( AC)(CA) =(AC)(CC)A(AC) =(AC)A=A13. (1)(PRQP)()(PRQP)()(RPQP不惟一 . (2) )()(afRxQPx=)4()4()0(fRQPQP=00)11()01(四、计算解答题14. (1) R S= ,=2,3,1 , 11 4 5 8 9 2 10 6 7 3 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 优秀学习资料欢迎下载010000001SRM(2) 110) 11(10)100() 1 ,0 ,0(EcbcbacbaE)(),(的对偶式为cbcba)(，其真值是010110) 100(15. x 的辖域为： F(x)G(x， z) P(x) x 的辖域为： H(x， y) x 既是约束变元，也是自由变元，约束出现4 次，自由出现1 次 y 是自由变元，自由出现1 次 . z 是自由变元，自由出现1 次)(),(xxPyxfQyx)3()2(),3(),2(PPyfyQyfyQ10)3,2()2 ,2()3 ,3()2, 3(QQQQ11)10()10(16. 做法如下：选边 1； 选边 2；选边 3； 选边 5；选边 7 最小生成树为1,2,3,5,7 如图 4 中粗线所示权数为 18图 4 17. 设图 G 有 x 个结点，有握手定理2 1+2 2+3 43 （x 2 2 3） 12 2 271821243xx 9 图 G 至少有 9 个结点图满足条件的图如图5 所示五、证明题18. SRxxSxxRxxAx,，所以SR有自反性；,Ayx因为 R，S是对称的，SyxRyxSRyx,SxyRxySR, 对称的SRxy,所以， R S是对称的Azyx,，因为 R，S是传递的，SRzySRyx,SzyRzySyxRyx,SzySyxRzyRyx,SRzxSzxRzxSR, 传递所以，SR是传递的总之， RS是等价关系 . 19. 首先证 * 在 S上封闭任取S中的元素yxba00,00，其中 a,b,x,yR*1 4 5 8 9 2 10 6 7 3 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 优秀学习资料欢迎下载Sbyaxyxba000000，因为 ax,byR*即 *在 S上封闭且有byaxyxba000000bayx0000即运算 *满足交换律。任取 S中的元素dcyxba00,00,00，其中 a,b,x,y,c,dR*，有bydaxcdcbyaxdcyxba0000*0000*)00*00(bydaxcydxcbadcyxba0000*00)00*00(*00可见， *满足结合律设单位元为E=yox0,任取 S中的元素ba00, 有ybxabayxbabyaxyxba0000*00000000*00得到bbyaax，由 a,b 的任意性，得x=1,y=1, 有 E=1001S,即 E 是 S 上关于运算 *的单位任取 S中的元素ba00如果其逆元为X=yx00，应有ba00*yx00=ba00*yx00=1001得到11byax,因为 a,b 不为 0，得byax1,1。显然 x,y 不为 0，即 x,y R*，yx1001S，它是ba00的逆元。 S的每个元素都有逆元，名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页，共 7 页 - - - - - - - - -