《离散数学》求取 ⇩

第1章命题逻辑1

1.1命题与命题公式1

1.1.1 命题1

1.1.2 命题联结词2

1.1.3 命题公式5

1.1.4 命题公式的真值表7

1.2重言式8

1.2.1 重言式和矛盾式8

1.2.2 等价重言式8

1.2.3 蕴含重言式10

1.2.4 对偶与对偶原理12

1.3命题演算的推理规则和证明方法13

1.3.1 真值表的证明方法13

1.3.2 形式推理的证明方法——直接证法14

1.3.3 间接证法18

1.4命题公式的标准形式21

1.4.1 范式21

1.4.2 主范式23

习题128

第2章谓词逻辑31

2.1个体、谓词与命题函数32

2.1.1 个体与谓词32

2.1.2 命题函数33

2.2量词33

2.2.1 全称量词34

2.2.2 存在量词35

2.3谓词公式与翻译35

2.3.1 谓词公式35

2.3.2 命题的符号化36

2.3.3 自由变元和约束变元38

2.4谓词演算的推理理论39

2.4.1 谓词演算的等价式和蕴含式39

2.4.2 谓词演算的推理规则43

习题246

第3章集合50

3.1基本概念50

3.1.1 集合及其表示方法50

3.1.2 集合的包含和相等51

3.1.3 空集和全集52

3.1.4 幂集53

3.2集合的运算与运算定律54

3.2.1 集合的运算与文氏图54

3.2.2 集合运算的定律56

3.2.3 集合的对称差59

3.3 集合的划分与覆盖61

3.4 容斥原理62

习题364

第4章关系68

4.1序偶与笛卡儿积68

4.1.1 序偶与有序n元组68

4.1.2 笛卡儿积68

4.2关系、关系矩阵和关系图70

4.2.1 关系的概念70

4.2.2 关系矩阵72

4.2.3 关系图73

4.3关系的运算74

4.3.1 关系的并、交、补、差运算74

4.3.2 关系的复合运算74

4.3.3 关系的逆运算77

4.4关系的性质78

4.4.1 定义78

4.4.2 举例81

4.4.3 关系性质的判定定理82

4.5关系的闭包运算82

4.5.1 定义82

4.5.2 闭包运算的性质84

4.5.3有限集合上关系的传递闭包85

4.5.4 p+的关系图的画法85

4.6等价关系与等价类86

4.6.1 定义86

4.6.2 等价关系与划分87

4.7偏序88

4.7.1 定义88

4.7.2 哈斯图89

4.7.3 偏序集中的特殊元素90

习题492

第5章函数97

5.1函数与特殊类型函数97

5.1.1 函数的定义97

5.1.2 特殊类型函数99

5.2函数的运算101

5.2.1 函数的复合101

5.2.2 逆函数103

5.3集合的势与可数集105

5.3.1 集合的势105

5.3.2 可数集107

5.4鸽舍原理110

5.4.1 鸽舍原理1110

5.4.2 鸽舍原理2111

习题5112

第6章代数系统的基本理论和特殊代数系统115

6.1运算和代数系统115

6.1.1 运算115

6.1.2 运算的运算表116

6.1.3 代数系统117

6.2二元运算的性质与特殊元素118

6.2.1 二元运算的性质118

6.2.2 二元运算的特殊元素119

6.3同态和同构123

6.3.1 同构123

6.3.2 同态124

6.4半群和独异点127

6.4.1 半群127

6.4.2 独异点128

6.4.3 子半群和子独异点131

6.5群131

6.5.1 定义131

6.5.2 群的基本性质134

6.6群中元素的周期与循环群135

6.6.1 群中元素的周期135

6.6.2 元素周期的性质136

6.6.3 循环群137

6.7子群138

6.7.1 两个等价的定义138

6.7.2 子群的判定定理139

6.8格140

6.8.1 格的定义和性质140

6.8.2 几种特殊的格142

习题6144

第7章图论149

7.1图的基本概念149

7.1.1 图149

7.1.2 结点的度150

7.1.3 几种常见的图151

7.1.4 子图151

7.1.5 图的同构152

7.2路与圈153

7.2.1 路、圈和连通性153

7.2.2 有权图的最短路径问题155

7.3 图的矩阵表示158

7.4有向图和可达性矩阵160

7.4.1 有向图160

7.4.2 有向图的可达性161

7.5欧拉图与哈密尔顿图164

7.5.1 欧拉图164

7.5.2 哈密尔顿图168

7.6树170

7.6.1 树171

7.6.2 生成树与最小生成树172

7.7根树及其应用173

7.7.1 根树、有序树、M叉树173

7.7.2 二叉树175

7.7.3 二叉树在计算机中的应用177

7.8偶图与匹配181

7.8.1 偶图181

7.8.2 匹配182

7.9平面图与欧拉公式183

7.9.1 平面图183

7.9.2 欧拉公式185

习题7187

参考文献193