离散数学PDF电子书下载

第1章　命题逻辑 1

1.1　数理逻辑简介 1

1.1.1　从形式逻辑谈起 1

1.1.2　数理逻辑 1

1.1.3　数理逻辑与计算机科学的关系 2

1.1.4　命题逻辑 2

1.2　命题及命题符号化 3

1.2.1　命题的概念 3

1.2.2　逻辑联结词 4

1.3　命题公式及命题符号化 6

1.3.1　命题公式的定义 6

1.3.2　公式的解释 7

1.3.3　命题符号化 9

1.4　公式的等价 11

1.4.1　公式等价的基本概念 11

1.4.2　基本等价公式 13

1.4.3 等价演算 13

1.4.4　公式的类型 15

1.5.1　公式蕴涵的基本概念 17

1.5　公式的蕴涵 17

1.5.2　基本蕴涵式 18

1.5.3　蕴涵式A？B的证明 19

1.6　联结词完备集 20

1.6.1　其他联结词 20

1.6.2　联结词的数目 21

1.6.3　联结词完备集 22

1.7　公式的对偶 23

1.7.1　公式对偶的基本概念 23

1.7.2　对偶原理 24

1.8.1　简单合取式与简单析取式 25

1.8　公式的范式 25

1.8.2　公式的范式 26

1.9　公式的主范式 28

1.9.1　主析取范式 28

1.9.2　主合取范式 33

1.10　命题逻辑推理理论 36

1.10.1　有效结论和推理规则 36

1.10.2 由前提推导出结论的证明方法 37

习题 43

2.1　一阶逻辑简介 48

第2章　一阶逻辑 48

2.2　一阶逻辑的基本概念 49

2.2.1　个体词和个体域 49

2.2.2　谓词和函词 49

2.2.3　变元和常元 51

2.2.4　量词 52

2.3　一阶逻辑中命题的符号化 55

2.4　一阶逻辑公式及其解释 58

2.4.1　合式公式 58

2.4.2　合式公式的语义 62

2.5　一阶逻辑公式的等价与蕴含 66

2.5.1　逻辑等价 66

2.5.2　逻辑蕴含 70

2.6 自由变元与约束变元 71

2.6.1　量词的辖域 71

2.6.2 自由变元与约束变元 71

2.7　前束范式与Skolem标准形 72

2.7.1　前束范式 73

2.7.2 ？-前束范式和Skolem标准形 76

2.7.3　Skolem函词、Skolem常元和Skolem范式 78

2.8　一阶逻辑的推理理论 79

2.8.1　全称量词消去规则（UI规则） 79

2.8.2　全称量词引入规则（UG规则） 79

2.8.3　存在量词引入规则（EG规则） 80

2.8.4　存在量词消去规则（EI规则） 80

2.8.5　一阶逻辑推理举例 80

习题 83

第3章　模态命题逻辑 87

3.1　模态命题逻辑简介 87

3.2　模态命题语言 88

3.3　模态命题逻辑推理 89

3.4　模态命题逻辑公式 91

习题 94

第4章　模态一阶逻辑 96

4.1　模态一阶逻辑简介 96

4.2　模态一阶语言 97

4.2.1 MPTL的语言 97

4.2.2　MPTL的语义 98

4.3.2　带等词的一阶时序逻辑 100

4.3.1　时序命题演算 100

4.3　模态一阶逻辑推理 100

4.4　模态一阶逻辑公式 103

习题 104

第5章　集合的基本关系与运算 105

5.1　集合论简介 105

5.2　集合的基本概念 105

5.2.1　集合的描述性定义 105

5.2.2　集合的表示法 106

5.2.4　集合论的公理化简介 107

5.2.3　空集 107

5.2.5　韦恩图 109

5.3　集合的运算 109

5.3.1　集合的交与并 109

5.3.2　集合的差与对称差 110

5.3.3　集合等式的证明 111

5.4　集合的覆盖与划分 113

5.4.1　集合的覆盖 113

