离散数学

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

1.1 集合的有关概念.1

1.1.1 集合1

1.1.2 子集3

1.1.3 幂集3

1.1.4 n元组4

1.1.5 笛卡儿积4

习题1.1 4

1.2 映射的有关概念5

1.2.1 映射的定义5

1.2.2 映射的性质7

1.2.3 逆映射8

1.2.4 复合映射9

习题1.2 10

1.3 运算的定义及性质11

1.3.1 运算的定义12

1.3.2 运算的性质13

习题1.3 17

1.4 集合的运算18

1.4.1 并运算18

.1.4.2 交运算19

1.4.3 补运算20

1.4.4 差运算21

1.4.5 对称差运算22

习题1.4 23

1.5 集合的划分与覆盖24

1.5.1 集合的划分25

1.5.2 集合的覆盖27

习题1.5 27

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.6 31

第2章 关系33

2.1 关系的概念33

2.1.1 n元关系的定义33

2.1.2 2元关系34

2.1.3 关系的定义域和值域36

2.1.4 关系的表示36

2.1.5 函数的关系定义38

习题2.1 39

2.2 关系的运算39

2.2.1 关系的集合运算40

2.2.2 关系的逆运算40

2.2.3 关系的复合运算41

2.2.4 关系的其他运算45

习题2.2 45

2.3 关系的性质46

2.3.1 自反性46

2.3.2 反自反性47

2.3.3 对称性48

2.3.4 反对称性49

2.3.5 传递性50

习题2.3 52

2.4 关系的闭包53

2.4.1 自反闭包r(r)53

2.4.2 对称闭包s(r)54

2.4.3 传递闭包t(r)55

习题2.4 58

2.5 等价关系59

2.5.1 等价关系的定义60

2.5.2 等价类60

习题2.5 62

2.6 相容关系63

2.6.1 相容关系的定义63

2.6.2 相容类65

习题2.6 65

2.7 偏序关系66

2.7.1 偏序关系的定义66

2.7.2 偏序集的哈斯图67

2.7.3 偏序集中的特殊元素68

习题2.7 70

第3章 命题逻辑73

3.1 命题的有关概念73

习题3.1 75

3.2 逻辑联结词75

3.2.1 ┐p 75

3.2.2 p∧q 76

3.2.3 p∨q 76

3.2.4 p﹒ 76

3.2.5 p→q 77

3.2.6 p←→q 78

3.2.7 p↑q 78

3.2.8 p↓q 79

3.2.9 p→nq 79

习题3.2 79

3.3 命题公式及其真值表80

3.3.1 命题公式的定义80

3.3.2 命题的符号化81

3.3.3 命题公式的真值表81

3.3.4 命题公式的类型82

习题3.3 84

3.4 逻辑等值的命题公式84

3.4.1 逻辑等值的定义85

3.4.2 基本等值式86

3.4.3 等值演算法87

3.4.4 对偶原理88

习题3.4 89

3.5 命题公式的范式90

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

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

习题3.5 99

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

3.6.1 联结词的个数100

3.6.2 功能完备联结词集101

习题3.6 103

3.7 命题逻辑中的推理103

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

3.7.2 基本推理规则105

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

习题3.7 110

第4章 谓词逻辑113

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

4.1.1 个体113

4.1.2 谓词114

4.1.3 量词114

4.1.4 函词116

习题4.1 117

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

4.2.1 谓词公式117

4.2.2 命题的符号化118

习题4.2 120

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

4.3.1 谓词公式的解释121

4.3.2 谓词公式的类型123

习题4.3 123

4.4 逻辑等值的谓词公式125

4.4.1 谓词公式等值的定义125

4.4.2 基本等值式125

习题4.4 127

4.5 谓词公式的前束范式127

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

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

习题4.5 128

4.6 谓词逻辑中的推理129

4.6.1 逻辑蕴涵式..129

4.6.2 基本推理规则129

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

习题4.6 132

第5章 群、环和域135

5.1 代数结构简介135

5.1.1 代数结构的定义135

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

5.1.3 子代数137

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

