离散数学

第1章 命题逻辑 1 1.1 命题 1 1.2 联结词 2 1.3 命题公式与翻译 7 1.4 真值表与等价公式 9 1.5 重言与蕴含 13 1.6 其他联结词与全功能集 15 1.7 对偶与范式 19 1.8 命题逻辑的推理 26 1.9 典型例题解析 31 上机实验1 命题演算的计算机实现 35 习题1 36 第2章 谓词逻辑 38 2.1 谓词与量词 38 2.2 谓词公式与翻译 41 2.3 变元的约束 43 2.4 谓词演算的等价式与蕴含式 45 2.5 前束范式 51 2.6 谓词演算的推理理论 53 2.7 典型例题解析 57 习题2 60 第3章 集合 65 3.1 集合的基本概念 65 3.2 集合的运算与性质 69 3.3 集合的划分与覆盖 74 3.4 集合中元素的计数 75 3.5 典型例题解析 77 上机实验2 编程实现任意两个集合的交、并、差和补运算 81 习题3 81 第4章 二元关系和函数 84 4.1 序偶与笛卡尔积 84 4.2 关系及其表示 87 4.3 关系的性质 89 4.4 关系的复合 92 4.5 逆关系 96 4.6 关系的闭包运算 98 4.7 等价关系与等价类 104 4.8 相容关系 108 4.9 偏序关系 110 4.10 函数及其性质 114 4.11 复合函数和逆函数 116 4.12 典型例题解析 120 上机实验3 关系及函数性质的判定 125 习题4 126 第5章 代数系统 129 5.1 代数系统的概念 129 5.2 运算及其性质 131 5.3 半群 138 5.4 群与子群 143 5.5 阿贝尔群、循环群与置换群 149 5.6 陪集与拉格朗日定理 153 5.7 代数系统的同态与同构 155 5.8 环与域 160 5.9 格与布尔代数 162 5.10 典型例题解析 167 习题5 169 第6章 图论导论 173 6.1 图的基本概念 173 6.2 图中的路与图的连通性 180 6.3 图的矩阵表示 185 6.4 典型例题解析 189 上机实验4 图的连通性判定 194 习题6 194 第7章 特殊的图 197 7.1 欧拉图 197 7.2 汉密尔顿图 202 7.3 二分图 208 7.4 平面图 211 7.5 图的着色 216 7.6 典型例题解析 220 上机实验5 特殊图形的判定 227 习题7 227 第8章 树及其应用 230 8.1 无向树与生成树 230 8.2 根树及其应用 235 8.3 典型例题解析 243 上机实验6 树的有关算法 245 习题8 245 第9章 组合数学基础 247 9.1 排列与组合 247 9.2 生成函数 251 9.3 递推关系 255 9.4 容斥原理 260 9.5 抽屉原理 265 9.6 典型例题解析 267 习题9 269 参考文献 272