离散数学PDF电子书下载

第一篇 数理逻辑 3

1.1 命题与命题公式 3

1.1.1 命题 3

第1章 命题逻辑 3

目录 3

1.1.2 命题联结词 4

1.1.3 命题公式 7

1.1.4 命题公式的真值表 9

1.2 重言式 10

1.2.1 重言式和矛盾式 10

1.2.2 等价重言式 10

1.2.3 蕴含重言式 13

1.2.4 对偶与对偶原理 15

1.3 命题演算的推理规则和证明方法 15

1.3.1 真值表的证明方法 16

1.3.2 形式推理的证明方法——直接证法 17

1.3.3 间接证法 21

1.4.1 范式 24

1.4 命题公式的标准形式 24

1.4.2 主范式 26

1.5 其他联结词 31

习题1 34

第2章 谓词逻辑 37

2.1 个体、谓词与命题函数 37

2.1.1 个体与谓词 37

2.1.2 命题函数 39

2.2 量词 39

2.2.1 全称量词 40

2.2.2 存在量词 41

2.3 谓词公式与翻译 41

2.3.1 谓词公式 41

2.3.2 命题的符号化 42

2.3.3 自由变元和约束变元 44

2.4.1 谓词演算的等价式和蕴含式 45

2.4 谓词演算的推理理论 45

2.4.2 谓词演算的推理规则 49

2.5 前束范式 52

习题2 53

第二篇 集合论 59

第3章 集合 59

3.1 基本概念 59

3.1.1 集合及其表示方法 59

3.1.2 集合的包含和相等 60

3.1.3 空集和全集 61

3.1.4 幂集 61

3.2 集合的运算与运算定律 63

3.2.1 集合的运算与文氏图 63

3.2.2 集合运算的定律 66

3.2.3 集合的对称差 69

3.3 集合的划分与覆盖 70

3.4 容斥原理简介 72

习题3 74

第4章 关系 79

4.1 序偶与笛卡尔积 79

4.1.1 序偶与有序n元组 79

4.1.2 笛卡尔积 79

4.2 关系、关系矩阵和关系图 81

4.2.1 关系的概念 81

4.2.2 关系矩阵 83

4.2.3 关系图 84

4.3 关系的运算 84

4.3.1 关系的并、交、补、差运算 84

4.3.2 关系的复合运算 85

4.3.3 关系的逆运算 88

4.4 关系的性质 89

4.4.1 定义 89

4.4.2 举例 92

4.4.3 关系性质的判定定理 93

4.5 关系的闭包运算 94

4.5.1 定义 94

4.5.2 闭包运算的性质 95

4.5.3 有限集合上关系的传递闭包 96

4.5.4 ρ+的关系图的画法 97

4.6 等价关系与等价类 98

4.6.1 定义 98

4.6.2 等价关系与划分 99

4.7 相容关系 100

4.7.1 定义 100

4.7.2 相容关系与覆盖 101

4.8.1 定义 102

4.8 偏序 102

4.8.2 哈斯图 103

4.8.3 偏序集中的特殊元素 104

习题4 106

5.1 函数与特殊类型函数 111

5.1.1 函数的定义 111

第5章 函数 111

5.1.2 特殊类型函数 113

5.2 函数的运算 114

5.2.1 函数的复合 114

5.2.2 逆函数 117

5.3 集合的势与可数集 118

5.3.1 集合的势 119

5.3.2 可数集 121

5.4 自然数与数学归纳法 123

5.4.2 数学归纳法 124

5.4.1 自然数的性质 124

习题5 126

第三篇 图论 131

第6章 图论基础 131

6.1 基本概念 131

6.1.1 图 131

6.1.2 结点的度 132

6.1.3 几种常见的图 132

6.1.4 子图 133

6.1.5 图的同构 134

6.2.1 路、圈和连通性 135

6.2 路与圈 135

6.2.2 有权图的最短路径问题 137

6.3 图的矩阵表示 141

6.4 有向图和可达性矩阵 142

6.4.1 有向图 142

6.4.2 有向图的可达性 144

习题6 148

7.1 欧拉图与哈密尔顿图 151

第7章 图论的典型问题 151

7.1.1 欧拉图 151

7.1.2 哈密尔顿图 155

7.2.1 树 158

7.2 树 158

7.2.2 生成树与最小生成树 159

7.2.3 点割集与边割集 161

7.3.1 根树、有序树、M叉树 162

7.3 根树及其应用 162

7.2.4 基本回路与基本割集 162

7.3.2 二叉树 164

7.3.3 二叉树在计算机中的应用 167

7.4.1 偶图 171

7.4 偶图与匹配 171

7.4.2 匹配 172

7.5.1 平面图 174

7.5 平面图与欧拉公式 174

7.5.2 欧拉公式 176

7.6 连通度 179

7.7.1 运输网络、流、割 180

7.7 运输网络 180

7.7.2 最大流最小割定理 182

7.7.3 标记法 184

习题7 187

8.1.1 运算 195

第四篇 近世代数 195

第8章 代数系统 195

8.1 运算和代数系统 195

8.1.2 运算的运算表 196

8.1.3 代数系统 197

8.2 二元运算的性质与特殊元素 198

8.2.1 二元运算的性质 199

8.2.2 二元运算的特殊元素 200

8.3.1 同构 203

8.3 同态和同构 203

8.3.2 同态 205

8.4 同余关系和商代数 208

8.4.1 同余关系 208

8.4.2 商代数 209

8.5 积代数 212

8.5.1 积代数的定义 212

8.5.2 积代数的性质 213

习题8 213

第9章 群与格 217

9.1 半群和独异点 217

9.1.1 半群 217

9.1.2 独异点 218

9.1.3 子半群和子独异点 220

9.2 群 221

9.2.1 定义 221

9.2.2 群的基本性质 224

9.3 群中元素的周期与循环群 225

9.3.1 群中元素的周期 225

9.3.2 元素周期的性质 225

9.3.3 循环群 227

9.4 子群 228

9.4.1 两个等价的定义 228

9.4.2 子群的判定定理 229

9.5 陪集和正规子群 231

9.5.1 陪集和陪集划分 231

9.5.2 正规子群 233

9.6 群同态 235

9.7 格与布尔代数 237

9.7.1 格的定义和性质 237

9.7.2 格的代数系统定义 239

9.7.3 几种特殊的格 240

9.7.4 布尔代数和布尔表达式 242

9.8 环与域 246

9.8.1 环 246

9.8.2 域 248

习题9 249

第五篇 组合数学基础 255

第10章 组合计数基本方法 255

10.1 基本计数方法 255

10.2.1 排列 257

10.2 排列与组合 257

10.2.2 组合 258

10.2.3 组合恒等式 260

10.3 排列组合生成算法 262

10.3.1 排列的生成 262

10.3.2 组合的生成 265

习题10 266

第11章 差分方程 268

11.1 生成函数 268

11.1.1 幂级数型生成函数的定义 268

11.1.2 幂级数型生成函数的运算性质 269

11.1.3 整数拆分问题 271

11.1.4 指数型生成函数 274

11.2 差分方程 275

11.2.1 差分方程及其初值问题 275

11.2.2 线性常系数齐次差分的特征根求解方法 278

11.2.3 线性常系数非齐次差分的解 283

11.3 应用举例 286

习题11 292

第12章 容斥原理和抽屉原理 295

12.1 容斥原理 295

12.2 有限制排列 298

12.3 抽屉原理 301

习题12 306

参考文献 308