离散数学PDF电子书下载

第1篇 数理逻辑 1

第1章 命题逻辑 1

1-1命题与联结词 1

1-1-1命题 1

1-1-2联结词 2

1-2命题公式及其赋值 5

1-2-1命题公式 5

1-2-2命题公式的真值表 6

1-2-3语句的形式化 8

1-3重言式 9

1-3-1重言式 10

1-3-2等价式 10

1-3-3蕴含式 13

1-4对偶与范式 16

1-4-1对偶 16

1-4-2范式 17

1-4-3联结词完备集 23

1-5推理理论 26

1-6小结 29

习题 30

第2章 谓词逻辑 32

2-1谓词逻辑基本概念 32

2-1-1个体和谓词 32

2-1-2量词 34

2-1-3谓词公式及语句的符号化 35

2-2谓词逻辑永真式 38

2-2-1公式的解释 38

2-2-2谓词演算永真式 39

2-3谓词公式的前束范式 42

2-4谓词演算推理理论 43

2-5消解原理 48

2-5-1化为子句集 48

2-5-2消解推理规则 49

2-5-3含有变量的消解式 51

2-5-4消解反演求解过程 52

2-3小结 56

习题 57

第2篇 集合论 59

第3章 集合 59

3-1集合的概念与表示 59

3-1-1集合及其元素 59

3-1-2集合的表示 60

3-1-3集合之间的关系 61

3-2集合的基本运算 63

3-2-1集合的交、并、补及对称差 63

3-2-2证明集合相等的方法 67

3-3集合的笛卡儿积运算 68

3-4有限集合中元素的计数 71

3-4-1鸽笼原理 71

3-4-2容斥原理 71

3-5集合的覆盖与划分 73

3-6小结 74

习题 75

第4章 关系 77

4-1n元组与关系 77

4-1-1关系的基本概念 77

4-1-2二元关系的表示 78

4-2二元关系的性质与类型 80

4-2-1自反性与反自反性 80

4-2-2对称性与反对称性 81

4-2-3传递性 81

4-2-4关系性质的等价描述 82

4-2-5关系性质的证明 83

4-3关系的运算 84

4-3-1关系的基本运算 84

4-3-2关系的复合运算 84

4-3-3关系的逆运算 86

4-3-4利用关系矩阵求解复合关系 87

4-4关系的闭包运算 89

4-4-1特性闭包 89

4-4-2特性闭包的求解 90

4-5等价关系 94

4-5-1等价关系与等价类 95

4-5-2等价关系与划分 96

4-6相容关系 97

4-6-1相容关系与最大相容类 98

4-6-2相容关系与完全覆盖 99

4-7偏序关系 100

4-7-1偏序关系与盖住关系 100

4-7-2偏序集上的特殊元素 101

4-7-3全序关系与良序关系 102

4-8小结 103

习题 104

第5章 函数 106

5-1函数的定义 106

5-2函数的性质 108

5-3函数的逆运算与复合运算 109

5-3-1函数的逆运算与逆函数 109

5-3-2函数的复合运算与复合函数 110

5-3-3特殊函数 111

5-4特征函数与一致性函数 112

5-5有限集和无限集 114

5-5-1有限集、可数集与不可数集 115

5-5-2无限集的特性 118

5-6基数 119

5-6-1有限集、可数无限集和连续统的基数 119

5-6-2基数比较 120

5-7小结 122

习题 123

第3篇 代数系统 124

第6章 代数系统 124

6-1代数系统的基本概念 124

6-1-1代数运算 124

6-1-2代数运算的基本性质 125

6-1-3代数系统的定义 126

6-2代数系统的同态与同构 131

6-2-1同态与同构 131

6-2-2同态与同构的基本性质 132

6-3小结 133

习题 134

第7章 群、环、域 136

7-1半群与独异点 136

7-1-1半群与独异点的概念 136

7-1-2半群的基本性质 136

7-1-3子半群与半群的同态 137

7-2群与子群 139

7-2-1群的基本概念 139

7-2-2群的基本性质 140

7-2-3子群 142

7-3陪集与拉格朗日定理 144

7-3-1陪集定义及基本性质 144

7-3-2拉格朗日定理及其应用 146

7-4正规子群与商群 147

7-4-1正规子群的定义及实例 147

7-4-2商群 148

7-5群的同态与同构 149

7-5-1基本概念 149

7-5-2同态映射的性质 150

7-5-3同态基本定理 151

7-6特殊群 152

7-6-1交换群 153

7-6-2循环群 153

7-7环和域 155

7-7-1环 155

7-7-2域 156

7-8小结 158

习题 158

第8章 格与布尔代数 160

8-1格 160

8-1-1格的定义 160

8-1-2格的对偶原理与格的基本性质 163

8-1-3格的同态与同构 163

8-2特殊格 165

8-2-1分配格 165

8-2-2模格 167

8-2-3有界格 167

8-2-4有补格 168

8-3布尔代数与布尔表达式 169

8-3-1布尔代数 169

8-3-2布尔表达式 171

8-4小结 173

习题 174

第4篇 图论 175

第9章 图 175

9-1图的基本概念 175

9-1-1图的定义 175

9-1-2结点的度数 178

9-1-3子图与补图 179

9-1-4图的同构 180

9-1-5图的操作 181

9-2通路、回路与连通性 182

9-2-1通路与回路 182

9-2-2无向图的连通性 184

9-2-3有向图的连通性 186

9-3图的矩阵表示 189

9-3-1邻接矩阵 189

9-3-2可达性矩阵 194

9-3-3完全关联矩阵 197

9-4小结 199

习题 200

第10章 特殊图 202

10-1二部图 202

10-1-1二部图的基本概念 202

10-1-2匹配 203

10-2欧拉图与汉密尔顿图 205

10-2-1欧拉图 205

10-2-2汉密尔顿图 207

10-3平面图 211

10-4对偶图与图的着色 215

10-4-1对偶图 216

10-4-2图的着色 216

10-5树与生成树 220

10-5-1无向树 220

10-5-2生成树 222

10-5-3最小生成树 223

10-6根树及其应用 225

10-6-1有向树与根树 225

10-6-2有序树、最优树与二叉树 227

10-6-3前缀码问题 230

10-7小结 232

习题 233

附录A 初等数论 234

附录B 计数原理 242

参考文献 252