《离散数学》总复习讲解.ppt

《离散数学》总复习;1.主范式、集合、布尔格(有补分配格)运算 2.命题符号化+命题/谓词逻辑推理 3.前束范式 4.元素与集合、集合与集合的关系(判断,证明) 5.排列组合、容斥原理、递推方程 6.关系合成、函数复合、置换乘法 7.等价关系(等价类、商集、划分、自然映射) 8.偏序集(偏序关系、覆盖、哈斯图)、格 9.同构=同态∩双射 10.代数系统及其性质(判断) 11.域=整环∩除环 0.重要概念:幂集,笛卡积,闭包,积代数,循环群;;0.重要概念:生成子图,自补图,自对偶图,割集;第1章 命题逻辑;联结词与复合命题(小结);1.3 命题逻辑等值演算;基本等值式（续）;1.4复合联结词（重要的非重点）;1.5 主范式（重点）;1.6 命题逻辑推理（重点）;注意事项1：命题;注意事项2：蕴涵联结词“?”;了解概念、掌握方法;第2章 一阶逻辑;一阶逻辑与命题逻辑关系;2.3 一阶逻辑等值式;注意事项1：前束范式（重点）;2.4 一阶逻辑推理理论（重点）;注意事项2：一阶逻辑中命题符号化;了解;第3章 集合的基本概念和运算;3.1 集合的基本概念;3.2 集合的基本运算（重点）;集合运算的文氏图表示;集合运算的算律（重点）;集合运算的算律（续）;3.3 集合中元素的计数;注意;了解概念、掌握方法;第4章 二元关系与函数;4.1 集合的笛卡儿积和二元关系;A上重要关系;4.2 关系的运算;4.3 关系的性质（基础，重中之重）;关系性质判别;运算与性质的关系（了解）;4.5 等价关系和偏序关系（重点）;(2) 偏序关系,覆盖,偏序集与哈斯图;注意事项：特定元素;4.6 函数;了解;第5章 代数系统的一般性质;5.1 一、二元运算, 代数系统, 封闭性;二元运算可能的性质;一些二元运算的性质;一些二元运算的性质;二元运算可能的特异元素;一些二元运算的特异元素;由运算表判别算律的一般方法;5.2 代数系统及其子代数和积代数;5.3 代数系统的同态与同构(重点);满同态保持运算的算律及特异元素;注意事项;了解;第6章 几个典型的代数系统;6.1 (半)群;(半)群实例;掌握重要概念，了解性质;6.2 环与域;环与域的实例;6.3 格与布尔代数(“布尔代数”是重点);6.3 格与布尔代数;注意事项;了解;第四部分 图论;第7章 图的基本概念;7.1 无向图及有向图;2）既无平行边也无环的图称为简单图. 题7.13 n阶无向完全图Kn:边数m=n(n-1)/2,?=?=n-1.题7.7 n阶有向完全图: 边数m=n(n-1), ?=?=2(n-1), ?+=?+=?-=?-=n-1. 习题7.9 3）若G ??G 且V ?=V，则称G ?为G的生成子图. 4）设G=V,E为n阶无向简单图，以V为顶点集,所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作 . 习题7.8 若G? , 则称G是自补图.习题7.20，7.12 习题7.12，7.10；例7.10;7.2 通路、回路、图的连通性(了解);割集（重点）;7.3 图的矩阵表示;有向图的邻接矩阵（重点）;7.4 最短路径与关键(最长)路径;了解;第8章 一些特殊的图;8.1 二部图;8.2 欧拉图;8.3 哈密顿图;无向哈密顿图的一个充分条件;8.4 平面图（欧拉公式是重点）;了解;第9章 树;9.1 无向树及生成树;9.2 根树及其应用;了解;综合;第10章 组合分析初步;10.2 基本排列组合的计数方法(重点);注意事项与了解内容;二/多项式定理与组合恒等式;“排列组合”与前面章节融合 ;10.3 递推方程的求解与应用;10.3 递推方程的求解与应用;应用实例;函数与关系的计数;n个球放到m个盒子的方法计数