离散数学PDF电子书下载

第1篇 数理逻辑 1

第1章 命题逻辑 1

1．1命题和联结词 1

命题及其表示 1

联结词 2

1．2命题公式和真值表 5

命题公式 5

命题的符号化 6

真值表 7

永真式与永假式 8

1．3等价式 9

1．4蕴涵式 14

1．5联结词的完备集 16

扩充的联结词 16

联结词完备集 18

1．6对偶式 20

1．7范式 22

析取范式与合取范式 22

主析取范式与主合取范式 24

1．8命题演算的推理理论 33

推理的形式结构 33

推理的方法 34

1．9习题 40

第2章 谓词逻辑 45

2．1谓词逻辑的基本概念 45

个体和谓词 45

个体域和量词 47

2．2谓词公式与命题的符号化 49

谓词公式 49

谓词逻辑中命题的符号化 49

变元的约束 51

谓词公式的真值 52

2．3谓词演算的等价式和蕴涵式 54

2．4谓词演算的置换规则 57

2．5前束范式 58

2．6谓词演算的推理理论 60

推理规则 60

推理应用举例 62

2．7习题 64

第2篇 集合论 68

第3章 集合 68

3．1集合的基本概念 68

集合及其元素 68

集合的表示法 69

集合间的关系 70

3．2文氏图与集合的运算 72

文氏图 72

集合的运算 72

3．3集合恒等式 74

3．4集合成员表 77

3．5包含排斥原理 79

3．6习题 81

第4章 关系 84

4．1序偶与笛卡儿积 84

4．2关系及其表示 86

关系的基本概念 86

关系矩阵与关系图 88

4．3关系的运算 89

关系的逆运算 89

关系的复合运算 90

关系的幂运算 94

4．4关系的性质 95

4．5关系的闭包 100

4．6集合的覆盖与划分 104

4．7等价关系与等价类 105

4．8相容关系与相容类 108

4．9次序关系 110

4．10习题 113

第5章 函数 117

5．1基本概念 117

5．2复合函数和逆函数 120

5．3置换与轮换 123

5．4集合的特征函数 125

5．5递归函数 127

5．6集合的基数 129

5．7习题 135

第3篇 代数结构 138

第6章 代数系统 138

6．1运算及其性质 138

6．2代数系统 145

6．3同态与同构 147

6．4同余关系 150

6．5商代数与积代数 153

商代数 153

积代数 156

6．6习题 158

第7章 半群与群 162

7．1半群与独异点 162

7．2群与子群 166

7．3交换群与循环群 171

7．4变换群与置换群 174

7．5陪集、正规子群和商群 176

7．6群的同态与同构 181

7．7习题 182

第8章 环和域 186

8．1环和子环 186

8．2子环与理想 189

8．3域 191

8．4习题 192

第9章 格与布尔代数 193

9．1格 193

偏序集定义的格 193

代数系统定义的格 196

子格与格的同态 198

9．2分配格和有补格 201

分配格 201

有补格 202

9．3布尔代数与布尔表达式 204

布尔代数 204

布尔表达式及其范式定理 205

9．4习题 207

第4篇 图论 209

第10章 图 209

10．1图的基本概念 209

图的定义 209

图的相关术语 211

伪图、多重图和简单图 213

完全图 214

子图 215

图的同构 217

10．2图的连通性 218

通路和回路 218

图的连通性 219

连通度 221

10．3图的矩阵表示 223

关联矩阵 223

邻接矩阵 224

可达矩阵 228

10．4习题 230

第11章 欧拉图与哈密尔顿图 234

11．1欧拉图 234

11．2哈密尔顿图 237

11．3最短通路问题 241

赋权图与最短通路的算法 241

旅行推销员问题 242

11．4习题 243

第12章 特殊图 246

12．1二分图 246

12．2平面图 248

平面图的基本概念 249

欧拉公式 250

平面图的判定 252

对偶图与平面图的着色 253

12．3树 255

无向树及其性质 256

生成树 257

根树及其应用 259

12．4习题 266

参考文献 270