高等学校计算机教育规划教材 离散数学PDF电子书下载

第1章　命题逻辑 1

1.1　现代逻辑学的基本研究方法 1

1.1.1　思维：感知的概念化和理性化 1

1.1.2　现代逻辑学求助数学——符号化 2

1.1.3　现代逻辑学追随数学——公理化 2

1.1.4　现代逻辑学改造数学——形式化 3

1.2　命题及其表示法 4

1.2.1　命题的概念 4

1.2.2　复合命题 4

1.2.3　联结词 5

1.2.4　复合命题真假值 7

1.3　命题公式与翻译 9

1.3.1　命题公式的定义 9

1.3.3　翻译 10

1.3.2　公式的层次 10

1.4　真值表与等价公式 11

1.4.1　真值表 11

1.4.2　等价公式 12

1.5　重言式与等值演算 12

1.5.1　重言式 12

1.5.2　等值演算 14

1.6　对偶与范式 16

1.6.1　对偶 16

1.6.2　简单合取式和简单析取式 17

1.6.3　范式 18

1.6.4　范式的唯一性——主范式 20

1.7　其他联结词 25

1.7.1　n元真值函数 26

1.7.2　真值函数与命题公式的关系 26

1.7.3　联结词完备集 27

1.7.4　单元素联结词构成的联结词完备集 28

1.8　推理理论 29

1.8.1　有效推理 29

1.8.2　有效推理的等价定理 30

1.8.3　重言蕴涵式 32

1.8.4　形式推理系统P1 34

1.8.5 自然推理系统P2 35

习题 41

第2章　谓词逻辑 51

2.1　谓词逻辑的基本概念 51

2.1.1　个体词 52

2.1.2　谓词 52

2.1.3　量词 53

2.2.1　一阶语言 54

2.2　谓词逻辑公式与翻译 54

2.2.2 自由与约束 55

2.2.3 闭公式 56

2.2.4　谓词逻辑公式的解释 57

2.2.5　谓词逻辑命题符号化 58

2.2.6　谓词逻辑公式的分类 61

2.3　谓词逻辑等值演算 62

2.3.1　基本等价式与置换规则 62

2.3.2　谓词逻辑前束范式 66

2.4　谓词演算的推理理论 68

2.4.1　推理定律 68

2.4.2　量词消去与引入规则 69

2.4.3　一阶谓词演算公理系统F1 69

2.4.4 自然推理系统F2 71

2.5.1　逻辑与计算 73

2.5　逻辑在计算机科学中的作用 73

2.5.2　逻辑与计算机的起源 74

2.5.3　逻辑与程序设计 75

习题 76

第3章　集合与关系 82

3.1　集合的概念和表示法 82

3.1.1　集合的表示 82

3.1.2　集合的基本概念 84

3.2　集合的运算 85

3.2.1　集合的基本运算 85

3.2.2　有穷计数集 86

3.2.3　广义交和广义并 87

3.3　有序对与笛卡儿积 89

3.4　关系及其表示 91

3.4.1　关系的基本概念 91

3.4.2　关系表示法 92

3.5　关系的运算 94

3.5.1　基本概念 94

3.5.2　复合关系 95

3.5.3　逆关系 96

3.5.4　关系幂 98

3.5.5　幂运算的性质 99

3.6　关系的性质 101

3.6.1　关系的五种基本性质 101

3.6.2　关系性质的等价描述 102

3.7　关系的闭包 106

3.7.1　闭包的基本概念 106

3.7.2　闭包的性质 110

3.8　集合的划分与覆盖 111

3.9.1　等价关系 112

3.9　等价关系和等价类 112

3.9.2　等价类的性质 114

3.9.3　商集与划分 115

3.10　偏序关系 116

3.11　偏序集与哈斯图 117

3.12　包含排斥原理 120

习题 121

第4章　函数 128

4.1　函数的定义 128

4.1.1　函数和像 128

4.1.2　函数的性质 130

4.1.3　常用函数 131

4.2　复合函数和反函数 132

4.2.1　复合函数 132

4.2.2　反函数 134

4.3　特征函数与模糊子集 136

4.3.1　特征函数 136

4.3.2　模糊集合 137

4.4　基数的概念 138

4.4.1　后继与归纳集 138

4.4.2 自然数，有穷集，无穷集 139

4.4.3　基数 144

