前  言

在计算机科学教学中，离散数学主要是为专业服务的基础理论课，是一门概念较多、理论性较强，应用性较广的课程。本课程主要教授数理逻辑、集合论、代数系统、图论方面的基础知识，是计算机科学教学中一些后续课程学习的基础和工具。通过本课程的学习，要使学生掌握离散数学的基本概念和基本原理，以现代数学的观点和方法，初步掌握处理离散结构所必须的描述工具和方法。同时，也要培养学生抽象思维、缜密概括、逻辑推理的能力，从而使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力。

【课程目的】

《离散数学》课程的主要任务是研究离散体系的结构特征, 使学生初步掌握研究计算机科学的基础理论。能够掌握集合的概念、运算及应用，集合内元素间的关系以及集合之间的关系，无限集的特性；掌握抽象代数的基本理论和应用；掌握图论学科的基本理论知识和相关应用；掌握数理逻辑中命题演算、谓词演算等形式逻辑的推理规律。

【课程内容简介】

本课程主要内容包括：等价关系、偏序关系、命题逻辑、谓词逻辑、推理规则、代数系统、群论、环、图论、树

【教学要求】 通过本课程的学习，学生除了记住并理解基本的概念和知识外，更重要的使培养自己的数学思维能力。通过各个教学环节，逐步培养学生的抽象概括问题的能力、逻辑推理能力、自学能力，较熟练的运算能力和综合运用所学知识分析问题、解决问题的能力，使学生在众多的概念中找到最重要的，在众多的定理中找到最根本的，将这些少量的概念和定理能够透彻地理解，自如运用，为学生学习后续课程和进一步获得近代科学技术知识奠定必要的数学基础。

本课程教学时数共54学时。

教学目的要求和内容

第一章  命题逻辑

【目的要求】

1．理解命题和逻辑联结词的基本概念；

2．掌握公式分类和真值表构造。

3．理解命题等值关系式；

4．掌握公式的析取范式和合取范式；

5．了解联结词的完备集。

6．掌握重要的重言蕴涵式；

7．理解推理的形式结构

【教学内容】

1. 掌握命题定义；逻辑联结词。

2. 理解命题联结词。

3. 掌握命题公式的概念

4. 掌握公式的真值表。

5. 熟练掌握求给定公式真值表的方法

6. 掌握真值表法和等值演算法

7. 掌握范式；会用等值演算法求公式的析取范式和合取范式

8. 掌握重言蕴涵式。

9. 理解推理的形式结构。

10.了解一些常用的联结词的完备集。

【授课方法与学时】

课程讲授    9学时

第二章  一阶逻辑

【目的要求】

1．掌握一阶逻辑的命题符号化；

2．理解谓词公式与解释。

3．掌握一阶逻辑的等值关系式；

4．理解谓词公式的前束范式；

5．掌握一阶逻辑的推理理论。

【教学内容】

1. 掌握一阶逻辑命题符号化。

2. 一阶逻辑公式；自由变元；约束变元；解释。

3. 掌握一阶逻辑公式在给定解释下的真值。

4. 一阶逻辑等值式；置换规则。

5. 掌握一阶逻辑等值式；

6. 换名规则；前束范式。

7. 掌握一阶逻辑推理过程。

【授课方法与学时】

课程讲授    8学时

第三章  集合

【目的要求】

1．了解集合的基本概念；

2．理解集合的运算和性质；

3．掌握集合定律、集合恒等式。

【教学内容】

1. 集合的基本概念。

2. 子集；幂集。

3. 集合的运算和性质。

4. 掌握集合的运算和性质；理解集合的计数问题。

5. 集合恒等式。

6. 掌握集合的笛卡尔乘积及性质

【授课方法与学时】

课程讲授    6学时

第四章  二元关系

【目的要求】

1．理解二元关系的概念；

2．掌握二元关系的运算和性质；

3．了解关系的闭包；

4．掌握等价关系和划分；

5．了解偏序关系。

【教学内容】

1. 了解二元关系的概念

2. 掌握三种特殊的关系；

3. 掌握关系的性质。

4. 掌握关系的运算。

5. 掌握等价关系及划分的概念与性质

6. 了解偏序关系的定义

7. 掌握偏序关系的性质

【授课方法与学时】

课程讲授    9学时

第六章  集合的基数

【目的要求】

1.了解基数的概念；

2．了解可数集与不可数集

【教学内容】

1. 了解基数的定义

2. 了解可数集和不可数集

【授课方法与学时】

课程讲授    1学时

第七章  代数系统

【目的要求】

1．了解二元运算及其性质；

2．了解代数系统的概念。

3. 了解同态与同构的基本概念

【教学内容】

1. 了解二元运算及其性质。

2. 了解代数系统的概念。

3. 了解同态与同构的基本概念

【授课方法与学时】

课程讲授    3学时

第八章  半群与群

【目的要求】

1．了解半群的概念；

2．理解群的定义与性质；

3．了解子群的概念和判别方法；

4．理解循环群和置换群。

【教学内容】

1. 群的定义与性质。

2. 了解子群的概念和判别方法。

3. 理解循环群的概念；

4. 掌握有限循环群的性质

【授课方法与学时】

课程讲授    4学时

第十章  格与布尔代数

【目的要求】

1．了解格和布尔代数的基本概念；

2．理解格的定义和性质；

3．掌握分配格、有补格、布尔代数性质。

【教学内容】

1. 了解格的定义与性质。

2. 了解子格与格同态的概念

3. 了解分配格与有补格的概念

4. 了解分配格与有补格的判别方法。

5. 掌握布尔代数的概念与性质。

【授课方法与学时】

课程讲授    5学时

第十一章  图

【目的要求】

1．理解图的基本概念；

2．理解图的连通性、矩阵表示和运算。

【教学内容】

1. 理解图的基本概念；

2. 掌握图的握手原理。

3. 了解通路与回路的概念

4. 了解通路(简单通路、初级通路和复杂通路)，

5. 了解回路(简单回路、初级回路和复杂回路)

6. 了解有向图和无向图的通路与回路的概念。

7. 了解有向图的连通性和无向图连通分支数。

8. 了解图的矩阵表示方法。

9. 了解欧拉图的判别方法。

10.了解哈密顿图的判别方法。

11.了解偶图的概念及判别方法。

12.了解平面图的概念及判别方法。

13.了解无向树的概念与性质。

14.了解生成树的概念与性质。

【授课方法与学时】

课程讲授    9学时

课时分配安排

教材及教学参考资料

【教材】

《离散数学（第2版）》刘玉珍,刘咏梅主编.武汉:武汉大学出版社,2002年8月第2版

【教学参考资料】

1. 《离散数学》. 耿素云,屈婉玲,张立昂编. 清华大学出版社, 2001年

2. 《离散数学》. 刘贵龙主编. 人民邮电出版社, 2000年

（信息工程学院  应用数学教研室）