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

第一章 集合论基础 1

1.1集合的基本概念 2

习题1.1 6

1.2关系 6

1.2.1关系的基本概念及其性质 6

1.2.2等价关系 11

1.2.3偏序关系 15

习题1.2 17

1.3映射 18

1.3.1集合的基数 19

1.3.2可数集合 20

1.3.3不可数集合 22

习题1.3 23

1.4集合在计算机科学中的应用 24

1.4.1关系在关系数据库中的应用 24

1.4.2关系代数与数据子语言 28

1.4.3等价关系在计算机中的应用 30

1.4.4序关系在项目管理中的应用 30

第二章 计数 32

2.1两个基本计数原理 33

2.1.1加法原理 33

2.1.2乘法原理 33

习题2.1 34

2.2排列与组合 34

2.2.1集合的排列数和组合数 34

2.2.2多重集的排列数和组合数 36

习题2.2 38

2.3二项式定理 38

2.3.1二项式定理 38

2.3.2二项式定理的推广 40

习题2.3 42

2.4容斥原理 42

2.4.1容斥原理 42

2.4.2容斥原理的应用 45

习题2.4 47

2.5鸽巢原理 48

2.5.1简单的鸽巢原理 48

2.5.2加强的鸽巢原理 49

习题2.5 51

第三章 古典数理逻辑 52

3.1命题逻辑 53

3.1.1命题与公式 53

3.1.2命题公式的等价关系和蕴涵关系 56

3.1.3范式 61

3.1.4命题逻辑在二值逻辑器件和语句逻辑中的应用 65

习题3.1 68

3.2谓词逻辑 69

3.2.1谓词逻辑的基本概念 69

3.2.2谓词公式 72

3.2.3谓词公式的等价关系和蕴涵关系 74

3.2.4范式 75

3.2.5谓词逻辑的应用 79

习题3.2 88

第四章 图与网络 91

4.1图 93

4.1.1图的基本概念 93

4.1.2权图Dijkstra算法 96

习题4.1 100

4.2树 100

4.2.1树及其等价命题 101

4.2.2最优树Kruskal算法 102

4.2.3求最优树的其他算法 104

习题4.2 107

4.3有向图 欧拉路 107

4.3.1有向图与有向树 107

4.3.2欧拉路 欧拉图 110

4.3.3无向图 无向图中的欧拉路 114

习题4.3 115

4.4哈密顿图 115

4.4.1哈密顿路 哈密顿图的必要条件 116

4.4.2哈密顿图的若干充分条件 117

习题4.4 122

4.5平面图 123

4.5.1平面图判定 库拉托夫斯基判定准则 123

4.5.2平面图的欧拉公式 124

4.5.3平面图的着色 127

习题4.5 129

4.6匹配 二部图 130

习题4.6 134

4.7 Konig无限性引理 135

习题4.7 137

4.8网络优化算法 138

4.8.1单源最短路径问题具体算法及实现和比较 138

4.8.2最大流问题具体算法及实现和比较 140

习题4.8 144

第五章 数论基础 145

5.1整除性 辗转相除 146

5.1.1整除及其性质 146

5.1.2辗转相除 148

习题5.1 151

5.2互质 质因数分解 152

5.2.1整数互质 152

5.2.2质数与合数 算术基本定理 153

习题5.2 155

5.3合同 一次同余式 156

5.3.1合同及其性质 157

5.3.2剩余类 一次同余式 158

习题5.3 160

5.4秦九韶定理 欧拉函数 161

5.4.1一次同余式组秦九韶定理 161

5.4.2一元高次同余式的化简 162

5.4.3剩余系遍历欧拉函数 164

习题5.4 167

5.5一元高次同余式 二次剩余 168

5.5.1一元高次同余式的解 168

5.5.2二次同余式 二次剩余 170

习题5.5 171

5.6数论在计算机通信安全中的应用 172

5.6.1密码系统 172

5.6.2恺撒密码 173

5.6.3 Vigenere密码 173

5.6.4希尔密码 174

5.6.5 RSA公钥系统 175

习题5.6 177

第六章群、环、域 178

6.1代数系统 179

习题6.1 181

6.2群的定义 181

6.2.1半群 181

6.2.2群 182

6.2.3群的性质 182

6.2.4置换群 184

习题6.2 187

6.3子群及其陪集 187

6.3.1子群的定义 187

6.3.2子群的判别条件 188

6.3.3循环群 189

6.3.4陪集 191

习题6.3 193

6.4群的同态及同构 193

6.4.1同态映射 193

6.4.2同构映射 194

6.4.3同态核 195

习题6.4 197

6.5环 197

6.5.1环的定义及性质 197

6.5.2环同态 200

习题6.5 204

6.6域的特征 素域 205

6.6.1域的特征 205

6.6.2素域 206

习题6.6 207

6.7多项式 208

6.7.1多项式的整除性 208

6.7.2多项式的根 211

6.7.3有理域上的多项式 214

6.7.4分圆多项式 216

习题6.7 219

6.8有限域 220

习题6.8 223

6.9群环域在计算机科学中的应用 223

6.9.1计数问题 223

6.9.2纠错码 228

6.9.3多项式编码方法及其实现 237

习题6.9 240

第七章 格与布尔代数 241

7.1引言 241

7.2格的定义 242

习题7.2 245

7.3格的性质 246

7.3.1对偶原理 246

7.3.2格的其他性质 248

7.3.3格的同态与同构 249

习题7.3 252

7.4几种特殊的格 253

7.4.1有界格 253

7.4.2有余格 254

7.4.3分配格 255

7.4.4模格 257

习题7.4 259

7.5布尔代数 260

7.5.1布尔代数的定义及其性质 260

7.5.2有限布尔代数的表示理论 265

7.5.3布尔代数的同态与同构 268

习题7.5 271

7.6布尔表达式的化简问题 272

习题7.6 282

7.7格与布尔代数在计算机科学中的应用 283

7.7.1开关电路函数 283

7.7.2逻辑门 285

7.7.3全加器的逻辑设计 285

第八章 语言和有限状态机 288

8.1语言和语法 288

8.1.1语法结构 290

8.1.2语法结构的类型 291

8.1.3演绎树 292

8.1.4巴克斯-诺尔形式 294

习题8.1 294

8.2带有输出的有限状态机 296

习题8.2 300

8.3没有输出的有限状态机 301

习题8.3 306

8.4语言识别 306

8.4.1正则集合 306

8.4.2克林定理 307

8.4.3其他几种类型的有限状态机 313

习题8.4 314

8.5图灵机 315

习题8.5 320

参考文献 322