离散数学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∧…∧n的子句集 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数据表的并（U）运算 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 of Set） 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

习题六 147

实验六 函数的图形可视化 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语言和文法 166

8.3有限状态机 168

8.4有限状态自动机 170

8.5语言与自动机的关系 174

习题八 178

实验八 设计输出状态自动机实验 182

第9章 代数系统 184

9.1代数系统的概念 184

9.2代数系统的运算及其性质 186

9.3群与子群 191

9.4同态与同构 196

9.5交换群与循环群、置换群 203

9.5.1交换群 203

9.5.2循环群 204

9.5.3置换群 205

9.6子群与群的陪集分解 207

9.7环与域 210

习题九 215

实验九代数系统的基本运算 219

第10章 格与布尔代数 221

10.1格的概念 221

10.2分配格 229

10.3有补格 233

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

10.5数字电路逻辑运算 244

习题十 247

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

第四部分 图论 252

第11章 图的基本概念 252

11.1图的概念 252

11.1.1无向图和有向图 252

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

11.1.3完全图和正则图 255

11.1.4几种特殊的图 256

11.1.5子图 257

11.1.6图的操作 258

11.2图的连通性 259

11.2.1通路与回路 259

11.2.2连通图 261

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.5.3哥尼斯堡七桥问题 273

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边着色 283

11.9应用举例 285

11.9.1中国邮路问题 285

11.9.2冰箱分隔问题 287

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博奕树 300

习题十二 301

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

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

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

13.1.1支配集 305

13.1.2覆盖集 305

13.1.3独立集 306

13.2边覆盖集与匹配 307

13.3二部图中的匹配 310

13.4图论的综合应用举例 311

13.4.1会议议程安排问题 311

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

习题十三 319

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

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

参考文献 326