离散数学简明教程PDF电子书下载

第1章 命题逻辑 1

1.1 命题及其表示 1

1.1.1 命题的概念 1

1.1.2 命题分类 2

1.1.3 命题标识符 3

1.2 逻辑联结词 3

1.2.1 否定联结词 3

1.2.2 合取联结词 3

1.2.3 析取联结词 4

1.2.4 条件联结词 5

1.2.5 双条件联结词 6

1.3 命题公式与符号化 6

1.3.1 命题公式 6

1.3.2 命题的符号化 7

1.4 真值表与命题公式的分类 8

1.4.1 真值表 8

1.4.2 命题公式的分类 10

1.5 等价公式 11

1.5.1 真值表法 12

1.5.2 等值演算法 13

1.6 蕴含式与对偶式 16

1.6.1 蕴含式 16

1.6.2 对偶式 17

1.7 命题公式的范式 18

1.7.1 命题公式的析取范式与合取范式 18

1.7.2 命题公式的主析取范式与主合取范式 21

1.8 命题逻辑的推理理论 34

1.8.1 直接证法 35

1.8.2 间接证法 37

本章小结 39

习题1 40

第2章 谓词逻辑 42

2.1 谓词的概念与表示 42

2.1.1 个体和谓词 42

2.1.2 量词 44

2.2 谓词公式与翻译 45

2.2.1 谓词公式 45

2.2.2 谓词公式的翻译 45

2.3 变元的约束 47

2.4 谓词演算的等价式与蕴含式 49

2.4.1 谓词公式的赋值 49

2.4.2 谓词公式的分类 50

2.4.3 谓词演算的等价式 51

2.4.4 谓词演算的蕴含式 53

2.5 谓词公式范式 54

2.5.1 前束范式 55

2.5.2 前束析取范式和前束合取范式 56

2.6 谓词演算的推理理论 56

本章小结 62

习题2 62

第3章 集合 65

3.1 集合的基本概念 65

3.1.1 集合及其表示 65

3.1.2 集合的基本特征 66

3.2 集合间的关系 67

3.3 幂集 68

3.4 集合的运算 69

3.4.1 集合的交与并 69

3.4.2 集合的差与补 70

3.4.3 集合的对称差 71

3.5 集合运算的恒等式 72

本章小结 74

习题3 74

第4章 关系 76

4.1 序偶与笛卡尔积 76

4.1.1 序偶与有序n元组 76

4.1.2 笛卡尔积 77

4.2 关系的概念及其表示法 78

4.2.1 关系的概念 78

4.2.2 几种特殊的关系 80

4.2.3 关系的表示法 80

4.3 关系的运算 82

4.3.1 关系的复合运算 82

4.3.2 复合关系的矩阵表示和图形表示 84

4.3.3 关系的逆运算 86

4.4 关系的性质 87

4.4.1 关系的性质 87

4.4.2 关系性质的判定方法 88

4.4.3 关系的闭包 90

4.5 等价关系与划分 93

4.5.1 集合的划分与覆盖 94

4.5.2 等价关系与等价类 94

4.6 偏序关系 97

4.6.1 偏序关系的定义 97

4.6.2 偏序关系的哈斯图 97

4.6.3 偏序集中特殊位置的元素 99

4.6.4 全序和良序 101

本章小结 101

习题4 102

第5章 函数 104

5.1 函数的定义及其性质 104

5.1.1 函数的定义 104

5.1.2 函数的性质 106

5.2 函数的运算 108

5.2.1 函数的复合 108

5.2.2 反函数 111

本章小结 112

习题5 112

第6章 图论 114

6.1 图的基本概念 114

6.1.1 无向图和有向图 114

6.1.2 结点的度数 117

6.1.3 子图与补图 118

6.1.4 图的同构 121

6.2 路与图的连通性 124

6.2.1 通路与回路 124

6.2.2 无向图的连通性 125

6.2.3 有向图的连通性 127

6.3 图的矩阵表示 129

6.3.1 邻接矩阵 129

6.3.2 可达性矩阵 131

6.3.3 关联矩阵 132

6.4 特殊图 134

6.4.1 欧拉图 134

6.4.2 哈密顿图 136

本章小结 139

习题6 139

第7章 树 141

7.1 无向树及其性质 141

7.2 生成树 144

7.2.1 生成树的定义 144

7.2.2 最小生成树及其应用 145

7.3 根树 146

7.3.1 根树与m叉树 146

7.3.2 最优树与哈夫曼编码 148

本章小结 150

习题7 151

参考文献 152