习题5.1 140

5.2 群的定义及性质140

5.2.1 群的定义141

5.2.2 群的性质143

习题5.2 143

5.3 置换群144

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

5.3.2 置换的复合运算145

5.3.3 置换群的定义145

习题5.3 146

5.4 阿贝尔群与循环群146

5.4.1 阿贝尔群146

5.4.2 循环群147

习题5.4 150

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

5.5.1 子群151

5.5.2 群的陪集分解152

5.5.3 正规子群154

习题5.5 156

5.6 群的同态与同构157

5.6.1 群的同态157

5.6.2 群的同构158

5.6.3 群的自同态与自同构160

习题5.6 160

5.7 环161

5.7.1 环的定义161

5.7.2 环的基本性质162

5.7.3 子环及理想163

习题5.7 164

5.8 域165

5.8.1 域的定义165

5.8.2 有限域166

习题5.8 167

第6章 格与布尔代数169

6.1 用偏序集定义的格169

6.1.1 格的第一种定义169

6.1.2 格的性质171

6.1.3 格的保序映射172

习题6.1 173

6.2 用代数结构定义的格173

6.2.1 格的第二种定义173

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

6.2.3 子格175

6.2.4 格的同态与同构176

习题6.2 176

6.3 分配格177

6.3.1 分配格的定义177

6.3.2 分配格的性质178

习题6.3 178

6.4 有补格179

6.4.1 有界格179

6.4.2 补元179

习题6.4 180

6.5 布尔代数181

6.5.1 布尔代数的格定义181

6.5.2 布尔代数的性质182

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

6.5.4 子布尔代数185

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

习题6.5 186

6.6 有限布尔代数的结构187

习题6.6 189

6.7 布尔表达式190

6.7.1 布尔表达式的定义190

6.7.2 布尔表达式的化简191

6.7.3 布尔表达式的主范式191

6.7.4 布尔函数192

习题6.7 193

第7章 图论195

7.1 图的基本概念195

7.1.1 图的定义195

7.1.2 邻接197

7.1.3 关联197

7.1.4 简单图197

习题7.1 198

7.2 节点的度数199

习题7.2 201

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

7.3.1 子图202

7.3.2 图的运算203

7.3.3 图同构203

习题7.3 204

7.4 路与回路205

7.4.1 路205

7.4.2 回路206

习题7.4 206

7.5 图的连通性207

7.5.1 无向图的连通性207

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

7.5.3 有向图的连通性210

习题7.5 212

7.6 图的矩阵表示212

7.6.1 图的邻接矩阵213

7.6.2 图的可达矩阵214

7.6.3 图的关联矩阵214

习题7.6 216

7.7 赋权图及最短路径217

7.7.1 赋权图217

7.7.2 最短路径217

习题7.7 219

第8章 几类特殊的图221

8.1 欧拉图221

8.1.1 欧拉图的有关概念221

8.1.2 欧拉定理222

8.1.3 中国邮递员问题223

习题8.1 223

8.2 哈密尔顿图224

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

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

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

8.2.4 旅行商问题227

习题8.2 228

8.3 无向树229

8.3.1 无向树的定义229

8.3.2 无向树的性质229

8.3.3 生成树231

8.3.4 最小生成树232

习题8.3 233

8.4 有向树234

8.4.1 有向树的定义234

8.4.2 根树234

8.4.3 m叉树235

8.4.4 有序树238

8.4.5 定位2叉树239

习题8.4 241

8.5 平面图242

8.5.1 平面图的有关概念243

8.5.2 欧拉公式244

8.5.3 库拉托夫斯基定理245

8.5.4 平面图的对偶图245

习题8.5 246

8.6 平面图的面着色247

8.6.1 平面图的面着色定义248

8.6.2 图的节点着色248

8.6.3 任意图的边着色249

习题8.6 250

8.7 二部图及其匹配251

8.7.1 二部图251

8.7.2 匹配252

习题8.7 252

附录a 符号索引255

附录b 中英文名词索引259

附录c 习题答案及提示263

参考文献...289