离散数学及其应用PDF电子书下载

第1章　命题逻辑 1

1.1　命题及其表示 1

1.1.1　命题的基本概念 1

1.1.2　命题分类 2

1.1.3　命题标识符 2

习题1.1 2

1.2　逻辑联结词 2

1.2.1　否定联结词 3

1.2.2　合取联结词 3

1.2.3　析取联结词 3

1.2.4　条件联结词 4

1.2.5　双条件联结词 4

习题1.2 5

1.3　命题公式与翻译 5

1.3.1　命题公式 5

1.3.2　命题的符号化 6

习题1.3 7

1.4　真值表与等价公式 8

1.4.1　真值表 8

1.4.2　等价公式 9

习题1.4 13

1.5　命题公式的分类与蕴含式 13

1.5.1　命题公式的分类 13

1.5.2　重言式与矛盾式的性质 14

1.5.3　蕴含式 14

习题1.5 16

1.6　其他逻辑联结词和最小功能完备联结词组 17

1.6.1　其他逻辑联结词 17

1.6.2　最小功能完备联结词组 18

习题1.6 19

1.7　对偶与范式 19

1.7.1　对偶式与对偶原理 19

1.7.2　命题公式的范式 20

1.7.3　命题公式的主析取范式和主合取范式 22

习题1.7 30

1.8　推理理论 30

1.8.1　直接证法 31

1.8.2　间接证法 33

习题1.8 35

第2章　谓词逻辑 36

2.1　谓词的概念与表示 36

2.1.1　个体和谓词 36

2.1.2　量词 38

习题2.1 39

2.2　谓词公式与翻译 39

2.2.1　谓词公式 39

2.2.2　谓词公式的翻译 39

习题2.2 41

2.3　变元的约束 41

习题2.3 43

2.4　谓词演算的等价式与蕴含式 43

2.4.1　谓词公式的赋值 43

2.4.2　谓词公式的分类 44

2.4.3　谓词演算的等价式 45

2.4.4　谓词演算的蕴含式 48

习题2.4 50

2.5　谓词公式范式 50

2.5.1　前束范式 50

2.5.2　前束析取范式和前束合取范式 52

2.5.3　斯柯林范式 53

习题2.5 53

2.6　谓词演算的推理理论 53

习题2.6 58

第3章　集合与关系 59

3.1　集合的基本概念 59

3.1.1　集合与元素 59

3.1.2　集合间的关系 60

3.1.3　幂集 61

习题3.1 62

3.2　集合的运算 63

3.2.1　集合的交与并 63

3.2.2　集合的差与补 65

3.2.3　集合的对称差 67

习题3.2 69

3.3　包含排斥原理 70

3.4　序偶与笛卡尔积 73

3.4.1　序偶 73

3.4.2　笛卡尔积 74

习题3.4 76

3.5　关系及其表示 76

3.5.1　关系的定义 76

3.5.2　几种特殊的关系 77

3.5.3　关系的表示 78

习题3.5 80

3.6　关系的性质及其判定方法 80

3.6.1　关系的性质 80

3.6.2　由关系图、关系矩阵判别关系的性质 82

习题3.6 83

3.7　复合关系和逆关系 84

3.7.1　复合关系 84

3.7.2　复合关系的矩阵表示及图形表示 86

3.7.3　逆关系 87

习题3.7 89

3.8　关系的闭包运算 90

习题3.8 95

3.9　等价关系与相容关系 96

3.9.1　集合的划分和覆盖 96

3.9.2　等价关系与等价类 97

3.9.3　相容关系 102

习题3.9 104

3.10　偏序关系 105

3.10.1　偏序关系的定义 105

3.10.2　偏序关系的哈斯图 105

3.10.3　偏序集中特殊位置的元素 107

3.10.4　两种特殊的偏序集 109

习题3.10 110

第4章　映射 111

4.1　映射的概念 111

习题4.1 114

4.2　特殊映射 115

习题4.2 116

4.3　复合映射和逆映射 117

