离散数学

第一部分数理逻辑

第一章命题逻辑的基本概念

1.1命题与联结词

1.2命题公式及其赋值

习题一

第二章命题逻辑等值演算

2.1等值式

2.2析取范式与合取范式

2.3联结词的完备集

2.4可满足性问题与消解法

习题二

第三章命题逻辑的推理理论

3.1推理的形式结构

3.2自然推理系统P

习题三

第四章一阶逻辑基本概念

4.1一阶逻辑命题符号化

4.2一阶逻辑公式及其解释

习题四

第五章一阶逻辑等值演算与推理

5.1一阶逻辑等值式与置换规则

5.2一阶逻辑前束范式

5.3一阶逻辑的推理理论

习题五

第二部分集合论

第六章集合代数

6.1集合的基本概念

6.2集合的运算

6.3有穷集的计数

6.4集合恒等式

习题六

第七章二元关系

7.1有序对与笛卡儿积

7.2二元关系

7.3关系的运算

7.4关系的性质

7.5关系的闭包

7.6等价关系与划分

7.7偏序关系

习题七

第八章函数

8.1函数的定义与性质

8.2函数的复合与反函数

8.3双射函数与集合的基数

8.4一个电话系统的描述实例

习题八

第三部分代数结构

第九章代数系统

9.1二元运算及其性质

9.2代数系统

9.3代数系统的同态与同构

习题九

第十章群与环

10.1群的定义及其性质

10.2子群与群的陪集分解

10.3循环群与置换群

10.4环与域

习题十

第十一章格与布尔代数

11.1格的定义与性质

11.2分配格、有补格与布尔代数

习题十一

第四部分组合数学

第十二章基本的组合计数公式

12.1加法法则与乘法法则

12.2排列与组合

12.3二项式定理与组合恒等式

12.4多项式定理

习题十二

第十三章递推方程与生成函数

13.1递推方程的定义及实例

13.2递推方程的公式解法

13.3递推方程的其他解法

13.4生成函数及其应用

13.5指数生成函数及其应用

13.6Cata1an数与Stir1ing数

习题十三

第五部分图论

第十四章图的基本概念

14.1图

14.2通路与回路

14.3图的连通性

14.4图的矩阵表示

14.5图的运算

习题十四

第十五章欧拉图与哈密顿图

15.1欧拉图

15.2哈密顿图

15.3最短路问题与货郎担问题

习题十五

第十六章树

16.1无向树及其性质

16.2生成树

16.3根树及其应用

习题十六

第十七章平面图

17.1平面图的基本概念

17.2欧拉公式

17.3平面图的判断

17.4平面图的对偶图

习题十七

第十八章支配集、覆盖集、独立集、匹配与着色

18.1支配集、点覆盖集与点独立集

18.2边覆盖集与匹配

18.3二部图中的匹配

18.4点着色

18.5地图着色与平面图的点着色

18.6边着色

习题十八

第六部分初等数论

第十九章初等数论

19.1素数

19.2最大公约数与最小公倍数

19.3同余

19.4一次同余方程

19.5欧拉定理和费马小定理

19.6初等数论在计算机科学技术中的几个应用

习题十九

名词与术语索引

符号注释

参考文献

　　本书是根据CCC2005规范中关于离散数学核心内容的要求，对原版书中的有些章节进行了调整。该书增加了组合数学中关于递推方程、生成函数等组合计数方法的内容，并重点说明了这些方法在计算机算法分析中的应用。增加了有关初等数论基础知识的介绍，并讲述了它们在计算机加密技术中的应用。同时，删减了关于集合基数以及代数结构中群、环、域、格的部分内容。重新组织了图论中的部分知识点，以使得整个教材的中心更突出，知识体系更清晰，知识点的分布更合理。另外，本书还重写了数理逻辑中的一阶逻辑推理理论，并补充了和计算机科学技术应用背景紧密结合的实例，又在语言文字方面做了进一步的加工，同时订正了部分疏漏之处。　　本书起源于高等教育出版社1998年出版的《离散数学》，是教育部高等学校“九五”规划教材，2004年作为“十五”规划教材出版了修订版。作为“十一五”规划教材，根据教育部计算机科学与技术专业教学指导委员会提出的《计算机科学与技术专业规范》(CCC2005)的教学要求，本教材对内容进行了较多的调整与更新。　　本书分为数理逻辑、集合论、代数结构、组合数学、图论、初等数论等六个部分。全书既有严谨的、系统的理论阐述，也有丰富的、面向计算机科学技术发展的应用实例，同时选配了大量的典型例题与练习。各章内容按照模块化组织，可以适应不同的教学要求。与本书配套的电子教案和习题辅导用书随后将陆续推出。　　本书可以作为普通高等学校计算机科学与技术专业不同方向的本科生的离散数学教材，也可以供其他专业学生和科技人员阅读参考。