离散数学及其应用 第2版PDF电子书下载

第1篇 预备知识 2

引言 2

第1章 集合论 3

1.0内容提要 3

1.1学习要求 3

1.2集合 4

1.2.1集合的表示 5

1.2.2集合与元素的关系 6

1.2.3集合与集合的关系 7

1.2.4几个特殊的集合 9

1.2.5集合的运算 10

1.2.6集合的难点 13

1.3无限集 13

1.3.1可数集合和不可数集合 13

1.3.2无限集的难点 16

1.4集合的应用 16

1.5本章总结 19

1.6习题 20

第2章 计数问题 24

2.0内容提要 24

2.1学习要求 24

2.2基本原理 25

2.2.1乘法原理 25

2.2.2加法原理 26

2.2.3基本原理的难点 27

2.3排列与组合 27

2.3.1排列问题 27

2.3.2组合问题 30

2.3.3排列与组合的难点 31

2.4容斥原理与鸽笼原理 31

2.4.1容斥原理 31

2.4.2鸽笼原理 34

2.4.3容斥原理与鸽笼原理的难点 35

2.5本章总结 35

2.6习题 36

第2篇 数理逻辑 40

引言 40

第3章 命题逻辑 42

3.0内容提要 42

3.1学习要求 42

3.2命题与命题联结词 43

3.2.1命题 43

3.2.2命题联结词 44

3.2.3联结词的难点 50

3.2.4命题联结词的应用 51

3.3命题公式、解释与真值表 54

3.3.1命题公式 55

3.3.2命题公式的解释与真值表 56

3.3.3命题公式的分类 58

3.3.4命题公式的基本等价关系 60

3.3.5命题公式的难点 64

3.3.6命题公式的应用 64

3.4联结词的完备集 67

3.4.1命题联结词的种数 67

3.4.2联结词的完备集 69

3.4.3联结词的完备集的应用 70

3.5公式的标准型——范式 72

3.5.1析取范式和合取范式 72

3.5.2主析取范式和主合取范式 74

3.5.3范式的难点 81

3.5.4范式的应用 81

3.6命题逻辑的推理理论 83

3.6.1推理的基本概念和推理形式 83

3.6.2判断有效结论的常用方法 84

3.6.3命题逻辑推理的难点 90

3.6.4命题逻辑推理的应用 91

3.7本章总结 93

3.8习题 95

第4章 谓词逻辑 99

4.0内容提要 100

4.1学习要求 100

4.2谓词逻辑中的基本概念与表示 100

4.2.1谓词 101

4.2.2量词 103

4.2.3谓词的语言翻译 106

4.2.4谓词翻译的难点 107

4.2.5谓词翻译的应用 108

4.3谓词合式公式与解释 109

4.3.1谓词的合式公式 109

4.3.2自由变元和约束变元 110

4.3.3谓词合式公式的解释 112

4.3.4谓词合式公式的分类 114

4.3.5谓词合式公式的基本等价关系 115

4.3.6谓词合式公式的难点 117

4.3.7谓词合式公式的应用 117

4.4公式的标准型——范式 118

4.4.1前束范式 118

4.4.2 Skolem标准型 119

4.4.3范式的难点 120

4.5谓词逻辑的推理理论 120

4.5.1谓词演算的演绎与推理 120

4.5.2谓词演算的综合推理方法 123

4.5.3谓词逻辑推理的难点 127

4.5.4谓词逻辑推理的应用 127

4.6本章总结 132

4.7习题 134

第5章 证明技术 138

5.0内容提要 138

5.1学习要求 139

5.2证明定理的方法 139

5.2.1基本证明技术 139

5.2.2几种典型的证明技术 141

5.2.3带量词的证明技术 143

5.2.4证明中的错误 145

5.3数学归纳法 146

5.3.1数学归纳法 147

5.3.2强形式数学归纳法 150

5.3.3数学归纳法的应用 151

5.4按定义证明方法 154

5.4.1按定义证明方法 154

5.4.2按定义证明方法的应用实例 155

5.5本章总结 156

5.6习题 156

第3篇 二五关系 160

引言 160

第6章 二元关系 161

6.0内容提要 161

6.1学习要求 161

6.2二元关系 162

6.2.1序偶和笛卡儿积 162

6.2.2关系的定义 165

6.2.3关系的表示法 167

6.2.4二元关系的难点 171

6.2.5关系的应用 172

6.3关系的运算 173

6.3.1关系的复合运算 174

6.3.2关系的逆运算 178

6.3.3关系的幂运算 181

6.3.4关系运算的难点 183

6.3.5关系运算的应用 183

6.4关系的性质 184

6.4.1关系性质的定义 184

6.4.2关系性质的判定定理 192

6.4.3关系性质的保守性 193

6.4.4关系性质的难点 195

6.4.5关系性质的应用 195

6.5关系的闭包运算 195

6.5.1关系的闭包 195

6.5.2关系闭包的难点 200

6.5.3关系闭包的应用 200

6.6本章总结 201

6.7习题 202

第7章 特殊关系 207

7.0内容提要 207

7.1学习要求 207

7.2等价关系 208

7.2.1等价关系 208

7.2.2集合的划分 210

7.2.3等价类与商集 211

7.2.4等价关系与划分 213

7.2.5等价关系的难点 216

7.2.6等价关系的应用 217

7.3次序关系 218

7.3.1拟序关系 218

7.3.2偏序关系 219

7.3.3全序关系 225

7.3.4良序关系 226

7.3.5次序关系的难点 227

7.3.6次序关系的应用 227

7.4本章总结 229

7.5习题 230

第8章 函数 233

8.0内容提要 233

