本书是在作者出版的《离散数学学习指导》的基础上写成的一本适应面广、内容适中，可供两个学期选用的离散数学教材。
　　全书共分14章，主要介绍数理逻辑、集合论、代数系统、组合分析与算法数论、图论。各部分内容尽量由浅入深，同时都尽量安排了“应用”，试图让读者懂得“学以致用”。其中有些应用是对科技进步产生过重要作用的，有些应用在科学理论上意义重大。

本书的主要特色
　　●讲解透彻：深入浅出地介绍离散数学所包含的基本知识。
　　●内容新颖：融合了作者自己的理解、体会、方法和结果。
　　●注重应用：介绍了一些相关知识在现代科学技术领域的应用。
　　●习题适中：便于学生巩固所学知识，加深理解，学以致用。

无

本书可作为两个学期的《离散数学》教材，也可作为一个学期《离散数学》、另一个学期《密码学数学基础》或《信息安全数学基础》教材，适应面较广。其中大多数定理和推论都给出了证明，也有少量的定理或推论没有证明。没有证明的部分有的可以留作习题，也有个别定理的证明超出了本书的范围（这些在书中一般都已注明）。下面是本书的具体教学建议。
　　（1）本书的第一篇、第二篇和第五篇的有关内容可作为通常一学期的《离散数学》课程教学内容。这样选择至少有两个可虑：首先，“数理逻辑”、“集合论”和“图论”既是离散数学的基本内容，也是学习计算机学科其他课程所必需的基础；其次，这些内容可以独立成篇，“教”和“学”都很容易接受。
　　在这部分教学中，我们建议整个课时数为54。具体课时分配方案是：“数理逻辑”部分20课时、“集合论”部分18课时、“图论”部分16课时。其中，“数理逻辑”部分的“命题逻辑推理的机械化方法”、“集合论”部分的“二元运算”可以不讲。
　　（2）第三篇和第四篇的有关内容可独立作为另一个学期的《离散数学》课程教学内容，也可作为一学期《密码学数学基础》或《信息安全数学基础》的教学内容。这部分内容主要是“代数系统”、“组合分析和算法数论”，它们既是《离散数学》的内容，也是“密码学”或“信息安全理论”的数学基础课程教学内容。
这部分建议课时数也为54。具体课时分配方案有两种：第一种是不可虑与其他教学内容冲突，建议：“代数系统”部分最多可安排34课时、“组合分析和算法数论”部分20课时。第二种课时分配方案是需要考虑与其他内容可能存在的冲突。如果“形式语言与自动机”能够独立开课，那么这时建议“半群、语言和自动机”部分删除“语言和自动机”内容。这样可安排“代数系统”部分30课时、“组合分析和算法数论”部分24课时。
　　上述分配方案中，“算法数论”部分的“有限域上的椭圆曲线算术和ECC”、“配对和基于身份的公钥密码体制”可供选择作为激发学生学习兴趣的内容，而不要求在正常教学范围。同时，有些内容可以留作“大作业”，例如“原根计算”和对有关密码方案安全性的讨论等。
　　上述内容分配和课时分配建议可以用两张图来说明：

　　应该指出，上述教学建议仅供使用本教材的同仁参考。我们也会在实践中进一步完善本书的内容。希望使用本教材的同仁随时提出意见，在这里提前谢谢大家！

出版者的话

序言

前言

教学建议


第一篇数理逻辑


第1章命题逻辑

11命题与联结词

111命题基本概念

112命题联结词

113复合命题

12命题公式

121定义

122赋值

123真值表技术

13等值演算

131基本等值式

132等值演算过程

133对偶公式和内否公式

14命题公式的范式

141析取范式和合取范式

142主范式

15联结词的功能完全集

151真值函数

152功能完全集

16永真蕴涵式

161基本永真蕴涵式

162证明永真蕴涵式的
方法

17命题逻辑推理

18命题逻辑归结推理法

19命题逻辑推理的机械化方法

第2章谓词逻辑

21谓词逻辑的基本概念

211谓词的概念

212量词的概念

22谓词逻辑公式

221合式公式

222约束变元和自由变元

223赋值

224换名规则和替换规则

23谓词逻辑的等值演算与前束
范式

231基本等值式

232前束范式

24Skolem标准型

241前束范式

242无前束范式

25谓词逻辑的推理理论

251基本永真蕴涵式

252推理规则

253推理实例

26谓词逻辑的归结推理法

261归结证明过程

262归结证明实例



第二篇集合论


第3章集合

31集合的定义

32集合的基本运算

33有限集合的计数

34集合表达式的相等与包含


35集合的特征函数

第4章关系

41二元关系

42二元关系的表示及按性质分类


421二元关系的关系矩阵和
关系图表示

422二元关系的按性质
分类

43二元关系的运算

44二元关系的合成

45关系的闭包

46等价关系和偏序关系

461等价关系

462偏序关系

第5章函数

51函数的基本概念

52函数的性质