4.3.1　复合映射 117

4.3.2　逆映射 120

习题4.3 121

4.4　置换 122

习题4.4 123

4.5　特征函数 124

习题4.5 125

4.6　基数 126

4.6.1　无限集合 126

4.6.2　基数的概念 126

4.6.3　可数集与不可数集 128

习题4.6 130

第5章　代数结构 131

5.1　代数系统的概念 131

5.1.1　n元运算 131

5.1.2　代数系统的概念 133

习题5.1 134

5.2　二元运算 135

5.2.1　二元运算的性质 135

5.2.2　集合A的关于二元代数运算的特异元素 139

5.2.3　利用运算表判断代数运算的性质 143

习题5.2 144

5.3　半群 145

5.3.1　半群及其性质 145

5.3.2　含幺半群及其性质 148

习题5.3 149

5.4　群与子群 151

5.4.1　群的基本概念 151

5.4.2　群的基本性质 152

5.4.3　群的元素的阶 155

5.4.4　子群 156

习题5.4 158

5.5　阿贝尔群和循环群 159

5.5.1　阿贝尔群 159

5.5.2　循环群 159

5.5.3　置换群 161

习题5.5 162

5.6　代数系统的同态与同构 162

习题5.6 166

5.7　拉格朗日定理与同态基本定理 167

5.7.1　陪集与拉格朗日定理 168

5.7.2　正规子群、商群和同态基本定理 171

习题5.7 174

5.8　环与域 174

5.8.1　环 174

5.8.2　域 176

习题5.8 178

5.9　群在编码理论中的应用 178

习题5.9 184

第6章　格与布尔代数 185

6.1　格的概念及性质 185

6.1.1　格的概念 185

6.1.2　格的性质 188

习题6.1 194

6.2　分配格与模格 195

6.2.1　分配格 195

6.2.2　模格 197

习题6.2 198

6.3　有界格与有补格 199

6.3.1　有界格 199

6.3.2　有补格 200

习题6.3 201

6.4　布尔代数 202

6.4.1　布尔代数的概念 202

6.4.2　布尔代数的性质 203

6.4.3　子布尔代数 206

6.4.4　布尔代数的同态与同构 207

6.4.5　有限布尔代数的原子表示 209

习题6.4 212

6.5　布尔表达式与布尔函数 214

6.5.1　布尔表达式 214

6.5.2　布尔函数 219

习题6.5 220

6.6　布尔函数在电路设计中的应用 221

习题6.6 222

第7章　图论 223

7.1　图的基本概念 223

7.1.1　图 223

7.1.2　补图与子图 226

7.1.3　节点的度数 228

7.1.4　图的同构 229

习题7.1 231

7.2　路与图的连通性 232

7.2.1　路与回路 232

7.2.2　图的连通性 234

习题7.2 238

7.3　图的矩阵表示 239

7.3.1　邻接矩阵 239

7.3.2　可达性矩阵 241

7.3.3　完全关联矩阵 243

习题7.3 244

7.4　欧拉图与汉密尔顿图 245

7.4.1　欧拉图 245

7.4.2　汉密尔顿图 248

习题7.4 252

7.5　二部图及匹配 253

7.5.1　二部图 253

7.5.2　匹配 255

习题7.5 259

7.6　平面图 259

7.6.1　平面图的定义 259

7.6.2　欧拉公式 261

7.6.3　平面图的着色 264

习题7.6 267

7.7　树与生成树 268

7.7.1　无向树 268

7.7.2　无向图中的生成树与最小生成树 270

习题7.7 273

7.8　根树及其应用 274

7.8.1　有向树 274

7.8.2　m叉树 275

7.8.3　最优二叉树 278

7.8.4　二叉树在计算机中的应用 278

习题7.8 283

7.9　最短路问题 283

7.9.1　问题的提出 283

7.9.2　Dijkstra算法（双标号法） 284

7.9.3　无向图上的Dijkstra算法 286

习题7.9 286

参考文献 287