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

第0章 整数的整除与同余 1

0.1整除及带余除法 1

0.1.1整数 1

0.1.2整除的概念与性质 2

0.1.3带余除法 3

0.1.4整数的进制表示法 4

0.1.5数学归纳法 7

0.2整数分解 8

0.2.1最大公因数及其性质 8

0.2.2欧几里得算法 10

0.2.3因式分解法 11

0.3同余 15

0.3.1同余的概念和性质 15

0.3.2线性同余方程 18

0.3.3中国剩余定理 20

0.3.4威尔逊定理、欧拉定理与费马小定理 22

习题 25

第1篇 集合论 27

第1章 集合及其运算 29

1.1集合的基本概念 29

1.1.1集合和元素 29

1.1.2集合的表示方法 30

1.1.3集合的基数 31

1.2集合间的关系 31

1.2.1集合的包含 31

1.2.2集合的相等 32

1.2.3维恩图 32

1.2.4幂集 33

1.2.5有限集合幂集元素的编码表示 34

1.3集合的运算和运算定律 34

1.3.1集合的运算 34

1.3.2集合运算的定律 35

1.3.3集合恒等式的证明方法 37

1.3.4包含排斥原理 39

1.4集合成员表 40

1.4.1并、交和补集的成员表 40

1.4.2有限个集合产生的集合的成员表 40

1.4.3利用集合成员表证明集合恒等式 41

1.5集合的覆盖与分划 42

1.6集合的标准形式 43

1.6.1最小集标准形式 43

1.6.2最大集标准形式 46

1.6.3集合范式的说明 47

1.7多重集合 49

习题 49

第2章 关系 54

2.1笛卡儿积与关系 54

2.1.1笛卡儿积 54

2.1.2关系的基本概念 56

2.2关系的表示方法 57

2.2.1集合表示法 57

2.2.2矩阵表示法 58

2.2.3关系图表示法 58

2.3关系的运算 59

2.3.1关系的并、交、差、补运算 59

2.3.2关系的逆运算 60

2.3.3关系的复合运算 61

2.4关系的性质 66

2.4.1关系性质的定义 66

2.4.2关系性质的判别 67

2.5关系的闭包 70

2.5.1关系闭包的定义 70

2.5.2关系闭包的性质 72

2.5.3关系闭包的求法 74

2.6等价关系 77

2.6.1等价关系的基本概念 77

2.6.2等价类的性质 78

2.6.3等价关系与分划 79

2.6.4等价关系的其他性质 80

2.7相容关系 81

2.7.1相容关系的基本概念 81

2.7.2相容关系与覆盖 82

2.8偏序关系 84

2.8.1偏序关系的基本概念 84

2.8.2偏序关系的次序图 84

2.8.3偏序集的特殊元素 85

2.8.4全序和良序 87

习题 88

第3章 函数 95

3.1函数及性质 95

3.1.1函数的基本概念 95

3.1.2函数的性质 97

3.2复合函数 99

3.2.1复合函数的定义 99

3.2.2函数复合运算的性质 100

3.2.3复合函数的性质 101

3.3逆函数 103

3.3.1逆函数的定义 103

3.3.2逆函数的性质 104

3.3.3左、右逆函数 105

3.4无限集的基数 106

3.4.1抽屉原理 106

3.4.2集合的等势 107

3.4.3可数集的基数 108

3.4.4不可数集的基数 111

3.4.5集合基数的比较 112

习题 114

第2篇 抽象代数 119

第4章 代数系统 121

4.1代数运算 121

4.1.1代数运算的概念 121

4.1.2二元运算的性质 123

4.1.3特殊元素 124

4.2代数系统与子代数 128

4.2.1代数系统的概念 128

4.2.2子代数的概念 129

4.3代数系统的同态与同构 130

4.3.1代数系统的同态 130

4.3.2满同态的性质 132

4.3.3同构的性质 132

4.4代数系统的积代数 134

