离散数学复习：二元关系

二元关系

1. 序偶和笛卡尔乘积

1.1 序偶

定义：由两个元素按照一定的次序组成的二元组称为序偶，记做$<x,y>$，其中**$x$是第一元素，$y$是第二元素**。【顺序很重要】

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

1.2 笛卡尔乘积

1.2.1 定义

定义：设A，B是两个集合，称集合 A × B = { < x , y > ∣ ( x ∈ A ) ∧ ( y ∈ B ) } A\times B=\{|(x\in A) \land (y\in B)\} A×B={<x,y>∣(x∈A)∧(y∈B)}为集合A与B的笛卡尔乘积。

1.2.2 性质

• 笛卡尔积不满足交换律
• $A\times B=\varnothing$当且仅当$A=\varnothing$或者$B=\varnothing$
• 设A，B，C是任意三个集合，则不一定有$A\times (B\times C)=(A\times B)\times C$，即笛卡尔积不满足结合律
• 当A，B都是有限集合时，$|A\times B|=|B\times A|=|A|\times B$
• 笛卡尔积对并运算和交运算满足分配律

1.3 推广

定义：

• 由n个元素$a_1,a_2,...,a_n$按照一定的次序组成的n元组称为n重有序组，记做$<a_1,a_2,...,a_n>$，其中$a_1$是第一个元素，$a_2$是第二个元素，……，$a_n$是第n个元素。

• 设$A_1,A_2,...,A_n$是n个集合，称集合

  A 1 × A 2 × … … × A n = { < a 1 , a 2 , . . . , a n > ∣ a i ∈ A i , i = 1 , 2 , 3 , . . . , n } A_1\times A_2\times ……\times A_n=\{|a_i\in A_i,i=1,2,3,...,n\} A1​×A2​×……×An​={<a1​,a2​,...,an​>∣ai​∈Ai​,i=1,2,3,...,n}为集合$A_1,A_2,...,A_n$的笛卡尔积。当$A_1=A_2=...=A_n=A$时，可记$A_1\times A_2\times \dots \dots \times A_n=A^n$

  

2. 关系的定义

2.1 二元关系定义

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

几种重要的关系：

• 当$R=\varnothing$时，称R为从A到B的空关系(empty relation) ;
• 当$R=A\times B$时，称R为从A到B的全关系(total relation) ; A上的全关系通常记为$E_A$。
• 当 R = I A = { < x , x > ∣ x ∈ A } R=I_A=\{|x∈A\} R=IA​={<x,x>∣x∈A}时，称R为A上的恒等关系(identity relation)。

有限集合的二元关系的数量：

当集合A，B都是有限集时, $A\times B$共有$|A|\times |B|$ 个不同的元素，这些元素将会产生$2^{|A|\times |B|}$ 个不同的子集。即，从A到B的不同关系共有$2^{|A|\times |B|}$个。

2.2 定义域和值域

定义：设R是从A到B的二元关系，则A为关系R的前域，B为关系R的后域。

令： C = { x ∣ x ∈ A , ∃ y ∈ B , < x , y > ∈ R } C= \{x|x∈A,\exists y∈B,< x,y>∈R\} C={x∣x∈A,∃y∈B,<x,y>∈R} , D = { y ∣ y ∈ B , ∃ x ∈ A , < x , y > ∈ R } D=\{y|y∈B,\exists x∈A, ∈R\} D={y∣y∈B,∃x∈A,<x,y>∈R}。

称C为R的定义域(domain)，记为$C=domR$；D为R的值域(range)，记为$D=ranR$；

fldR = $domR\cup ranR$为R的域( field)。

2.3 n元关系

3. 关系的表示

3.1 集合表示法

关系是一种特殊的集合，因此集合的两种基本表示法(枚举法和叙述法) ，可以用到关系的表示中。

• 枚举法
• 叙述法
• 图示法

3.2 关系图表示法

• $A\ne B$

• $A=B$

  

3.3 关系矩阵法

关系运算用上述的两种方式进行较为困难，使用关系矩阵比较简便。

