离散数学：二元关系

二元关系

序偶和笛卡尔积

有序组

Definition

由两个元素按照一定的次序组成的二元组成为序偶，记作<x,y>,其中x是第一元素，y是第二元素。

tips：

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

笛卡尔积

Definition

设A，B是两个集合，称集合$A\times B=\{<x,y>\mid (x\in A)\wedge (y\in B)\}$为集合A与B的笛卡尔积。

性质

1. 设A，B是任意两个集合，则不一定有$A\times B=B\times A$,即笛卡尔积不满足交换律
2. $A\times B=\varnothing \mathrm{当}\mathrm{且}\mathrm{仅}\mathrm{当}A=\varnothing \mathrm{或}\mathrm{者}B=\varnothing$;
3. 设A，B，C是任意三个集合，则不一定有$A\times (B\times C)=(A\times B)\times C$,即笛卡尔积不满足结合律
4. 当集合A,B都是有限集时，$\mid A\times B\mid =\mid B\times A\mid =\mid A\mid \times \mid B\mid$
5. 笛卡尔积对并运算和交运算满足分配率。

推广

• 由n个元素$a_1,a_2,\cdots ,a_n$按照一定次序组成n元成为n重有序组，记作$<a_1,a_2,\cdots ,a_n>$，其中$a_1$是第一个元素，$a_2$是第二个元素，...,$a_n$是第n个元素。
• 设$A_1,A_2,\cdots ,A_n$是n个集合，称集合$A_1\times A_2\times A_3\times \cdots \times A_n=\{<a_1,a_2,\cdots ,a_n>\mid a_i\in A_i,i=1,2,3,\cdots ,n\}$为集合$A_1,A_2,\cdots ,A_n$的笛卡尔积。当$A_1=A_2=\cdots =A_n=A$时，可记$A_1\times A_2\times \cdots \times A_n=A^n$。

结论

• 两个n重有序组$<a_1,a_2,\cdots ,a_n>=<b_1,b_2,b_3,\cdots ,b_n>$当且仅当$a_i=b_i,i=1,2,3,\cdots ,n$

• 当集合$A_1,A_2,\cdots ,A_n$都是有限集时，

  $\mid A_1\times A_2\times \cdots \times A_n\mid =\mid A_1\mid \times \mid A_2\mid \times \cdots \times \mid A_n\mid$

关系的定义

Definition

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

标记

1. 若序偶$<x,y>\in R$,通常把这一事实记为xRy，读作“x对y有关系R”；
2. 若序偶$<x,y>\notin R$,通常把这一事实记为$x\mathrm{R̸}y$,读作“x对y没有关系R”

几种重要的关系

1. 当$R=\varnothing$时，称R为从A到B的空关系(empty relation);
2. 当$R=A\times B$时，称R为从A到B的全关系(total relation);A上的全关系通常记为$E_A$
3. 当$R=I_A=\{<x,x>\mid x\in A\}$时，称R为A上的恒等关系(identity relation)

有限集合的二元关系数量

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

定义域和值域

Definition

设R是从A到B的二元关系，则A为关系R的前域，B为关系R的后域。令：$C=\{x\mid x\in A,\mathrm{\exists }y\in B,<x,y>\in R\},D=\{y\mid y\in B,\mathrm{\exists }x\in A,<x,y>\in R\}$。称C为R的定义域(domain),记为C=domR；D为R的值域(range),记为D=ranR；$fldR=domR\cup ranR$为R的域(field)。

n元关系推广

Definition

设$A_1,A_2,\cdots ,A_n$为n个非空集合，称$A_1\times A_2\times \cdots \times A_n$的任意子集R为$A_1,A_2,\cdots ,A_n$的一个n元关系(n-ray relation)。

关系的表示

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

关系的矩阵表示

Definition

设$A=\{a_1,a_2,\cdots ,a_n\},B=\{b_1,b_2,\cdots ,b_m\}$,R是从A到B的一个二元关系，称矩阵$M_R=(m_{ij}{)}_{n\times m}$为关系R的关系矩阵(relation matrix),其中： $$m_{ij}=\{\begin{array}{l}1<a_i,b_i>\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)。

布尔矩阵的并和交运算

Definition