5.4.2　集合的划分 113

习题 114

6.2.1 函数的定义 117

6.2　函数的基本概念 117

第6章 函数 117

6.1 函数简介 117

6.2.2　特殊函数 119

6.2.3　函数的构造 121

6.3 函数的复合及逆函数 121

6.3.1　函数的复合 121

6.3.2　逆函数 124

6.4　特征函数和模糊集简介 125

6.4.1　特征函数 125

6.4.2　模糊集的概念及表示 127

6.4.3　模糊集的运算 128

6.4.4　λ截集和分解定理 129

6.5　集合的基数 131

6.5.1　集合的基数 131

6.5.2　基数的比较 131

6.5.3　集合运算后的基数 132

6.6　无限集合的性质 134

6.6.1　无限集合的性质 134

6.7.1　可数集合与不可数集合的基本概念 135

6.6.2　无限集合的基本运算 135

6.7　可数集合与不可数集合 135

6.7.2　连续统假设 137

6.8　函数的增长性 138

6.8.1　大O记号 138

6.8.2　大Ω记号和大θ记号 139

6.8.3　函数运算后的增长性 140

习题 140

7.2　关系的概念及表示法 144

7.2.1　序偶 144

7.1　关系简介 144

第7章　关系 144

7.2.2　笛卡儿积 145

7.2.3　关系的概念 147

7.2.4　关系的表示法 147

7.2.5　几种特殊关系 149

7.3　关系的运算 150

7.3.1　关系的逆与关系的复合 150

7.3.2　关系运算的矩阵表示 151

7.4　关系的性质 153

7.3.3　关系运算的关系图表示 153

7.4.1 自反性 154

7.4.2　反自反性 154

7.4.3　对称性 154

7.4.4　反对称性 155

7.4.5　传递性 156

7.5　关系的闭包 157

7.5.1　关系的自反闭包 157

7.5.2　关系的对称闭包 157

7.5.3　关系的传递闭包 158

7.5.4　关系闭包的矩阵和Warshall算法 159

7.6　等划关系与等价划分 161

7.6.1 等价关系与等价类 161

7.6.2　等价划分 162

7.7　偏序关系 164

7.7.1　偏序关系的概念 164

7.7.2　哈斯图 165

7.7.3　格 168

7.7.4　偏序关系的应用举例 169

7.8.1　相容关系和相容类 170

7.8　相容关系 170

7.8.2　相容关系的关系图和关系矩阵 171

7.8.3　最大相容类的存在性及求法 171

7.8.4　相容关系与覆盖 172

习题 173

第8章　离散概率 177

8.1　离散概率简介 177

8.2　排列与组合 178

8.2.1　加法法则和乘法法则 179

8.2.2　排列 181

8.2.3　组合 183

8.3　概率的基本概念及计算 186

8.3.1　实验与事件 186

8.3.2　概率的定义 187

8.3.3　事件的运算及其概率 188

8.3.4　条件概率与概率乘法定理 192

8.3.5　全概率公式与贝叶斯公式 194

8.4　离散型随机变量及其分布 196

8.4.1　概率分布 196

8.4.2　重要随机变量的分布 198

8.4.3　随机向量的概率分布 201

8.4.4　边缘分布 203

8.4.5　条件概率分布及随机变量的独立性 205

8.5　随机变量的函数 208

8.6　期望与方差 211

8.6.1　期望 211

8.6.2　方差 216

8.6.3　大数定理 222

习题 222

9.1　代数系统简介 226

第9章　代数系统 226

9.2　代数系统的概念 227

9.2.1　运算 227

9.2.2　运算的性质 229

9.2.3　代数系统 231

9.2.4　代数系统的特殊元素 232

9.2.5　利用运算表判断运算性质和特殊元素 235

9.2.6　积代数 238

9.3　代数系统的同态与同构 239

9.3.1　代数系统的同态与同构定义 239

9.3.2　满同态映射的性质 240

9.4 半群与子半群 241

