天津理工大学离散数学课程考试大纲.doc

天津理工大学离散数学课程考试大纲(2005年8月版)课程名称: 离散数学 课程代码: 0600030课程名称：离散数学 课程代码：0600030第一部分 课程性质及其设置目的和要求一、课程性质与特点 离散数学是现代数学的一个重要分支，课程充分描述了计算机科学离散性的特点，是计算机科学的数学基础，是计算机专业的专业基础课程。本课程的目的是使学生掌握计算机科学技术所必需的数学知识，结合离散数学在计算机科学中的应用，掌握处理离散量的基本数学方法，培养和提高学生的抽象思维能力和逻辑推理能力，为学习专业课奠定良好的数学基础。二、课程设置的目的和要求通过该课程的学习，使学生掌握数理逻辑、集合论、函数、代数系统和图论等离散数学的基本概念和基本原理，了解离散结构之间的关系和基于这些离散结构的算法，能够对一些简单的算法给出定量的分析，强化思维的推理，能够在理论推导上有所提高，并且能够对计算机描述的世界进行基本建模，为学习计算机专业各后续课程做好必要的知识准备，为从事计算机的应用提供必要的描述工具和理论基础。三、与本专业其他课程的关系离散数学是计算机专业的最重要的专业基础课程之一，它是学习计算机、管理信息类各专业的许多其他后续课程的基础。先修课程：高等数学、线性代数。后读课程有：数据结构、数据库、操作系统、编译原理、计算机网络等。第二部分 课程内容与考核目标第一章 命题逻辑一、学习目的与要求通过本章学习，使学生深刻理解命题的概念、联结词的定义，掌握命题公式的翻译、命题公式的化简和主范式表示以及推理证明的直接证法和间接证法。二、考核知识点与考核目标（一）命题公式的主范式表示（重点）识记：大项、小项的概念。理解：命题公式的主析取范式、主合取范式的概念及二者的联系。 应用：命题公式的主析取范式、主合取范式的求法。（二）命题演算的推理理论（重点） 识记：P规则、T规则、CP规则。 理解：推理证明的直接证法和间接证法的应用条件。 应用：推理证明的直接证法和间接证法。（三）命题的概念、联结词及命题公式（次重点） 识记：命题、原子命题、复合命题、命题的真值、命题公式的递归定义等概念。天津理工大学离散数学课程考试大纲(2005年8月版)课程名称: 离散数学 课程代码: 0600030理解：五种逻辑联结词的定义、真值表、命题公式的类型及命题公式的等价式与蕴涵式。应用：命题的符号化与翻译、构造真值表证明命题公式的等价、不构造真值表证明蕴涵式与等价式及命题公式的化简。第二章 谓词演算一、学习目的与要求 通过本章学习，使学生深刻理解客体、个体域、谓词、量词、谓词公式等概念，掌握谓词公式的翻译、谓词演算的等价式与蕴涵式、前束范式以及谓词演算的推理理论。二、考核知识点与考核目标（一）谓词演算的推理理论（重点）识记：谓词演算的US规则、UG规则、ES规则、EG规则。应用：应用US规则、UG规则、ES规则、EG规则进行谓词演算的推理证明。（二）谓词公式及其翻译、谓词演算的等价式与蕴涵式（次重点） 识记：谓词公式及谓词公式的赋值的概念、理解：前束范式及谓词演算的等价式与蕴涵式。 应用：谓词公式的翻译，求公式的前束范式。（三）n元谓词与量词（一般） 识记：客体、个体域、全总个体域、谓词、命题函数、n元谓词、全称量词、存在量词、量词的辖域、约束变元、自由变元等概念。第三章 集合与关系一、学习目的与要求 通过本章学习，使学生掌握序偶与笛卡尔积的概念、关系的概念及其表示；关系的性质；自反闭包、对称闭包、传递闭包的概念及求法；复合关系与逆关系的概念及求法；划分与覆盖的概念；相容关系与最大相容类的概念；等价关系与等价类的概念；偏序关系、偏序集的概念及其哈斯图表示；为代数结构的学习奠定基础。二、考核知识点与考核目标（一）等价关系与划分（重点）理解：划分、等价关系、等价类及商集的概念；等价关系与划分之间的联系。应用： 给定集合A上的等价关系R确定集合A的划分（或A关于R的商集）及给定集合A的划分确定集合A上的等价关系。（二）偏序关系（重点）理解：偏序关系、偏序集的概念及其哈斯图表示；偏序集中的特殊元素。应用：会证明一个关系是偏序关系；会画偏序关系的哈斯图；会求偏序集中的特殊元素。（三）关系的概念及性质（次重点）识记：序偶与笛卡尔积的概念。理解：关系的概念及其表示、关系的性质；复合关系与逆关系的概念。应用：关系的性质的判定、复合关系与逆关系的求法。（四）关系的闭包运算（次重点）理解：关系的矩阵表示；关系的自反闭包、对称闭包、传递闭包的概念。天津理工大学离散数学课程考试大纲(2005年8月版)课程名称: 离散数学 课程代码: 0600030应用：自反闭包、对称闭包、传递闭包求法。（五）集合的概念与运算（一般）识记：集合的概念及其交、并、补和对称差运算。理解：集合的幂集的概念。应用：集合的幂集的求法。（六）相容关系（一般）识记：覆盖、相容关系及最大相容类的概念。理解：相容关系与覆盖之间的联系。第四章 函数一、学习目的与要求通过本章学习，使学生掌握函数（映射）、函数的前域、函数的值域、函数的相等、入射、满射、双射、恒等映射、反函数、复合函数的概念；掌握函数复合运算的性质；掌握函数与一般关系、反函数与逆关系的区别；掌握函数是入射、满射、双射的证明；掌握集合的基数、可数集和不可数集的概念及集合基数的比较。为代数结构的学习奠定基础。（一） 函数（重点）识记：函数的前域、函数的值域、函数的相等。理解：函数、入射、满射、双射、复合函数和逆函数的概念及其性质；函数与一般关系、逆函数与逆关系的区别。应用：会证明一个函数是入射、满射、双射。（二） 集合的基数（一般）识记：集合的基数、可数集和不可数集的概念及集合基数的比较。第五章 代数结构一、学习目的与要求 通过本章学习，使学生掌握代数系统的概念；代数运算及其性质；半群、独异点与群、子群、循环群、交换群（Abel群）及其性质；了解环和域。 二、考核知识点与考核目标（一）群与子群（重点）理解：半群、独异点、群、子群、交换群、循环群、循环群的生成元的概念及其性质。应用：会证明一个代数系统构成独异点、群、交换群。（二）代数系统的同构（重点）理解：两个代数系统同构的概念。应用：会证明两个代数系统同构。(三) 代数系统及运算（次重点）识记：代数运算的概念与性质。理解：代数系统中的幺元、零元、逆元及其性质。应用：求代数系统中的幺元、零元、逆元。（四）环与域（一般）识记：环与域的概念。第六章 格与布尔代数一、学习目的与要求通过本章学习，使学生掌握格、格所诱导的代数系统、子格、分配格、有界格、全上（下）界、补元、有补格、布尔格、原子、布尔代数、布尔表达式等概念；掌握格的基本性质、格对偶原理、格的基本性质；掌握分配格、有补格及布尔格的判别方法；理解关于有限布尔格结构的Stone表示定理；掌握布尔表达式的析（合）取范式的求法。为后续课程的学习奠定必需的基础。二、考核知识点与考核目标（一） 格的概念（重点）识记：格对偶原理。理解：格与格所诱导的代数系统、子格的概念及格的基本性质。应用：会判断一个偏序集是否构成格。（二） 几种特殊的格（重点）理解：分配格、有界格、全上（下）界、补元、有补格、等概念；。应用：会判断一个偏序集是否构成分配格、有界格、有补格。（三） 布尔代数（重点）识记：原子的概念及关于有限布尔格结构的Stone表示定理。理解：布尔格、原子、布尔代数、布尔表达式及布尔表达式的析（合）取范式等概念。应用：会判定一个偏序集是否构成布尔格；会判定一个代数系统是否构成布尔代数； 会求布尔表达式的析（合）取范式。第五章 图论一、学习目的与要求 通过本章学习，使学生掌握图的基本概念、图的连通性及Euler图、Hamilton图、树的有关应用，掌握用图形表达事物的科学方法，为今后的数据结构、计算机网络等课程的学习奠定必需的基础。二、考核知识点与考核目标（一）图的基本概念及连通性（重点）识记：图、有向图、无向图、简单图、多重图、零图、完全图等概念。理解：结点的度数、出度及入度等概念；弱连通、单侧连通、强连通等概念。 应用：图的结点的度数与边数的关系及其应用；图的连通性的判别。（二）树及应用（重点） 理解：无向树的等价定义、无向图的生成树与最小生成树、根树、m叉树、完全m叉树等概念。 应用：最小生成树的Kruscal算法及最优二叉树的构造方法。最小生成树及根树的应用。（三）图的矩阵表示（次重点） 理解：图的邻接矩阵及可达性矩阵的概念及其性质。应用：求图的邻接矩阵及可达性矩阵；根据图的邻接矩阵求结点的度数、出度、入度及由一个结点到另一个结点长度为k的路径的条数。（四）Euler图与Hamilton图（次重点）理解：Euler图与Hamilton图的概念及其充分条件和必要条件。应用： Euler图与Hamilton图的判定。（五）平面图（次重点）理解：平面图的概念、有限平面图面的次数与其边数的关系。应用：会判别一些简单的图是否是平面图。天津理工大学离散数学课程考试大纲(2005年8月版)课程名称: 离散数学 课程代码: 0600030第三部分 有关说明与实施要求一、考核目标的能力层次表述本课程的考核目标共分为三个能力层次：识记、理解、应用，它们之间是递进等级的关系，后者必须建立在前者基础上。其具体含义为：识记：能知道有关的名词、概念、知识的含义，并能正确认识和表述，是低层次的要求。理解：在识记的基础上，能全面把握基本概念、基本原理、基本方法，能掌握有关概念、原理、方法的区别与联系，是较高层次的要求。应用：在理解的基础上，能运用基本概念、基本原理、基本方法联系学过的多个知识点分析和解决有关的理论问题和实际问题，是最高层次的要求。二、指定教材离散数学 左孝凌编著 上海科技文献出版社 1982年9月 第一版三、参考书目1 Discrete Mathematics and Its Applications （英文版） (美)Kenneth H.Rosen 著，机械工业出版社，2003. 2 离散数学 理论分析题解 左孝凌等著， 上海科技文献出版社，2000.4 3 耿素云编，离散数学，清华大学出版社，1992年2月第一版。 4 王遇科编，离散数学，北京理工大学出版社。 5 简明离散数学 王存礼等著 天津人民出版社四、各章学时分配本课程共5学分，总课时为80学时，各章学时分配如下：章次课程内容助学学时1命题逻辑162谓词逻辑143集合与关系164函数45代数系统106格与布尔代数107图论10总 计80五、关于命题考试的若干规定1、本大纲各章所提到的内容和考核目标都是考试内容。试题覆盖到章，适当突出重点。2、试卷中对不同能力层次的试题比例大致是：“识记”为10%、“理解”为30%、“应用”为60%。3、试题难易程度应合理：易、较易、较难、难比例为2：3：3：2。天津理工大学离散数学课程考试大纲(2005年8月版)课程名称: 离散数学 课程代码: 06000304、每份试卷中，各类考核点所占比例约为：重点占65%，次重点占25%，一般占10%。5、本课程命题采用的基本题型包括单项选择、填空题、简答与计算题、证明题等。6、考试采用闭卷考试，考试时间150分钟，采用百分制评分，60分为及格。六、题型示例（样题）（一）单项选择题 下列哪个命题是假命题（）(1)如果是偶数，那么一个命题公式的析取范式唯一；(2)如果是偶数，那么一