离散数学及算法PDF电子书下载

第一篇 计算机科学中的离散结构 2

第1章 命题逻辑 2

1.1引言 2

1.2命题及命题逻辑联结词 2

1.2.1命题 2

1.2.2逻辑联结词 3

1.3命题变元和合式的公式 8

1.4重言式（或永真式）和永真蕴涵式 10

1.4.1有关重言式的讨论 10

1.4.2重言式与恒等式 10

1.4.3永真蕴涵式的定义和常用永真蕴涵式 11

1.4.4代入规则和替换规则 13

1.5对偶原理 14

1.6范式和判定问题 17

1.6.1析取范式和合取范式 17

1.6.2主析取范式和主合取范式 19

1.7命题演算的推理理论 23

小结 28

第2章 谓词逻辑 29

2.1谓词演算 29

2.1.1谓词和个体 29

2.1.2量词 30

2.1.3合式公式 32

2.1.4自由变元和约束变元 32

2.1.5谓词公式的解释 33

2.1.6含有量词的等价式和永真蕴涵式 33

2.2谓词逻辑中的推理理论 36

2.2.1谓词公式的翻译 36

2.2.2推理规则 38

2.3谓词公式的范式 44

2.3.1前束范式 44

2.3.2斯柯林范式 45

小结 47

第3章 集合论 48

3.1集合的概念及其表示 48

3.2集合的运算 51

3.3集合定律 58

3.4包含排斥原理 60

3.5多重序元与笛卡儿乘积 63

3.5.1序偶和多重序元 64

3.5.2笛卡儿乘积 64

小结 66

第4章 二元关系 67

4.1关系的基本概念 67

4.2关系的性质 68

4.3关系的表示 70

4.4关系的运算 72

4.4.1关系的合成 73

4.4.2合成关系的矩阵表达和图解 76

4.4.3关系的求逆运算 79

4.4.4关系的闭包运算 82

4.5特殊关系 87

4.5.1集合的划分和覆盖 87

4.5.2等价关系 89

4.5.3相容关系 93

4.5.4次序关系 98

4.5.5偏序集合与哈斯图 100

小结 104

第5章 函数 105

5.1函数的基本概念和性质 105

5.2函数的合成与合成函数的性质 108

5.3特殊函数 111

5.4反函数 114

5.5特征函数 116

5.6基数 118

小结 122

第6章 代数系统 123

6.1二元运算及其性质 123

6.1.1运算的概念 123

6.1.2二元运算的性质 124

6.2代数系统的概念 129

6.2.1代数系统的基本概念 129

6.2.2子代数系统 130

6.3同态与同构 131

6.4同余关系和商代数 138

6.4.1同余关系 138

6.4.2商代数 139

6.5积代数 142

6.6特殊代数系统——半群与群 143

6.6.1半群 143

6.6.2群的概念与性质 145

6.6.3子群与陪集 148

6.6.4循环群和置换群 152

6.7特殊代数系统——环与域 156

6.8特殊代数系统——格与布尔代数 157

小结 160

第7章 图论 161

7.1图的基本概念 161

7.2子图和图的运算 165

7.3路径、回路和连通性 168

7.4图的矩阵表示 174

7.4.1邻接矩阵 174

7.4.2可达性矩阵 178

7.5欧拉图 182

7.6特殊图 184

7.6.1二部图 184

7.6.2平面图 187

7.7树 192

7.8网络 205

7.8.1网络流与最大流 205

7.8.2割集 207

7.8.3标号法 209

7.8.4开关网络 211

小结 219

第二篇 离散数学中的算法 222

第8章 数理逻辑中的算法 222

8.1逻辑联结词的定义方法 222

8.2合式公式的表示方法 224

8.3构造合式公式的真值表 225

第9章 集合论中的算法 227

9.1求并集 227

9.2求交集 228

9.3求差集 229

9.4求笛卡儿乘积 231

第10章 关系中的算法 233

10.1判断关系R是否为自反关系及对称关系 233

10.2判断关系R是否为可传递关系 234

10.3判断关系R是否为等价关系 236

10.4求等价类 236

10.5求极大相容类 237

10.6关系的合成运算 238

10.7关系的闭包运算（1） 239

10.8关系的闭包运算（2） 241

10.9m个字符串按字典顺序分类算法 242

第11章 函数中的算法 244

第12章 代数系统中的算法 246

12.1判断是否为代数系统的算法 246

12.2判断是否为同余关系的算法 247

12.3判断是否为群的算法 249

第13章 图论中的算法 252

13.1道路矩阵的Warshall算法 252

13.2二叉树的遍历 253

13.3构造最优二叉树算法 256

13.4最小生成树的Kruskal算法 258

13.5求最短距离的Dijkstra算法 260

13.6判别连通性的算法 265

附录A考研例题解析 269

附录B离散数学名词中英文对照表 279

参考文献 283