离散数学PDF电子书下载

目录 1

前言 1

第1章　预备知识 1

1.1　集合论的初步知识 1

1.1.1　集合的基本概念 1

1.1.2　集合的表示 2

习题1.1 3

1.2 集合的关系与运算 3

1.2.1　集合间的基本关系 3

1.2.2　幂集 5

1.2.3　集合的基本运算 5

1.2.4　文氏图 6

1.2.5　主要的运算律 6

1.2.6　集合运算成员表 8

习题1.2 9

1.3　有限集合中元素的计数 10

1.3.1　文氏图法计数 10

1.3.2　容斥原理 10

习题1.3 12

1.4　整数的基本性质 12

1.4.1　带余除法与整除 12

1.4.2　最大公因数和最小公倍数 14

1.4.3　同余 17

习题1.4 17

1.5　例题解析 17

复习题1 19

第2章　命题逻辑 21

2.1　命题与命题联结词 21

2.1.1　命题 21

2.1.2　命题联结词 22

习题2.1 26

2.2　命题公式及其分类 27

2.2.1　命题公式 27

2.2.2　公式的赋值及分类 28

习题2.2 30

2.3　等价演算 30

2.3.1　基本等价式 30

2.3.2　等价演算 32

习题2.3 34

＊2.4　其他常用联结词及功能完备集 35

2.4.1　其他常用联结词介绍 35

2.4.2　联结词的功能完备集 36

习题2.4 37

2.5.1　对偶 38

2.5　对偶与范式 38

2.5.2　范式 39

2.5.3　主范式 40

习题2.5 44

2.6　推理理论 45

2.6.1　重言蕴含式 45

2.6.2　形式证明 46

习题2.6 49

＊2.7　命题逻辑在门电路中的应用介绍 50

习题2.7 51

2.8　例题解析 51

复习题2 54

第3章　谓词逻辑 57

3.1　谓词逻辑的基本概念 57

3.1.1　个体与谓词 57

3.1.2　量词 58

习题3.1 61

3.2　谓词合式公式及解释 61

3.2.1　谓词公式 62

3.2.2　谓词公式的解释 63

3.2.3　谓词公式的类型 64

习题3.2 65

3.3　谓词逻辑等值式 66

习题3.3 69

3.4　谓词逻辑推理理论 69

习题3.4 73

3.5　例题解析 74

复习题3 78

4.1.1　有序对 80

4.1 有序对与笛卡尔积 80

第4章　关系 80

4.1.2　笛卡尔积 81

习题4.1 82

4.2　关系及其表示 83

4.2.1　关系的基本概念 83

4.2.2　关系矩阵和关系图 84

习题4.2 85

4.3 复合关系与逆关系 86

4.3.1　复合关系 86

4.3.2　复合关系的性质 87

4.3.3　关系的幂和逆关系 88

习题4.3 89

4.4　关系的性质 90

4.5 关系的闭包 94

4.5.1　关系闭包的概念 94

习题4.4 94

4.5.2　关系闭包的求法 95

习题4.5 100

4.6　等价关系 100

4.6.1　集合的划分 100

4.6.2　等价关系 102

4.6.3　等价类 102

习题4.6 105

＊4.7　相容关系 105

4.7.1　相容关系 105

4.7.2　相容类 106

习题4.7 107

4.8　偏序关系 107

4.8.1　偏序关系和拟序关系 107

4.8.2　哈斯图 109

4.8.3　全序关系和良序关系 112

习题4.8 113

4.9　例题解析 113

复习题4 120

第5章　函数 121

5.1 函数的基本概念 121

习题5.1 123

5.2　特殊函数及特征函数 124

5.2.1　特殊函数 124

5.2.2　特征函数 125

习题5.2 127

5.3　逆函数与复合函数 127

5.3.1　逆函数 127

5.3.2　复合函数 128

5.4.1　集合的势 131

5.4　集合的势与无限集合 131

习题5.3 131

5.4.2　可数集 132

习题5.4 134

5.5　例题解析 134

复习题5 136

第6章　图论基础 138

6.1 图的基本概念 138

6.1.1　图的定义及相关概念 139

6.1.2　结点的度 140

6.1.3　完全图和补图 142

6.1.4　子图与图的同构 143

习题6.1 145

6.2　图的连通性 146

6.2.1　通路 146

6.2.2　无向图和有向图的连通性 148

6.2.3　割边和割点 149

习题6.2 149

6.3 图的矩阵表示 150

6.3.1　无向图的关联矩阵 150

6.3.2　无环有向图的关联矩阵 151

6.3.3　有向图的邻接矩阵 151

6.3.4　无向简单图的邻接矩阵 153

6.3.5　有向图的可达矩阵 153

习题6.3 153

6.4　欧拉图与哈密尔顿图 154

6.4.1　欧拉图 154

6.4.2　哈密尔顿图 158

习题6.4 160

6.5.1　最短路问题 161

6.5 图论的应用 161

6.5.2　中国邮递员问题 163

6.5.3　旅行售货员问题 166

习题6.5 168

6.6　例题解析 168

复习题6 171

第7章　特殊图类 174

7.1 树 174

7.1.1　树的定义及性质 174

7.1.2　生成树 176

7.1.3　最小生成树 178

习题7.1 179

7.2　根树 180

7.2.1　根树及相关概念 180

7.2.2　二元树 181

7.2.3　二元树的一个应用——前缀码 183

习题7.2 186

7.3　二部图与匹配 186

7.3.1　二部图的概念及性质 186

7.3.2　二部图的匹配 187

习题7.3 188

7.4 平面图 189

7.4.1　平面图的定义 189

7.4.2　欧拉公式 190

7.4.3　库拉图斯基定理 192

习题7.4 193

7.5　例题解析 194

复习题7 196

8.1　二元运算及其性质 198

8.1.1　运算 198

第8章　代数系统 198

8.1.2　二元运算的性质 199

8.1.3　代数系统的特殊元素 201

习题8.1 203

8.2　代数系统　子代数　积代数 204

8.2.1　代数系统 204

8.2.2　子代数 205

8.2.3　积代数 205

习题8.2 206

8.3 同态与同构 206

8.3.1　同态与同构的概念 206

8.3.2　满同态的性质 207

8.4　例题解析 209

习题8.3 209

复习题8 211

第9章　特殊的代数系统 212

9.1　半群与独异点 212

9.1.1　半群 212

9.1.2　独异点 213

习题9.1 214

9.2　群的定义与性质 215

9.2.1　群的定义 215

9.2.2　群的性质 216

9.2.3　群的同态 217

习题9.2 218

9.3　循环群与置换群 218

9.3.1　循环群 218

9.3.2　置换群 220

9.4　子群及其特征 223

习题9.3 223

习题9.4 224

＊9.5　陪集　正规子群和商群 225

9.5.1　子群的陪集 225

9.5.2　正规子群 227

9.5.3　商群 228

习题9.5 229

＊9.6　环和域 229

9.6.1　环的定义及其性质 229

9.6.2　子环 231

9.6.3　整环和域 232

习题9.6 234

9.7　例题解析 234

复习题9 235

10.1.1　格的定义 237

10.1　格 237

第10章　格和布尔代数 237

10.1.2　格的对偶原理和性质 239

习题10.1 241

10.2　格的代数定义 241

习题10.2 243

10.3　特殊的格 243

10.3.1　分配格 243

10.3.2　有界格和有补格 244

10.3.3　有补分配格 246

习题10.3 246

10.4　布尔代数 247

习题10.4 249

10.5　例题解析 249

复习题10 251

参考文献 252