目 录

第1章集合及其运算1

1.1集合1

1.1.1集合的概念1

1.1.2集合的表示2

1.1.3集合的分类3

1.2子集、集合的相等4

1.2.1子集4

1.2.2集合的相等5

1.2.3幂集6

1.3集合的基本运算8

1.3.1并运算8

1.3.2交运算11

1.3.3差运算13

1.3.4对称差运算14

1.3.5求补运算、德·摩根公式15

1.4笛卡儿乘积运算17

1.4.1序对17

1.4.2笛卡儿乘积的定义18

1.4.3n元组18

1.5有穷集合的基数19

1.5.1映射20

1.5.2有穷集合的基数的定义20

1.5.3计数法则20

1.5.4容斥原理21

1.6逻辑与证明24

1.6.1数理逻辑简介24

1.6.2公理系统25

1.6.3命题逻辑26

1.6.4谓词逻辑27

1.6.5推理与证明29

1.7习题选解32

1.7.1建立语言的数学模型32

1.7.2证明集合相等34

1.7.3建立数学模型35

1.8本章小结37

习题38第2章映射40

2.1函数的一般概念——映射40

2.1.1函数概念的回顾40

2.1.2映射的定义41

2.1.3有穷集合间的映射42

2.2抽屉原理44

2.2.1抽屉原理的形式44

2.2.2抽屉原理的应用44

2.3映射的一般性质46

2.3.1导出映射46

2.3.2映射的一般性质及其证明46

2.4映射的合成48

2.4.1映射的合成的定义49

2.4.2合成运算的性质49

2.5逆映射50

2.5.1逆映射的存在条件及其唯一性51

2.5.2左(右)可逆映射51

2.6置换52

2.6.1置换的定义52

2.6.2置换的乘积53

2.6.3循环置换与对换53

2.6.4置换的循环置换分解54

2.6.5奇置换和偶置换55

2.7序列、矩阵与运算56

2.7.1序列56

2.7.2矩阵56

2.7.3运算57

2.7.4代数结构58

2.8集合的特征函数59

2.8.1特征函数59

2.8.2集合在计算机中的存储60

2.9习题选解61

2.9.1再论集合相等61

2.9.2利用映射建立数学模型62

2.9.3抽屉原理的应用64

2.9.4映射的性质67

2.9.5置换69

2.10本章小结69

习题69第3章关系71

3.1关系的概念71

3.1.1关系的等价定义71

3.1.2n元关系与关系数据库73

3.2几种特殊的二元关系74

3.2.1自反关系、反自反关系74

3.2.2对称关系、反对称关系74

3.2.3传递关系75

3.2.4相容关系、关系的计数75

3.3关系的运算76

3.3.1关系的集合运算76

3.3.2关系的合成运算77

3.3.3关系合成运算的性质77

3.4二元关系的传递闭包79

3.4.1二元关系的传递闭包、自反传递闭包79

3.4.2传递闭包的性质79

3.4.3迷宫问题81

3.5关系矩阵与关系图81

3.5.1关系矩阵81

3.5.2(0,1)矩阵的运算82

3.5.3Warshall算法82

3.5.4关系的图83

3.6等价关系与集合的划分83

3.6.1等价关系83

3.6.2等价类84

3.6.3集合的划分85

3.6.4等价关系与集合划分互相确定86

3.6.5从等价关系看线性代数87

3.6.6等价闭包与等价关系的合成87

3.7映射按等价关系分解88

3.7.1由映射确定的等价关系与集合划分88

3.7.2商集、自然映射88

3.7.3映射按等价关系分解89

3.7.4与映射相容的等价关系89

3.8偏序关系与偏序集90

3.8.1偏序关系与偏序集的定义90

3.8.2Hasse图91

3.8.3上(下)界、最大(小)元素、上(下)确界91

3.8.4链与反链93

3.9习题选解95

3.9.1利用关系建立数学模型95

3.9.2二元关系的概念97

3.9.3二元关系的闭包98

3.9.4二元关系与映射99

3.9.5等价关系和偏序关系101

3.10本章小结102

习题102第4章无穷集合及其基数104

4.1可数集104

4.1.1关于无穷104

4.1.2可数集的定义105

4.1.3可数集的性质105

4.1.4无穷集合107

4.2连续统集108

4.2.1康托对角线法108

4.2.2连续统109

4.2.3连续统的性质109

4.2.4例题111

4.3基数及其比较112

4.3.1基数的定义112

4.3.2基数的比较113

4.3.3连续统假设113

4.3.4康托定理113

4.4康托伯恩斯坦定理114

4.4.1问题114

4.4.2康托伯恩斯坦定理的定义114

4.4.3选择公理116

4.4.4基数的算术运算116

4.5公理化集合论117

4.5.1直觉集合论中一些著名的悖论117

4.5.2一些非数学上的悖论118

4.5.3公理集合论简介118

4.6图灵机、可计算性与计算复杂性120

