离散数学PDF|Epub|txt|kindle电子书版本网盘下载

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