离散数学考试重点

重点参考：PPT中参考作业解题思路也可参考

1.逻辑推理

1. 分配律结合律主析取合取范式极大项极小项

2. 自然推理系统附加化简 "要拿满分"

拒取式（->知道后面）假言推理(->知道前面) 析取三段论（有析取）假言三段论(A推B，B推C，得到A推C)

直接推理法

附加前提法(结论带->，前件作为条件)

归谬法(结论否定作为前提，推出矛盾结论)

1. 定义域值域域

2. 等价关系与划分自反性传递性对称性证明这些性质参考作业

偏序关系对称反对称

商集与集合的划分等价类

偏序集画哈斯图

3. 函数单射满射双射(y不重 x不漏不重不漏)

结合图论一起考察解决图的同构问题

4. 关系矩阵传递闭包P81-P93 Warshell算法传递闭包有什么用参考ppt例题

5. 通过关系运算符求解一个集合

并交补合成

6. 容斥原理 Venn图(文氏图韦恩图)

1. 给出边的集合点画出无向图

2. 求所有顶点的度数注意自环

3. 求补图、自补图

5. 两幅图能不能代替同构给出证明

双射

6. 求点连通度边连通度

7. 图的矩阵表示

邻接矩阵参考作业 "好好掌握"

8. 由无向图求最小生成树权重

破圈法(Kruskal算法) "要拿满分"

9. 点割集边割集

10. 哈密顿图(走所有点) 欧拉图(只走一次点) 平面图

证明简单说明即可符合什么公式

11. 二部图匹配最大匹配完美匹配备匹配 Hall定理

1. 加法规则乘法规则

2. 递推方程

3. 生成函数