离散数学II笔记(3)

关系及其性质

关系的定义

定义（关系）：设 $n\in I_+$ , 且 $A_1, A_2, …, A_n$ 为n个任意的集合， $R \in A_1 \times A_2 \times … \times A_n$ ，
(1) 称R为 $A_1, A_2, …, A_n$ 间的n元关系；
(2) 若n=2，则称R为从A1到A2的二元关系；
(3) 若 $R= \varnothing$ , 则称R为空关系；
(4) 若 $R= A_1 \times A_2 \times … \times A_n$ ，则称R为全关系
(5) 若 $A_1 = A_2 = … = A_n =A$ , 则称R为A上的n元关系

对于于二元关系R，
若 <x, y> $\in$ R , 则可表示成 x R y , 读做“x与y有关系R”
若 <x, y> $\notin$ R , 则记作 x $\overline R$ y, 读作“ x与y不存在关系R

两类特殊关系：
X上的全(域)关系:
$U_X = \{ <x_i , x_j > | x_i ,x_j\in X \} = X \times X$
X上的恒等关系： $I_X = \{ < x, x > | x \in X \}$

关系的相等 定义：设 $R_1$ 为 $A_1, A_2, …, A_n$ 间的n元关系， $R_2$ 为 $B_1, B_2, …, B_m$ 间的m元关系．如果
(1) n=m;
(2) 若 $1≤ i ≤ n$ , 则 $A_i=B_i$ ;
(3) 把 $R_1$ 和 $R_2$ 作为集合看， $R_1=R_2$ ．
则称n元关系 $R_1$ 与m元关系 $R_2$ 相等，记为 $R_1=R_2$

与集合相等的区别？
例：设 $R_1 \subseteq N \times I_+，R_2 \subseteq I \times I, R_3 \subseteq I \times I$ ，且
$R_1=\{<n, m> | n\in N, m\in I_+, 且m=n+1\}$ ， $R_2=\{<n, n+1> | n\in I, 且n≥0\}$ , $R_3=\{<|n|, |n|+1> | n\in I\}$
作为集合看，R1=R2=R3
作为关系看，R1≠R2，R2=R3

定义设 $R \subseteq A \times B$ , 令
$dom (R) = \{ x\in A | \exist y \in B使 <x, y>\in R \}$ ,
$ran (R) = \{ y\in B | \exist x \in A 使 <x , y>\in R \}$ ,
称dom ®为R 的定义域， ran ®为R 的值域。

二元关系的表示

关系图

定义 6.4 (关系图) 设A和B为任意的非空有限集，R
为任意从A到B的二元关系．以 $A ∪B$ 中的每个元素
为一个结点，对每个<x, y> $\in$ R，皆画一条从x到y
的有向边，就得到一个有向图G_R, 称为R的关系图

关系矩阵

定义 6.5 (关系矩阵) 设A和B为任意的非空有限集，R
为任意从A到B的二元关系．令 $A = \{ a_1, a_2, …, a_m \}$ , $B = \{ b_1, b_2, …, b_n \}$ ，R的关系矩阵，记作 $M_R=(r_{ij})_{m×n}$ ，其中

$r_{ij} = \begin{cases} 0, &x_i \, \overline R \,\, y_i \\ 1, & x_i \, R \,\, y_i \end{cases}$

关系的性质

自反性

定义 6.6 (自反性) 设R是A上的二元关系，如果对任意的 $x \in A$ ，都有 $xRx$ ，则称R是自反的，否则称R是非自反的．

在R的关系图中，每个顶点均有自环；
在R的关系矩阵中，主对角线的元素均为1．

反自反性

定义 6.7 (反自反性) 设R是A上的二元关系，如果对任意的 $x \in A$ ，都有 $x \overline R x$ ，则称R是反自反的，否则称R是非反自反的．

在R的关系图中，每个顶点均无自环；
在R的关系矩阵中，主对角线的元素均为0．

对称性