1. 如果$A=(a_{ij})$和$B=(b_{ij})$是两个$m\times n$的矩阵，则A和B的并也是一个$m\times n$的矩阵，记为$A\vee B=C=(c_{ij})$，其中： $$c_{ij}=\{\begin{array}{l}1if{a}_{ij}=1or{b}_{ij}=1\\ 0if{a}_{ij}=0and{b}_{ij}=0\end{array}$$

2. 如果$A=(a_{ij})$和$B=(b_{ij})$是两个$m\times n$的矩阵，则A和B的交也是一个$m\times n$的矩阵，记为$A\wedge B=C=(c_{ij})$，其中： $$c_{ij}=\{\begin{array}{l}1if{a}_{ij}=1and{b}_{ij}=1\\ 0if{a}_{ij}=0or{b}_{ij}=0\end{array}$$

布尔矩阵的积运算

Definition

如果$A=(a_{ij})$是$m\times p$矩阵，$B=(b_{ij})$是$p\times n$矩阵，则A和B的积是一个$m\times n$矩阵，记为$A\odot B=C=(c_{ij})$,其中: $$c_{ij}=\{\begin{array}{l}1\mathrm{\exists }k,a_{ik}=1and{b}_{kj}=1\\ 0else\end{array}$$

关系的运算

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

Definition

设R，S是从A到B的两个关系，则 $$\begin{gathered} R\cup S=\{<x,y>\mid (xRy)\vee (xSy)\} \\ R\cap S=\{<x,y>\mid (xRy)\wedge (xSy)\} \\ R-S=\{<x,y>\mid (xRy)\wedge (x\mathrm{S̸}y)\} \\ \bar{R}=\{<x,y>\mid (x\mathrm{R̸}y)\}(\mathrm{即}\mathrm{全}\mathrm{集}\mathrm{为}A\times B) \end{gathered}$$

关系的复合运算

Definition

设A，B，C是三个集合，R是从A到B的关系，S是从B到C的关系（即$R:AarrowB,S:BarrowC$）,则R与S的复合关系(合成关系)(composite relation)$R\circ S=\{<x,z>\mid (x\in A)\wedge (z\in C)\wedge (\mathrm{\exists }y)(y\in B\wedge xRy\wedge ySz\}$。运算$"\circ "$成为复合运算(composite operation)。

$M_{R\circ S}=M_R\odot M_S$

关系的逆运算

Definition

设A，B是两个集合，R是A到B的关系，则从B到A的关系$R^{-1}=\{<b,a>\mid <a,b>\in R\}$称为R的逆关系(inverse relation),运算${"}^{-1}"$成为逆运算(inverse operation)。

$(R^{-1}{)}^{-1}=R$

${\varnothing }^{-1}=\varnothing$

$(A\times B{)}^{-1}=B\times A$

总结

关系的运算定律

结合律与同一律

Theorem

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

1. $(R\circ S)\circ R=R\circ (S\circ T)$
2. $I_A\circ R=R\circ I_B=R$

分配率

Theorem

设A、B、C、和D是任意四个集合，R是从A到B的关系，$S_1,S_2$是从B到C的关系，T是从C到D的关系，则

1. $R\circ (S_1\cup S_2)=(R\circ S_1)\cup (R\circ S_2)$
2. $R\circ (S_1\wedge S_2)\subset (R\circ S_1)\cap (R\circ S_2)$
3. $(S_1\cup S_2)\circ T=(S_1\circ T)\cup (S_2\circ T)$
4. $(S_1\cap S_2)\circ (T)\subset (S_1\circ T)\cap (S_2\circ T)$

逆运算性质定律

Theorem

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

设R，S是从集合A到集合B的关系，则有

1. 分配性 $$\begin{gathered} (R\cup S{)}^{-1}=R^{-1}\cup S^{-1} \\ (R\cap S{)}^{-1}=R^{-1}\cap S^{-1} \\ (R-S{)}^{-1}=R^{-1}-S^{-1} \end{gathered}$$

2. 可换性 $(\bar{R}{)}^{-1}=\overline{R^{-1}}$

3. $(R^{-1}{)}^{-1}=R$

4. 单调性$S\subset R\iff S^{-1}\subset R^{-1}$

关系的幂运算

Definition

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

1. $R^0=I_A$
2. $R^1=R$
3. $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^{mn},m,n\in N$

tips

• $R^n$的基数并非随着n的增加而增加，而是递减的趋势

• 当$n\ge \mid A\mid$,则 $$R^n\subset \bigcup _{i=1}^{\mid A\mid }{R}^i$$

幂运算的收敛定理

Theorem

设A是有限集合，且$\mid A\mid =n$,R是A上的关系，则 $$\bigcup _{i=1}^{\mathrm{\infty }}{R}^i=\bigcup _{i=1}^n{R}^i$$

关系的性质

自反性和反自反性

Definition

设R是集合A上的关系。

1. 如果对任意$x\in A$,都有$<x,x>\in R$,那么称R在A上市自反的(reflexive),或称R具有自反性(reflexivity);
2. 如果对于任意$x\in A$,都有$<x,x>\notin R$,那么称R在A上是反自反的(antireflexive),或称R具有反自反性(antireflexivity);

eg:

• 同姓关系，小于等于，包含、整除关系都是自反的关系
• 父子关系，小于关系，真包含关系都是反自反的的关系

对称性

Definition

设R是集合A上的关系.

1. 如果对任意的$x,y\in A$，如果$<x,y>\in R$,那么$<y,x>\in R$,则称R是对称的(symmetric),或称R具有对称性(symmetry);
2. 如果对任意的$x,y\in A$,如果$<x,y>\in R\mathrm{且}<y,x>\in R$,那么x=y，则称R是反对称的(antisymmetric),或称R具有反对称性；

eg:

• 同姓关系、朋友关系，同余关系都是对称的关系
• 父子关系，小于等于关系，包含关系，整除关系都是反对称的关系

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

关系图判定法：关系R是对称的当且仅当R的关系图中，任何一对结点之间，要么有方向相反的两条边，要么无边，关系R是反对称的当且仅当R的关系图中，任何一对结点之间至多只要一条边。

传递性

Definition

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

eg:

• 同姓关系，小于关系，包含关系，整除关系，飞机航线的可达关系都是传递的关系；

• 父子关系，朋友关系，婚姻关系，飞机航线的直达关系都不是可传递的。

### 关系集合的判定定理

Definition

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

1. $R\mathrm{是}\mathrm{自}\mathrm{反}\mathrm{的}\iff I_A\subset R$;
2. $R\mathrm{是}\mathrm{反}\mathrm{自}\mathrm{反}\mathrm{的}\iff R\cap I_A=\varnothing$;
3. $R\mathrm{是}\mathrm{对}\mathrm{称}\mathrm{的}\iff R=R^{-1}$;
4. $R\mathrm{是}\mathrm{反}\mathrm{对}\mathrm{称}\mathrm{的}\iff R\cap R^{-1}\subset I_A$;
5. $R\mathrm{是}\mathrm{传}\mathrm{递}\mathrm{的}\iff R\circ R\subset R$

总结：关系性质判定方法

	自反性	反自反性	对称性	反对称性	传递性
定义	$\mathrm{\forall }x\in A,\mathrm{有}<x,x>\in R$	$\mathrm{\forall }A,\mathrm{有}<x,x>\notin R$	$\mathrm{\forall }x,y\in A,\mathrm{若}<x,y>\in R,\mathrm{则}<y,x>\in R$	$\mathrm{\forall }x,y\in A，\mathrm{若}<x,y>\in R\mathrm{且}<y,x>\in R,\mathrm{则}x=y$	$\mathrm{\forall }x,y,z\in R,\mathrm{若}<x,y>\in R,\mathrm{且}<y,z>\in R,\mathrm{则}<x,z>\in R$
关系运算	$I_A\subset R$	$R\cap I_A=\varnothing$	$R=R^{-1}$	$R\cap R^{-1}\subset I_A$	$R\circ R=R$
关系图	每个结点都有环	每个结点都无环	任两结点间，要么没有边，要么有方向相反的两条边	任两结点，至多有一条边	如果x到y有边，从y到z有边，则从x到z一定有边
关系矩阵	主对角线上全为1	主对角线上全为0	对称矩阵	$\mathrm{\forall }i\ne j,r_{ij}=0\mathrm{或}{r}_{ji}=0$	$\mathrm{\forall }i,j,k,\mathrm{若}{r}_{ij}=1\mathrm{且}{r}_{jk}=1,\mathrm{必}\mathrm{有}{r}_{ik}=1$

关系性质的保守性

Definition

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

1. R，S是自反的，则$R^{-1},R\cup S,R\cap S,R\circ S$也是自反的；
2. R，S是反自反的，则$R^{-1},R\cup S,R\cap S,R-S$也是反自反的；
3. R，S是对称的，则$R^{-1},R\cup S,R\cap S,R-S$也是对称的
4. R，S是反对称的，则$R^{-1},R\cap S,R-S$也是反对称的
5. R，S是传递的，则$R^{-1},R\cap S$也是传递的

关系的闭包

Definition

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

1. $R^{\prime }$是自反的（对称的，或传递的）
2. 对任意自反的（对称的，或传递的）关系系$R^{{}^{″}}$,如果$R\subset R^{{}^{″}}$,则称R‘为R的自反闭包（reflexive closure）(对称闭包（symmetric closure）,或传递闭包(transitive closure)），分别记为r(R)(s(R)或t(R)).

利用关系集合求闭包

Theorem

设R是集合A上的元素，则

1. $r(R)=R\cup I_A$;
2. $s(R)=R\cup R^{-1}$
3. $t(R)=\bigcup _{i=1}^{\mathrm{\infty }}{R}^i$,若$|A|=n$,则$t(R)=\bigcup _{i=1}^n{R}^i$.