本书系统地介绍了计算机科学与技术等相关专业所必需的离散数学知识。全书共8章。第1章介绍命题及命题逻辑，第2章介绍谓词逻辑及其推理理论，第3章介绍集合与关系的基本概念和性质，第4章介绍函数，第5章介绍代数系统，第6章介绍格与布尔代数，第7章介绍图论的基本概念及其性质，第8章介绍离散数学在计算机科学中的一些具体应用。

本书适合作为高等学校计算机专业及相关专业的本科生教材，也可以供对离散数学有兴趣的读者自学。

离散数学是现代数学的重要分支，也是计算机科学的重要理论基础。离散数学作为应用计算机求解实际问题的重要工具，在离散建模中具有重要的意义。随着计算机技术的日益普及，越来越多的行业开始采用计算机解决实际问题，学习和掌握离散建模的重要性日益凸显。学好离散数学，不仅能为计算机相关专业的学生后续课程的学习打下坚实的基础，也能培养学生的逻辑推理和抽象思维能力，为学生今后从事相关专业的学习和工作打下坚实的数学基础。

离散数学的主要研究对象是计算机相关学科中离散量的结构及其相互关系。本书主要包括数理逻辑、集合与函数、代数系统及布尔代数、图论等主要内容，内容涵盖计算机科学技术中常用的离散结构的数学基础。本书在注重离散数学体系的基础上，强化证明思想和方法的介绍，在讲解基本内容及基本概念的时候尽可能结合实例，重视理论和方法的实用性。本书除在每章中增加了一些实例的讲解和习题之外，还专门在第8章讨论了数理逻辑、集合论、代数系统以及图论在计算机科学中的应用。

本书系统地介绍了计算机科学与技术等相关专业所必需的离散数学知识。全书共8章，第1章介绍命题及命题逻辑，第2章介绍谓词逻辑及其推理理论，第3章介绍集合与关系的基本概念和性质，第4章介绍函数，第5章介绍代数系统，第6章介绍格与布尔代数，第7章介绍图论的基本概念及其性质，第8章介绍离散数学在计算机科学中的一些具体应用。

本书适合作为高等学校计算机专业及相关专业的本科生教材，也可以供对离散数学有兴趣的读者自学。

限于作者水平，书中不当之处在所难免，恳请读者批评指正。

编者[]2013年8月

第1章命题逻辑1

1.1命题及联结词1

1.1.1命题的概念1

1.1.2原子命题和复合命题3

1.1.3联结词3

1.2命题的合式公式和翻译6

1.2.1命题公式6

1.2.2命题公式的翻译7

1.2.3真值表8

1.3公式的等价和蕴含10

1.3.1永真式、永假式和可满足式10

1.3.2等价式和常用的等价式10

1.4全功能联结词集合13

1.5对偶与范式14

1.5.1对偶定义14

1.5.2对偶定理14

1.5.3析取范式和合取范式15

1.5.4主析取范式和主合取范式16

1.6推理理论20

1.6.1蕴含式20

1.6.2有效结论21

1.6.3证明方法21

本章小结26

习题26

第2章谓词逻辑31

2.1谓词的概念与表示31

2.1.1谓词31[][]◆[]离散数学[][]2.1.2命题函数32

2.1.3量词33

2.2谓词公式与翻译34

2.2.1谓词的合式公式34

2.2.2谓词的翻译34

2.2.3自由变元和约束变元35

2.3谓词演算的等价式和蕴含式36

2.4前束范式39

2.5谓词演算的推理理论39

本章小结42

习题43

第3章集合与关系45

3.1集合的概念和表示45

3.1.1集合与元素45

3.1.2集合的表示46

3.1.3集合与集合的关系47

3.2集合的运算50

3.2.1交运算50

3.2.2并运算51

3.2.3相对补与绝对补51

3.2.4对称差52

3.2.5集合运算中的恒等式52

3.2.6包含排斥原理54

3.3序偶与笛卡儿积56

