在编译器进行数据流分析的时候，很多的分析都是基于gen和kill来做的，这是一个经典的算法框架，然而，要真正的理解这个算法框架的核心，例如结束迭代的条件（慢慢的达到不动点），IN和OUT的初始化什么时候全是0，什么时候全是1，这些细节都是需要通过理论去支撑的，这其中需要用到离散数学的知识。本篇博客总结自电子科技大学大学的网课。

由两个元素按照一定的次序组成的二元组称为序偶，记作：

其中x是第一个元素，y是第二个元素。

例如：

张明喜欢离散数学可用序偶表示为:

通常情况下，尖括号< >都是用于表明元素之间是有顺序性的。

由定义可见，两个序偶< a,b > = < c,d >，当且仅当 a = c, b = d

我们可以用序偶来定义笛卡尔积，设A，B是两个集合,称集合

为集合A与B的笛卡尔积。

设A,B为两个非空集合，称AxB的任意子集R为从A到B的一个二元关系，简称关系(relation)。其中A称为关系R的前域，B称为关系R的后域。如果A=B，则称R为A上的一个二元关系。（其中，二元指的就是A，B两个集合）

从定义可以得知，二元关系本身也是一个集合，并且二元关系中的元素也是序偶的形式。

假没A={a,b} B= {c,d} ,试写出从A到B的所有不同关系。解 首先求丙个集合的笛卡尔积: A x B = {< a,c >,< a,d >,< b,c >,< b,d >}.再求A x B的所有不同子集:

所以，上面的16个不同子集就是从A到B的所有不同关系。

因为关系被定义为笛卡尔积的子集，所以，关系也是集合。所以，可以使用集合的表示方法（枚举法和叙述法）来表示一个关系。

例如：

集合 A = {1,2,3,4}上的整除关系 R 可用枚举法表示为：R = {< 1,1 >, < 1,2 >, < 1,3 >, < 1,4 >, < 2,2 >, < 2,4 >, < 3,3 >, < 4,4 >}

实数集R上的”相等”关系S可用叙述法表示为：S= {< x,y > |(x,y ∈ R) ∧ (x = y)}。

设 A = {a1,2,.. ,an}, B = {b1,b,… ,bm}, R是从A到B的一个关系。

设 A = {a1,a2,… ,an}, R是A上的一个关系。

我们主要关注同一个集合上的关系

设R是集合A上的关系。

这里需要注意的是，任意 … 都有，这暗示着x要取遍集合A中的每个元素需要注意的是，我们说关系R是不是有自反性，是基于某一个给定的集合来进行讨论的，而不仅仅是关系R。因为R具有自反性的全称是R在A上是自反的

例如：

设A = {1,2,3}，定义A上的关系R,S和T如下:

根据自反性的例子，< 1,1 >、< 2,2 >、< 3,3 >都在集合R里面，所以R具有反自反性；而根据反自反性的定义，这三组序偶都不在关系S里面，所以S是反自反的；因为T不满足自反也不满足反自反，所以T是非自反的也是非反自反的。

用关系图来理解自反性和反自反性。对于关系R：

如果集合A里面的每个元素都有一个自环，那么这个关系具有自反性。

对于关系S：

如果集合A里面的每个元素都不存在自环，那么这个关系具有反自反性。

对于关系T：

如果集合A里面的元素有的有自环，有的没有自环，那么这个关系既没有自反性，没有反自反性。

设R是集合A上的关系。

注意，对称性和反对称性的描述与自反性和反自反性的区别，这里是任意 … 如果，也就是说，不需要取遍集合A中的每个元素

例如：

例子的第一条比较容易理解，如果a和b同姓，那么b和a一定同姓；如果a和b是朋友，那么b和a一定是朋友例子的第二条父子关系为什么是反对称性呢？因为“如果< x,y > ∈ R且< y,x > ∈ R，那么x = y”是蕴含式，因为“如果< x,y > ∈ R且< y,x > ∈ R”为假，所以整句是真的。所以父子关系是反对称性；小于等于关系中，满足蕴含式前件为真，后件也为真，所以整句为真，所以具有反对称性。

设A = {1,2,3,4}，定义A上的关系R,S,T和V如下:

我们会发现两点与自反性和反自反性的差异：

第一，对称性不需要包含所有满足对称的序偶；第二，关系可以同时具备对称性和反对称性，但是关系不可能同时具备自反性和反自反性（因为同一个节点不可能既有自环又没有自环）

用关系图来理解对称性和反对称性。对于关系R：

1到3有一条边，3到1也有一条边，所以具有对称性。

对于关系S：

1到3有一条边，但是3到1没有边；1到4有一条边，但是4到1没有边；2到4有一条边，但是4到2没有边。所以具有反对称性。

对于关系T：

1到2有一条边，但是2到1没有边；1到3有一条边，3到1有一条边；1到4有一条边，但是4到1没有边。所以既不是对称性，也不是反对称性。

对于关系V：

只有自环，所以既具有对称性，也具有反对称性。

我们会发现，对称性和反对称性更多的是关注节点与节点之间有没有边，而自反性和反自反性更多的是关注节点本身有没有自环。

设R是集合A上的关系。对任意的 x,y,z ∈ A，如果< x,y > ∈ R且< y,z > ∈ R，那么< x,z > ∈ R，则称R是传递的(transitive)，或称R具有传递性(transitivity)。

注意，传递性与自反性和反自反性的区别，这里是任意 … 如果，也就是说，不需要取遍集合A中的每个元素

例如：

设A = {1,2,3}，定义A上的关系R,S,T和V如下:

在第一个例子里面，像< 1,1 >这种自环的序偶，是一定可以找得到传递的（除非没有第二个1开头的序偶了，但是这种情况，也是符合传递性，因为蕴含式的前件为假，所以式子为真）；< 1,2 >, < 2,3 >, < 1,3 >满足传递性的定义；< 2,3 >找不到3开头的序偶；< 1,3 >找不到3开头的序偶。所以R关系式具有传递性的。

在第二个例子里面，因为找不到2开头的序偶，所以S关系具有传递性。

在第三个例子里面，因为< 1,2 >, < 2,3 >找不到< 1,3 >，所以不具有传递性。

第四个例子里面，因为< 1,2 >, < 2,1 >找不到< 1,1 >，所以不具有传递性。

设R是非空集合A上的关系，如果R是自反的、反对称的、传递的，则称R为A上的偏序关系(partial order relation), 记为”≤”。读作”小于等于”，并将”< a,b > ∈ ≤”记为 a ≤ b。序偶 < A, ≤ > 称为偏序集(partial order set)。

用”≤”来表示偏序关系是由于”小于等于关系”是偏序关系的典型范例，此时已不局限于”小于等于”关系，它指代的是在偏序关系中元素之间的先后顺序,不局限于通常的数的大小。

我们可以这样这样去记忆反对称性：如果 x ≤ y，一定没有y ≤ x，除非x = y

要理解偏序集的一个核心要点是，不需要让集合里面的每一个元素都满足偏序，只要能够找到的元素之间满足偏序，那我们就说是偏序的。

设R是非空集合A上的偏序关系，∀ x,y ∈ A，

通过定义可知，如果x和y之间有覆盖关系，那么x和y之间是可比的。（因为可比是覆盖的前提）