4.6.1图灵机产生的背景120

4.6.2图灵其人121

4.6.3图灵机的直观模型122

4.6.4图灵机的形式定义123

4.6.5可计算性124

4.6.6计算复杂性126

4.7习题选解127

4.7.1可数集127

4.7.2对角线法128

4.7.3康托伯恩斯坦定理的应用129

4.7.4连续统130

4.8本章小结130

习题131第5章逻辑演算132

5.1等值演算132

5.1.1指派与解释132

5.1.2逻辑等价135

5.1.3对偶式和内否式137

5.1.4联结词完备集138

5.2范式139

5.2.1析取范式与合取范式139

5.2.2主范式140

5.2.3前束范式142

5.3命题演算形式系统PC143

5.3.1PC的组成143

5.3.2PC的基本定理143

5.3.3PC的性质定理152

5.4谓词演算形式系统FC153

5.4.1FC的组成153

5.4.2FC的基本定理153

5.4.3FC的性质定理157

5.5习题选解157

5.6本章小结161

习题161

第6章图163

6.1利用图模型解决问题163

6.1.1图论史上的标志性问题164

6.1.2游戏类问题168

6.1.3应用类问题169

6.2基本概念169

6.2.1图的定义169

6.2.2子图172

6.2.3度173

6.2.4正则图173

6.2.5图的同构174

6.3路、圈与连通图175

6.3.1路与圈176

6.3.2图的连通性176

6.3.3连通图的判定177

6.3.4有圈图的判定179

6.4补图与偶图180

6.4.1补图180

6.4.2偶图182

6.4.3极值图论182

6.5欧拉图185

6.5.1欧拉图的定义185

6.5.2欧拉定理185

6.6哈密顿图186

6.6.1哈密顿图及背景186

6.6.2哈密顿图的判定186

6.6.3哈密顿图的几个充分条件187

6.6.4Kp的哈密顿圈分解188

6.6.5比赛图189

6.7图的表示190

6.7.1邻接矩阵190

6.7.2可达矩阵192

6.7.3邻接表192

6.7.4关联矩阵192

6.8带权图194

6.8.1最短路径问题194

6.8.2巡回售货员(货郎担或旅行商)问题196

6.8.3中国邮路问题196

6.9习题选解196

6.9.1连通图、圈196

6.9.2同构198

6.9.3哈密顿图199

6.9.4最长路200

6.10本章小结200

习题200第7章树和割集202

7.1树202

7.1.1树和森林202

7.1.2树的性质203

7.1.3树的中心204

7.2生成树205

7.2.1生成树的定义205

7.2.2生成树计数206

7.2.3最小生成树207

7.3有根树与有序树210

7.3.1有根树210

7.3.2有序树212

7.4割点、桥和割集213

7.4.1割点和桥213

7.4.2割点和桥的特征性质213

7.4.3割集215

7.5习题选解216

7.6本章小结218

习题218第8章连通度、匹配和覆盖219

8.1连通度219

8.1.1连通度的定义219

8.1.2κ(G)、λ(G)、δ(G)的关系220

8.1.3n连通222

8.2门格尔定理223

8.2.1门格尔定理及推论223

8.2.2网络流224

8.2.3割集226

8.2.4求最大流227

8.3匹配229

8.3.1匹配问题及模型230

8.3.2独立集230

8.3.3相异代表系232

8.3.4霍尔定理233

8.3.5求最大匹配235

8.4覆盖与支配集236

8.4.1覆盖237

8.4.2支配集237

8.5习题选解239

8.5.1建立网络流模型239

8.5.2连通度240

8.5.3匹配与覆盖241

8.5.4门格尔定理242

8.6本章小结242

习题243第9章平面图与图的着色244

9.1平面图及欧拉公式244

9.1.1背景244

9.1.2平面图的定义244

9.1.3平面图的欧拉公式245

9.1.4K5、K3,3不可平面246

9.2非哈密顿平面图247

9.3库拉托夫斯基定理249

9.4图的顶点着色250

9.4.1图的顶点着色的概念250

9.4.2色数的上下界251

9.4.3平面图的四色定理252

9.4.4平面图的五色定理254

9.5图的边着色255

9.5.1边着色及边色数255

9.5.2几个主要结果255

9.6习题选解256

9.7本章小结261

习题261第10章代数系统264

10.1半群和幺半群265

10.1.1半群和幺半群的概念265

10.1.2子半群、子幺半群、理想266

10.1.3同构和同态268

10.2群272

10.2.1群的概念272

10.2.2子群、生成子群273

10.2.3变换群、同构274

10.2.4循环群275

10.2.5子群的陪集275

10.2.6正规子群、商群277

10.2.7同态基本定理279

10.2.8直积281

10.3环和域283

10.3.1环和域的概念283

10.3.2环和域的基本性质284

10.4格与布尔代数286

10.4.1格286

10.4.2布尔代数288

10.5习题选解290

10.6本章小结295

习题295参考文献296