资源描述
201 9 年硕士研究 生入学考试 自命题科目考试大纲 科目代码：823 科目名称：离散数学 一. 考试要求 主要考 察学生对离散 数 学中 集合 、关系、 函数、图论、命题 逻辑 、一阶谓 词逻辑 、 推理 系统、 布尔代 数 等计算 机数学的 基 本 概念、 计 算和证明 方法的 理解 与掌握情 况 ，以及应 用 上述概念 和方法 进行应 用 问题离散 建模、 计算 求解和逻 辑推 理的能 力 。注重概 念 的深入理 解、知 识的 综合运用， 以 及现实问题分析和解决。 二、考试内容 1 . 逻 辑和证 明基 础 命题、 逻 辑联接词、 真值 表、位操 作和位 串、命 题符号化 及应 用 、逻辑等价 和 蕴含、命题 可满 足性及应用、 谓词、 量词、 量词表达式等 价及否定、 嵌套量词、 谓词逻辑符号 化、 推理规则、 归结、 逻辑证 明 、证明方 法、证 明策 略、逻辑 语义 。要求 熟练 掌 握 命题逻 辑 和谓词逻 辑的基 本概 念，掌握 逻辑等 价 和蕴含分 析方法 ，掌 握逻辑推 理方 法和证 明方法 ，能 够 熟练运用 命题逻 辑和 谓词逻辑求 解 逻辑问题，了解可满足性问题。 2. 基本 结 构： 集合、 函数、 序 列、求 和 集合基本 概念、 集合描述 方法、 常见集合、 集合相等 、 属于、 子集 、 空集、 幂集 、 集合的基 数 、 n 元组、 笛卡尔乘 积、 集合运算（交、 并、 差、 补 ） 、 集合恒等 式、 广义交、 广义并 、 集合的计 算机 表示 、 （全） 函 数、 函数算 术、 1 对 1 函数 、 1- 1 对应、 内射、满 射、 双射、函数 运 算（逆函数、 函 数的合成） 、 若干重要 函数 、 部分函数 、 序列、 算术级数 、 几何级数 、 递推关系、 一些特殊 序列、 累 加、 基数 比较关系（ =， ， ， ） 、可 数集 、不可 数集、 基数关系证 明 。要 求熟 练掌握 集合的 基 本概念、集合的运算；熟练掌 握函数、函数的运算及其证明；熟练掌握级数、累加；掌握基数比较 和函数的关系、可数集。 3 . 归 纳和递 归 数学归纳法原理、 数学归纳法运用、 强归纳法原理、 强归纳法运用、 良序性质、 递归定义函数、 归纳定 义 法、递归 定义的 集合 和结构、 结构 归纳法 、结构归纳 法 的运用、 广义归 纳法 、递归算法 、 递归算法正确性证明、递归和 迭代。要求熟练掌握数学归纳法、强归纳法和结构归纳法，能够熟练 运用归 纳 定义法； 掌握递 归和 递归算法 的基 本概念 ，能够较熟 练 编写递归 算法； 了解 递归算法正 确 性证明。 4. 关系 二元关 系 基本概念、 关系 与函数、 二元关 系的性 质 （自反、 对 称、反对称、 传 递）及其证 明、 关系的 运 算、n-元关系 基 本概念、n-元关系 的运算、 关 系与数据库 、 关系 的 表示（关系 矩阵 、关系 图） 、 关系的闭包 、 等价关系、 等价类、 划分、 偏序、 全序、 良序归纳原 理、 哈斯图 、 最大 （ 小） 元 、 极大（ 小 ）元、上 （下） 界、 上（下） 确界 、格、 拓扑排序。 要 求熟悉集 合、关 系和 函数的关联 关 系；掌握关系的性质判定和运 算；熟悉关系与关系数据库的关系；掌握等价关系、序关系，能够证 明相关性质；了解格和拓扑排序。 5. 图 图的基 本 概念、图模 型、 图的基本 术语和 特殊类 型图 、二部 图 和匹配、图的 应 用、图的运 算、 图的表 示 、图同构 、路径 和连 通性、欧 拉路 径和哈 密顿路径 及 其应用 、最 短路径 算法 、平面图及 其 应用、 欧 拉公式、 库拉托 瓦斯 基定理、 图的 着色问 题 。要求熟 悉 图的基本 概念和 术语 ；掌握最短 路 径算法；熟悉路径和连通性；较熟练掌握图的性质证明；较好掌握二部图和平面图。 6. 树树的基 本 概念和术语 、树 建模、树 的性质 及其证 明 、树的应 用 、二叉树、树 的 遍历算法、 树的 编码、生成树、最小生成树、 回溯。要求熟悉树的基本概念；掌握树的算法和性质证明；能够使用 树进行建模和应用；掌握各种树的遍历算法；掌握回溯法。 7 . 布 尔代数 布尔函 数 、布尔表达 式、 布尔代数 恒等式 、对偶 、布尔代数 定 义、范式展开 、 逻辑门、电 路、 电路极小化。要求掌握布尔表达式变换方法；熟悉布尔代数与电路的关联关系；了解布尔代数。 三、考试形式 考试形式为闭卷、笔试，考试时间为 3 小时，满分 1 5 0 分。 题型包括：计算题、证明题、分析题、推理题等。 四、参考书目 1. Di sc re te Ma th em at ic s an d I t s Ap pl ic at io ns (7 t h e di ti on) , K en ne th H . R o s e n , I S B N : 9 78 -0 -0 7- 33 83 09 -5 , M c G r a w - H i l l , 2 01 2. 2.离散数学 ，王兵山、张强、毛晓光主编，国防科技大学出版社，2 0 0 1 .
展开阅读全文