离散数学PDF电子书下载

第1章 命题逻辑 1

1.1 命题和逻辑联结词 1

1.1.1 命题 1

1.1.2 逻辑联结词 2

1.2 命题公式和真值表 4

1.2.1 命题公式 4

1.2.2 命题的翻译 5

1.2.3 真值表 6

1.2.4 永真式与永假式 7

1.3 等价式和蕴涵式 8

1.3.1 等价式 8

1.3.2 蕴涵式 11

1.4 扩充的联结词和全功能联结词集 13

1.4.1 扩充的联结词 13

1.4.2 全功能联结词集 15

1.5 对偶式 17

1.6.1 析取范式与合取范式 19

1.6 命题范式 19

1.6.2 主析取范式与主合取范式 21

1.7 命题演算的推理理论 30

1.7.1 推理的基本概念 30

1.7.2 推理的方法 30

1.8 习题 37

2.1 谓词逻辑的基本概念 41

2.1.1 谓词的概念和表示 41

第2章 谓词逻辑 41

2.1.2 命题函数和量词 42

2.2 谓词公式与翻译 44

2.2.1 谓词公式 44

2.2.2 谓词逻辑中命题的翻译 45

2.2.3 变元的约束 46

2.3 谓词演算的永真式 48

2.3.1 谓词公式的真值 48

2.3.2 谓词演算的永真式 49

2.3.3 永真式的变换规则 52

2.4 前束范式 53

2.5 谓词演算的推理理论 55

2.5.1 推理规则 55

2.5.2 推理应用举例 57

2.6 习题 59

第3章 集合论 63

3.1 基本概念 63

3.1.1 概述 63

3.1.3 集合的包含关系 64

3.1.2 集合的表示法 64

3.2 集合的运算 67

3.2.1 文氏图 67

3.2.2 集合的交 67

3.2.3 集合的并 68

3.2.4 集合的补 69

3.2.5 集合的对称差 69

3.3 集合成员表 70

3.4 集合定律 71

3.5 习题 75

第4章 关系 78

4.1 序偶与笛卡尔积 78

4.2 关系及其表示 80

4.3 关系距阵与关系图 82

4.4 关系的性质 83

4.5 关系的运算 84

4.5.1 关系的逆运算 84

4.5.2 关系的复合运算 86

4.5.3 关系的幂运算 89

4.5.4 关系的闭包运算 90

4.6 集合的划分与完全覆盖 95

4.7 等价关系与等价类 96

4.8 相关关系与最大相容类 98

4.9 次序关系 100

4.10 习题 104

第5章 函数 108

5.1 基本概念 108

5.2 复合函数和逆函数 110

5.3 置换与轮换 113

5.4 集合的特征函数 116

5.5 集合的基数 118

5.6 习题 124

第6章 代数系统 127

6.1 运算及其性质 127

6.2 代数系统 133

6.3 同态与同构 134

6.4 同余关系 138

6.5 商代数与积代数 140

6.6 习题 145

第7章 半群与群 149

7.1 半群与独异点 149

7.2 群与子群 153

7.3 交换群与循环群 158

7.4 交换群与置换群 161

7.5 陪集、正规子群与商群 163

7.6 习题 170

第8章 环和域 173

8.1 环和子环 173

8.2 理想 176

8.3 域 177

8.4 习题 178

第9章 格与布尔代数 179

9.1 格 179

9.1.1 偏序集定义的格 179

9.1.2 代数系统定义的格 182

9.1.3 子格与格的同态 184

9.2 分配格和有补格 187

9.2.1 分配格 187

9.2.2 有补格 188

9.3 布尔代数与布尔表达式 189

9.3.1 布尔代数 189

9.3.2 布尔表达式 190

9.4 习题 192

10.1.1 图的定义 194

第10章 图 194

10.1 图的基本概念 194

10.1.2 图的相关术语 196

10.1.3 伪图、多重图和简单图 197

10.1.4 完全图 198

10.1.5 子图及图的同构 199

10.1.6 图的同构 200

10.2 图的连通性 202

10.2.1 通路和回路 202

10.2.2 图的连通性 203

10.2.3 连通度 205

10.3 图的矩阵表示 207

10.3.1 关联矩阵 207

10.3.2 邻接矩阵 208

10.3.3 可达矩阵 211

10.4 欧拉图与哈密尔顿图 214

10.4.1 欧拉图 214

10.4.2 哈密尔顿图 217

10.5.1 赋权图与最短通路的算法 220

10.5 最短通路问题 220

10.5.2 旅行推销员问题 221

10.6 习题 222

第11章 特殊图 227

11.1 二分图 227

11.2 平面图 229

11.2.1 平面图的基本概念 230

11.2.2 平面图的欧拉公式 231

11.2.3 平面图的判定 233

11.2.4 对偶图与平面图的着色 233

11.3 树 235

11.3.1 树的定义 235

11.3.2 生成树与最小生成树 237

11.3.3 有向树 239

11.3.4 最优二元树 242

11.4 习题 244

参考文献 248