工科离散数学

目 录

第1章 命题逻辑1
1.1 命题1
思考与练习1.13
1.2 逻辑联结词3
1.2.1 基本联结词3
1.2.2 其他联结词6
思考与练习1.26
1.3 命题公式与真值表7
1.3.1 命题公式7
1.3.2 真值表8
思考与练习1.39
1.4 命题翻译9
1.4.1 合取命题9
1.4.2 可兼与不可兼析取命题10
1.4.3 条件命题10
1.4.4 多联结词命题11
思考与练习1.413
1.5 命题公式的值与等价14
1.5.1 命题公式的分类14
1.5.2 命题公式的等价14
1.5.3 联结词的功能完备集17
1.5.4 由德摩根律到对偶原理17
思考与练习1.518
1.6 范式19
1.6.1 简单的范式19
1.6.2 小项与大项20
1.6.3 主析取范式与主合取范式21
思考与练习1.623
1.7 推理理论24
1.7.1 蕴含与论证24
1.7.2 自然推理系统26
思考与练习1.733
第2章 谓词逻辑34
2.1 谓词、个体词与量词34
2.1.1 个体词与谓词34
2.1.2 量词与量化36
思考与练习2.137
2.2 谓词逻辑中的命题翻译38
2.2.1 特殊化个体词的命题38
2.2.2 量词量化的命题39
思考与练习2.242
2.3 量词约束与谓词公式的解释42
2.3.1 量词对个体词变元的作用42
2.3.2 谓词公式的解释与求值43
2.3.3 量词与联结词的搭配44
思考与练习2.345
2.4 谓词逻辑中的基本等价和蕴含
关系46
2.4.1 基本等价与蕴含关系46
2.4.2 利用等价关系计算前束范式49
思考与练习2.450
2.5 谓词演算的推理理论50
思考与练习2.556
第3章 集合论基础58
3.1 集合的概念与表示方法58
3.1.1 集合描述58
3.1.2 集合的包含与相等59
3.1.3 空集与全集60
3.1.4 集合的幂集62
思考与练习3.163
3.2 集合运算64
3.2.1 基本运算64
3.2.2 多集合的交与并66
思考与练习3.268
3.3 集合运算的性质与证明方法69
3.3.1 集合运算的性质与演算证明69
3.3.2 基于定义的集合运算证明
方法70
思考与练习3.373
3.4 序偶与笛卡尔积73
3.4.1 序偶与元组74
3.4.2 笛卡尔积74
思考与练习3.477
第4章 关系78
4.1 二元关系的含义与表示78
4.1.1 二元关系78
4.1.2 关系的矩阵和图表示法80
思考与练习4.181
4.2 关系运算81
4.2.1 关系求逆与复合82
4.2.2 关系运算的性质83
4.2.3 利用关系图与关系矩阵实现
关系运算85
4.2.4 多关系的复合87
思考与练习4.289
4.3 关系的主要性质89
4.3.1 自反与反自反关系89
4.3.2 对称与反对称关系90
4.3.3 传递关系92
4.3.4 特殊关系的判定92
思考与练习4.394
4.4 关系的闭包95
4.4.1 闭包的概念95
4.4.2 闭包计算96
思考与练习4.499
4.5 相容关系与等价关系100
4.5.1 集合的覆盖与划分100
4.5.2 相容与等价101
4.5.3 相容关系产生的完全覆盖102
4.5.4 等价关系产生的划分103
4.5.5 由覆盖、划分生成相容关系
和等价关系105
思考与练习4.5106
4.6 序关系107
4.6.1 体现部分次序的偏序关系107
4.6.2 哈斯图107
4.6.3 偏序集的特殊元素110
思考与练习4.6112
第5章 函数114
5.1 从关系到函数114
5.1.1 函数的概念114
5.1.2 函数集115
5.1.3 特殊函数116
思考与练习5.1118
5.2 函数的逆与复合119
5.2.1 双射的反函数119
5.2.2 函数的复合119
5.2.3 函数运算的性质121
思考与练习5.2122
5.3 集合的基数123
5.3.1 集合等势123
5.3.2 有限集与无限集124
5.3.3 可数集与不可数集124
5.3.4 基数比较126
思考与练习5.3127
第6章 运算与代数系统129
6.1 运算及其性质129
6.1.1 n元运算129
6.1.2 二元运算的主要性质130
思考与练习6.1132
6.2 二元运算中的特殊元素132
6.2.1 幺元132
6.2.2 零元133
6.2.3 逆元134
思考与练习6.2135
6.3 代数系统135
6.3.1 代数与子代数135
6.3.2 同态与同构136
思考与练习6.3138
6.4 半群与独异点138
思考与练习6.4140
6.5 群与子群140
6.5.1 群的概念140
6.5.2 群的性质141
6.5.3 子群142
思考与练习6.5144
6.6 循环群与置换群145
6.6.1 循环群145
6.6.2 置换群146
思考与练习6.6148
6.7 群的陪集分解149
6.7.1 陪集149
6.7.2 拉格朗日定理150
思考与练习6.7151
第7章 环、域、格和布尔代数152
7.1 环和域152
7.1.1 环152
7.1.2 域153
思考与练习7.1154
7.2 格155
7.2.1 格与其诱导的代数系统155
7.2.2 子格157
7.2.3 特殊格157
思考与练习7.2160
7.3 布尔代数161
7.3.1 布尔格诱导的布尔代数161
7.3.2 典型的布尔代数162
思考与练习7.3164
第8章 图165
8.1 图的基本概念165
8.1.1 图的认知165
8.1.2 结点的度与握手定理166
8.1.3 完全图与正则图168
8.1.4 子图、补图与图同构169
思考与练习8.1170
8.2 图的连通性171
8.2.1 路与回路171
8.2.2 无向图的连通性172
8.2.3 有向图的连通性173
思考与练习8.2174
8.3 图的矩阵表示174
8.3.1 邻接矩阵174
8.3.2 关联矩阵176
思考与练习8.3177
8.4 二部图、欧拉图与汉密尔顿图177
8.4.1 二部图177
8.4.2 欧拉图179
8.4.3 汉密尔顿图181
思考与练习8.4183
8.5 平面图183
8.5.1 平面图与欧拉定理183
8.5.2 平面图的对偶图186
8.5.3 平面图的着色187
思考与练习8.5188
8.6 树188
8.6.1 无向树188
8.6.2 生成树190
8.6.3 根树192
思考与练习8.6195
附录A 符号索引197
参考文献199