4.5　可数集与不可数集 144

4.6　数学归纳法 146

4.6.1　归纳法证明 146

4.6.2　数学归纳法第一原理 146

4.6.3　数学归纳法第二原理 147

习题 149

5.1.1 图的定义和表示 153

5.1　图的基本概念 153

第5章 图论 153

5.1.2　图的同构 157

5.1.3　完全图与正则图 159

5.1.4　子图与补图 159

5.1.5　通路与回路 161

5.2　图的连通性 163

5.2.1　无向图的连通性 163

5.2.2　有向图的连通性 165

5.3　图的矩阵表示 165

5.3.1　关联矩阵 165

5.3.2　有向图的邻接矩阵 166

5.3.3　有向图的可达矩阵 168

5.4　二部图 168

5.4.1　二部图及判别定理 168

5.4.2　完备匹配 169

5.5　欧拉图 171

5.6　哈密顿图 174

5.7　平面图 177

5.7.1 平面图及其判定定理 177

5.7.2 平面图的对偶图 183

5.8　带权图 184

习题 185

第6章　树及其应用 193

6.1　树的术语和性质 193

6.1.1　树的定义及相关术语 193

6.1.2　树的性质 195

6.2　生成树 196

6.3　最小生成树 199

6.4　树的遍历 202

6.5.1　二叉树的性质 204

6.5　二叉树 204

6.5.2　二叉搜索树 205

6.5.3　赫夫曼树 206

6.6　决策树 207

6.6.1　决策树的定义 207

6.6.2　最短时间排序 209

6.7　树的同构 209

6.8　博弈树 213

6.8.1　博弈树的概念 213

6.8.2　极大极小分析法 213

6.8.3　α-β剪枝技术 216

习题 218

7.1　基本原理 222

7.1.1　加法原理 222

第7章　计数方法与鸽巢原理 222

7.1.2　乘法原理 223

7.2　排列与组合 224

7.2.1　排列 224

7.2.2　组合 224

7.3　排列组合生成算法 225

7.3.1　排列生成算法 225

7.3.2　组合生成算法 226

7.4　离散概率论 229

7.4.1　离散概率简介 229

7.4.2　有限概率 230

7.4.3　条件概率与独立性 232

7.4.4　Bayes定理 233

7.5 　广义的排列和组合 234

7.6.1　二项式定理 236

7.6　二项式系数和组合恒等式 236

7.6.2　组合恒等式 238

7.7　鸽巢原理 239

7.7.1　鸽巢原理的简单形式 239

7.7.2　鸽巢原理的一般形式 240

习题 241

第8章　数论与递归关系 243

8.1　素数 243

8.2　最大公约数与最小公倍数 244

8.3 同余 247

8.4　一次同余方程和中国剩余定理 249

8.4.1　一次同余方程 249

8.4.2 中国剩余定理 250

8.5　数论在密码学中的应用 251

8.5.1　公钥密码学 251

8.6.1　递归定义函数 252

8.5.2　RSA密码 252

8.6　递归关系简介 252

8.6.2　递归定义集合 254

8.6.3　递推关系模型 255

8.7　求解递归关系 257

8.8　递归在算法分析中的应用 259

习题 262

第9章　代数系统 264

9.1　二元运算及其性质 264

9.1.1　定义和表示 264

9.1.2　二元运算的性质 266

9.2　代数系统 268

9.2.1　定义和实例 268

9.2.3　代数系统的同态与同构 270

9.2.2　子代数系统 270

9.3.1　定义与性质 271

9.3　半群与独异点 271

9.3.2　子系统与直积 272

9.4　群 273

9.4.1　群的定义 273

9.4.2　群的性质 275

9.4.3　子群的定义 277

9.4.4　正规子群与商群 278

9.4.5　群的同态与同构实例 281

9.4.6　循环群与置换群 284

9.5　环与域 286

9.5.1 环 286

9.5.2　域 287

9.6.1　格 288

9.6　格与布尔代数 288

9.6.2　布尔代数 292

9.7　组合电路 295

习题 297

第10章 自动机、文法和语言 305

10.1 串和语言 305

10.2　形式文法 306

10.3　有限状态机 309

10.4　有限状态自动机 311

10.5　不确定有限状态自动机 314

10.6　语言和自动机之间的关系 317

习题 318

附录A　历史注记 322

参考文献 332