离散数学PDF电子书下载

第一部分 数理逻辑 3

第一章 命题逻辑基本概念 3

1.1 命题及其符号化 3

1.1.1 命题 3

1.1.2 命题符号化 4

1.2 合式公式和真值赋值 10

1.2.1 合式公式及层次 10

1.2.2 真值赋值及公式分类 12

1.3 真值表和真值函数 14

习题一 16

第二章 命题逻辑等值演算 19

2.1 等值关系 19

2.2 联结词的全功能集 24

2.3 范式 27

2.4.1 门电路和触发器 34

2.4 数字逻辑电路初步 34

2.4.2 组合逻辑电路的设计 36

2.4.3 时序逻辑电路的设计 38

习题二 42

第三章 命题逻辑自然推理 44

3.1 推理的形式结构 44

3.2 自然推理系统P 47

3.3 常见的证明方法 49

习题三 53

第四章 谓词逻辑的基本概念 54

4.1 谓词和量词 55

4.2 一阶语言 59

4.2.1 一阶语言 60

4.2.2 解释和赋值 63

4.2.3 公式的分类 66

4.3 一阶逻辑等值演算 67

4.3.1 等值演算 67

4.3.2 前束范式 69

4.4 一阶逻辑形式推理 71

4.4.1 推理定律 71

4.4.2 推理规则 72

习题四 75

第二部分 集合论 79

第五章 集合代数 79

5.1 集合的概念及表示 79

5.2 集合运算 85

5.3 集合定律 89

5.4 有限集的计数问题 90

5.5 有序对与卡氏积 94

习题五 96

第六章 二元关系 99

6.1 二元关系及其表示 99

6.2 二元关系的性质 102

6.3.1 关系的限制和像 104

6.3 二元关系的运算 104

6.3.2 关系的逆 106

6.3.3 关系的合成 106

6.3.4 关系的闭包 109

6.4 特殊关系及其性质 117

6.4.1 等价关系及性质 117

6.4.2 相容关系及性质 120

6.4.3 序关系及性质 123

习题六 127

第七章 函数 130

7.1 函数基本概念 130

7.2 函数的合成 134

7.3 反函数 137

7.4 特殊函数 140

7.4.1 特征函数 140

7.4.2 变换函数和置换函数 142

7.5 集合的基数 146

习题七 150

第三部分 代数系统 152

第八章 代数结构 152

8.1 代数系统基本概念 152

8.1.1 代数运算及其性质 152

8.1.2 代数系统 156

8.1.3 积代数和商代数 157

8.2 半群和群 159

8.2.1 半群 159

8.2.2 群 161

8.2.3 子群和陪集 170

8.3 环和域 174

8.4 差错编码初步 179

8.5 差错解码初步 185

习题八 188

第九章 格与布尔代数 191

9.1 格的定义和性质 191

9.2 分配格与有补格 197

9.3 布尔代数 200

习题九 203

第四部分 图论 207

第十章 图 207

10.1 图的基本概念 207

10.1.1 有向图和无向图 207

10.1.2 关联和相邻或邻接 209

10.1.3 点的度数 209

10.1.4 特殊图 211

10.1.5 图的同构 213

10.2 图的运算 214

10.3 图的连通性 218

10.3.1 通路和回路 218

10.3.2 无向图的连通性 219

10.3.3 有向图的连通性 222

10.4.1 无向图的矩阵表示 225

10.4 图的矩阵表示 225

10.4.2 有向图的矩阵表示 230

习题十 234

第十一章 通路应用问题 236

11.1 最短径问题 236

11.2 关键路径问题 240

11.3 网络最大流量问题 242

11.4 穿程问题 248

11.4.1 欧拉图 248

11.4.2 哈密顿图 250

习题十一 254

第十二章 树 256

12.1 无向树基本概念 256

12.2 生成树 258

12.2.1 生成树及其做法 258

12.2.2 生成树的应用 262

12.3 最小生成树 266

12.4 根树 269

12.5 二叉树应用 275

习题十二 279

第十三章 平面图 281

13.1 平面图基本概念 281

13.2 欧拉公式 284

13.3 平面图的判断 287

13.4 对偶图及着色 289

习题十三 293

第十四章 偶图与匹配 295

14.1 偶图的判断 295

14.2 匹配 296

习题十四 300

附录1 数学工具 302

附录2 习题答案或提示 308

参考文献 348