《计算机数学基础.docVIP

《计算机数学基础》(一)――离散数学期末复习参考 一、关于期末考试 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. 函数 复合函数 单射 满射和双射，求反函数 第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. 求前束范式。 集合及其运算 1. 求集合表达式(列举法或描述法)。 2. 判断集合与元素、集合与集合的关系，用?，?，?，?，?？ 3. 求幂集。 4. 包含或相等的化简或证明。 5. 求笛卡儿积，或某些等式证明。 第4章 二元关系与函数 1. 求关系的表达式，关系矩阵、关系图，Dom(R),Ran(R). 2. 验证或证明关系的性质。 3. 关系计算：求?，?，－，～，? 4. 求复合关系、逆关系及其矩阵。 5. 求自反闭包或对称闭包。 6. 验证或证明关系R是等价关系或偏序关系。 7. 作偏序关系的哈斯图，求极大(小)元、最大(小)元。 8. 验证是否是函数，是满射、单射、双射？ 第5章 图的基本概念 1. 图G与G＝V，E互求。 2. 判断简单图、多重图、完全图。 3. 求子图或生成子图。 4. 求结点度数或用握手定理求结点数，或判断是否度数序列。 5. 判断是否同构，主要用必要条件判断不同构。会作2或3个结点非同构的生成子