离散数学【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

离散数学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