loading离散数学教学大纲
一、教学目标
本课程的教学目标是：
1．学习和掌握离散型关系结构的构成及分析方法，包括：
集合论的主要内容：集合的基本概念、二元关系、函数、自然数和基数等； 图论的主要内容：图的基本概念、欧拉图与哈密尔顿图、树、图的矩阵表示、平面
图、图的着色、支配集、覆盖集、独立集与匹配、带权图及其应用等；
2. 学习和掌握离散型代数结构的构成、性质和分析方法，熟悉半群、群、环、域、格、布尔代数等有着重要应用背景的代数模型；
3. 学习和掌握组合配置的存在性证明和计数方法，并用于离散结构的性质分析。 4. 学习和掌握命题逻辑、一阶谓词逻辑的基本概念和推理方法。
5. 能够理论联系实际，用上述离散数学的描述工具和分析方法对实践中的离散系统进行建模和分析。
6. 通过严谨证明及正确逻辑推理的训练，进一步培养学生的抽象思维、计算思维能力和专业素质。
二、教学内容
1．集合（教材第一章） ? 引言
? 预备知识（命题逻辑） ? 预备知识（一阶谓词逻辑） ? 集合的概念和集合之间的关系 ? 集合的运算 ? 基本的集合恒等式 2．二元关系（教材第二章） ? 有序对与卡氏积 ? 二元关系
? 关系的表示和关系的性质 ? 关系的幂运算和闭包 ? 等价关系和划分 ? 序关系
3． 函数（教材第三章）
? 函数的基本概念、性质、合成、反函数
4． 自然数（教材第四章） ? 自然数的定义 ? 自然数的性质 5． 基数（教材第五章）
? 集合的等势、有穷集合与无穷集合 ? 基数和基数的比较与运算 6． 图（教材第七章）
? 图的基本概念 ? 通路与回路
? 无向图和有向图的连通性 ? 无向图的连通度
7． 欧拉图与哈密顿图（教材第八章） ? 欧拉图 ? 哈密顿图 8． 树（教材第九章） ? 树
9． 图的矩阵表示（教材第十章） ? 图的矩阵表示
10．平面图（教材第十一章） ? 平面图的基本概念 ? 欧拉公式与平面图的判断 ? 平面图的对偶图与外平面图 ? 平面图与哈密顿图 11．图的着色（教材第十二章） ? 点着色和色多项式 ? 平面图着色和边着色
12．支配集、覆盖集、独立集与匹配（教材第十三章） ? 支配集、点覆盖集、点独立集 ? 边覆盖数与匹配 ? 二部图中的匹配
13．带权图及其应用（教材第十四章） ? 中国邮递员问题和货郎问题
14. 代数系统（教材第十五章）
? 二元运算及其性质
? 代数系统、子代数和积代数 ? 代数系统的同态与同构 ? 同余关系与商代数
15. 半群与独异点（教材第十六章） ? 半群与独异点 16 . 群（教材第十七章） ? 群的定义和性质、子群 ? 循环群、变换群与置换群
? 群的分解、正规子群与商群、群的同态与同构 17. 环与域（教材第十八章） ? 环与域
18. 格与布尔代数（教材第十九章） ? 格的定义和性质、子格、格同态与直积 ? 模格、分配格、有补格与布尔代数 19. 组合存在性定理（教材第二十章） ? 鸽巢原理和Ramsey定理
20. 基本的计数公式（教材第二十一章） ? 两个计数原则、排列组合 ? 二项式定理与组合恒等式 ? 多项式定理
21. 组合计数方法（教材第二十二章） ? 递推方程的公式解法 ? 递推方程的其他求解方法 ? 生成函数的定义和性质 ? 生成函数、指数生成函数及应用 ? Catalan数与Stirling数
22. 组合计数定理（教材第二十三章） ? 包含排斥原理与对称筛公式 ? Burnside引理与Polya定理
23. 命题逻辑（教材第二十六章） ? 引言 ? 命题和联结词 ? 命题形式和真值表 ? 联结词的完全集
? 推理形式
? 命题演算自然推理形式系统N ? 命题演算形式系统P ? N与P的等价性 ? 赋值与等值演算 ? 命题范式
? 可靠性、和谐性与完备性
24. 一阶谓词逻辑（教材第二十七章） ? 一阶谓词演算的符号化 ? 一阶语言
? 一阶谓词演算形式系统NL ? 一阶谓词演算形式系统KL ? NL与KL的等价性 ? KL的解释与赋值 ? KL的可靠性与和谐性 ? KL的和谐公式集
三、教学方式
以课堂讲授为主，辅以作业和练习，并配备助教对作业进行批改。采用网上教学平台发布课程的教学资源，并进行教学讨论、交流和答疑。组织有兴趣的学生参加课题研究，提高解决实际问题的能力。
四、授课对象要求
修过高等数学（或数学分析）、线性代数（或高等代数）等课程。
五、教材及参考资料
教材：耿素云，屈婉玲，王捍贫，离散数学教程，北京大学出版社，2004修订版。 参考资料：
1. 屈婉玲、耿素云、王捍贫、刘田，离散数学习题解析，北京大学出版社，2008。 2. Discrete Mathematics and Its Applications（7th Edition）, Kenneth H. Rosen, McGraw Hill Companies, Inc, 2012 （或机械工业出版社影印第6版）。