计算机数学基础(1)期末复习要点与模拟练习师范部 冯泰一、关于期末考核1.本学期的结业考核由形成性考核和期末考核构成形成性考核由平时作业成绩构成，占结业考核成绩的 20%, 期末考核成绩占结业考核成绩的 80%2.期末考核实行全国统一考核，根据本课程考试说明，由中央电大统一命题，统一考核时间，制定统一评分标准开办试点的地方电大组织考核期末考核的考核内容和要求以考核说明为准；采用闭卷笔试，试卷满分 100 分；时限120 分钟试题类型及分数：单项选择题和填空题，分数约占 25解答与计算题，分数约占56；证明题，分数约占 193, 考核试卷分数分布：第 1 编数理逻辑约 30 分，第 2 编集合论约 30 分，第 3 编图论约 25 分，第 4 编代数系统约 154. 易、中、较难题目在试卷中占的比例是 4：4：2二、各章基本问题与重点第 1 章 命题逻辑基本问题：1. 命题符号化，是否命题判断或求真值2. 命题公式赋值，及类型判别3. 命题公式等值判别或证明方法有真值表法、等值演算法和主范式法. 4. 求范式和主范式5. 蕴含式(推理理论)证明：方法有：真值表法、等值演算法、主析取范式法、构造证明法直接法、附加前提证明法和反证法重点：真值表，命题公式的赋值于命题公式类型以及公式之间等值的判别，求主范式和构造推理证明第 2 章 谓词逻辑基本问题：1. 命题符号化2. 求辖域、约束变元、自由变元3. 给定解释求谓词公式的真值(多为个体域有限的情形) 4. 判断谓词公式是否重言式(用代换实例) 、永假式或可满足式？5. 求前束范式6. 谓词公式等值式的证明重点：求辖域、变元，在有限个体域内求谓词公式的真值，求前束范式第 3 章 集合及其运算基本问题：1. 求集合表达式(列举法或描述法 )2. 判断集合与元素、集合与集合的关系，用， ，？3. 求幂集4. 包含或相等的化简或证明5. 求笛卡儿积，或某些等式证明重点：求幂集合，集合(包括笛卡儿积 )的化简或等式证明第 4 章 二元关系与函数基本问题：1. 求关系的表达式，关系矩阵、关系图，Dom(R),Ran(R).2. 验证或证明关系的性质3. 求复合关系、逆关系及其矩阵 4. 求关系闭包5. 关系计算：求， ，6. 验证或证明关系 R 是等价关系或偏序关系7. 求等价关系的等价类8. 作偏序关系的哈斯图，求极大(小) 元、最大(小) 元9. 验证是否是函数，是满射、单射、双射？求函数定义域、值域 10. 求复合函数、反函数判别是否存在反函数？重点：求关系的表达式(矩阵或关系图 )，判别关系的性质，求复合关系和逆关系，证明是否等价关系或偏序关系，作哈斯图求极(最) 大极(最) 小元第 5 章 图的基本概念基本问题：1. 图 G 与 G互求2. 判断简单图、多重图、完全图3. 求补图子图或生成子图4. 求结点度数或用握手定理求结点数，或判断是否度数序列 5. 判断是否同构，主要用必要条件判断不同构 6. 用握手定理或推理进行证明7. 求图中通路、回路、长度或通路、回路的数目(主要用定理 8)8.判断是否连通、强连通、单侧连通或弱连通 9. 求点割集、割点和边割集、割边 10. 求图的关联矩阵、邻接矩阵和可达矩阵重点：作图，用握手定理求结点或推理证明，求通路、回路及其长度，判别强(单侧、弱) 连通，求有向图的邻接矩阵并求结点之间的通路或回路条数第 6 章 几种特殊的图基本问题：1.判断或作欧拉图，求欧拉通路、回路2. 判断或作哈密顿图，求哈密顿通路、回路，说明不是哈密顿图3. 判断是否可平面图，将可平面图改画为平面图 4. 求连通平面图的面、边界和次数5. 用第 6，7，8 作某些证明6. 判断是否树7. 求树枝的内点和求树叶数8. 求最小生成树和权 9. 画根树，求层数和树高10. 求简单的二元完全树的内点和树叶 重点：欧拉(哈密顿)通路、回路的判别，平面图的判别，平面图的面、边的关系，定理6,7，求树的结点或边，最小生成树第 7 章 群基本问题：1. 验证代数运算 f 在 A 上封闭，即是代数系统 2. 验证代数运算有结合律，交换律等 3. 验证代数运算 f，g 有无分配律，吸收律等4. 求运算的单位元，逆元.5. 判断是否半群、群、交换群、循环群，求生成元和循环群的子群.7. 在群中进行计算、化简等 8. 求复合置换、逆置换等9. 证明群同态、同构，找同态(同构) 映射重点：验证是否二元运算以及结合律、交换律、求单位元和逆元，半群、群，交换群和循环群，置换第 8 章 其它代数系统基本问题：1. 验证是否为环？2. 给出偏序集，判断是否为格？3. 在格中进行计算、化简或证明等4. 判断是否为布尔代数(简单的，告知验证 H1,H2,H3,H4)5. 布尔代数式的化简、求值或证明. 重点：环的定义，偏序格的判别，布尔式的化简或证明三、模拟练习题模拟练习题(1)(一) 单项选择题1. 给定无向图如图 1 所示，下面给出的顶点集的子集中，不是点割集的为（ ）(A) b,d (B) d g af d be c图 1 (C) a,c (D) e,g 2. 无向完全图 K3 的不同构的生成子图有（ ）个(A) 6 (B) 5 (C) 4 (D) 33. 在自然数集合 N 上，下列运算可结合的是（ ）(A) (B) ),max(yyx2(C) (D) 2y4. 设 N 为自然数集合，在下面 4 种运算下不构成代数系统的是（ ）(A) x y = x+y2xy (B) x y = x+y (C) x y = x y (D) x y = |x|+|y|(其中，+ 、分别为普通加法和减法)5. 已知偏序集的哈斯图，如图 2 所示，是格的为( )(A) (B) (C) (D)图 2(二) 填空题6. 若命题变元 P，Q，R 赋值为(1,0,1)，则命题公式 G 的)()(QPRP真值是 7. 设 N(x)：x 是自然数，Z( y)；y 是整数，则命题“自然数都是整数，而有的整数不是自然数”符号化为 8. 设 A,，B 为任意集合，命题 ABA的真值为 9. 设 A，B 为有限集，且Am,n,那末 A 与 B 间存在双射，当且仅当 10. 在有向图的邻接矩阵中，第 i 行元素之和,第 j 列元素之和分别为 (三) 化简解答题11. 做命题公式 的真值表，并判断该公式的类型)()(PQP12.化简集合表达式：(ABC )(AC)(C (CB) A) 13. （1）将命题公式 化为只含和的尽可能简单的等值式R(2) 求谓词公式 的真值)()(afx其中 P：4 3，Q（x）：x1，R（x）：x 2，f(0)=0，f(4)=4a：4个体域 D=0，4(四) 计算解答题14. (1) 设 R 和 S 是集合 A1,2,3上的二元关系，R, S=,求 RS，写出它的矩阵 MRS(2) 求布尔表达式 的对偶式，并求当 a,b,c 取值 0,0,1cbacbE)(),(时，E (a,b,c)以及其对偶式的真值15. 指出谓词公式 中x 和x 的辖域，)(,()(,()( SyxHPzxGFx 并指出该公式的约束变元和自由变元以及约束出现次数和自由出现次数16. 已知带权图 G，如图 3 所示试求图 G 的最小生成树，并计算该生成树的权17. 设简单连通无向图 G 有 12 条边，G 中有 1 度结点 2 个，2 度结点 2 个，4 度结点 3 个，其余结点度数不超过 3求 G 中至少有多少个结点试作一个满足 该条件的简单无向图 图 3(五) 证明题18. 证明如果 R 和 S 是非空集合 A 上的等价关系，则 也是 A 上的等价关系SR19. 设 R*是非 0 实数集，在 R*上定义集合 S 为,ba证明 (S，*)是代数系统，满足结合律，交换律，存在单位元，S 的每个元素有逆元其中*是矩阵的乘法运算模拟练习题(2)(一) 单项选择题1. 设命题公式 G： ,则使公式 G 取真值为 1 的 P，Q，R 赋值分别是 ( )(RQP0,)D(01C,0)B(,0)A(2. 谓词公式 取真值为 1 的充分必要条件是( )y(A) 对任意 y，使 P(y)都取真值 1 (B) 存在一个 y0，使 P(y0)取真值 1 (C) 存在某些 y，使 P(y)都取真值 1 (D) 存在 y0，使 P(y0)取真值 03. 设 GxyP(x,y)Q(z,w)，下面三个命题为真的是 ( )(A) G 是前束范式 (B) G 不是前束范式 (C) G 不是一阶公式 (D) G 是永真式4. 设集合 A1,2,3,4,5,6,7,8，则下列各式为真的是( )(A) 1A (B) 4,5A (C) 1,2,3A (D) A14 5 8 9 210 6 735. 已知集合 Aa,b,c上的二元关系 R 的关系矩阵 MR ，那么 R( )，01(A) , (B) , (C) , (D) , (二) 填空题6.令 P：天气晴朗，Q：我去爬山， R：我有时间，则命题“如果天气好，而且我又有时间，那么我就去爬山”符号化为 7. 设 R，S 都是集合 A 上的等价关系，则对称闭包 s(RS)= ，自反闭r(RS)=，传递闭包 t(RS)= . 8. 设 f：AB 是双射函数，则 f 1 是函数，并且是从 B 到 A 的 9.设有向图 D的邻接矩阵为 A(D)= ，那么E . 10210. 无向连通图 G 含有欧拉通路的充分必要条件是 (三) 化简解答题11. (1) 求命题公式(PQ) (PQ)的成真赋值（2）设集合 A1,2,求 P()P(A).12. 设 f 是一元运算，P 是一元谓词，Q 是二元谓词，给定解释如下 ,1)3(,02,3,)2(,3 fDI()(0)(求在解释 I 下 的真值),(xPyxf13. 判断下列各式哪些是正确的？哪些是错误的？（1） （2）AB)( AB)(（3）