定义：设 A = { a 1 , a 2 , . . . , a n } , B = { b 1 , b 2 , . . . , b m } A= \{a_1,a_2, ... ,a_n\}, B= \{b_1,b_2,... ,b_m\} A={a1​,a2​,...,an​},B={b1​,b2​,...,bm​}，R是从A到B的一个二元关系，称矩阵$M_R=(m_{ij}{)}_{n\times m}$ 为关系R的关系矩阵(relation matrix) ,其中:$\{\begin{array}{l}1<a_i,b_j>\in R\\ 0<a_i,b_j>\notin R\end{array}(1\le i\le m,1\le j\le n)$又称$M_R$为R的邻接矩阵(adjacency matrix)。

3.4 布尔矩阵的运算

3.4.1 布尔矩阵的交和并

3.4.2 布尔矩阵的积运算

4. 关系的运算

4.1 关系的并交差补运算

关系是一种特殊的集合，因此集合的所有基本运算(并、交、差、补)，都可以应用到关系中，并且同样满足集合的所有运算定律。

4.2 关系的复合运算

定义：设A，B，C是3三个集合，R是从A到B的关系，S是从B到C的关系（即$R：A\to B,S：B\to C$），则R与S的复合关系(合成关系）（composite relation）RoS是从A到C的关系，并且： R o S = { < x , z > ∣ ( x ∈ A ) ∧ ( z ∈ C ) ∧ ( ∃ y ) ( y ∈ B ∧ x R y ∧ y S z ) } R o S=\{|(x∈A)\land (z∈C)\land (\exists y)(y∈B\land xRy\land ySz)\} RoS={<x,z>∣(x∈A)∧(z∈C)∧(∃y)(y∈B∧xRy∧ySz)}。运算"o"称为复合运算（composite operation）。

​ ——R的后域是S的前域

4.3 逆运算

定义：设A，B是两个集合，R是A到B的关系，则从B到A的关系 R − 1 = { < b , a > ∣ < a , b > ∈ R } R^{-1}=\{|∈R\} R−1={<b,a>∣<a,b>∈R}称为R的逆关系(inverse relation) ,运算“-1” 称为逆运算(inverse operation)。

• $(R^{-1}{)}^{-1}=R$
• KaTeX parse error: Undefined control sequence: \O at position 1: \̲O̲^{-1}=\O
• $(A\times B{)}^{-1}=B\times A$

求逆运算在三种表示法中的体现：

5. 关系的运算定律

5.1 复合运算性质

设A、B、C和D是任意四个集合，R、S和T分别是从A到B，B到C和C到D的二元关系，$I_A$和$I_B$分别是A和B上的恒等关系，则

证明方法：

证明两个关系相等，即证明两个集合相等；证明两个集合相等，也即证明两个集合相互包含。

以结合律为例，证明两个集合相等：

• 分配律

5.2 逆运算的运算定律

设A，B，C是三个集合，R, S分别是从A到B和从B到C的关系，则有：
$$(R\circ S{)}^{-1}=S^{-1}\circ R^{-1}$$

6. 关系的幂运算

只要运算满足结合律，那么一定可以定义该运算的幂运算。

关系的复合运算满足结合律，因此可以定义关系的复合运算的幂运算。

6.1 幂运算的定义

设R是集合A上的关系，则R的n次幂，记为$R^n$，定义如下：

• $R^0=I_A$——【why？考虑同一律】
• $R^1=R$
• $R^{n+1}=R^n\circ R=R\circ R^n$

$R^n$仍是A上的关系，表示R多次自我复合的结果：

• $R^{m+n}=R^m\circ R^n=R^n\circ R^m=R^{m+n}$
• $(R^m{)}^n=R^{mn},m,n\in N$

6.2 幂运算的性质

由前例可见，$R^n$的基数并非随着n的增加而增加，而是呈递减趋势

当$n\ge |A|$时，则$R^n\subseteq {\cup }_{i=1}^{|A|}{R}^i$

6.3 幂运算收敛定理

定理：设A是有限集合，且$|A|=n$，R是A上的关系，则：
$${\cup }_{i=1}^{\infty }{R}^i={\cup }_{i=1}^n{R}^i$$

7. 关系的性质

关系的性质可以对关系进行分类。

7.1 自反性与反自反性

定义：

设R是集合A上的关系，

• 如果对任意的$x\in A$，都有$<x,x>\in R$，那么称R在A上是自反的，或者称R具有自反性。
• 如果对任意的$x\in A$，都有$<x,x>\notin R$，那么称R在A上是反自反的，或者称R具有反自反性。

对于关系矩阵上的体现，会体现在对角线上：

总结

• 存在既不是自反的也不是反自反的关系;
• 关系R是自反的当且仅当R的关系图中每个结点都有自环，关系R是反自反的当且仅当R的关系图中每个结点都无自环;
• 关系R是自反的当且仅当R的关系矩阵的主对角线上全为1，关系R是反自反的当且仅当R的关系矩阵的主对角线上全为0.

7.2 对称性

设R是A上的关系：

• 如果对任意的$x,y\in A$，如果$<x,y>\in R$，那么$<y,x>\in R$，那么称R是对称的，或称R具有对称性。
• 如果对任意的$x,y\in A$，如果$<x,y>\in R且<y,x>\in R$，那么$x=y$，那么称R是反对称性的。

存在既是对称也是反对称的关系，也存在既不是对称也不是反对称的关系。

7.3 传递性

定义：设R是集合A上的关系，对任意的$x,y,z\in A$，如果$\in R $且$\in R$，那么$\in R$，则称R是传递的，或称R具有传递性。

对于关系图上的传递性的表现：有a->b, b->c一定有a->c

关系矩阵：

7.4 关系性质的判定定理

对具体集合上的具体关系，我们可根据关系图和关系矩阵等方法来判定关系的性质，但对于抽象集合上的抽象关系，则存在一定的局限性。为此，我们从集合运算的观点，给出相应的判定定理。

7.4.1 判定定理

设R是集合A上的关系，则：

• R是自反的，当且仅当$I_A\subseteq R$——最小的是$I_A$
• R是反自反的，当且仅当KaTeX parse error: Undefined control sequence: \O at position 11: R\cap I_A=\̲O̲
• R是对称的，当且仅当$R=R^{-1}$
• R是反对称的，当且仅当$R\cap R^{-1}\subseteq I_A$——只可能是$I_A$中的元素
• R是传递的，当且仅当$R\circ R\subseteq R$

7.4.2 判定方法总结

7.4.3 关系性质判定例子

一个关系可能满足多种性质：

一个关系可能多种性质都不满足：

7.5 关系性质的保守性

关系既可做各种集合基本运算，又可做关系特有的复合运算和求逆运算。具有特殊性质的关系通过各类运算后产生的新关系是否仍然保持原有的特殊性质呢？这就是关系性质的保守性问题。

8. 关系的闭包

​ 一个关系可能不具备某一个特殊性质。但是，如果希望它有我们希望它具备的某一个性质，应该如何操作呢？我们可以通过添加一些元素，使得关系具备我们想要的性质。例如，对给定集合A= {1, 2, 3}上的关系R= {< 1,1 >, < 1,2 >, < 2,1 >}，它不具有自反性。根据自反性的定义，在关系R中添加< 2,2>, < 3,3 >这两个元素后，所得到的新关系$R^{{}^{\prime }}$就具有自反性。另外还可以添加<2,2>, ❤️,3>, <1,3>，得到的新关系$R^{{}^{\prime \prime }}$仍然具有自反性。

​ 如何在给定关系中添加最少的元素，使其具有需要的特殊性质，这就是关系的闭包问题。

​ 自反性，对称性，传递性可以通过添加元素得到，但是对于反自反性，反对称性，无法通过添加元素得到，只能通过删除元素得到。这里不考虑删除元素得到关系性质的情况。

8.1 闭包的定义

设R是集合A上的关系，若存在A上的另一个关系$R^{\prime }$，满足：

• $R^{\prime }$是自反的（对称的，或传递的）——满足性质
• 对于任何自反的（对称的，传递的）关系$R^{{}^{\prime \prime }}$，如果$R\subseteq R^{{}^{\prime \prime }}$，就有$R^{{}^{\prime }}\subseteq R^{{}^{\prime \prime }}$。则称$R^{\prime }$为R的自反闭包（对称闭包或者传递闭包），分别记为$r(R)(s(R)或t(R))$

8.2 闭包求解

利用关系图求闭包

• 检查R的关系图，在没有自环的结点处加上自环，可得r®的关系图;
• 检查R的关系图，将每条单向边全部改成双向边，可得s( R)的关系图;
• 检查R的关系图，从每个结点出发，找到其终点，如果该结点到其终点没有边相连，就加上此边，可得t®的关系图.

定理：

设 $R$ 是集合 $A$ 上的关系, 则
(1) $r(R)=R\cup I_A$;
(2) $s(R)=R\cup R^{-1}$;
(3) $t(R)={\bigcup }_{i=1}^{\infty }{R}^i$, 若 $|A|=n$ ，则 $t(R)={\bigcup }_{i=1}^n{R}^i$.