本书在内容安排上由浅入深、循序渐进，在引入概念时力求使用大家熟悉的实例，引入抽象的数学概念，便于初学都对新的抽象的数学概念的学习。为了让读者能够灵活运用有关解题技巧，在每一章都安排了题目并加以解析，使读者举一反三，将知识巩固和深化。

本书系统地介绍了集合论、数理逻辑、图论和代数结构等离散数学的基本知识，在内容安排上突出由浅入深、循序渐进、通俗易懂的特点，非常适合普通高等院校计算机及其相关专业的本科生作为教材使用，也可供一般科技人员作为参考书。

前言

第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  对偶与范式 /38

 2.5.1 对偶 /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章 关系 /80

 4.1 有序对与笛卡尔积 /80

 4.1.1 有序对 /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.4 /94

 4.5 关系的闭包 /94

 4.5.1 关系闭包的概念 /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.3 /131

 5.4 集合的势与无限集合131

 5.4.1 集合的势 /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 图论的应用 /161

 6.5.1 最短路问题 /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章 代数系统 /198

 8.1 二元运算及其性质 /198

 8.1.1 运算 /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.3 /209

 8.4 例题解析 /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.3 /223

 9.4 子群及其特征 /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章 格和布尔代数 /237

 10.1 格 /237

 10.1.1 格的定义 /237

 10.1.2 格的对偶原理和性质239

 习题 10.1 /241

 10.2 格的代数定义 /241

 习题 10.2 /243

 1O.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