8.1学习要求 233

8.2函数 234

8.2.1函数的定义 234

8.2.2函数的类型 236

8.2.3常用函数 239

8.2.4函数的难点 240

8.2.5函数的应用 240

8.3函数的运算 242

8.3.1函数的复合运算 242

8.3.2函数的逆运算 244

8.3.3函数运算的难点 245

8.3.4函数运算的应用 245

8.4置换函数 247

8.4.1基本概念 247

8.4.2置换函数的难点 248

8.4.3置换函数的应用 248

8.5本章总结 249

8.6习题 250

第4篇 图论 254

引言 254

第9章 图 256

9.0内容提要 256

9.1学习要求 256

9.2图的基本概念 257

9.2.1图的定义 257

9.2.2图的表示 258

9.2.3邻接点与邻接边 260

9.2.4图的分类 261

9.2.5图的操作 263

9.2.6子图与补图 264

9.2.7结点的度数与握手定理 267

9.2.8图的同构 270

9.2.9图的难点 271

9.2.10图的应用 271

9.3通路、回路与连通性 272

9.3.1通路与回路 273

9.3.2无向图的连通性 280

9.3.3有向图的连通性 282

9.3.4通路、回路与连通性的难点 286

9.3.5通路、回路与连通性的应用 286

9.4本章总结 289

9.5习题 290

第10章 树 294

10.0内容提要 294

10.1学习要求 294

10.2树 295

10.2.1树的定义与性质 295

10.2.2生成树 297

10.2.3最小生成树 300

10.2.4无向树的难点 302

10.2.5无向树的应用 303

10.3根树 303

10.3.1根树的定义与分类 303

10.3.2根树的遍历 307

10.3.3最优树与赫夫曼算法 309

10.3.4根树的难点 311

10.3.5根树的应用 312

10.4本章总结 317

10.5习题 318

第11章 特殊图 320

11.0内容提要 320

11.1 学习要求 320

11.2欧拉图 321

11.2.1欧拉图的引入与定义 321

11.2.2欧拉图的判定 322

11.2.3欧拉图的难点 324

11.2.4欧拉图的应用 324

11.3哈密顿图 326

11.3.1哈密顿的引入与定义 326

11.3.2哈密顿图的判定 328

11.3.3哈密顿图的难点 332

11.3.4哈密顿图的应用 332

11.4偶图 337

11.4.1偶图的定义 337

11.4.2偶图的判定 337

11.4.3匹配 338

11.4.4偶图的难点 339

11.4.5偶图的应用 340

11.5平面图 341

11.5.1平面图的定义 341

11.5.2平面图的简单判定方法——观察法 342

11.5.3欧拉公式 343

11.5.4库拉托夫斯基定理 346

11.5.5对偶图 347

11.5.6图的着色 348

11.5.7平面图的难点 351

11.5.8平面图的应用 351

11.6本章总结 353

11.7习题 354

第5篇 代数系统 360

引言 360

第12章 代数系统 361

12.0内容提要 361

12.1学习要求 361

12.2代数系统 362

12.2.1代数运算 362

12.2.2代数系统与子代数 365

12.2.3代数系统的难点 366

12.2.4代数系统的应用 366

12.3代数系统的基本运算和性质 367

12.3.1二元运算律 367

12.3.2代数系统的性质 373

12.3.3代数系统性质的难点 381

12.3.4代数系统性质的应用 381

12.4同态与同构 382

12.4.1同态与同构 383

12.4.2同态的性质 385

12.4.3同态与同构的难点 387

12.4.4同态与同构的应用 387

12.5本章总结 389

12.6习题 390

第13章 群 392

13.0内容提要 392

13.1 学习要求 392

13.2半群与含么半群 393

13.2.1半群与含么半群 393

13.2.2元素的幂 395

13.2.3循环半群 396

13.2.4半群与含么半群的难点 398

13.2.5半群的应用 398

13.3群及其性质 399

13.3.1群的定义及基本性质 401

13.3.2元素的周期 403

13.3.3子群 407

13.3.4群的同态 413

13.3.5群及子群的难点 414

13.3.6群的应用 414

13.4特殊群 416

13.4.1交换群（阿贝尔群） 416

13.4.2循环群 417

13.4.3置换群 420

13.4.4特殊群的难点 421

13.4.5特殊群的应用 421

13.5陪集与拉格朗日定理 423

13.5.1陪集 423

13.5.2拉格朗日定理 426

13.5.3陪集与拉格朗日定理的难点 427

13.5.4拉格朗日定理的应用 427

13.6正规子群与商群 428

13.6.1正规子群（不变子群） 428

13.6.2商群 430

13.6.3正规子群与商群的难点 433

13.6.4商群的应用 433

13.7本章总结 434

13.8习题 435

第14章 环与域 438

14.0内容提要 438

14.1学习要求 438

14.2环与域 439

14.2.1环与域的定义 439

14.2.2环与域的性质 441

14.2.3环与域的应用 443

14.3本章总结 443

14.4习题 444

第15章 格与布尔代数 445

15.0内容提要 445

15.1学习要求 446

15.2格 446

15.2.1偏序格 446

15.2.2代数格 448

15.2.3偏序格与代数格的等价性 449

15.2.4格的性质 451

15.2.5子格与格同态 452

15.2.6分配格与模格 455

15.2.7有界格与有补格 458

15.2.8格的难点 460

15.2.9格的应用 461

15.3布尔代数 461

15.3.1布尔代数 461

15.3.2布尔表达式 464

15.3.3布尔代数的难点 467

15.3.4布尔代数的应用 467

15.4本章总结 472

15.5习题 472

参考文献 475