1. 集合
① 集合A和集合B相等的充分必要条件是这两个集合互为子集
② 集合的运算：∪(并)、∩(交)、—(差)、⊕(对称差)
对称差A⊕B=A∪B - A∩B
2. 序偶
① 符号：< , >
② 序偶可以看作具有两个元素（两个元素具有顺序）的集合。
3. 笛卡尔积
① 令A、B是任意两个集合，则有A×B={<x,y>|(x∈A)∧(y∈B)}
例：A={1,2} B={a,b,c} 则A×B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}
② 若C≠∅，则A⊆B⇔(A×C⊆B×C)⇔(C×A⊆C×B)
③ A×B⊆C×D⇔A⊆C且B⊆D
注：A×B≠B×A（不遵循交换律） A×B×C≠A×(B×C)（不遵循结合律）
4. 关系
① 关系是序偶的集合，关系R中任一序偶<x,y>可记作<x,y>∈R 或 xRy
② domR（定义域）是关系R中所有序偶的x的集合，ranR（值域）是关系R中所有序偶的y的集合
③ 恒等关系：Ix={<x,x>|x∈X}
④ 关系的性质：
自反性⇔(∀x)(x∈X→xRx)
对称性⇔(∀x)(∀y)(x∈X∧y∈X∧xRy→yRx)
传递性⇔(∀x)(∀y)(∀z)(x∈X∧y∈X∧z∈X∧xRy∧yRz→∧xRz)
反自反性⇔(∀x)(x∈X→<x,x>∉R)
反对称性⇔(∀x)(∀y)(x∈X∧y∈X∧xRy∧yRx→x=y)
注：可能存在某种关系既是对称的，又是反对称的
5. 复合关系
① 设R为X到Y的关系，S为Y到Z的关系，则R◦S称为R和S的复合关系
② R◦S={<x,z>|x∈X∧z∈Z∧(∃y)(y∈Y∧<x,y>∈R∧<y,z>∈S)}
6. 逆关系
① 将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系
② A×B的逆关系为B×A
③ R◦S的的逆关系为S逆◦R逆
④ R是对称的⇔R=R逆
⑤ R是反对称的⇔R∩R逆⊆Ix
7. 关系的闭包运算
① 设R是X上的二元关系，则有：
R是自反的⇔r(R)=R
R是对称的⇔s(R)=R
R是传递的⇔t(R)=R
② 求关系的闭包
r(R)=R∪Ix
s(R)=R∪R逆
t(R)=R+
8. 集合的划分与覆盖
① 通过一个例子来区分划分与覆盖
例如：A={a,b,c}
S={{a,b},{b,c}} Q={{a},{a,b},{a,c}} D={{a},{b,c}} G={{a,b,c}} F={{a},{a,c}}
S，Q是A的覆盖，D，G是A的划分，F既不是覆盖也不是划分
② 如果是个划分，那么一定是覆盖
9. 等价关系
① 自反+对称+传递
② 集合A上的等价关系R决定了A的一个划分，该划分就是商集A/R
③ 集合A的一个划分确定A的元素间的一个等价关系
10. 相容关系
① 自反+对称
② 等价一定相容
③ 集合A的任意一个覆盖可以确定A的一个相容关系
④ 最大相容类：找最大的完全多边形
⑤ 完全覆盖：最大相容类的覆盖
11. 序关系
① 自反+反对称+传递
③ 哈斯图：去自环→取消所有由于传递性出现的边→箭头全向上
