离散数学PDF格式文档图书下载

第1章 命题逻辑 1

1.1 命题与联结词 1

1.1.1 命题的基本概念 1

1.1.2 命题分类及命题标识符 2

1.1.3 命题联结词 2

1.2 命题公式、翻译与真值表 4

1.2.1 命题公式 4

1.2.2 命题的符号化 4

1.2.3 真值表 5

1.3 公式分类与等价式 6

1.3.1 公式分类 6

1.3.2 等价公式（等值演算） 6

1.3.4 代入规则和替换规则 7

1.3.3 基本等价式——命题定律 7

1.3.5 证明两个命题公式等价的方法 8

1.4 对偶式与蕴涵式 9

1.4.1 对偶式 9

1.4.2 蕴涵式 10

1.4.3 蕴涵式的证明方法 11

1.5 联结词的扩充与全功能联结词组 11

1.5.1 联结词的扩充 11

1.5.2 与非、或非、异或的性质 12

1.5.3 全功能联结词组 13

1.6 公式标准型——范式 13

1.6.1 简单合取式与简单析取式 13

1.6.2 析取范式与合取范式 13

1.6.3 范式的应用 14

1.7.1 主析取范式 15

1.7 公式主范式 15

1.7.2 主合取范式 17

1.7.3 主范式的应用 19

1.8 命题逻辑的推理理论 20

1.8.1 推理规则 20

1.8.2 推理定律 21

1.8.3 判断有效结论的常用方法 21

1.9 典型例题分析 24

习题 28

第2章 谓词逻辑 32

2.1 基本概念 32

2.1.1 个体、谓词和命题的谓词形式 32

2.1.2 量词 33

2.2.1 谓词公式 34

2.2 谓词公式与翻译 34

2.2.2 谓词逻辑的翻译 35

2.3 自由变元和约束变元 35

2.4 谓词公式的解释与分类 36

2.4.1 谓词公式的解释 36

2.4.2 谓词公式的分类 37

2.5 谓词演算的等价式与蕴涵式 38

2.5.1 等价式 38

2.5.2 蕴涵式 40

2.6 谓词演算中的公式范式 41

2.6.1 前束范式 41

2.6.2 斯柯林范式 42

2.7 谓词演算的推理理论 42

2.8 典型例题分析 46

习题 48

3.1.2 集合的表示法 52

3.1.1 集合的概念 52

第3章 集合 52

3.1 集合的概念与表示法 52

3.1.3 集合的包含与相等 53

3.1.4 空集、集族、幂集和全集 54

3.1.5 有限幂集元素的编码表示 55

3.2 集合的运算与性质 55

3.2.1 集合的交、并和补 55

3.2.2 集合的对称差 57

3.2.3 集合的广义并和广义交 57

3.2.4 集合的文氏图 58

3.3 集合的划分与覆盖 58

3.4 排列与组合 60

3.4.1 加法原理与乘法原理 60

3.4.2 排列 60

3.4.4 排列与组合的生成 61

3.4.3 组合 61

3.5 归纳原理 62

3.5.1 结构归纳原理 62

3.5.2 数学归纳原理 63

3.6 容斥原理和抽屉原理 64

3.6.1 容斥原理 64

3.6.2 抽屉原理（鸽巢原理） 65

3.7 递推关系 66

3.7.1 递推关系的概念 66

3.7.2 递推关系的求解 66

3.8 集合论在命题逻辑中的应用 68

3.8.1 命题逻辑中的集合表示 68

3.8.2 应用举例 70

3.9 典型例题分析 70

习题 72

3.10 上机实验 72

4.1 序偶与笛卡儿积 75

4.1.1 序偶及有序n元组 75

4.1.2 笛卡儿积 75

第4章 关系 75

4.2 关系及其表示 77

4.2.1 关系 77

4.2.2 关系矩阵与关系图 79

4.3 复合关系及逆关系 79

4.4 关系的性质 81

4.5 关系的闭包 83

4.6 等价关系和等价类 88

4.7 相容关系 90

4.8 偏序关系 92

4.9 典型例题分析 95

习题 97

4.10 上机实验 97

第5章 函数 100

5.1 函数的概念 100

5.1.1 函数定义 100

5.1.2 函数性质 101

5.2 逆函数和复合函数 102