53函数的复合与反函数

54可逆函数集与置换

55二元运算

56基数



第三篇代数系统


第6章半群、语言和自动机

61半群与语言

62语言和文法

63有限状态机

64有限状态自动机

65语言与自动机的关系

第7章群、环和域

71群的基本概念

72子群

73群的同态与同构

74子群的陪集

75对称群、置换群、正规性与
商群

76群在集合上的作用

77同态基本定理与同构定理

78环的基本概念

79子环、理想与商环

710交换环中的因子分解

711多项式环

712多项式环的因子分解

713域的基本概念

714分裂域

715有限域

第8章格与布尔代数

81格的概念

82分配格

83有补格

84布尔代数

85布尔表达式

86数字电路与最小化



第四篇组合分析与算法数论


第9章组合分析

91计数

92排列与组合

93递推序列

94抽屉原理

95生成函数

第10章算法数论

101整数论

102与整数有关的典型算法

103素性测试、因数分解与公钥
密码学

1031素性测试

1032因数分解

1033公钥密码

104有限域上的椭圆曲线算术和
ECC


105*配对和基于身份的公钥密码
体制

1051双线性配对

1052基于身份的密码


第五篇图论


第11章无向图

111无向图的基本概念


112无向图的表示

113无向图的连通性

114欧拉图与哈密顿图

1141欧拉图

1142哈密顿图

115最短通道问题


第12章平面图与图着色

121平面图的基本概念

122欧拉公式和极大平面图

123平面图的对偶图


124图着色

第13章有向图

131有向图的基本概念

132有向图的连通性

第14章树

141基本定义和性质

142生成树与最小生成树

143有根树

144二叉树和哈夫曼树

参考文献

顾名思义，离散数学是研究离散对象及其相互间关系的一个数学分支，它的基本内容已出现在现代科学技术的各个领域。例如，计算机科学、程序设计、计算机网络、信息论与编码、通信理论、现代密码学、数字信号处理和形式语言等都与离散数学密切相关。正因为如此，离散数学在国际上已受到高度重视，在我国也已成为理工科高等院校各专业的重要基础课，尤其是计算机和应用数学专业。
　　离散数学的内容非常广泛，它至少包含了数理逻辑、集合论、代数学、组合数学、数论、图论、计算理论和复杂性理论、复杂网络以及协同网络计算等内容。这些内容里面又细分了许多个分支学科，包含了当前国际前沿的数学和科学技术理论研究课题。在已出版的众多离散数学教科书及其习题解答中，大部分都是介绍那些应用广泛且易理解、可接受的基本知识和方法。我们也出版了一本《离散数学学习指导》，该书的写作风格类似于国外流行的Schaums Outline Series教材，在内容上则增加了“密码学”或“信息安全理论”的数学基础内容，使离散数学的基本内容有了一些扩展。而本书是在《离散数学学习指导》的基础上编写的一本适应面广、内容适中的离散数学教材。
　　全书共五篇，依次为数理逻辑、集合论、代数系统、组合分析与算法数论、图论，分成14章：命题逻辑，谓词逻辑，集合，关系，函数，半群、语言和自动机，群、环和域，格与布尔代数，组合分析，算法数论，无向图，平面图与图着色，有向图，树。各章都尽量安排了“应用”，试图让学生学以致用。其中，有些应用是对科技进步产生重要作用的，例如，自动定理证明、数字电路、语言与有限自动机、基于身份的密码设计等；有些应用在科学理论上意义重大，例如，超越数无穷的集合论证明等。另外，第10章（算法数论）还引进了最新的研究成果，特别是近几年才产生的“双线性配对与基于身份的密码”，供读者选学。
　　本书可作为高等院校计算机及相关专业“离散数学”课程的教材或教学参考书，供两个学期使用。其中，第一篇、第二篇和第五篇的有关内容可作为通常一学期的“离散数学”课程教学内容；第三篇和第四篇的有关内容可作为独立的一学期的“离散数学”课程教学内容，也可作为一学期“密码学”或“信息安全理论”的数学基础课程教学内容。应该指出的是，本书有些内容非常深刻，是近年来的最新研究成果介绍，教师在讲授时应有所选择，读者在学习中也应有所区别。
　　本书在编写过程中参考了许多已经出版的同类书籍，例如，第一篇、第二篇参考了文献［113］，第三篇参考了文献［1417］，第四篇参考了文献［1830］，第五篇参考了文献［3136］。在此对这些书的作者表示由衷的感谢！
　　我们在编写本书时虽然花费了很多时间，且又有《离散数学学习指导》作为蓝本，但由于水平所限，书中难免存在疏漏。希望读者发现问题随时与我们联系（Email: dmjc@cssjtueducn）,我们会在重印或再版时加以改正。
最后，我们感谢傅育熙教授在百忙之中的审稿，感谢机械工业出版社华章分社的编辑的细心编辑加工，使本书增色不少。
　　作者

　　2008年5月于上海