第1章集合、映射与运算1

1.1集合的有关概念1

1.1.1集合1

1.1.2子集3

1.1.3幂集3

1.1.4n元组4

1.1.5笛卡儿积4

习题1.14

1.2映射的有关概念5

1.2.1映射的定义5

1.2.2映射的性质7

1.2.3逆映射8

1.2.4复合映射9

习题1.210

1.3运算的定义及性质11

1.3.1运算的定义12

1.3.2运算的性质13

习题1.317

1.4集合的运算18

1.4.1并运算18

1.4.2交运算19

1.4.3补运算20

1.4.4差运算21

1.4.5对称差运算22

习题1.423

1.5集合的划分与覆盖24

1.5.1集合的划分25

1.5.2集合的覆盖27

习题1.527

1.6集合的对等28

1.6.1集合对等的定义28

1.6.2无限集合29

1.6.3集合的基数29

1.6.4可列集合30

1.6.5不可列集合30

1.6.6基数的比较30

习题1.631

离散数学目录第2章关系33

2.1关系的概念33

2.1.1n元关系的定义33

2.1.22元关系34

2.1.3关系的定义域和值域36

2.1.4关系的表示36

2.1.5函数的关系定义38

习题2.139

2.2关系的运算39

2.2.1关系的集合运算40

2.2.2关系的逆运算40

2.2.3关系的复合运算41

2.2.4关系的其他运算45

习题2.245

2.3关系的性质46

2.3.1自反性46

2.3.2反自反性47

2.3.3对称性48

2.3.4反对称性49

2.3.5传递性50

习题2.352

2.4关系的闭包53

2.4.1自反闭包r(R)53

2.4.2对称闭包s(R)54

2.4.3传递闭包t(R)55

习题2.458

2.5等价关系59

2.5.1等价关系的定义60

2.5.2等价类60

习题2.562

2.6相容关系63

2.6.1相容关系的定义63

2.6.2相容类65

习题2.665

2.7偏序关系66

2.7.1偏序关系的定义66

2.7.2偏序集的哈斯图67

2.7.3偏序集中的特殊元素68

习题2.770

第3章命题逻辑73

3.1命题的有关概念73

习题3.175

3.2逻辑联结词75

3.2.1?瘙
綈p75

3.2.2p∧q76

3.2.3p∨q76

3.2.4pq76

3.2.5p→q77

3.2.6pq78

3.2.7p↑q78

3.2.8p↓q79

3.2.9p→nq79

习题3.279

3.3命题公式及其真值表80

3.3.1命题公式的定义80

3.3.2命题的符号化81

3.3.3命题公式的真值表81

3.3.4命题公式的类型82

习题3.384

3.4逻辑等值的命题公式84

3.4.1逻辑等值的定义85

3.4.2基本等值式86

3.4.3等值演算法87

3.4.4对偶原理88

习题3.489

3.5命题公式的范式90

3.5.1命题公式的析取范式及合取范式90

3.5.2命题公式的主析取范式及主合取范式93

习题3.599

3.6联结词集合的功能完备性100

3.6.1联结词的个数100

3.6.2功能完备联结词集101

习题3.6103

3.7命题逻辑中的推理103

3.7.1推理形式有效性的定义104

3.7.2基本推理规则105

3.7.3命题逻辑的自然推理系统106

习题3.7110

第4章谓词逻辑113

4.1个体、谓词、量词和函词113

4.1.1个体113

4.1.2谓词114

4.1.3量词114

4.1.4函词116

习题4.1117

4.2谓词公式及命题的符号化117

4.2.1谓词公式117

4.2.2命题的符号化118

习题4.2120

4.3谓词公式的解释及类型121

4.3.1谓词公式的解释121

4.3.2谓词公式的类型123

习题4.3123

4.4逻辑等值的谓词公式125

4.4.1谓词公式等值的定义125

4.4.2基本等值式125

习题4.4127

4.5谓词公式的前束范式127

4.5.1谓词公式的前束范式的定义127

4.5.2谓词公式的前束范式的计算128

习题4.5128

4.6谓词逻辑中的推理129

4.6.1逻辑蕴涵式129

4.6.2基本推理规则129

4.6.3谓词逻辑的自然推理系统130

习题4.6132

第5章群、环和域135

5.1代数结构简介135