习题 135

第5章 群、环和域 139

5.1半群和独异点 139

5.1.1半群和独异点的基本概念 139

5.1.2子半群和子独异点 142

5.1.3半群和独异点的同态 143

5.2群 143

5.2.1群的基本概念 143

5.2.2群的基本性质 146

5.2.3群的同态 148

5.3置换群与循环群 148

5.4子群及其陪集 152

5.4.1子群的定义 152

5.4.2子群的判别 153

5.4.3陪集与正规子群 155

5.4.4拉格朗日定理 158

5.5环和域 160

5.5.1环 160

5.5.2整环 162

5.5.3域 163

5.5.4环和域的同态 165

习题 166

第6章 格和布尔代数 170

6.1格及其性质 170

6.1.1格的偏序集定义 170

6.1.2格的性质 171

6.1.3格的代数系统定义 174

6.1.4子格 175

6.1.5格的同态 176

6.2分配格和有补格 177

6.2.1分配格 177

6.2.2有补格 179

6.2.3有补分配格 181

6.3布尔代数 182

6.3.1布尔代数的基本概念 182

6.3.2布尔代数的性质 184

习题 186

第3篇 图论 191

第7章 图与树 195

7.1图的基本概念 195

7.1.1图及其图解表示 195

7.1.2完全图与补图 197

7.1.3结点的度与握手定理 198

7.1.4图的连通性 199

7.1.5图的同构 202

7.1.6子图与分图 204

7.1.7图的运算 207

7.2图的矩阵表示 208

7.2.1图的关联矩阵 208

7.2.2图的邻接矩阵 209

7.2.3图的连接矩阵 211

7.3树 213

7.3.1树的基本概念 213

7.3.2树的基本性质 213

7.3.3最小生成树 215

7.4有向树 219

7.4.1有向树的基本概念 219

7.4.2二元树及其周游 221

7.4.3有向树中的一些数量关系 222

习题 223

第8章 特殊图 229

8.1欧拉图 229

8.1.1欧拉图的基本概念 229

8.1.2欧拉图的判别 230

8.1.3中国邮路问题 232

8.2哈密顿图 233

8.2.1哈密顿图的基本概念 233

8.2.2哈密顿图的判别 233

8.2.3流动售货员问题 235

8.3二部图 237

8.3.1二部图的基本概念 237

8.3.2二部图的判别 238

8.3.3匹配问题 239

8.4平面图 240

8.4.1平面图的基本概念 240

8.4.2平面图的判别 242

8.4.3地图着色问题 246

习题 248

第4篇 数理逻辑 253

第9章 命题逻辑 257

9.1命题的基本概念 257

9.2命题联结词 258

9.3命题公式的基本概念 262

9.4命题公式的等值关系和蕴含关系 266

9.4.1命题公式的等值关系 266

9.4.2基本的等值式 266

9.4.3等值式的判定 267

9.4.4命题公式的蕴含关系 271

9.4.5基本的蕴含式 271

9.4.6蕴含式的判定 272

9.4.7命题公式的对偶 274

9.5命题公式的范式 275

9.5.1析取范式和合取范式 275

9.5.2主析取范式和主合取范式 277

9.6命题演算的推理理论 281

9.6.1推理的概念 281

9.6.2推理的方法 281

习题 285

第10章 谓词逻辑 293

10.1个体、谓词和量词 293

10.2谓词公式的基本概念 297

10.3谓词公式的等值关系与蕴含关系 300

10.3.1谓词公式的类型 300

10.3.2谓词公式间的等值与蕴含关系 301

10.3.3谓词公式的对偶 305

10.4谓词公式的范式 305

10.4.1前束范式 305

10.4.2前束合取范式与前束析取范式 306

10.4.3斯柯林范式 308

10.5谓词演算的推理理论 309

10.5.1推理规则 310

10.5.2推理规则的应用 311

习题 314

参考文献 319