《邓辉文-离散数学章节》由会员分享，可在线阅读，更多相关《邓辉文-离散数学章节（6页珍藏版）》请在金锄头文库上搜索。
1、第1章 集合、映射与运算11.1 集合的有关概念11.1.1 集合11.1.2 子集31.1.3 幂集41.1.4 n元组51.1.5 笛卡儿积6习题1.161.2 映射的有关概念71.2.1 映射的定义71.2.2 映射的性质91.2.3 逆映射101.2.4 复合映射11习题1.2131.3 运算的定义及性质141.3.1 运算的定义141.3.2 运算的性质17习题1.3211.4 集合的运算221.4.1 并运算221.4.2 交运算231.4.3 补运算241.4.4 差运算261.4.5 对称差运算27习题1.4281.5 集合的划分与覆盖291.5.1 集合的划分291.5.2
2、集合的覆盖32习题1.5321.6 集合的对等321.6.1 集合对等的定义331.6.2 无限集合331.6.3 集合的基数341.6.4 可数集合341.6.5 不可数集合351.6.6 基数的比较35习题1.636第2章 关系372.1 关系的概念372.1.1 n元关系的定义372.1.2 2元关系382.1.3 关系的定义域和值域412.1.4 关系的表示422.1.5 函数的关系定义43习题2.1442.2 关系的运算462.2.1 关系的集合运算462.2.2 关系的逆运算462.2.3 关系的复合运算472.2.4 关系的其他运算51习题2.2512.3 关系的性质522.3.
3、1 自反性522.3.2 反自反性532.3.3 对称性542.3.4 反对称性552.3.5 传递性56习题2.3582.4 关系的闭包592.4.1 自反闭包r(R)592.4.2 对称闭包s(R)602.4.3 传递闭包t(R)61习题2.4642.5 等价关系652.5.1 等价关系的定义652.5.2 等价类66习题2.5682.6 相容关系692.6.1 相容关系的定义692.6.2 相容类70习题2.6712.7 偏序关系712.7.1 偏序关系的定义712.7.2 偏序集的哈斯图732.7.3 偏序集中的特殊元素74习题2.776第3章 命题逻辑783.1 命题的有关概念78习
4、题3.1803.2 逻辑联结词803.2.1 否定联结词瘙綈p813.2.2 合取联结词pq813.2.3 析取联结词pq813.2.4 异或联结词pq823.2.5 条件联结词pq823.2.6 双条件联结词pq833.2.7 与非联结词pq833.2.8 或非联结词pq843.2.9 条件否定联结词pnq84习题3.2843.3 命题公式及其真值表853.3.1 命题公式的定义853.3.2 命题的符号化863.3.3 命题公式的真值表863.3.4 命题公式的类型87习题3.3883.4 逻辑等值的命题公式893.4.1 逻辑等值的定义903.4.2 基本等值式913.4.3 等值演算法
5、923.4.4 对偶原理93习题3.4933.5 命题公式的范式953.5.1 命题公式的析取范式及合取范式953.5.2 命题公式的主析取范式及主合取范式98习题3.51033.6 联结词集合的功能完备性1043.6.1 联结词的个数1043.6.2 功能完备联结词集105习题3.61073.7 命题逻辑中的推理1083.7.1 推理形式有效性的定义1083.7.2 基本推理规则1093.7.3 命题逻辑的自然推理系统110习题3.7114第4章 谓词逻辑1164.1 个体、谓词、量词和函词1164.1.1 个体1164.1.2 谓词1174.1.3 量词1174.1.4 函词119习题4.
6、11194.2 谓词公式及命题的符号化1204.2.1 谓词公式1204.2.2 命题的符号化120习题4.21224.3 谓词公式的解释及类型1244.3.1 谓词公式的解释1244.3.2 谓词公式的类型125习题4.31254.4 逻辑等值的谓词公式1274.4.1 谓词公式等值的定义1274.4.2 基本等值式127习题4.41294.5 谓词公式的前束范式1294.5.1 谓词公式的前束范式的定义1294.5.2 谓词公式的前束范式的计算130习题4.51304.6 谓词逻辑中的推理1314.6.1 逻辑蕴涵式1314.6.2 基本推理规则1314.6.3 谓词逻辑的自然推理系统13
7、2习题4.6134第5章 代数结构1365.1 代数结构简介1365.1.1 代数结构的定义1365.1.2 两种最简单的代数结构: 半群及独异点1375.1.3 子代数1385.1.4 代数结构的同态与同构138习题5.11405.2 群的定义及性质1415.2.1 群的有关概念1415.2.2 子群1435.2.3 群的同态144习题5.21445.3 环和域1455.3.1 环的定义1455.3.2 几种特殊的环1465.3.3 域的定义1475.3.4 有限域148习题5.31495.4 格与布尔代数1505.4.1 格的定义和性质1505.4.2 分配格1535.4.3 有补格154
8、5.4.4 布尔代数155习题5.4157第6章 图论1596.1 图的基本概念1596.1.1 图的定义1596.1.2 邻接1616.1.3 关联1616.1.4 简单图161习题6.11626.2 节点的度数163习题6.21656.3 子图、图的运算和图同构1656.3.1 子图1656.3.2 图的运算1666.3.3 图同构167习题6.31686.4 路与回路1686.4.1 路1696.4.2 回路169习题6.41706.5 图的连通性1716.5.1 无向图的连通性1716.5.2 无向连通图的点连通度与边连通度1726.5.3 有向图的连通性173习题6.51756.6
9、图的矩阵表示1766.6.1 图的邻接矩阵1766.6.2 图的可达矩阵1776.6.3 图的关联矩阵178习题6.61796.7 赋权图及最短路径1806.7.1 赋权图1806.7.2 最短路径180习题6.7182第7章 几类特殊的图1837.1 欧拉图1837.1.1 欧拉图的有关概念1837.1.2 欧拉定理1837.1.3 中国邮递员问题184习题7.11857.2 哈密尔顿图1867.2.1 哈密尔顿图的有关概念1867.2.2 哈密尔顿图的必要条件1877.2.3 哈密尔顿图的充分条件1877.2.4 旅行商问题189习题7.21897.3 无向树1907.3.1 无向树的定义
10、1907.3.2 无向树的性质1917.3.3 生成树1927.3.4 最小生成树193习题7.31947.4 有向树1957.4.1 有向树的定义1957.4.2 根树1957.4.3 m叉树1967.4.4 有序树1997.4.5 定位二叉树199习题7.42017.5 平面图2027.5.1 平面图的有关概念2037.5.2 欧拉公式2047.5.3 库拉托夫斯基定理2057.5.4 平面图的对偶图205习题7.52067.6 平面图的面着色2077.6.1 平面图的面着色定义2087.6.2 图的节点着色2087.6.3 任意图的边着色209习题7.62107.7 二部图及其匹配2107.7.1 二部图2117.7.2 匹配211习题7.7212第8章 组合计数2148.1 排列组合与二项式定理2148.1.1 排列2148.1.2 组合2158.1.3 二项式定理216习题8.12178.2 生成函数2178.2.1 组合计数生成函数2178.2.2 排列计数生成函数219习题8.22218.3 递归关系2218.3.1 递归关系的概念2218.3.2 常用的递归关系求解方法223习题8.3227附录A 符号索引228附录B 中英文名词索引231附录C 习题答案及提示236参考文献259
