离散数学教程PDF电子书下载

第一章 集合 1

1.1 预备知识 1

1.2 集合的概念及集合之间的关系 7

1.3 集合的运算 10

1.4 基本的集合恒等式 13

1.5 集合列的极限 17

习题一 20

第二章 二元关系 23

2.1 有序对与卡氏积 23

2.2 二元关系 26

2.3 关系矩阵和关系图 32

2.4 关系的性质 34

2.5 二元关系的幂运算 37

2.6 关系的闭包 39

2.7 等价关系和划分 45

2.8 序关系 49

习题二 53

第三章 函数 58

3.1 函数的基本概念 58

3.2 函数的性质 59

3.3 函数的合成 62

3.4 反函数 64

习题三 68

4.1 自然数的定义 70

第四章 自然数 70

4.2 传递集合 74

4.3 自然数的运算 76

4.4 N上的序关系 78

习题四 80

第五章 基数（势） 81

5.1 集合的等势 81

5.2 有穷集合与无穷集合 83

5.3 基数 84

5.4 基数的比较 85

5.5 基数运算 89

习题五 93

6.1 关于序关系的进一步讨论 95

第六章 序数 95

6.2 超限递归定理 97

6.3 序数 99

6.4 关于基数的进一步讨论 105

习题六 105

第七章 图 107

7.1 图的基本概念 107

7.2 通路与回路 119

7.3 无向图的连通性 121

7.4 无向图的连通度 123

7.5 有向图的连通性 129

习题七 130

8.1 欧拉图 132

第八章 欧拉图与哈密顿图 132

8.2 哈密顿图 137

习题八 142

第九章 树 144

9.1 无向树的定义及性质 144

9.2 生成树 146

9.3 环路空间 147

9.4 断集空间 151

9.5 根树 153

习题九 154

10.1 关联矩阵 156

第十章 图的矩阵表示 156

10.2 邻接矩阵与相邻矩阵 159

习题十 163

第十一章 平面图 165

11.1 平面图的基本概念 165

11.2 欧拉公式 168

11.3 平面图的判断 170

11.4 平面图的对偶图 172

11.5 外平面图 175

11.6 平面图与哈密顿图 177

习题十一 179

12.1 点着色 180

第十二章 图的着色 180

12.2 色多项式 181

12.3 地图的着色与平面图的点着色 185

12.4 边着色 187

习题十二 189

第十三章 支配集、覆盖集、独立集与匹配 190

13.1 支配集、点覆盖集、点独立集 190

13.2 边覆盖集与匹配 193

13.3 二部图中的匹配 198

习题十三 199

第十四章 带权图及其应用 201

14.2 关键路径问题 204

14.1 取短路径问题 204

14.3 中国邮递员问题 206

14.4 最小生成树 208

14.5 最优树 213

14.6 货郎担问题 216

习题十四 220

15.3 代数系统的同态与同构 220

第十五章 代数系统 222

15.1 二元运算及其性质 222

15.2 代数系统、子代数和积代数 227

15.4 同余关系和商代数 233

15.5 Σ代数 236

习题十五 237

第十六章 半群与独异点 240

16.1 关群与独异点 240

16.2 有穷自动机 242

习题十六 247

第十七章 群 249

17.1 群的定义和性质 249

17.2 子群 253

17.3 循环群 255

17.4 变换群与置换群 257

17.5 群的分解 263

17.6 正规子群和商群 269

17.7 群的同态与同构 272

17.8 群的直积 278

习题十七 281

第十八章 环与域 285

18.1 环的定义与性质 285

18.2 子环、理想、商环和环同态 289

18.3 有限域上的多项式环 294

习题十八 296

第十九章 格与布尔代数 299

19.1 格的定义和性质 299

19.2 子格、格同态的格的直积 303

19.3 模格、分配格和有补格 307

19.4 布尔代数 311

习题十九 318

第二十章 组合存在性定理 322

20.1 鸽巢原理和Ramsey定理 322

20.2 相异代表系 331

习题二十 335

第二十一章 基本的计数公式 337

21.1 两个计数原则 337

21.2 排列和组合 338

21.3 二项式定理与组合恒等式 343

21.4 多项式定理 347

习题二十一 349

22.1 递推方程的公式解法 352

第二十二章 组合计数方法 352

22.2 递推方程的其他解法 361

22.3 生成函数的定义和性质 370

22.4 生成函数与组合计数 375

22.5 指数生成函数与多重集的排列问题 384

22.6 Catalan数与Stirling数 388

习题二十二 394

第二十三章 组合计数定理 398

23.1 包含排斥原理 398

23.2 对称筛公式及应用 403

23.3 Burnside引理 410

23.4 Polya定理 414

习题二十三 420

第二十四章 组合设计与编码 422

24.1 拉丁方 422

24.2 t-设计 427

24.3 编码 436

24.4 编码与设计 446

习题二十四 449

第二十五章 组合最优化问题 450

25.1 组合优化问题的一般概念 450

25.2 网络的最大流问题 452

习题二十五 457

26.1 形式系统 458

第二十六章 命题逻辑 458

26.2 命题和联结词 462

26.3 命题形式和真值表 465

26.4 联结词的完全集 468

26.5 推理形式 472

26.6 命题演算的自然推理形式系统N 474

26.7 命题演算形式系统P 487

26.8 N与P的等价性 494

26.9 赋值 496

26.10 可靠性、和谐性与完备性 506

习题二十六 508

第二十七章 一阶谓词演算 511

27.1 一阶谓词演算的符号化 511

27.2 一阶语言 515

27.3 一阶谓词演算的自然推演形式系统N 519

27.4 一阶谓词演算的形式系统K 530

27.5 N和K的等价性 534

27.6 K的解释与赋值 536

27.7 K的可靠性与和谐性 547

27.8 K的完全性 551

习题二十七 558

第二十八章 消解原理 562

28.1 命题公式的消解 562

28.2 Herbrand定理 567

28.3 代换与合一代换 572

28.4 一阶谓词公式的消解 576

第二十九章 直觉主义逻辑 583

29.1 直觉主义逻辑的直观介绍 583

习题二十八 584

29.2 直觉主义的一阶谓词演算的自然推演形式系统 585

29.3 直觉主义一阶谓词演算形式系统IK 594

29.4 直觉主义逻辑的克里普克（Kripke）语义 597

29.5 直觉主义逻辑的完备性 602

习题二十九 607

附录1 第一编与第二编符号注释与术语索引 608

附录2 第三编与第四编符号注释与术语索引 614

附录3 第五编符号注释与术语索引 620

参考书目和文献 624