离散数学

目录

绪论离散数学与计算机1

**部分集合论

第1章集合7

1.1集合的概念与表示7

1.1.1集合的概念7

1.1.2集合的元素8

1.1.3集合的表示方法8

1.1.4集合之间的关系10

习题1.111

1.2集合的运算12

1.2.1交运算12

1.2.2并运算12

1.2.3补运算13

1.2.4差运算14

1.2.5对称差运算14

习题1.215

1.3集合的划分与覆盖16

1.3.1集合的划分16

1.3.2集合的覆盖17

习题1.317

1.4容斥原理18

习题1.421

1.5集合的思维导图22

1.6集合的算法思想23

1.6.1求任意一个集合的幂集23

1.6.2求任意两个集合的交集、并集、差集23

1.7本章小结23〖1〗〖2〗离散数学目录〖2〗〖2〗第2章关系24

2.1有序n元组24

习题2.125

2.2笛卡儿积25

2.2.1笛卡儿积的定义25

2.2.2笛卡儿积的性质27

习题2.229

2.3二元关系30

2.3.1二元关系的概念30

2.3.2二元关系的表示32

习题2.333

2.4关系的运算34

2.4.1关系的集合运算34

2.4.2关系的复合运算35

2.4.3关系的逆运算37

习题2.437

2.5关系的性质38

2.5.1自反性39

2.5.2反自反性40

2.5.3对称性42

2.5.4反对称性43

2.5.5传递性44

习题2.549

2.6关系的闭包50

2.6.1自反闭包r(R)50

2.6.2对称闭包s(R)51

2.6.3传递闭包t(R)52

2.6.4闭包之间的关系54

习题2.655

2.7等价关系和等价类56

2.7.1等价关系56

2.7.2等价类57

习题2.760

2.8相容关系和相容类61

2.8.1相容关系61

2.8.2相容类62

习题2.864

2.9偏序关系64

2.9.1偏序关系的定义64

2.9.2哈斯图及特殊元素65

2.9.3全序关系70

2.9.4良序关系71

2.9.5拟序关系71

习题2.971

2.10关系的思维导图73

2.11关系的算法思想74

2.11.1求任意个元素的全排列74

2.11.2求笛卡儿积74

2.11.3判断关系性质及类型算法74

2.11.4求等价类75

2.11.5求极大相容类75

2.11.6求关系的闭包75

2.12本章小结76

第3章映射77

3.1映射的基本概念77

习题3.179

3.2映射的性质80

3.2.1单射80

3.2.2满射80

3.2.3双射81

习题3.282

3.3映射的复合运算82

习题3.384

3.4映射的逆运算85

习题3.486

3.5映射的思维导图87

3.6映射的算法思想87

3.6.1映射的判定87

3.6.2求满射88

3.7本章小结88

第二部分数 理 逻 辑

第4章命题逻辑91

4.1命题91

习题4.193

4.2联结词94

4.2.1否定联结词??瘙綈94

4.2.2合取联结词∧（与）95

4.2.3析取联结词∨（或）95

4.2.4不可兼析取联结词∨（异或）96

4.2.5条件联结词→97

4.2.6双条件联结词98

4.2.7与非联结词↑98

4.2.8或非联结词↓98

4.2.9条件否定联结词n99

4.2.10联结词与集合运算之间的关系99

习题4.2101

4.3命题公式101

4.3.1命题公式的定义101

4.3.2命题公式的符号化102

4.3.3命题公式的解释104

4.3.4命题公式的真值表105

4.3.5命题公式的类型106

习题4.3106

4.4命题公式的逻辑等值107

4.4.1命题公式逻辑等值的定义107

4.4.2命题公式基本的逻辑等值式108

4.4.3命题公式的等值演算110

4.4.4命题公式的对偶定理113

习题4.4113

4.5范式114

4.5.1析取范式与合取范式114

4.5.2主析取范式与主合取范式116

4.5.3主范式的应用122

习题4.5124

4.6命题公式的逻辑蕴涵125

4.6.1逻辑蕴涵的定义125

4.6.2蕴涵式的证明方法126

4.6.3基本的逻辑蕴涵式128

习题4.6129

4.7全功能联结词与极小联结词组129

习题4.7130

4.8命题逻辑推理131

4.8.1命题逻辑推理理论131

4.8.2推理规则131

4.8.3判断有效结论的常用方法133

习题4.8137

4.9命题逻辑的思维导图138

4.10命题逻辑的算法思想——求任意一个命题公式的真值表139

4.11本章小结140

第5章谓词逻辑141

5.1谓词逻辑的相关概念141

5.1.1个体词与谓词141

5.1.2量词143

习题5.1144

5.2谓词公式145

5.2.1谓词公式的定义145

5.2.2谓词公式的符号化146

5.2.3谓词的约束与替换148

5.2.4谓词公式的解释151

5.2.5谓词公式的类型152

习题5.2153

5.3谓词公式的逻辑等值154

5.3.1谓词公式逻辑等值的定义154

5.3.2谓词公式基本的逻辑等值式155

习题5.3158

5.4谓词公式的前束范式158

5.4.1谓词公式前束范式的定义158

