离散数学 -- 二元关系

Comments

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

序偶定义

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

1
< x,y >

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

例如：

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

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

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

笛卡尔积定义

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

1
A x B= {< x,y >|(x ∈ A) ∧ (y ∈ B)}

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

二元关系定义

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

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

  1. 若序偶< x,y > ∈ R，通常把这一事实记为xRy，读作”x对y有关系R”;

例子

  1. 设R1为自然数集合上的小于关系，则< 2,3 > ∈ R1(或2R13)，但< 5,5 >就不属于R1。
  2. 设R2为中国城市的地区归属关系,则成都R2四川。

例题

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

  1. 0-元子集: ∅;
  2. 1-元子集: {< a,c>}, {< a,d>}, {< b,c>}, {< b,d>} ;
  3. 2-元子集: {< a,c>,< a,d>}, {< a,c>,< b,c>}, {< a,c>,< b,d>}, {< a,d>,< b,d>}, {< a,d>,< b,d>}, {< b,c>,< b,d>}
  4. 3-元子集: {< a,c>,< a,d>,< b,c>}, {< a,c>,< a,d>,< b,d>}, {< a,c>,< b,c>,< b,d>}, {< a,d>,< b,c>,< b,d>}
  5. 4-元子集: {< a,c>,< a,d>,< b,c>,< b,d>}

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

几种重要关系

  1. 当R=∅时，称R为从A到B的空关系(empty relation) ;
  2. 当R=A x B时，称R为从A到B的全关系(total relation); A上的全关系，通常记为EA。

关系的表示

关系的集合表示

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

例如：

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

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

关系的图形表示（A ≠ B）

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

  1. 集合中的元素a1,a2,… ,an 和 b1, b2,…，bm分别作为图中的结点，用一个小圆圈”o”表示。
  2. 如果<ai, bj> ∈ R,则从ai到bj可用一条有向边ai → bj相连。

关系的图形表示（A = B）

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

  1. 集合中的元素a1,a2,…，an分别作为图中的结点,用小圆圈”o”表示;
  2. 如果<ai, aj> ∈ R，则从ai到aj可用一条有向边ai → aj相连。
  3. 如果<ai, aj> ∈ R,则从ai到aj可用一条带箭头的小圆圈表示，即画个自环。

关系的性质

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

自反性与反自反性

设R是集合A上的关系。

  1. 如果对任意的x ∈ A，都有< x,x > ∈ R, 那么称R在A上是自反的(reflexive)，或称R具有自反性(reflexivity);
  2. 如果对任意的x ∈ A，都有< x,x > ∉ R,那么称R在A上是反自反的(antireflexive)，或称R具有反自反性(antirflexivity)

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

例如：

  1. 小于等于关系，包含关系，整除关系都是自反的关系。
  2. 小于关系，真包含关系都是反自反的关系。

自反性和反自反性的例子

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

  1. R = {< 1,1 >, < 1,2 >, < 2,2 >, < 3,3 >} 自反
  2. S = {< 1,2 >, < 2,3 >, < 3,1 >} 反自反
  3. T = {< 1,1 >, < 1,2 >, < 1,3 >, < 3,1 >, < 3,3 >} 非自反，非反自反

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

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

graph TB
    1((1)) --> 1((1))
    1((1)) --> 2((2))
    3((3)) --> 3((3))

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

对于关系S：

graph TB
    1((1)) --> 2((2))
    2((2)) --> 3((3))
    3((3)) --> 1((1))

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

对于关系T：

graph TB
    1((1)) --> 1((1))
    1((1)) --> 2((2))
    1((1)) --> 3((3))
    3((3)) --> 1((1))
    3((3)) --> 3((3))

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

对称性与反对称性

设R是集合A上的关系。

  1. 如果对任意的x,y ∈ A,如果< x,y > ∈ R,那么< y,x > ∈ R，则称R是对称的(symmetric)，或称R具有对称性(symmetry);
  2. 如果对任意的x,y ∈ A,如果< x,y > ∈ R且< y,x > ∈ R，那么x = y，则称R是反对称的(antisymmetric)，或称R具有反对称性(antisymmetry);

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

例如：

  1. 同姓关系，朋友关系都是对称的关系
  2. 父子关系，小于等于关系都是反对称的关系

例子的第一条比较容易理解，如果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如下:

  1. R = {< 1,1 >, < 1,3 >, < 3,1 >, < 4,4 >} 对称性
  2. S = {< 1,1 >, < 1,3 >, < 1,4 >, < 2,4 >} 反对称性
  3. T = {< 1,1 >, < 1,2 >, < 1,3 >, < 3,1 >, < 1,4 >} 非对称性，非反对称性
  4. V = {< 1,1 >, < 2,2 >, < 3,3 >, < 4,4 >} 对称性，反对称性

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

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

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

graph TB
    1((1)) --> 1((1))
    1((1)) --> 3((3))
    3((3)) --> 1((1))
    4((4)) --> 4((4))

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

对于关系S：

graph TB
    1((1)) --> 1((1))
    1((1)) --> 3((3))
    1((1)) --> 4((4))
    2((2)) --> 4((4))

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

对于关系T：

graph TB
    1((1)) --> 1((1))
    1((1)) --> 2((2))
    1((1)) --> 3((3))
    3((3)) --> 1((1))
    1((1)) --> 4((4))

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

对于关系V：

graph TB
    1((1)) --> 1((1))
    2((2)) --> 2((2))
    3((3)) --> 3((3))
    4((4)) --> 4((4))

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

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

传递性

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

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

例如：

  1. 小于等于关系是传递的关系
  2. 父子关系不是传递的关系

传递性的例子

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

  1. R = {< 1,1 >, < 1,2 >, < 2,3 >, < 1,3 >} 传递性
  2. S = {< 1,2 >} 传递
  3. T = {< 1,1 >, < 1,2 >, < 2,3 >} 非传递
  4. V = {< 1,2 >, < 2,3 >, < 1,3 >, < 2,1 >} 非传递

在第一个例子里面，像< 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，

  1. 如果 x ≤ y 或 y ≤ x，则称x与y可比
  2. 如果 x ≤ y 且不存在 z ∈ A使得 x ≤ z ≤ y，则称y覆盖x

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

codinghuangPHP Developer

PHP开发者~