总复习

集合和二元关系

命题逻辑

联结词的定义(含义及真值表定义).

会命题符号化.

永真式的证明.

永真蕴涵式的证明,记住并能熟练应用常用公式

等价公式的证明,记住并能熟练应用常用公式

会写命题公式的范式,能应用范式解决问题.

熟练掌握命题逻辑三种推理方法.

谓词逻辑

准确掌握有关概念.

会命题符号化.

掌握常用的等价公式和永真蕴涵式.包括:

带量词的公式在论域内展开式,量词否定,量词辖域扩充,量词分配公式.

会用等价公式求谓词公式的真值.(如 P66 题(3))

会写前束范式

熟练掌握谓词逻辑推理（命题的+四个规则）

集合论初步

1. 集合的表示，幂集、全集、空集
2. 集合的三种关系（包含，相等，真包含）
3. 包含排斥原理

二元关系

关系的概念,表示方法.

二元关系的性质的定义,熟练掌握性质的判断及证明.

掌握关系的复合,求逆运算(计算方法及有关性质),掌握关系的闭包运算

掌握等价关系的判断,证明,求等价类和商集。

掌握相容关系定义,简化图和简化矩阵,相容类,最大相容类,完全覆盖.

偏序关系的判断,会画 Hasse 图,会求一个子集的极小(大)元、最小(大)元、上界与下界、最小上界及最大下界.

函数

图

掌握图的基本概念.(特别注意相似的概念)

熟练掌握图中关于结点度数的定理。(会应用)

无向图的连通性的判定,连通分支及连通分支数的概念.

有向图的可达性、强连通、单侧连通和弱连通的判定。

求强分图、单侧分图和弱分图.

会求图的矩阵。

会判定欧拉图和汉密尔顿图.

会判断平面图，熟悉平面图性质.

会画一个平面图的对偶图，会着色。

掌握树的基本定义,v 和 e 间的关系式.会画生成树,会求最小生成树.

掌握根树的概念,正则 m 叉树的公式,会画最优树,会设计前缀码.

或者的二义性

范式的应用

见第一章习题

条件论证

重点掌握用定义来证

但是不同题目可能不同方法难度不一样

计算闭包的方法

1. 集合的方法

等价类

1. 任何两个等价类要么相等，要么不相交

盖住：

上确界、下确界

函数