5.4.2谓词公式前束范式的计算159

习题5.4160

5.5谓词公式的逻辑蕴涵160

习题5.5163

5.6谓词逻辑的推理164

5.6.1谓词逻辑中的逻辑蕴涵式164

5.6.2谓词逻辑的推理规则164

5.6.3谓词逻辑的自然推理系统165

习题5.6168

5.7谓词逻辑的思维导图169

5.8本章小结170

第三部分图论

第6章图173

6.1图的基本概念173

6.1.1图174

6.1.2子图176

6.1.3通路与回路177

6.1.4图的同构179

习题6.1180

6.2结点的度181

6.2.1结点的度的概念181

6.2.2握手定理及其推论181

习题6.2182

6.3图的连通性183

6.3.1无向图的连通性183

6.3.2有向图的连通性186

习题6.3188

6.4图的矩阵表示189

6.4.1邻接矩阵189

6.4.2可达矩阵190

6.4.3关联矩阵193

习题6.4195

6.5图的应用196

6.5.1加权图的*短通路196

6.5.2加权图的关键路径200

习题6.5202

6.6图的思维导图203

6.7图的算法思想204

6.7.1图的可达矩阵算法204

6.7.2有向图的所有强分支算法204

6.7.3有向图的所有单向分支算法204

6.7.4图的所有割点算法205

6.7.5图的所有割边算法205

6.7.6发点到其他各点的所有*短通路算法206

6.7.7求两点间*短通路的WarshallFloyd算法207

6.7.8图的所有关键路径算法207

6.8本章小结208

第7章欧拉图与哈密尔顿图209

7.1欧拉图209

7.1.1欧拉图的定义209

7.1.2欧拉图的判定210

7.1.3欧拉图的应用212

习题7.1215

7.2哈密尔顿图216

7.2.1哈密尔顿图的定义216

7.2.2哈密尔顿图的判定217

7.2.3哈密尔顿图的应用220

习题7.2221

7.3欧拉图和哈密尔顿图的思维导图223

7.4欧拉图和哈密尔顿图的算法思想224

7.4.1求欧拉回路的算法224

7.4.2判断一个图是否为哈密尔顿图224

7.5本章小结225

第8章特殊图226

8.1树226

8.1.1无向树226

8.1.2生成树与*小生成树228

8.1.3有向树与根树232

8.1.4k叉树与有序树233

习题8.1238

8.2二部图239

8.2.1二部图的概念239

8.2.2二部图的匹配241

习题8.2243

8.3平面图244

8.3.1平面图的概念244

8.3.2欧拉公式245

8.3.3平面图的判定247

8.3.4平面图的着色248

习题8.3253

8.4特殊图的思维导图254

8.5特殊图的算法思想255

8.5.1求Huffman树255

8.5.2求无（有）向图的生成树的算法256

8.5.3求*小生成树的两种算法: Kruskal算法、Prim算法256

8.5.4广度优先搜索算法257

8.5.5深度优先搜索算法257

8.5.6二叉树的遍历258

8.5.7二部图的所有完备匹配算法259

8.5.8图的着色算法259

8.6本章小结259

第四部分代 数 系 统

第9章代数结构263

9.1代数系统的定义263

9.1.1代数运算263

9.1.2代数系统266

习题9.1267

9.2代数系统的性质267

9.2.1交换律267

9.2.2结合律268

9.2.3分配律268

9.2.4吸收律268

9.2.5幂等律269

9.2.6单位元（幺元）269

9.2.7零元270

9.2.8逆元270

9.2.9消去律272

习题9.2274

9.3代数系统的同态与同构275

习题9.3278

9.4半群与独异点279

9.4.1半群279

9.4.2独异点280

习题9.4282

9.5群283

9.5.1群的定义283

9.5.2群的性质285

习题9.5286

9.6子群287

9.6.1子群的定义287

9.6.2子群的判定287

习题9.6289

9.7特殊的群289

9.7.1阿贝尔群289

9.7.2循环群291

9.7.3置换群293

习题9.7296

9.8群的同态与同构297

习题9.8299

9.9代数系统的思维导图300

9.10代数系统的算法思想301

9.11本章小结301

第10章环与域302

10.1环302

10.1.1环的概念302

10.1.2子环与理想305

10.1.3环的同态与同构306

习题10.1307

10.2域307

10.2.1域的概念307

10.2.2有限域309

10.2.3域的同态与同构309

习题10.2310

10.3环与域的思维导图311

10.4本章小结312

第11章格与布尔代数313

11.1格的定义和性质313

11.1.1格的定义313

11.1.2格的对偶原理314

11.1.3格的性质315

习题11.1316

11.2子格与格同态317

11.2.1子格317

11.2.2格同态与格同构317

习题11.2318

11.3几种特殊的格319

11.3.1分配格319

11.3.2模格321

11.3.3有界格321

11.3.4有补格322

习题11.3323

11.4布尔代数324

11.4.1布尔代数的定义324

11.4.2布尔代数的性质325

11.4.3布尔代数的同态与同构326

习题11.4328

11.5格与布尔代数的思维导图329

11.6本章小结330

附录1符号索引331

附录2相关数学概念336