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

第1章基础知识 1

1.1集合与子集 1

1.1.1集合的概念和表示 1

目 录 1

1.1.2集合之间的关系 2

1.1.3集合的运算 3

1.1.4集合运算的代数性质 5

练习1.1 6

1.2 序列 7

1.2.1 序列 7

1.2.2 特征函数 8

1.2.3串和正则表达式 10

练习1.2 13

1.3.1 素数 14

1.3整数的除法 14

1.3.2最大公约数 15

1.3.3最小公倍数 17

练习1.3 18

1.4 矩阵 18

1.4.1矩阵和运算 18

1.4.2布尔矩阵的运算 21

练习1.4 23

1.5数学结构 24

练习1.5 28

要点回顾1 30

自测题1 31

2.1.1 命题 33

2.1.2逻辑联结词与复合命题 33

2.1命题和逻辑运算 33

第2章逻辑 33

2.1.3谓词和量词 35

练习2.1 37

2.2条件命题 38

2.2.1蕴涵联结词和等价联结词 38

2.2.2三类命题 40

2.2.3命题运算的性质 41

2.2.4逻辑的应用 43

练习2.2 44

2.3证明方法 46

2.3.1直接证明法 46

2.3.2间接证明法 48

2.3.3反证法 48

练习2.3 49

2.3.4证明过程 49

2.4数学归纳法 50

2.4.1数学归纳法 50

2.4.2强归纳法 53

练习2.4 53

要点回顾2 56

自测题2 57

第3章计数 58

3.1叠加原理 58

练习3.1 59

3.2排列 59

练习3.2 62

3.3组合 62

练习3.3 65

3.4鸽巢原理 65

练习3.4 66

3.5.1样本空间 67

3.5概率基础 67

3.5.2事件 68

3.5.3给事件赋概率 68

3.5.4等可能结果 70

练习3.5 71

3.6递归关系 73

练习3.6 76

要点回顾3 76

自测题3 77

第4章关系 79

4.1乘积集合 79

练习4.1 80

4.2关系和有向图 81

4.2.1 关系 81

4.2.2 由关系得到的集合 82

4.2.3关系的矩阵 84

4.2.4关系的有向图 84

练习4.2 86

4.3关系和有向图中的路径 87

练习4.3 90

4.4关系的性质 91

4.4.1 自反的关系和反自反的关系 91

4.4.2对称的、不对称的、反对称的关系 92

4.4.3传递关系 95

练习4.4 95

4.5等价关系 97

4.5.1等价关系 97

4.5.2等价关系和划分 98

练习4.5 99

4.6关系的计算机表示 100

4.6.1线性表的表示 101

4.6.2关系的表示 102

4.6.3关系的矩阵表示方法的计算量 103

4.6.4关系的链表表示方法的计算量 104

4.6.5检查传递性的计算量对比 105

练习4.6 105

4.7关系的运算 107

4.7.1关系的运算 107

4.7.2关系的运算的性质 108

4.7.3合成 110

练习4.7 112

4.8闭包 115

4.8.1闭包 115

4.8.2传递闭包的WARSHALL算法 117

练习4.8 120

要点回顾4 121

自测题4 123

第5章 函数 124

5.1 函数 124

5.1.1 函数定义 124

5.1.2特殊的函数 125

5.1.3 反函数 126

练习5.1 128

5.2计算机科学中的函数 130

练习5.2 132

5.3函数的增长 133

练习5.3 135

5.4排列函数 137

5.4.1排列和循环 137

5.4.2奇排列和偶排列 139

练习5.4 141

自测题5 143

要点回顾5 143

第6章序关系和结构 145

6.1偏序集合 145

6.1.1偏序集合 145

6.1.2哈斯图 147

6.1.3拓扑排序 149

6.1.4 同构 149

练习6.1 150

6.2偏序集合的极值元素 153

练习6.2 156

6.3 格 158

6.3.1 格 158

6.3.2 同构格 160

6.3.3格的性质 161

6.3.4特殊的格 162

练习6.3 164

6.4有限布尔代数 166

6.4.1一类特殊的格 166

6.4.2布尔代数 168

6.4.3布尔代数的性质 169

练习6.4 171

6.5布尔代数上的函数 172

练习6.5 175

6.6电路设计 176

练习6.6 182

要点回顾6 183

自测题6 185

第7章树 187

7.1树 187

练习7.1 189

7.2.1标记树 190

7.2标记树 190

7.2.2定位二元树的计算机表示 191

练习7.2 193

7.3树搜索 193

7.3.1搜索二元树 194

7.3.2搜索一般的树 197

练习7.3 198

7.4无向树 200

7.4.1无向树 200

7.4.2连通关系的生成树 201

练习7.4 205

7.5最小生成树 206

练习7.5 209

要点回顾7 210

自测题7 211

8.1.1图 213

第8章图论 213

8.1图 213

8.1.2子图和商图 215

练习8.1 216

8.2欧拉路径及回路 218

练习8.2 220

8.3哈密尔顿路径及回路 221

练习8.3 222

8.4运输网 223

8.4.1运输网 223

8.4.2流 224

8.4.3 最大流 224

8.4.4最大流算法 225

8.4.5扩展的运输网 230

8.4.6匹配问题 231

练习8.4 233

8.5 图着色 235

8.5.1 图着色 235

8.5.2颜色多项式 236

练习8.5 237

要点回顾8 238

自测题8 239

第9章半群和群 241

9.1二元运算回顾 241

9.1.1二元运算 241

9.1.2二元运算的表格 242

9.1.3二元运算的性质 243

练习9.1 244

9.2.1半群 246

9.2半群 246

9.2.2子半群 247

9.2.3同构映射和同态 247

练习9.2 250

9.3半群的积和商 252

练习9.3 255

9.4群 257

练习9.4 263

9.5群的积和商 265

练习9.5 267

要点回顾9 268

自测题9 269

10.1.1语言 271

10.1.2语法 271

10.1语言 271

第10章语言和有限状态机 271

练习10.1 275

10.2语法和语言的表示 276

10.2.1 BNF符号 276

10.2.2 句法图 278

10.2.3正则语法和正则表达式 281

练习10.2 282

10.3有限状态机 284

10.3.1有限状态机 284

10.3.2摩尔机器 285

10.3.3机器一致和商机器 286

练习10.3 288

10.4半群、机器和语言 291

练习10.4 294

10.5机器和正则语言 296

练习10.5 300

10.6机器简化 301

练习10.6 304

要点回顾10 306

自测题10 307

第11章群和编码 309

11.1二进制编码和错误检测 309

11.1.1编码函数 309

11.1.2群码 312

练习11.1 314

11.2解码和纠错 316

练习11.2 321

要点回顾11 323

自测题11 324

附录A符号表 325

附录B术语表 329