5.2.1 逆函数 102

5.2.2 函数的复合 102

5.2.3 几种特殊的函数 105

5.3 集合的基数 105

5.3.1 基数的概念 106

5.3.2 可数集与不可数集 106

5.3.3 基数的比较 107

5.4.1 Fuzzy集 108

5.4 经典集合的扩展 108

5.4.2 Vague集 109

5.4.3 Rough集 110

5.5 典型例题分析 111

习题 113

第6章 整除 115

6.1 因数和倍数 115

6.2 素数和合数 115

6.3 带余除法与辗转相除法 116

6.4 最大公因数和最小公倍数 117

6.5 算术基本定理 119

6.6 典型例题分析 120

6.7 上机实验 122

习题 122

7.1 同余及其性质 123

第7章 同余 123

7.2 剩余类和剩余系 125

7.3 欧拉定理与威尔逊定理 126

7.4 一次同余式 128

7.5 一次同余式组 130

7.6 数论在密码学中的应用 131

7.6.1 仿射加密法 132

7.6.2 RSA系统 133

7.6.3 MH系统 134

7.7 典型例题分析 135

习题 136

第8章 代数系统 137

8.1 代数系统的定义 137

8.2 代数系统的性质 138

8.3 代数系统的同态与同构 142

8.4 同余关系 144

8.5 商代数与积代数 145

8.6 半群和独异点 146

8.6.1 半群 146

8.6.2 独异点 147

8.7 群与子群 148

8.7.1 群 148

8.7.2 元素的阶 149

8.7.3 子群 150

8.8 循环群和置换群 151

8.8.1 循环群 151

8.8.2 置换群 153

8.9 陪集和正规子群 156

8.9.1 陪集 156

8.9.2 正规子群 158

8.10 群的同态与同构 159

8.11 环与域 161

8.11.1 环 161

8.11.2 子环与理想 163

8.11.3 域 163

8.11.4 环的同态与同构 165

8.12 典型例题分析 166

习题 170

第9章 格与布尔代数 174

9.1 格的定义与性质 174

9.2 子格与格同态 176

9.3 特殊的格 177

9.4 布尔代数 178

9.5 典型例题分析 181

习题 182

第10章 图 184

10.1 图的基本概念 184

10.1.1 图 184

10.1.2 子图与补图 185

10.1.3 结点的度 186

10.1.4 图的同构 188

10.2 路、回路与连通性 189

10.3 图的矩阵表示 193

10.4 欧拉图与哈密顿图 196

10.4.1 欧拉图 196

10.4.2 哈密顿图 198

10.5 二部图与匹配 200

10.6 平面图 202

10.6.1 平面图的基本概念 202

10.6.2 欧拉公式 203

10.6.3 平面图的判定 204

10.6.4 平面图的对偶图 205

10.7 树及其应用 206

10.7.1 无向树及生成树 206

10.7.2 根树及其应用 209

10.8 着色问题 214

10.8.1 图中结点的着色 214

10.8.2 地图的着色与平面图的点着色 215

10.8.3 边着色 216

10.9 最短路径和关键路径 216

10.9.1 最短路径问题 216

10.9.2 关键路径问题 218

10.10 典型例题分析 220

习题 223

10.11 上机实验 223

第11章 形式语言与自动机简介 229

11.1 语言及其表示 229

11.1.1 语言 229

11.1.2 文法 230

11.1.3 识别器 231

11.2 正规语言与有限自动机 232

11.2.1 确定的有限自动机 232

11.2.2 不确定的有限自动机 235

11.3 上下文无关语言与下推自动机 237

11.3.1 上下文无关语言 238

11.3.2 下推自动机 238

11.3.3 下推自动机与上下文无关语言的关系 240

11.4.1 图灵识别器 241

11.4 图灵机 241

11.4.2 用于计算的图灵机 243

11.5 线性界限自动机 244

11.6 典型例题分析 244

11.7 上机实验 245

习题 245

第12章 纠错码简介 247

12.1 纠错码的基本概念 247

12.2 纠错码的纠错能力 249

12.3 纠错码的选择 251

12.4 群码的校正 255

12.5 典型例题分析 256

12.6 上机实验 258

习题 258

参考文献 259

查看更多关于离散数学的内容