离散数学PDF电子书下载

第1章 命题逻辑 1

1.1 命题和联结词 1

1.1.1 命题的概念 1

1.1.2 联结词 2

1.2 合式公式与真值表 7

1.2.1 合式公式 7

1.2.2 真值表 8

1.3 永真式和等价式 9

1.3.1 永真式 9

1.3.2 等价式 10

1.3.3 代入规则和替换规则 11

1.4 对偶式与蕴涵式 12

1.4.1 对偶式 12

1.4.2 蕴涵式 14

1.5 范式和判定问题 15

1.5.1 析取范式和合取范式 15

1.5.2 主析取范式和主合取范式 17

1.6 命题演算的推理理论 20

1.7 基于布尔逻辑的信息检索 24

1.7.1 布尔逻辑运算符 24

1.7.2 应用技巧 26

习题 26

第2章 谓词逻辑 30

2.1 基本概念和表示 30

2.1.1 个体、谓词和谓词形式 30

2.1.2 量词 32

2.1.3 合式谓词公式 33

2.1.4 自由变元和约束变元 34

2.2 谓词逻辑的翻译与解释 35

2.2.1 谓词逻辑的翻译 35

2.2.2 谓词公式的解释 36

2.3 谓词逻辑的等价式与蕴涵式 36

2.4 谓词逻辑中的推论理论 39

2.4.1 推理规则 39

2.4.2 推理实例 40

2.5 谓词逻辑中公式范式 44

2.5.1 前束范式 44

2.5.2 斯柯林范式 45

2.6 谓词逻辑的应用 46

习题 47

第3章 集合论 50

3.1 集合的概念及其表示 51

3.2 集合的运算及恒等式 53

3.3 有穷集的计数和包含排斥原理 58

习题 62

第4章 二元关系 65

4.1 多重序元与笛卡儿乘积 65

4.2 关系的基本概念 67

4.3 关系的运算 68

4.4 关系的性质 74

4.5 关系的表示 76

4.6 关系的闭包运算 81

4.7 特殊关系 85

4.7.1 集合的划分和覆盖 85

4.7.2 等价关系 86

4.7.3 相容关系 91

4.7.4 次序关系 94

4.7.5 偏序集合与哈斯图 97

4.8 关系型数据库与非关系型数据库 99

4.8.1 关系型数据库 99

4.8.2 非关系型数据库 101

习题 102

第5章 函数 108

5.1 函数的基本概念和性质 108

5.2 函数的合成和合成函数的性质 111

5.3 特殊函数 113

5.4 反函数 115

5.5 特征函数 118

5.6 基数 120

5.7 不可解问题 122

5.7.1 不可解问题的存在性 123

5.7.2 停机问题 123

习题 124

第6章 代数系统 127

6.1 代数系统的一般概念 128

6.1.1 二元运算 128

6.1.2 代数系统 129

6.2 代数系统的基本性质 130

6.3 同态与同构 137

6.3.1 同态 138

6.3.2 同构 140

6.3.3 同态与同构的性质 144

6.4 同余关系 144

6.5 商代数 146

6.6 积代数 146

6.7 云环境中的数据安全之同态计算 148

6.7.1 云计算中的同态计算 148

6.7.2 数据安全的同态计算过程 149

6.7.3 同态计算在数据安全中的主要应用 149

习题 149

第7章 群与环 152

7.1 半群 152

7.2 群 154

7.2.1 群的概念 154

7.2.2 群的性质 156

7.3 子群与群的陪集分解 159

7.3.1 子群 159

7.3.2 子群的判定 159

7.3.3 子群的性质 160

7.3.4 子群的陪集分解 161

7.3.5 拉格朗日定理 164

7.4 循环群与置换群 164

7.4.1 循环群 165

7.4.2 置换群 166

7.5 群的同态与同构 167

7.6 环与域 168

7.6.1 环的概念与性质 168

7.6.2 域的概念 169

7.7 群理论的应用 170

7.7.1 群与网络安全 170

7.7.2 群与纠错编码 171

习题 173

第8章 格与布尔代数 176

8.1 格的定义与性质 177

8.2 分配格、有补格与布尔代数 179

8.3 应用 180

习题 181

第9章 图的基本概念及其矩阵表示 183

9.1 图的基本概念 184

9.1.1 图的定义及相关概念 184

9.1.2 结点的度 186

9.2 子图和图的运算 188

9.2.1 子图和补图 189

9.2.2 图的运算 190

9.3 路径、回路和连通性 192

9.3.1 路径和回路 192

9.3.2 图的连通性 195

9.4 图的矩阵表示 198

9.4.1 邻接矩阵 198

9.4.2 可达性矩阵 203

9.4.3 关联矩阵 206

9.5 图论在社会网络分析中的应用 208

习题 209

第10章 几种特殊图 215

10.1 欧拉图 215

10.2 哈密尔顿图 218

10.3 二部图及匹配 220

10.3.1 二部图的概念及性质 220

10.3.2 二部图匹配 222

10.4 平面图 224

10.4.1 平面图的概念及性质 224

10.4.2 多边形图、对偶图及平面图着色 226

10.5 网络 229

10.5.1 网络的基本概念 230

10.5.2 网络流 231

10.5.3 网络最大流求解 232

10.5.4 开关网络 239

10.6 图的实例分析 247

10.6.1 中国邮递员问题 247

10.6.2 旅行售货员问题 249

10.6.3 排课问题 250

10.6.4 时延容忍网络问题 252

10.6.5 最短路径问题 253

习题 256

第11章 树 260

11.1 树与生成树 260

11.1.1 树及其性质 260

11.1.2 生成树与最小生成树 262

11.2 有向树及其应用 264

11.2.1 有向树 264

11.2.2 m叉树 265

11.2.3 有序树 267

11.2.4 二叉树的遍历 269

11.2.5 搜索树 270

习题 273

参考文献 276