离散数学：二元关系

发表于 更新于 分类于 Waline： 阅读次数：

二元关系

序偶和笛卡尔积

有序组

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当且仅当A=\varnothing或者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 \not 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,\exists y \in B,<x,y>\in R \},D= \{y\mid y\in B,\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{cases} 1 <a_i,b_i>\in R\\ 0 <a_i,b_j> \notin R \end{cases} ,(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{cases} 1 \space if \space a_{ij}=1\space or \space b_{ij}=1\\ 0 \space if \space a_{ij}=0\space and \space b_{ij}=0 \end{cases} \]

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

布尔矩阵的积运算

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{cases} 1\quad \exists k,a_{ik}=1\space and\space b_{kj}=1\\ 0\quad else \end{cases} \]

关系的运算

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

Definition

设R，S是从A到B的两个关系，则 \[ 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\not Sy) \}\\ \overline{R}= \{<x,y>\mid(x\not R y) \}(即全集为A\times B) \]

关系的复合运算

Definition

设A，B，C是三个集合，R是从A到B的关系，S是从B到C的关系（即\(R:A arrow B,S:B arrow C\)）,则R与S的复合关系(合成关系)(composite relation)\(R\circ S= \{<x,z>\mid(x\in A)\wedge(z\in C)\wedge(\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. 分配性 \[ (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} \]

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

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

  4. 单调性\(S\subset R\Leftrightarrow 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}^{\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>\not\in 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且<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是自反的\Leftrightarrow I_A\subset R\);
  2. \(R是反自反的\Leftrightarrow R\cap I_A=\varnothing\);
  3. \(R是对称的\Leftrightarrow R=R^{-1}\);
  4. \(R是反对称的\Leftrightarrow R\cap R^{-1}\subset I_A\);
  5. \(R是传递的\Leftrightarrow R\circ R\subset R\)

总结：关系性质判定方法

自反性 反自反性 对称性 反对称性 传递性
定义 \(\forall x\in A,有<x,x>\in R\) \(\forall A,有<x,x>\not\in R\) \(\forall x,y\in A,若<x,y>\in R,则<y,x>\in R\) \(\forall x,y\in A，若<x,y>\in R且<y,x>\in R,则x=y\) \(\forall x,y,z\in R,若<x,y>\in R,且<y,z>\in R,则<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 对称矩阵 \(\forall i\neq j,r_{ij}=0或r_{ji}=0\) \(\forall i,j,k,若r_{ij}=1且r_{jk}=1,必有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^{'}\),满足：

  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}^{\infty}R^i\),若\(|A|=n\),则\(t(R)=\bigcup_{i=1}^nR^i\).