3.3.1序偶56

3.3.2笛卡儿积57

3.4关系及其表示59

3.4.1关系的引入59

3.4.2关系的定义59

3.4.3二元关系59

3.4.4关系的表示法60

3.5关系的性质62

3.5.1自反性与反自反性62

3.5.2对称性与反对称性64

3.5.3传递性65

3.6关系的运算66

3.6.1关系的交、并、补、差运算66

3.6.2关系的复合运算67

3.6.3关系的逆运算69

3.7关系的闭包运算71

3.8等价关系74

3.8.1等价关系的定义74

3.8.2等价类与商集75

3.8.3集合的划分76

3.8.4等价关系与划分77

3.9偏序关系78

3.9.1偏序关系的定义78

3.9.2偏序关系的哈斯图78

3.9.3偏序集中的特殊元素80

3.9.4全序与良序80

本章小结81

习题81

第4章函数91

4.1函数的概念91

4.2函数的性质94

4.3函数的运算95

4.3.1函数的复合运算95

4.3.2函数的逆运算96

本章小结96

习题97

第5章代数系统99

5.1代数系统概述99

5.1.1代数运算及其性质99

5.1.2代数系统的定义103

5.2半群和独异点104

5.2.1半群104

5.2.2独异点105

5.2.3可交换半群和循环半群106

5.3群107

5.3.1群的定义107

5.3.2群的性质108

5.3.3子群108

5.4特殊的群109

5.4.1交换群109

5.4.2循环群110

5.5陪集和拉格朗日定理110

5.5.1陪集110

5.5.2拉格朗日定理112

5.6同态和同构113

5.6.1同态113

5.6.2同构114

5.6.3群的同态和同构115

5.7环和域116

5.7.1环116

5.7.2子环和理想117

5.7.3域118

本章小结119

习题120

第6章格与布尔代数122

6.1格的概念122

6.2特殊格127

6.3布尔代数131

6.4本章小结135

习题136

第7章图论138

7.1图的基本概念138

7.1.1图的定义138

7.1.2无向图和有向图139

7.1.3顶点度数和握手定理141

7.1.4子图和补图143

7.1.5图的同构144

7.2通路与回路145

7.2.1通路与回路的定义145

7.2.2无向连通图146

7.2.3点割集和割点147

7.2.4边割集和割边147

7.2.5连通分图147

7.3图的矩阵表示150

7.3.1邻接矩阵和关联矩阵150

7.3.2可达矩阵153

7.4特殊图155

7.4.1欧拉图155

7.4.2哈密尔顿图158

7.5平面图160

7.5.1平面图的定义161

7.5.2欧拉公式162

7.5.3平面图的判断165

7.6对偶图与着色166

7.6.1对偶图166

7.6.2点着色168

7.7树与生成树170

7.7.1无向树的概念170

7.7.2生成树与最小生成树172

7.8有向树及其应用175

7.8.1有向树的概念175

7.8.2最优树177

7.8.3前缀码179

7.9本章小结182

习题182

第8章离散数学在计算机科学中的应用189

8.1谓词逻辑在计算机科学中的应用189

8.1.1谓词逻辑在程序设计中的应用189

8.1.2谓词逻辑与数据子语言191

8.1.3谓词逻辑与逻辑程序设计语言192

8.1.4谓词逻辑在人工智能中的应用193

8.2集合论在计算机科学中的应用194

8.2.1关系在关系数据库中的应用194

8.2.2关系代数与数据子语言196

8.2.3等价关系在计算机中的应用197

8.2.4序关系在项目管理中的应用197

8.3代数系统在计算机科学中的应用198

8.3.1布尔代数与逻辑电路设计198

8.3.2半群与形式语言201

8.3.3纠错码202

8.4图论在计算机科学中的应用207

8.4.1二叉树在搜索算法中的应用207

8.4.2图论在形式语言的应用209

8.4.3图论在有限状态自动机中的应用210

习题211