离散数学PDF电子书下载

第一篇 数理逻辑 3

第1章 命题逻辑 3

1.1 命题 4

1.1.1 命题的概念 4

1.1.2 命题的分类 5

1.2 联结词 5

1.2.1 否定联结词 6

1.2.2 合取联结词 6

1.2.3 析取联结词 7

1.2.4 条件联结词 8

1.2.5 双条件联结词 9

1.3 命题公式与翻译 10

1.3.1 命题公式的定义 10

1.3.2 真值表 11

1.3.3 命题的翻译 12

1.4 命题公式的等价、蕴涵 13

1.4.1 重言式和矛盾式 13

1.4.2 命题公式的等价关系 14

1.4.3 置换 16

1.4.4 命题公式的蕴涵关系 17

1.5 对偶与范式 19

1.5.1 对偶式 19

1.5.2 析取范式与合取范式 21

1.5.3 主析取范式 21

1.5.4 主合取范式 23

1.6 其他联结词 25

1.6.1 不可兼析取联结词 26

1.6.2 条件否定联结词 27

1.6.3 与非联结词 28

1.6.4 或非联结词 28

1.6.5 联结词之间的关系 29

1.7 命题演算推理 29

1.7.1 有效论证的概念 29

1.7.2 真值表法 30

1.7.3 直接证法 32

1.7.4 间接证法 34

1.8 应用 36

1.9 典型例题解析 40

本章小结 45

习题 45

2.1.1 谓词的概念 52

2.1 谓词和量词 52

第2章 谓词逻辑 52

2.1.2 全称量词和存在量词 54

2.2 谓词公式与翻译 56

2.2.1 谓词公式的定义 56

2.2.2 谓词公式的翻译 56

2.3 约束变元与自由变元 57

2.4 谓词公式的等价、蕴涵 59

2.4.1 一些基本概念 59

2.4.2 量词与联结词？之间的关系 59

2.4.3 量词辖域的扩张与收缩 60

2.4.4 量词与命题联结词之间的一些等价、蕴涵式 60

2.5 前缀范式 63

2.5.1 前缀范式的定义 63

2.6.1 四个基本的推理规则 64

2.6 谓词演算推理 64

2.5.2 前缀合取范式和前缀析取范式 64

2.6.2 推理规则的应用 66

2.7 应用 67

2.8 典型例题解析 70

本章小结 72

习题 72

第二篇 集合论 83

第3章 集合及其运算 83

3.1 集合的概念与性质 84

3.1.1 集合的概念 84

3.1.2 集合的表示 85

3.1.3 三个基本原理 86

3.1.4 集合的性质 87

3.2.1 Venn图 89

3.1.5 幂集 89

3.2 集合的运算 89

3.2.2 集合的运算 90

3.2.3 集合的运算性质 93

3.3 序偶和笛卡尔积 94

3.3.1 序偶 94

3.3.2 笛卡尔积 94

3.4 数学归纳法 96

3.4.1 集合的归纳定义 96

3.4.2 自然数的集合论定义 97

3.4.3 数学归纳法 98

3.5 典型例题解析 99

本章小结 101

习题 102

第4章 关系 106

4.1 关系的概念及性质 107

4.1.1 关系的概念 107

4.1.2 关系的表示方法 107

4.1.3 关系的性质 109

4.2 关系的运算 110

4.2.1 复合运算 111

4.2.2 逆运算 114

4.2.3 闭包运算 115

4.3 等价关系、等价类与划分 120

4.4 相容关系、相容类与覆盖 124

4.5 偏序关系 127

4.6 典型例题解析 131

本章小结 136

习题 137

第5章 函数 141

5.1 函数的概念 141

5.2 函数的分类 143

5.2.1 满射、单射和双射 143

5.2.2 合成映射、恒等映射及逆映射 144

5.3 特征函数 149

5.4 典型例题解析 152

本章小结 153

习题 154

第6章 基数 157

6.1 基本概念 157

6.1.1 等势 157

6.1.3 基数 158

6.1.2 有限集和无限集 158

6.2 可数集和不可数集 159

6.2.1 基本概念 159

6.2.2 连续统的势 161

6.2.3 无限集的性质 162

6.3 基数的比较 163

6.3.1 基数的比较 163

6.3.2 基数的性质 165

6.4 典型例题解析 168

本章小结 169

习题 169

第7章 集合论的发展与应用 172

7.1 计数原理 172

7.1.1 计数的基础 172

7.1.2 容斥原理 174

7.1.3 鸽笼原理 177

7.1.4 重集 179

7.2 模糊集基础 180

7.2.1 发展简介 180

7.2.2 模糊集合的概念与方法 181

7.2.3 模糊理论的其他应用 190

7.3 集合的应用 193

7.3.1 关系在信息模型设计中的应用 193

7.3.2 关系数据库 193

本章小结 197

习题 197

第三篇 代数结构 201

第8章 群 201

8.1.1 运算 202

8.1 代数系统的基本概念 202

8.1.2 代数系统、子代数与积代数 204

8.2 半群与独异点 206

8.3 群 207

8.3.1 群 207

8.3.2 群的性质 208

8.4 子群 209

8.4.1 子群的定义 209

8.4.2 子群的判别条件 209

8.5 阿贝尔群与循环群 210

8.5.1 阿贝尔群 210

8.5.2 循环群 211

8.6.1 置换的定义 213

8.6 置换群 213

8.6.2 置换群 214

8.7 拉格朗日定理 216

8.8 同态及同构 219

8.8.1 同态映射 219

8.8.2 同构映射 220

8.8.3 同态核 221

8.9 典型例题解析 223

本章小结 226

习题 226

第9章 格与布尔代数 228

9.1 格 229

9.1.1 格的定义 229

9.1.2 格的性质 232

9.1.3 格的同态与同构 235

9.1.4 几种特殊的格 238

9.2 布尔代数 244

9.2.1 布尔代数的定义 244

9.2.2 布尔代数的性质 245

9.2.3 亨廷顿（Huntington）公理 246

9.2.4 有限布尔代数 248

9.2.5 布尔表达式与布尔函数 252

9.2.6 布尔代数的同态与同构 253

9.3 应用 255

9.3.1 开关电路函数 255

9.3.2 全加器的逻辑设计 256

9.4 典型例题解析 257

习题 265

本章小结 265

第四篇 图论 269

第10章 图 269

10.1 图模型 270

10.2 图的分类 275

10.3 图的连通性 278

10.4 图的矩阵表示 283

10.5 典型例题解析 290

本章小结 294

习题 295

第11章 特殊图 297

11.1 欧拉图与Hamilton图 297

11.1.1 欧拉图 297

11.1.2 Hamilton图 299

11.1.3 应用举例 303

11.2 二分图与匹配 304

11.2.1 二分图的基本概念 305

11.2.2 匹配 306

11.2.3 分配问题 308

11.3 平面图、对偶图与地图着色 309

11.3.1 平面图 309

11.3.2 对偶图与地图着色 313

11.4 网络及最大流问题 316

11.5 典型例题解析 319

本章小结 325

习题 325

第12章 树 329

12.1 树的概念 329

12.2 生成树 331

12.3 根树、二叉树及其应用 335

12.3.1 根树 335

12.3.2 二叉树及其遍历 336

12.3.3 应用举例 340

12.4 典型例题解析 343

本章小结 346

习题 346

第13章 超图概述 348

13.1 基本概念 348

13.2 超图的链和圈 349

13.3 E-C-R性质和Helly性质 350

本章小结 351

参考文献 352