《离散数学教程》

第1章命题逻辑1

1.1命题的表示与逻辑联结词1

1.2命题合适公式与真值表6

1.3命题公式的等价9

1.4命题公式的范式表示13

1.5命题公式的蕴含17

1.6命题逻辑的推理方法20

1.7逻辑联结词的功能完备集24

1.8应用：数字逻辑电路设计26

第2章一阶谓词逻辑30

2.1量词化逻辑30

2.2谓词合适公式及其解释33

2.3谓词公式的等价与范式表示37

2.4谓词公式的蕴含42

2.5谓词逻辑的推理方法45

2.6应用：逻辑程序设计49

第3章集合及其运算52

3.1集合的基本概念52

3.2集合间的运算55

3.3集合的范式表示58

3.4集合的幂集和笛卡尔集60

3.5应用：形式语言62

第4章初等数论和证明方法66

4.1整数集合66

4.2商和余数68

4.3整除和素因子分解70

4.4最大公因子72

4.5数学归纳法74

4.6应用：随机数77

第5章二元关系79

5.1二元关系及其表示79

5.2二元关系的性质82

5.3关系的运算84

5.4二元关系的闭包87

5.5等价关系91

5.6偏序关系94

5.7应用：关系数据库管理系统99

第6章函数101

6.1一般集合的函数概念101

6.2单射、满射和双射104

6.3函数的递归定义108

6.4集合的基数、可数集和不可数集111

6.5应用：算法的复杂性表示116

第7章基本计数方法120

7.1排列计数120

7.2组合计数123

7.3组合恒等式126

7.4容斥原理128

7.5鸽巢原理131

第8章生成函数和递推关系134

8.1序列与生成函数134

8.2组合问题的生成函数137

8.3递推关系式及其解141

8.4递推关系式的生成函数求解146

8.5应用：排序算法150

第9章无向图和有向图153

9.1图的基本概念153

9.2图的道路与连通性161

9.3图的矩阵表示166

9.4独立集、点团和极图问题174

9.5图的着色179

第10章基本图类和算法186

10.1树与生成树186

10.2根树及其应用190

10.3图的生成树构造和计数196

10.4平面图与对偶图203

10.5欧拉图及其应用207

10.6哈密顿图及其应用212

10.7图的匹配与匈牙利算法217

10.8网络222

第11章群和环230

11.1运算与代数系统230

11.2半群233

11.3群和子群236

11.4交换群和循环群239

11.5陪集与拉格朗日定理241

11.6同态与同构243

11.7环和域246

11.8应用：群码250

第12章格与布尔代数253

12.1格的两个等价定义253

12.2格的性质和格同态256

12.3分配格和有补格259

12.4布尔代数262

附录266

一、本书使用记号一览266

二、离散数学术语的中、英文对照（以汉语拼音为序）268

三、离散数学自测试题276

参考文献279