5.1.1代数结构的定义135

5.1.2两种最简单的代数结构: 半群及独异点136

5.1.3子代数137

5.1.4代数结构的同态与同构138

习题5.1140

5.2群的定义及性质140

5.2.1群的定义141

5.2.2群的性质143

习题5.2143

5.3置换群144

5.3.1有限集合上的置换及表示144

5.3.2置换的复合运算145

5.3.3置换群的定义145

习题5.3146

5.4阿贝尔群与循环群146

5.4.1阿贝尔群146

5.4.2循环群147

习题5.4150

5.5子群、群的陪集分解及正规子群151

5.5.1子群151

5.5.2群的陪集分解152

5.5.3正规子群154

习题5.5156

5.6群的同态与同构157

5.6.1群的同态157

5.6.2群的同构158

5.6.3群的自同态与自同构160

习题5.6160

5.7环161

5.7.1环的定义161

5.7.2环的基本性质162

5.7.3子环及理想163

习题5.7164

5.8域165

5.8.1域的定义165

5.8.2有限域166

习题5.8167

第6章格与布尔代数169

6.1用偏序集定义的格169

6.1.1格的第一种定义169

6.1.2格的性质171

6.1.3格的保序映射172

习题6.1173

6.2用代数结构定义的格173

6.2.1格的第二种定义173

6.2.2格的两种定义的等价性174

6.2.3子格175

6.2.4格的同态与同构176

习题6.2176

6.3分配格177

6.3.1分配格的定义177

6.3.2分配格的性质178

习题6.3178

6.4有补格179

6.4.1有界格179

6.4.2补元179

习题6.4180

6.5布尔代数181

6.5.1布尔代数的格定义181

6.5.2布尔代数的性质182

6.5.3布尔代数的公理化定义183

6.5.4子布尔代数185

6.5.5布尔代数的同态与同构185

习题6.5186

6.6有限布尔代数的结构187

习题6.6189

6.7布尔表达式190

6.7.1布尔表达式的定义190

6.7.2布尔表达式的化简191

6.7.3布尔表达式的主范式191

6.7.4布尔函数192

习题6.7193

第7章图论195

7.1图的基本概念195

7.1.1图的定义195

7.1.2邻接197

7.1.3关联197

7.1.4简单图197

习题7.1198

7.2节点的度数199

习题7.2201

7.3子图、图的运算和图同构202

7.3.1子图202

7.3.2图的运算203

7.3.3图同构203

习题7.3204

7.4路与回路205

7.4.1路205

7.4.2回路206

习题7.4206

7.5图的连通性207

7.5.1无向图的连通性207

7.5.2无向连通图的点连通度与边连通度209

7.5.3有向图的连通性210

习题7.5212

7.6图的矩阵表示212

7.6.1图的邻接矩阵213

7.6.2图的可达矩阵214

7.6.3图的关联矩阵214

习题7.6216

7.7赋权图及最短路径217

7.7.1赋权图217

7.7.2最短路径217

习题7.7219

第8章几类特殊的图221

8.1欧拉图221

8.1.1欧拉图的有关概念221

8.1.2欧拉定理222

8.1.3中国邮递员问题223

习题8.1223

8.2哈密尔顿图224

8.2.1哈密尔顿图的有关概念224

8.2.2哈密尔顿图的必要条件225

8.2.3哈密尔顿图的充分条件226

8.2.4旅行商问题227

习题8.2228

8.3无向树229

8.3.1无向树的定义229

8.3.2无向树的性质229

8.3.3生成树231

8.3.4最小生成树232

习题8.3233

8.4有向树234

8.4.1有向树的定义234

8.4.2根树234

8.4.3m叉树235

8.4.4有序树238

8.4.5定位2叉树239

习题8.4241

8.5平面图242

8.5.1平面图的有关概念243

8.5.2欧拉公式244

8.5.3库拉托夫斯基定理245

8.5.4平面图的对偶图245

习题8.5246

8.6平面图的面着色247

8.6.1平面图的面着色定义248

8.6.2图的节点着色248

8.6.3任意图的边着色249

习题8.6250

8.7二部图及其匹配251

8.7.1二部图251

8.7.2匹配252

习题8.7252

附录A符号索引255

附录B中英文名词索引259

附录C习题答案及提示263

参考文献289