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

第1章 集合论 1

1.1集合的概念 2

1.1.1集合 2

1.1.2集合的表示 3

1.1.3集合的包含关系 3

1.1.4特殊集合 4

1.2集合的运算 5

1.2.1交、并、补的运算 5

1.2.2交、并、补运算的性质 6

1.2.3其他运算及其性质 6

1.2.4利用集合的编码表示运算 9

1.3集合的归纳定义与归纳原理 9

1.3.1集合的归纳定义 9

1.3.2结构归纳原理 10

习题1 11

第2章 关系 15

2.1二元关系的概念 16

2.1.1笛卡儿积 16

2.1.2二元关系的概念 16

2.1.3二元关系的表示 17

2.2二元关系的性质 19

2.2.1二元关系的性质概述 19

2.2.2二元关系性质的判断方法 20

2.3二元关系的运算 22

2.3.1交、并、补的运算 22

2.3.2逆运算和复合运算 22

2.3.3投影、选择、联系运算 25

2.3.4闭包 26

2.4等价关系 29

2.4.1等价关系概述 29

2.4.2模m同余关系 31

2.4.3等价关系与划分 32

2.5相容关系 33

2.5.1相容关系概述 33

2.5.2极大相容类 33

2.5.3完全覆盖 34

2.6序关系 36

2.6.1偏序关系 36

2.6.2偏序集中具有特殊位置的元素 38

2.6.3其他几个序关系 39

2.7函数 41

2.7.1函数的概念 41

2.7.2特殊的函数 42

2.7.3函数的逆与复合 45

习题2 46

第3章 命题逻辑 50

3.1命题 51

3.1.1命题概述 51

3.1.2联结词 52

3.1.3命题公式 55

3.1.4真值函数 55

3.1.5全功能集 56

3.2等值演算与范式 57

3.2.1逻辑等价式与永真蕴含式 57

3.2.2范式 59

3.3逻辑推理 61

3.3.1推理的形式结构 61

3.3.2推理系统 62

3.3.3证明方法 63

3.4例题与分析 65

习题3 69

第4章 谓词逻辑 73

4.1谓词与量词 73

4.1.1个体词和谓词 74

4.1.2量词 75

4.2谓词逻辑公式及解释 75

4.3等价值蕴含式与前束范式 77

4.4谓词的逻辑推理理论 81

4.4.1全称量词消去规则（简称US规则） 81

4.4.2全称量词引入规则（简称UG规则） 81

4.4.3存在量词引入规则（简称EG规则） 81

4.4.4存在量词消去规则（简称ES规则） 82

习题4 83

第5章 计数 86

5.1计数的基本原理 87

5.1.1相等原则 87

5.1.2加法原则 87

5.1.3乘法原则 87

5.2排列 88

5.2.1 n元集的r一排列 88

5.2.2 n元集的r一可重复排列 89

5.2.3多重集的排列 90

5.3组合 91

5.3.1 n元素的r组合 91

5.3.2 n元集的r一可重复组合 92

5.3.3组合数的基本性质 94

5.4容斥原理 95

5.5递推关系 97

5.5.1递推关系的建立和迭代解法 97

5.5.2常系数线性齐次递推关系 97

5.5.3特征方程没有重根常系数线性齐次递推关系的解法 98

5.5.4特征方程有重根常系数线性齐次递推关系的解法 100

习题5 100

第6章 初等数论 103

6.1整除、最大公约数 103

6.1.1整除 103

6.1.2上、下取整函数 104

6.1.3最大公约数 105

6.1.4最小公倍数 107

6.2素数、算术基本定理 107

6.2.1素数 107

6.2.2算术基本定理 108

6.3同余 110

6.3.1同余的概念 110

6.3.2同余的性质 110

6.3.3同余类 111

6.4一次同余式 113

6.4.1一次同余式概述 113

6.4.2欧拉定理和费马小定理 115

6.5初等数论在计算机中的应用 116

习题6 118

第7章 图论基础知识 121

7.1图的基本概念 122

7.1.1图的定义 122

7.1.2顶点的度 123

7.1.3一些特殊的图 124

7.1.4图的同构 126

7.2路径、回路、连通性 126

7.2.1路径、回路 126

7.2.2无向图的连通性 127

7.2.3有向图的连通性 128

7.2.4连通性与等价关系 129

7.3图的矩阵表示 131

习题7 135

第8章 几种典型的图和图的应用 138

8.1无向树和生成树 139

8.2有向树及其应用 143

8.2.1有向树的概念 143

8.2.2根树转化成二元树 146

8.2.3最优树 147

8.2.4前缀码 147

8.2.5树的遍历 149

8.3欧拉图与哈密顿图 150

8.4平面图与图的着色 152

习题8 156

第9章 代数系统 159

9.1二元运算及性质 160

9.1.1二元运算 160

9.1.2运算的性质 161

9.1.3关于运算性质的例题 163

9.2代数系统 166

9.3同态、同构与同余 169

9.3.1同态与同构的定义 169

9.3.2代数系统中关于同态与同构的性质 171

9.3.3同态核 171

9.3.4同余关系 171

9.4子半群与子群 173

9.4.1子代数 173

9.4.2子半群 173

9.4.3子群 174

9.5循环群 175

9.5.1元素的周期 176

9.5.2循环群的概念 176

9.5.3循环群与循环子群的性质 177

9.6置换群 179

9.6.1置换群概述 179

9.6.2伯恩赛德定理 181

9.7环和域 182

9.7.1环 183

9.7.2整环、除环和域 185

习题9 190

第10章 格与布尔代数 194

10.1格 194

10.1.1偏序集中的格 194

10.1.2偏序集中与格有关的性质 195

10.1.3对偶原理 197

10.1.4格的代数性质 198

10.1.5子格与格同态 201

10.2格的分类 204

10.2.1有界格 204

10.2.2有补格 205

10.2.3分配格 205

10.2.4有补分配格 207

习题10 209

习题答案 212

附录A符号表 230

主要参考文献 233