离散数学教学大纲

Discrete Mathematics

【课程编号】

【学分】3.5          【参考学时】56

【编写】             【审    核】

（一）授课对象

四年制本科数学与应用数学、信息与计算科学等专业。

（二）教学内容

1．数理逻辑部分

（1）命题公式（谓词公式）及表示法、联结词；（2）命题公式（谓词公式）的重言式、蕴含式、等价式。（3）命题公式的范式、谓词公式的前束范式；（4）约束变元和自由变元；（5）推理理论。

2．集合与关系部分

（1）集合的概念与表示法，集合的运算；（2）序偶与笛卡尔积；（3）二元关系、关系的五大性质（4）复合关系与逆关系；（5）关系的闭包运算；（6）等价关系、划分；（7）相容关系、覆盖；（7）偏序关系、偏序集。

3．代数系统部分

（1）半群；（2）群、子群；（3）阿贝尔群、循环群；（4）同态与同构，同余关系；（6）环与域的基本概念。

4．图论部分

（1）图及其相关概念，图的同构；（2）路和回路、连通性；（3）图的矩阵表示；（3）欧拉图和汉密尔顿图；（4）树、生成树。

（三）主要参考书

1．左孝凌主编 《离散数学》， 上海科学技术出版社,1982年版；

2．刘光奇等编 《离散数学》， 复旦大学出版社，1988年版；

3．张锦文等编 《离散数学引论》 天津科学技术出版社，1986年版。

二、大纲说明

（一）本课程的性质、地位和任务

   《离散数学》课程是专业基础课。它是计算机科学中基础理论的核心课程，是现代数学的一个重要分支。离散数学是以研究离散量的结构和相互关系为主要目标，其研究对象一般地是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。离散数学是一门新兴的工具性学科，是为培养适应市场经济要求的应用型人才服务的。

    通过本课程的学习，使学生获得数理逻辑、集合论、代数系统和图论的基本常识。培养学生的分析、推理能力，增强学生用具体与抽象相结合的方法处理问题和解决问题的能力。为下一步学习计算机方面的有关课程打好基础。

（二）课程教学的基本要求

   通过本课程的学习，学生应达到如下要求：能判断命题（谓词），熟悉五种常见联结词的作用，了解其余联结词；理解命题公式（谓词公式），会作命题公式的真值表，掌握重言式，矛盾式；掌握命题公式（谓词公式）的等价关系，熟练置换与代入规则；掌握命题公式（谓词公式）的蕴含关系及其证明；会求合取与析取范式，会求主合取与主析取范式，会求谓词公式的前束范式；掌握命题演算（谓词公式）的推理规则，并能运用。理解集合及其相关概念，掌握集合的表示方法；熟悉集合的并、交、补、差等运算并掌握集合的基本运算律；

能证明一些简单的集合恒等式；理解序偶与笛卡尔积；理解二元关系及有关概念；熟练掌握关系矩阵及关系图；关系的五大性质：自反、对称、传递、反自反、反对称性并了解其矩阵及图表示与特征；会求复合关系、逆关系；会求关系的闭包；理解等价关系、等价类、商集、划分等概念；理解相容关系、相容类与最大相容类；能判断偏序集的最大、最小、极大、极小元与界；理解二元运算的概念，理解二元运算的封闭性、交换律、结合律、分配律，了解幂等律、吸收律；理解半群、独异点，理解并能判断幺元、零元和逆元；理解群与子群的概念、理解循环群、阿贝尔群的概念；知道群的基本判定定理，了解群同态与同构；知道环与域的基本概念。掌握图、简单图、多重图、赋权图、子图、生成子图、完成图等概念；了解图的同构；理解路、回路、图的连通性，理解欧拉图，了解哈密尔顿图；理解邻接矩阵及可达性矩阵并能简单应用；理解树及其相关基本概念，会求加权图的最小生成树。

（三）本课程与其他课程的联系与分工

    离散数学是计算机科学知识的基础。它自成体系。对后续课程如数据结构、操作系统、编译理论、算法分析、逻辑设计、系统结构等的学习可以打下坚实的理论基础。

（四）重点与难点

   重点：翻译，范式，推理。关系的概念，关系的五大性质及其判断，等价关系与偏序关系。半群、群的概念及其判断，幺元、零元与逆元的判断。图的概念、树的概念，图的矩阵表示。

   难点：谓词的翻译，蕴含式，量词作用域的扩张与收缩。等价类，相容类。 群的性质，同态。有向图的连通性，欧拉图。

（五）习题、实验及上机要求

   1．习题要求：结合各章节的内容，注重基本知识和基本技能的掌握。布置一些习题，习题量适中即可。

   2．实验及上机要求：

（1）数理逻辑指导简单逻辑电路设计。

（2）欧拉图理论指导学生计算机鼓轮机的设计。

（六）学时分配

                                         上一篇 ：

                                         瀚海网（http://hanhai.org)