离散数学[电子资源.图书]

第1章 集合、关系与函数1

1．1 集合.1

1．1．1 集合的基本概念1

1．1．2 集合的基本运算5

1．1．3 包含排斥原理10

1．2 二元关系13

1．2．1 引言13

1．2．2 集合的笛卡儿乘积13

1．2．3 二元关系的3种表示方法15

1．2．4 关系的基本类型18

1．2．5 等价关系与划分24

1．2．6 偏序关系30

1．2．7 复合关系与逆关系35

1．2．8 关系的闭包运算42

1．3 函数45

1．3．1 函数的基本概念45

1．3．2 特殊函数47

1．3．3 复合函数与逆函数51

习题55

第2章 命题逻辑64

.2．1 命题和联结词64

2．1．1 命题和命题变元64

2．1．2 命题联结词65

2．2 真值表和逻辑等价70

2．2．1 命题公式的真值表70

2．2．2 逻辑等价71

2．3 永真蕴含式75

2．3．1 永真蕴含式的定义75

2．3．2 永真蕴含式的性质77

2．4 推理理论78

2．4．1 前提与有效结论78

2．4．2 直接证明法80

2．4．3 间接证明法83

2．5 范式86

2．5．1 析取范式和主析取范式87

2．5．2 合取范式和主合取范式94

习题100

第3章 谓词逻辑106

3．1 谓词逻辑的基本概念106

3．1．1 谓词与命题函数106

3．1．2 量词..108

3．1．3 谓词合式112

3．1．4 约束元和自由元113

3．2 等价式与永真蕴含式114

3．2．1 等价式114

3．2．2 前束范式117

3．2．3 永真蕴含式118

3．3 谓词演算的推理理论120

习题123

第4章 代数系统126

4．1 代数系统的基本概念126

4．1．1 代数系统的定义126

4．1．2 特殊运算与特殊元素128

4．1．3 同构135

4．2 半群与独异点137

4．2．1 半群与子半群137

4．2．2 独异点与子独异点138

4．3 群141

4．3．1 群的定义和性质141

4．3．2 子群144

4．3．3 循环群149

4．3．4 群码153

4．4 环和域157

4．4．1 环和特殊环157

4．4．2 域160

4．5 格163

4．5．1 格的基本概念163

4．5．2 特殊格166

习题170

第5章 图论176

5．1 图的基本概念176

5．1．1 图的基本类型176

5．1．2 图中顶点的度数178

5．1．3 正则图与完全图179

5．1．4 子图180

5．1．5 图的同构181

5．1．6 补图182

5．1．7 图的矩阵表示182

5．2 图的连通性186

5．2．1 通路与回路186

5．2．2 连通图186

5．3 欧拉图与哈密顿图189

5．3．1 欧拉图189

5．3．2 哈密顿图193

5．3．3 旅行售货员问题195

5．4 二部图与平面图199

5．4．1 二部图199

5．4．2 平面图201

5．5 树209

5．5．1 无向树209

5．5．2 有向树211

5．5．3 周游算法213

5．5．4 前缀码与最优树215

习题220

第6章 递推关系与生成函数226

6．1 递推关系的基本概念226

6．2 常系数线性递推关系227

6．2．1 齐次常系数线性递推关系227

6．2．2 非齐次常系数线性递推关系231

6．3 生成函数240

习题245

参考文献...247