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

第一部分 数理逻辑 3

第1章 命题逻辑 3

1.1 命题及其表示 3

1.1.1 命题的基本概念 3

1.1.2 命题分类 4

1.1.3 命题标识符 4

1.2 逻辑联结词 5

1.2.1 否定联结词 5

1.2.2 合取联结词 5

1.2.3 析取联结词 6

1.2.4 条件联结词 7

1.2.5 双条件联结词 7

1.2.6 字位运算与布尔检索 8

1.3 命题公式与解释 9

1.3.1 命题公式 9

1.3.2 命题的符号化 10

1.4 真值表与等价公式 12

1.4.1 真值表 12

1.4.2 等价公式 13

1.5 命题公式的分类与蕴含式 17

1.5.1 命题公式的分类 17

1.5.2 重言式与矛盾式的性质 18

1.5.3 蕴含式 18

1.6 其他逻辑联结词和最小功能完备联结词组 21

1.6.1 其他逻辑联结词 21

1.6.2 最小功能完备联结词组 22

1.6.3 联结词的逻辑电路表示 23

1.7 对偶与范式 24

1.7.1 对偶式与对偶原理 24

1.7.2 命题公式的范式 26

1.7.3 命题公式的主析取范式和主合取范式 28

1.8 推理理论 37

1.8.1 直接证法 38

1.8.2 间接证法 40

习题一 42

实验一 真值表的程序计算 47

第2章 谓词逻辑 49

2.1 谓词的基本概念 49

2.1.1 个体和谓词 49

2.1.2 量词 51

2.2 谓词公式与符号化解释 52

2.2.1 谓词公式 52

2.2.2 谓词公式的符号化 53

2.3 变元的约束 54

2.3.1 约束变元和自由变元 54

2.3.2 换名规则 55

2.3.3 代替规则 56

2.4 谓词演算的等价式与蕴含式 56

2.4.1 谓词公式的赋值 56

2.4.2 谓词公式的分类 57

2.4.3 谓词演算的等价式 58

2.4.4 谓词演算的蕴含式 62

2.5 谓词公式范式 64

2.5.1 前束范式 64

2.5.2 斯柯林范式 65

2.6 谓词演算的推理理论 66

2.6.1 US规则（Universal Specification，全称指定规则） 66

2.6.2 UG规则（Universal Generalization，全称推广规则） 66

2.6.3 ES规则（Existential Specification，存在指定规则） 66

2.6.4 EG规则（Existential Generalization，存在推广规则） 67

习题二 71

实验二 命题逻辑简单推理系统 73

第3章 基于归结原理的推理证明 75

3.1 谓词公式与子句集 75

3.1.1 斯柯林（Skolem）标准范式 75

3.1.2 子句与子句集 76

3.1.3 不可满足意义下的一致性 76

3.1.4 P=P1∧P2∧…∧Pn的子句集 76

3.2 海伯伦（Herbrand）理论 77

3.2.1 H域 77

3.2.2 原子集 77

3.2.3 H域上的解释 77

3.3 归结原理（Resolution Method） 78

3.3.1 置换与合一 78

3.3.2 命题逻辑中的归结原理 79

3.3.3 一阶谓词逻辑中的归结原理 80

3.3.4 归结原理的完备性 81

3.3.5 利用归结原理进行定理证明 81

3.3.6 应用归结原理进行问题求解 81

3.4 归结过程的控制策略 83

3.4.1 引入控制策略 83

3.4.2 归结控制策略及其应用举例 83

习题三 84

实验三 归结原理的程序实现 85

第二部分 集合论 89

第4章 集合及其运算 89

4.1 集合的概念及其表示 89

4.1.1 集合的概念 89

4.1.2 集合与集合间的关系 90

4.1.3 幂集（Power Set） 91

4.2 集合的基本运算 91

4.2.1 集合的并（Union）运算 91

4.2.2 集合的交（Intersection）运算 92

4.2.3 集合的交运算与并运算之间的关系 93

4.2.4 集合的补（Substraction）运算 93

4.2.5 集合的对称差（Symmetric Difference）运算 94

4.2.6 集合的计算机表示 96

4.3 集合中元素的计数 97

4.3.1 两个基本原理 97

4.3.2 排列、组合 97

4.3.3 容斥原理 98

4.4 集合的应用 100

4.4.1 数据表的并（∪）运算 101

4.4.2 数据表的差（-）运算 101

4.4.3 数据表的交（∩）运算 101

习题四 102

实验四 集合的基本运算 104

第5章 二元关系 106

5.1 集合的笛卡儿积 106

5.1.1 序偶（Ordered Pair） 106

5.1.2 笛卡儿积（Cartesian Product） 107

5.2 二元关系 109

5.2.1 二元关系的基本概念 109

5.2.2 二元关系的表示 109

5.2.3 关系的运算 110