9.4.1 半群 241

9.4.2　子半群 242

习题 243

第10章　群 246

10.1　群的概述 246

10.1.1　群的概念 246

10.1.2　元素的阶 249

10.2.2　对称群 250

10.2.1　循环群 250

10.2　循环群和对称群 250

10.3　子群与陪集 251

10.3.1　子群的概念及判别 251

10.3.2　陪集 253

10.3.3　正规子群 255

10.4　群在编码中的应用简介 255

10.4.1　编码函数 256

10.4.2　编码函数的查错纠错能力 257

10.4.3　群码 259

习题 263

第11章　环和域 265

11.1　环 265

11.1.1　环的概念 265

11.1.2　特殊的环 266

11.1.3　无零因子环的特征 267

11.2　域 268

习题 269

12.2.1　格的基本性质 270

12.2　格的性质 270

12.1　格的简介 270

第12章　格 270

12.2.2　格的代数系统定义 273

12.2.3　子格 274

12.2.4　格的同构 275

12.3　特殊格 276

12.3.1　分配格 276

12.3.2　有界格 278

12.3.3　有补格 279

12.4　布尔代数 280

12.3.4　有补分配格 280

12.4.1　布尔代数的性质 281

12.4.2　有限布尔代数的表示 282

12.5　布尔函数与布尔表达式 284

12.5.1　布尔函数 285

12.5.2　布尔函数的范式 286

习题 287

第13章 图的基本问题 289

13.1 图论简介 289

13.2.1 图论中的基本术语 290

13.2　图的基本概念 290

13.2.2 图的同构 294

13.2.3 图的运算 295

13.3　图的矩阵表示 296

13.3.1　邻接矩阵 297

13.3.2　关联矩阵 298

13.3.3 图的矩阵在同构判定中的作用 299

13.4　路与回路 300

13.4.1　路与回路的概念 300

13.4.2　路与回路的判别 301

13.4.3　路在同构判定中的作用 303

13.5　图的连通性 304

13.5.1　无向图的连通性 304

13.5.2　有向图的连通性 305

13.6　连通度 310

13.6.1　点连通度 310

13.6.2　边连通度 312

13.7.1　最短路问题的提出 315

13.7.2　最短路算法 315

13.7　最短路 315

13.8　拉姆赛问题简介 318

习题 319

第14章　树 323

14.1　树的简介 323

14.2　树的定义与性质 324

14.2.1　树的定义 324

14.2.2　树的性质 324

14.3　生成树 326

14.3.1　生成树的定义 326

14.3.2　回溯法和广度优先搜索法 329

14.4　最小生成树 331

14.5　根树 332

14.5.1　根树的定义及性质 332

14.5.2　有序树 334

14.5.3　子树 336

14.6　有序二元树的搜索 336

14.6.1　前序搜索 336

14.6.2 中序搜索 337

14.6.3　后序搜索 337

14.6.4　波兰记号和逆波兰记号 338

14.7 树的应用 341

14.7.1 哈夫曼树 341

14.7.2　前缀码 343

14.7.3　决策树 344

14.7.4　其他应用 345

习题 346

第15章　一些特殊的图 349

15.1 欧拉图 349

15.1.1　欧拉图及其判定 349

15.1.2　欧拉路与欧拉回路的简单应用 352

15.2　哈密顿图 354

15.2.1 哈密顿图的定义及判定 354

15.2.2　哈密顿图的应用 357

15.3　二分图 359

15.3.1　二分图的基本概念 359

15.3.2 匹配 361

15.4　平面图 363

15.4.1　平面图的概念 363

15.4.2　平面图的判别 364

15.4.3　极大平面图与极小非平面图 368

15.4.4　平面图的对偶图 369

15.5 图的着色 370

15.5.1　图着色的基本概念 370

15.5.2　颜色多项式 372

习题 374

附录A　与离散数学领域相关的一些著名数学家 378

附录B　术语索引 381

附录C　符号表 385

参考文献 387