离散数学PDF电子书下载

绪论 1

第1章 命题逻辑 4

1.1 命题及其表示 5

1.1.1 命题 5

1.1.2 命题的分类 6

1.1.3 命题标识符 6

习题1.1 7

1.2 常用逻辑联结词 7

1.2.1 否定联结词 7

1.2.2 合取联结词 8

1.2.3 析取联结词 8

1.2.4 条件联结词 9

1.2.5 双条件联结词 10

习题1.2 11

1.3 命题公式与翻译 12

1.3.1 命题公式 12

1.3.2 命题的符号化 13

习题1.3 14

1.4 真值表与等价公式 15

1.4.1 真值表 15

1.4.2 等价公式 16

习题1.4 21

1.5 命题公式的分类与蕴涵式 21

1.5.1 命题公式的分类 21

1.5.2 重言式与矛盾式的性质 22

1.5.3 蕴涵式 22

习题1.5 25

1.6 其他逻辑联结词和最小功能完备联结词组 26

1.6.1 其他逻辑联结词 26

1.6.2 最小功能完备联结词组 28

习题1.6 28

1.7 对偶与范式 28

1.7.1 对偶 28

1.7.2 范式 30

1.7.3 主范式 32

习题1.7 42

1.8 推理理论 43

1.8.1 直接证明法 43

1.8.2 间接证明法 46

习题1.8 48

本章解析 48

第2章 谓词逻辑 51

2.1 谓词的基本定义 51

2.1.1 个体和谓词 52

2.1.2 量词 53

习题2.1 54

2.2 谓词公式与翻译 54

2.2.1 谓词公式 54

2.2.2 谓词公式的翻译 55

习题2.2 56

2.3 自由与约束 57

习题2.3 59

2.4 谓词逻辑的等价式与蕴涵式 59

2.4.1 谓词公式的赋值 59

2.4.2 谓词公式的分类 60

2.4.3 谓词逻辑的等价式 61

2.4.4 谓词逻辑的蕴涵式 65

习题2.4 66

2.5 谓词公式范式 67

2.5.1 前束范式 67

2.5.2 前束析取范式和前束合取范式 68

2.5.3 斯柯林范式 69

习题2.5 69

2.6 谓词逻辑的推理理论 70

习题2.6 75

本章解析 75

第3章 集合 78

3.1 集合的基本定义 78

3.1.1 集合与元素 78

3.1.2 集合间的关系 79

3.1.3 幂集 81

习题3.1 82

3.2 集合的运算 83

3.2.1 集合的交与并 83

3.2.2 集合的差与补 85

3.2.3 集合的对称差 87

习题3.2 89

3.3 包含排斥原理 90

习题3.3 94

本章解析 95

第4章 关系 97

4.1 序偶与笛卡尔积 97

4.1.1 序偶 97

4.1.2 笛卡尔积 98

习题4.1 100

4.2 关系及其表示 101

4.2.1 关系的定义 101

4.2.2 几种特殊的关系 102

4.2.3 关系的表示 103

习题4.2 105

4.3 关系的性质 105

4.3.1 关系的性质 105

4.3.2 关系性质的判定 107

习题4.3 108

4.4 复合关系和逆关系 110

4.4.1 复合关系 110

4.4.2 逆关系 113

习题4.4 116

4.5 关系的闭包 116

习题4.5 120

4.6 等价关系与相容关系 120

4.6.1 集合的划分和覆盖 120

4.6.2 等价关系与等价类 122

4.6.3 相容关系 126

习题4.6 129

4.7 偏序关系 130

4.7.1 偏序关系 130

4.7.2 哈斯图 130

4.7.3 特殊元素 132

4.7.4 全序和良序 134

习题4.7 135

本章解析 136

第5章 函数 138

5.1 函数的定义 138

习题5.1 143

5.2 几种特殊函数 143

习题5.2 145

5.3 函数的运算 146

5.3.1 复合运算 146

5.3.2 逆运算 148

习题5.3 150

5.4 置换 151

习题5.4 152

5.5 基数 153

5.5.1 无限集合 153

5.5.2 基数的定义 154

5.5.3 可数集与不可数集 155

习题5.5 156

本章解析 157

第6章 代数结构 158

6.1 代数系统 159

6.1.1 n元运算 159

6.1.2 代数系统的定义 161

习题6.1 163

6.2 二元运算与特殊元素 164

6.2.1 二元运算的性质 164

6.2.2 代数系统中的特殊元素 168

6.2.3 利用运算表判断代数系统的性质 173

习题6.2 174

6.3 半群与含幺半群 176

6.3.1 半群及其性质 176

6.3.2 含幺半群及其性质 178

习题6.3 180

6.4 群与子群 182

6.4.1 群的定义 182

6.4.2 群的基本性质 183

6.4.3 群的元素的阶 187

6.4.4 子群 187

习题6.4 189

6.5 阿贝尔群、循环群和置换群 190

6.5.1 阿贝尔群 190

6.5.2 循环群 190

6.5.3 置换群 192

习题6.5 193

6.6 代数系统的同态与同构 194

习题6.6 197

6.7 环与域 198

6.7.1 环 198

6.7.2 域 200

习题6.7 200

本章解析 201

第7章 格与布尔代数 203

7.1 格 203

7.1.1 格的定义 203

7.1.2 格的性质 207

7.1.3 格的同态与同构 210

习题7.1 213

7.2 分配格与模格 214

7.2.1 分配格 214

7.2.2 模格 217

习题7.2 218

7.3 有界格与有补格 219

7.3.1 有界格 219

7.3.2 有补格 220

习题7.3 221

7.4 布尔代数 222

7.4.1 布尔代数的定义 222

7.4.2 布尔代数的性质 223

7.4.3 子布尔代数 225

7.4.4 布尔代数的同态与同构 226

7.4.5 布尔代数在电路设计中的应用 226

习题7.4 228

本章解析 229

第8章 图论 230

8.1 图的相关概念 230

8.1.1 图的基本定义 230

8.1.2 补图与子图 234

8.1.3 图的握手定理 235

8.1.4 图的同构 237

习题8.1 239

8.2 路与图的连通性 239

8.2.1 路与回路 239

8.2.2 图的连通性 241

习题8.2 244

8.3 图的存储矩阵 245

8.3.1 邻接矩阵 245

8.3.2 可达矩阵 247

8.3.3 关联矩阵 249

习题8.3 250

8.4 欧拉图与哈密顿图 251

8.4.1 欧拉图 251

8.4.2 哈密顿图 254

习题8.4 256

8.5 二部图与平面图 258

8.5.1 二部图 258

8.5.2 二部图的匹配 259

8.5.3 平面图 261

8.5.4 平面图的着色 266

习题8.5 267

8.6 树与生成树 268

8.6.1 无向树 268

8.6.2 生成树 271

8.6.3 最小生成树 272

习题8.6 274

8.7 根树及其应用 275

8.7.1 有向树 275

8.7.2 m叉树 276

8.7.3 最优二叉树 279

8.7.4 二叉树在计算机中的应用 280

习题8.7 285

8.8 图的应用 285

8.8.1 最短路径 285

8.8.2 关键路径 288

习题8.8 290

本章解析 291

参考文献 293