5.2.4 关系的性质 114

5.2.5 关系的闭包（Closure）运算 116

5.3 等价关系 122

5.3.1 集合的划分（Partion ofSet） 122

5.3.2 等价关系（Equivalent Relation）与等价类 124

5.4 相容关系 127

5.4.1 集合的覆盖（Covering） 127

5.4.2 相容关系（Consistent Relation）与相容类 127

5.5 偏序关系 130

5.5.1 偏序关系（Partial Relation）与偏序集的概念 130

5.5.2 偏序集的哈斯（Hasse）图 131

5.5.3 偏序集中的特殊元 132

5.5.4 全序关系（Complete Partial Relation）及其应用 134

5.6 关系的应用 135

5.6.1 等价关系在计算机中的应用 135

5.6.2 序关系在项目管理中的应用 136

习题五 137

实验五 求关系的闭包 140

第6章 函数 142

6.1 函数的概念 142

6.1.1 函数（Function）的概念 142

6.1.2 几类特殊函数 143

6.2 逆函数与复合函数 145

6.2.1 逆函数 145

6.2.2 复合函数 146

习题六 148

实验六 函数的图形可视化 150

第7章 集合的基数 151

7.1 集合的等势与优势 151

7.2 基数、可数集与不可数集 151

7.2.1 基数 152

7.2.2 可数集与不可数集 153

7.2.3 基数的比较 157

习题七 159

实验七 自然数性质的可视化表示 160

第三部分 代数结构 163

第8章 代数系统 163

8.1 代数系统的概念 163

8.2 代数系统的运算及其性质 165

8.3 半群、群与子群 170

8.4 同态与同构 175

8.5 交换群与循环群、置换群 182

8.5.1 交换群 182

8.5.2 循环群 183

8.5.3 置换群 184

8.6 子群与群的陪集分解 186

8.7 环与域 189

习题八 194

实验八 代数系统的基本运算 198

第9章 形式语言和自动机 200

9.1 语言 200

9.2 形式语言和文法 203

9.3 有限状态机 205

9.4 有限状态自动机 206

9.5 语言与自动机的关系 211

习题九 215

实验九 设计输出状态自动机实验 219

第10章 格与布尔代数 220

10.1 格的概念 220

10.2 分配格 228

10.3 有补格 232

10.4 布尔代数与布尔表达式 234

10.5 数字电路逻辑运算 243

习题十 246

实验十 代数系统综合课程设计 247

第四部分 图论 251

第11章 图的基本概念 251

11.1 图的概念 251

11.1.1 无向图和有向图 251

11.1.2 简单图、多重图和同构图 252

11.1.3 完全图和正则图 255

11.1.4 几种特殊的图 255

11.1.5 子图 257

11.1.6 图的操作 258

11.2 图的连通性 259

11.2.1 通路与回路 259

11.2.2 连通图 260

11.2.3 二部图 263

11.3 图的矩阵表示 264

11.3.1 关联矩阵 265

11.3.2 邻接矩阵 266

11.3.3 可达矩阵 268

11.4 图的运算 268

11.5 欧拉图 269

11.5.1 欧拉通路和回路 269

11.5.2 半欧拉图和欧拉图 270

11.6 哈密顿图 273

11.6.1 哈密顿图 274

11.6.2 哈密顿图的判断条件 275

11.7 带权图 278

11.8 平面图 278

11.8.1 平面图的基本概念及性质 278

11.8.2 库拉托夫斯基定理 280

11.8.3 平面图着色及应用 281

11.8.4 边着色 282

11.9 应用举例 284

11.9.1 中国邮路问题 284

11.9.2 冰箱分隔问题 286

11.9.3 排课表问题 287

习题十一 288

实验十一 应用邻接矩阵方法求解锁具装箱问题 292

第12章 树 294

12.1 树的概念及性质 294

12.1.1 树的定义 294

12.1.2 树的一些性质 294

12.2 最小生成树 295

12.2.1 生成树 295

12.2.2 最小代价生成树 297

12.3 根树 298

12.3.1 根树的定义 298

12.3.2 根树的分类 299

12.4 树的应用 300

12.4.1 决策树 300

12.4.2 博弈树 301

习题十二 302

实验十二 应用生成树算法求解旅行商问题 304

第13章 支配集、覆盖集、独立集与匹配理论 306

13.1 支配集、覆盖集、独立集概念 306

13.1.1 支配集 306

13.1.2 覆盖集 306

13.1.3 独立集 307

13.2 边覆盖集与匹配 308

13.3 二部图中的匹配 311

13.4 图论的综合应用举例＊＊ 312

13.4.1 会议议程安排问题 312

13.4.2 大中型工程项目的优化 315

习题十三 320

实验十三 程序求解支配集、独立集问题 322

《离散数学》常用符号表 323

参考文献 327