离散数学 第3版PDF电子书下载

第一篇 数理逻辑 5

第一章 命题逻辑 5

1.1命题和联结词 5

1.2公式和真值赋值 8

1.3等值演算 12

1.4对偶定理 15

1.5联结词的完全集 16

1.6范式 19

1.7逻辑推论 22

习题一 23

第二章 谓词逻辑 29

2.1谓词和量词 29

2.2项和公式 33

2.3解释和赋值 36

2.4永真式 42

2.5等值演算 45

2.6逻辑推论 49

习题二 50

第三章 公理系统 54

3.1命题逻辑的公理系统 54

3.2谓词逻辑的公理系统 59

习题三 63

第四章 归结法原理 65

4.1命题逻辑的归结法 65

4.2前束范式与斯科伦范式 69

4.3谓词逻辑的归结法 71

习题四 81

参考文献 83

第二篇 集 合论 87

第五章 集合的基本概念及其运算 87

5.1集合与元素 87

5.2集合间的相等和包含关系 89

5.3幂集 91

5.4集合的运算 92

5.5有穷集的计数原理 99

5.6集合的归纳定义法 101

5.7有序偶和笛卡儿乘积 105

习题五 106

第六章 关系 110

6.1关系及其性质 110

6.2关系的运算 113

6.3次序关系 119

6.4等价关系、划分及其他 123

习题六 127

第七章 函数 131

7.1基本概念 131

7.2函数的复合 135

7.3特殊性质的函数 138

7.4集合的特征函数 142

习题七 143

第八章 自然数和基数 146

8.1自然数及数学归纳法 146

8.2基数 149

习题八 155

参考文献 156

第三篇 图论 159

第九章 基本概念 159

9.1有向图及无向图 159

9.2图的基本结构 161

9.3子图 163

9.4连通性 166

9.5顶点基和强分图 171

习题九 174

第十章 通路问题 177

10.1最短通路 177

10.2关键通路 180

习题十 183

第十一章 图的矩阵表示 184

11.1邻接矩阵 184

11.2有向图的可达性矩阵 186

11.3关联矩阵 189

习题十一 190

第十二章树 192

12.1树的一般定义 192

12.2根树与有序树 194

12.3二元树 195

12.4生成树 199

12.5割集 202

习题十二 203

第十三章 穿程问题 206

13.1欧拉图 206

13.2哈密顿图 209

习题十三 211

第十四章 二分图的匹配问题 213

14.1基本概念 213

14.2二分图的最大匹配 215

14.3从X到Y的匹配 217

习题十四 219

第十五章 平面图及色数 220

15.1平面图 220

15.2色数 225

习题十五 228

参考文献 230

第四篇 代数系统 233

第十六章 基本概念 233

16.1代数系统 233

16.2同态和同构 236

16.3子代数和商代数 237

习题十六 240

第十七章 半群和群 241

17.1半群的概念 241

17.2子半群和半群同态 242

17.3商半群和半群直积 243

17.4群的概念 245

17.5子群和群的同态 247

17.6变换群、置换群和循环群 249

17.7不变子群和商群 250

习题十七 254

第十八章 环和域 256

18.1环和域的概念 256

18.2子环和环的同态 258

18.3理想和商环 259

习题十八 261

第十九章 格和布尔代数 262

19.1格的定义与基本性质 262

19.2子格和格的同态 264

19.3布尔代数 264

19.4布尔代数的表示 266

习题十九 268

第二十章 抽象数据类型的代数规范 270

20.1标记、项和代数规范 270

20.2 Σ-代数和范畴 275

20.3代数规范的初始语义 277

习题二十 278

参考文献 280

第五篇 有限自动机理论 283

第二十一章 基本概念 283

21.1字符表、字符串及其集合的运算 283

21.2有限自动机的定义 284

21.3有限自动机的等价 288

21.4 Mealy机与Moore机 290

习题二十一 292

第二十二章 有限自动机的简化 294

22.1最小有限自动机的定义及性质 294

22.2状态集的S划分和格LM 296

22.3有限自动机的最小化 302

习题二十二 309

第二十三章 有限自动机和正则表达式 311

23.1有限自动机的识别功能 311

23.2非确定有限自动机 313

23.3正则表达式 316

23.4由正则表达式构造FA的算法 318

23.5有限自动机和正则表达式的等价性 324

23.6正则集合及其性质 327

习题二十三 329

第二十四章 有限自动机的综合与应用 331

24.1有限自动机的综合 331

24.2 FA理论在算法设计中的应用 334

24.3 FA理论与形式语言理论的关系 339

习题二十四 342

参考文献 344

名词索引 345