定义 6.8 (对称性) 设R是A上的二元关系，如果对任意的 $x, y \in A$ ，都有 $x\, R\, y$ 则称R是对称的，否则称R是非对称的．

在R的关系图中，任意两个不同顶点之间：或者无弧或者有两条方向相反的弧；
R的关系矩阵是对称矩阵.

反对称性

定义 6.9 (反对称性) 设R是A上的二元关系，如果对任意的 $x, y \in A$ ，都有 $x\, R\, y$ 则称R是对称的，否则称R是非对称的．

在 R 的关系图中，任意不同顶点之间至多有一条弧;
在R的矩阵中,若 $i\neq j$ 且 $r_{ij} = 1$ , 则 $r_{ji} = 0$ 或 $r_{ij} · r_{ji}=0 (i \neq j )$

传递性

定义 6.10 (传递性) 设R是A上的二元关系，如果对任意的 $x, y, z \in A$ ，都有 $xRy$ 且 $yRz$ 则称R是传递的，否则称R是非传递的．

在 R 的关系图中，若顶点 x 到顶点 y有一条路径，则必有从 x 到 y 的一条边
在关系矩阵：若有 k 使 $r_{ik} . r_{kj} =1$ , 则 $r_{ij} = 1$

关系图和关系矩阵中五种性质的表述

只要不违反规则，就是符合规则的

关系的运算

关系的集合运算

集合运算定义：设R和S是从集合A到B的关系, 取全集为 $A×B$ , 则
$R∩S, R∪S, R－S, ～R, R \oplus S$
仍是A到B的关系，并且对于任意 x∈A, y∈B:
$x (R∩S) y\Leftrightarrow <x, y>∈ R ∩ S\Leftrightarrow x R y ∧ x S y$
$x (R∪S) y\Leftrightarrow <x, y>∈ R ∪ S\Leftrightarrow x R y ∨ x S y$
$x (R－S) y\Leftrightarrow <x, y>∈ R － S\Leftrightarrow x R y ∧ x \overline S y$
$x (～R) y\Leftrightarrow <x, y>∈ ～R\Leftrightarrow x \overline R y$
$x (R \oplus S) y\Leftrightarrow <x, y>∈ R \oplus S\Leftrightarrow x (R－S) y ∨ x (S－R) y$

集合运算下是否保持五个性质:

关系的逆运算

逆运算定义：(逆关系) 将关系R中每个有序偶的第一元和第二元对换所得到的关系, 称为R的逆关系，记作 $R^{-1}$ ，
$R^{-1} ＝\{<x, y>｜<y, x >∈R \}$
显然， $dom(R^{-1})＝ran(R)$ , $ran(R^{-1})＝dom(R)$
定理：设A,B为非空有限集合,R为从A到B的二元关系．
(1) M_R^-1=M_R^T（转置）
(2) 把G_R的每个有向边反向后, 得到R^-1的关系图G_R^-1

逆运算的性质：若 $R, R_i (i=0, 1, 2, …)$ 都是从集合A到集合B的二元关系，K 为 N 的非空子集，则有
(1) $(R^{-1})^{-1}=R$ ;
(2) $(～R)^{-1}= ～(R^{-1})$ ;
(3) 如果 $R_1\subseteq R_2$ , 则 $R_1^{-1}\subseteq R_2^{-1}$ ;
(4) 如果 $R_1 =R_2$ , 则 $R_1^{-1} =R_2^{-1}$ ;
(5) $(⋃_{𝒏∈K} R_𝒏)^{-1}=⋃_{𝒏∈K}(R_𝒏^{-𝟏})$ ;
(6) $(⋂_{𝒏∈K} R_𝒏)^{-1}=⋂_{𝒏∈K}(R_𝒏^{-𝟏})$ ;
(7) $(R_1-R_2)^{-1}=R_1^{-1}-R_2^{-1}$ ;
(8) $(R_1\oplus R_2)^{-1}=R_1^{-1}\oplus R_2^{-1}$ ．