3472 字
17 分钟
离散数学 Ch3: 二元关系
2024-04-18
笔记
离散数学

1. 关系#

定义1.1.11.1.1​ 集合的笛卡尔乘积的子集就是一个关系。

1.1 空关系和全域关系#

RR是×i=1nAi\mathop{\times}\limits_{i=1}^{n}{}A_i​的子集，

  1. 若R=∅R = \varnothing，则R为空关系。
  2. 若R=×i=1nAiR=\mathop{\times}\limits_{i=1}^{n}{}A_i，则RR为全域关系。

1.2 关系相等#

定义1.2.11.2.1 如果R1R_1是×i=1nAi\mathop{\times}\limits_{i=1}^{n}{}A_i的nn元关系，R2R_2是×i=1mBi\mathop{\times}\limits_{i=1}^{m}{}B_i的mm元关系，称R1R_1和R2R_2相等除非：

  1. 集合R1=R2R_1=R_2
  2. n=mn=m
  3. Ai=BiA_i = B_i，∀i=1,2,3,⋯ ,n\forall i=1,2,3,\cdots,n

即关系相等还需要笛卡尔乘积的扩集也完全相同。

2. 二元关系#

2.1 二元关系的组成部分#

关系是×i=1nAi\mathop{\times}\limits_{i=1}^{n}{}A_i的子集，若n=2n=2，就是一个二元关系。

A×BA\times B上的子集RR(RR是一个二元关系)可以用中缀记法，若<x,y>∈R<x,y> \in R，可以记作:xRyxRy

定义2.1.12.1.1 AA是RR的前域，BB是RR的陪域。

定义2.1.22.1.2 有集合{x∣∃y(<x,y>∈R)}\{x|\exists y(<x,y> \in R)\}称为RR的定义域，集合{y∣∃x(<x,y>∈R)}\{y|\exists x(<x,y> \in R)\}称为RR的值域。

由于关系RR也是一个集合，可以进行集合运算，特别地，对于二元关系还有:

x(R1∪R2)y⇔xR1y∨xR2yx(R1∩R2)y⇔xR1y∧xR2yxR1‾y⇔xR1y\begin{align} x(R_1 \cup R_2)y \Leftrightarrow xR_1y\vee xR_2y \\ x(R_1 \cap R_2)y \Leftrightarrow xR_1y\wedge xR_2y\\ x\overline{R_1}y \Leftrightarrow x\cancel{R_1}y \end{align}

定义2.1.32.1.3 AA上的二元关系{<x,x>∣x∈A}\{<x,x>|x\in A\}称为集合AA上的等价关系，记作IAI_A或EAE_A。单位阵

2.2 关系的特性:#

若RR是集合AA上的一个二元关系，即RR是A×AA \times A的一个子集。

2.2.1 自反#

关系RR具有自反特性，当且仅当：

∀x(x∈A→<x,x>∈R)\forall x(x\in A \to <x,x> \in R)

对于所有元素xx，xRxxRx成立。

2.2.2 反自反#

关系RR具有反自反特性，当且仅当：

∀x(x∈A→<x,x>∉R)\forall x(x\in A \to <x,x> \notin R)

对于所有元素xx，xRxx\cancel{R}x成立。

2.2.3 对称#

关系RR具有对称特性，当且仅当：

∀x∀y(<x,y>∈R→<y,x>∈R)\forall x\forall y(<x,y>\in R \to <y,x> \in R)

对于所有元素xx和yy，如果xRyxRy成立，那么yRxyRx也要成立

2.2.4 反对称#

关系RR具有对称特性，当且仅当：

∀x∀y(<x,y>∈R∧<y,x>∈R→x=y)\forall x\forall y(<x,y>\in R \wedge <y,x>\in R \to x=y)

对于所有元素xx和yy，如果xRyxRy成立，那么xRyx\cancel{R}y成立，除了x=y的情况！！

2.2.5 传递#

关系RR具有传递特性，当且仅当:

∀x∀y∀z(<x,y>∈R∧<y,z>∈R→<x,z>∈R)\forall x\forall y\forall z(<x,y>\in R \wedge <y,z>\in R \to <x,z> \in R)

有向回路的传递。

特殊的一些关系：

  1. 空关系: 反自反，对称，反对称，传递
  2. 空集AA上的空关系: 自反,反自反，对称，反对称，传递 [空集AA上只有空关系]
  3. 全域关系: 自反，对称，传递
  4. 等价关系: 自反，对称，反对称，传递

3. 关系的合成#

对一个从集合AA到BB的关系R1R_1，一个从集合BB到CC的关系R2R_2，定义关系的合成运算⋅\cdot:

R1⋅R2={<a,c>∣∃b(b∈B∧<a,b>∈R1∧<b,c>∈R2}R_1\cdot R_2 = \{<a,c>|\exists b (b \in B \wedge <a,b> \in R_1 \wedge <b,c>\in R_2\} (R1R2)R3=R1(R2R3)有结合律⋆R1(R2∪R3)=R1R2∪R1R3⋆(R1∪R2)R3=R1R3∪R1R2合成在∪有分配律R1(R2∩R3)⊆R1R2∩R1R3(R1∩R2)R3⊆R1R3∩R2R3\begin{align} (R_1R_2)R_3 &= R_1(R_2R_3) 有结合律\\ \star R_1(R_2\cup R_3) &= R_1R_2\cup R_1R_3 \\ \star (R_1 \cup R_2)R_3 &= R_1R_3 \cup R_1R_2 合成在\cup有分配律\\ R_1(R_2\cap R_3)&\subseteq R_1R_2\cap R_1R_3\\ (R_1\cap R_2)R_3 &\subseteq R_1R_3 \cap R_2R_3 \end{align}

3.1 关系的幂#

设RR是集合AA上的二元关系。

R0=I={<x,x>∣x∈A}R^0=I=\{<x,x>|x\in A\} Rn+m=Rn⋅RmR^{n+m} = R^n\cdot R^m

定理3.1.13.1.1 如果集合AA是有限集合，且∣A∣=n|A|=n，则AA上的关系最多只有2n22^{n^2}种。故能保证∃i∃j(Ri=Rj),0≤i<j≤2n2\exists i \exists j(R^i = R^j),0\le i< j\le 2^{n^2}(2n22^{n^2}种)

定理3.1.23.1.2 如果∃i∃j(Ri=Rj),i<j\exists i \exists j(R^i = R^j),i< j，则:

  1. Ri+k=Rj+kR^{i+k} = R^{j+k}
  2. R(j−i)∗k+l=Rl,l≥iR^{(j-i)*k + l} = R^{l},l\ge i
  3. Rn∈{R0,R1,⋯ ,Rj−1}R^n \in \{R^0,R^1,\cdots,R^{j-1}\}，(因为i以后的幂次都会以(j-i)一个循环。)

3.2 关系的合成和矩阵的关系#

两个关系R1R_1和R2R_2若对应布尔矩阵M1M_1和M2M_2，则R1⋅R2R_1\cdot R_2对应M1⋅M2M_1\cdot M_2，其中矩阵的⋅\cdot变为逻辑乘逻辑乘。

3.3 关系的逆#

定义3.3.13.3.1 关系RR的逆为:{<y,x>∣<x,y>∈R}\{<y,x>|<x,y> \in R\}，关系RR若对应布尔矩阵MM，则RR的逆R~\widetilde{R}就对应MTM^T。

若有关系R1R_1和R2R_2。

R1R2~=R2~R1~R1∪~R2=R1~∪R2~R1∩~R2=R1~∩R2~R1−~R2=R1~−R2~R1⊆R2⇔R1~⊆R2~\begin{align} \widetilde{R_1R_2} &=\widetilde{R_2}\widetilde{R_1}\\ R_1\widetilde{\cup} R_2 &=\widetilde{R_1}\cup\widetilde{R_2}\\ R_1\widetilde{\cap} R_2 &=\widetilde{R_1}\cap\widetilde{R_2}\\ R_1\widetilde{-}R_2&=\widetilde{R_1}-\widetilde{R_2}\\ R_1\subseteq R_2 &\Leftrightarrow \widetilde{R_1}\subseteq \widetilde{R_2} \end{align}

3. 关系的闭包#

原始定义： 一个关系RR的[自反∣对称∣传递][自反|对称|传递]闭包也是一个关系R′R'，并且它满足：

  1. R⊆R′R\subseteq R'
  2. R′R'是[自反∣对称∣传递][自反|对称|传递]的
  3. 如果有一关系R′′R''，他也是[自反∣对称∣传递][自反|对称|传递]的，并且有R⊆R′′R \subseteq R''，则一定有R′⊆R′′R' \subseteq R''​(闭包一定是最小的)。

3.1 自反闭包r(R)r(R)#

定义3.1.13.1.1 一个关系RR的自反闭包r(R)=R′=R∪Er(R) = R' = R \cup E，其中EE是全等关系。

定理3.1.13.1.1 一个关系RR是自反的当且仅当R=r(R)R = r(R)

3.2 对称闭包s(R)s(R)#

定义3.2.13.2.1 一个关系RR的对称闭包s(R)=R′=R∪R~s(R) = R' = R \cup \widetilde{R}。其中R~\widetilde{R}是RR的逆关系。

定理3.2.13.2.1 一个关系RR是对称的当且仅当R=s(R)R = s(R)

3.3 传递闭包t(R)t(R)#

定义3.3.13.3.1 一个关系RR的传递闭包是t(R)=R′=∪i=1∞Ri=R1∪R2∪R3∪⋯t(R) = R' = \mathop{\cup}\limits_{i=1}^{\infty} R^i= R^1 \cup R_2\cup R^3 \cup \cdots

定理3.3.13.3.1 一个关系RR是传递的当且仅当R=t(R)R = t(R)。

定理3.3.23.3.2 如果RR是有限集合AA上的关系，且∣A∣=n|A| = n，则t(R)=∪i=1∞Ri=∪i=1nRit(R) = \mathop{\cup}\limits_{i=1}^{\infty} R^i = \mathop{\cup}\limits_{i=1}^{n} R^i，即只需要前nn个幂集即可。(有向图上长度为n+kn+k的路径一定能找到一个长度为k′<nk'<n的路径起点和终点(删去重复兜圈子的部分)都和该路径一样。)

一般用R+R^+表示t(R)t(R)，而用R∗R^*表示rt(R)和tr(R)rt(R)和tr(R)。

注意:

  1. 如果RR是自反的，则s(R)s(R)和t(R)t(R)也都自反
  2. 如果RR是对称的，则r(R)r(R)和t(R)t(R)也都自反
  3. 如果RR是传递的，r(R)是传递的，但是s(R)s(R)不一定。

注意以下性质:

sr(R)=rs(R)tr(R)=rt(R)   [(R∪E)n=E∪(∪i=1nRi)]st(R)⊆ts(R)\begin{align} sr(R) &= rs(R)\\ tr(R) &= rt(R) \ \ \ [(R\cup E)^n = E \cup (\mathop{\cup}\limits_{i=1}^{n}R^i)]\\ st(R) &\subseteq ts(R) \end{align}

4. 次序关系#

4.1 偏序#

定义4.1.14.1.1 偏序关系是一种自反、反对称、传递的二元关系(≤\le)。

可以证明，如果RR是一个偏序关系，则R~\widetilde{R}也是一个偏序关系。他们互为对偶。≤\le的对偶是≥\ge。整除的对偶是倍数关系。

哈斯(Hasse)图上只画出能够使得tr(R′)=Rtr(R') = R的最小R′R'，不画自反边，也不画可以通过传递得到的边。

设RR是集合AA上的二元关系。

则通过Hasse图可以清楚的得到AA的子集BB的最大元、最小元(唯一、且在集合BB中，不一定存在)。子集BB的极大元、极小元(不一定唯一、在集合BB中，非空集合BB中一定存在)。子集BB的上界、下界(一般都是一个集合，不一定在集合BB中，也不一定存在)。子集BB的最小上界(lub)、最大下界(glb)(唯一、不一定在集合BB中，也不一定存在)。

如果集合BB有最大(小)元xx，则xx也一定为集合BB​​的极大(小)元、最小上界(最大下界)。

给一个偏序集合确定次序的方法是拓扑排序，这个过程就是给Hasse图拓扑排序。

4.2 拟序#

定义4.2.14.2.1 拟序关系是一种**反自反、传递、(反对称)**的二元关系(<<,⊊\subsetneq)，注意：反自反和传递蕴含着反对称。

能证明拟序R′R'和偏序RR的关系是:

  1. R′R' = RR - EE
  2. R=r(R′)R = r(R')

因此拟序也常用哈斯(Hasse)图表达。

4.3 线序#

定义4.3.14.3.1 线序的定义基于偏序。若集合AA上有偏序RR，且AA中每一对元素xx和yy都可以比较，则该偏序就为一个线序(全序)。[Hasse图就是一条线/链]

由于可以用Topological SortTopological \ Sort对偏序关系RR确定次序，因此可以用这种方式由一个偏序关系RR诱导出一个线序关系。并且这样诱导出的线序关系保持了原来的偏序关系。

4.4 良序#

定义4.4.14.4.1 良序的定义基于线序。若集合AA上由线序RR，且对于任意AA的非空子集BB都有最小元，则该线序是一个良序。

定理4.4.14.4.1 有限集合AA上的线序都是良序。

如果有一集合AA上的线序/良序RR，另一集合BB和一函数(单射？)f:B→Af:B \to A，则根据这个线序/良序RR可以诱导出一个BB上的线序/良序R′R': 若f(x)Rf(y)→xR′yf(x)Rf(y) \to x R'y。

比如{N,≤}\{N,\le\}和集合II，函数f:f:

f:I→Nf(i)={2∗∣i∣−1i<02∗∣i∣i≥0\begin{align} f&:I\to N \\ &f(i) =\left\{ \begin{aligned} &2*|i|-1 &i<0 \\ &2*|i| &i \ge 0\end{aligned}\right. \end{align}

以及字典序和标准序。

定义4.4.24.4.2 字典序定义在符号串(符号表为Σ\Sigma​)上的一个线序:

若串xx和串yy满足以下条件之一:

  1. 串xx是yy的前缀
  2. x=zau,y=zbvx = zau, y = zbv，zz是xx和yy的最长公共前缀，aa和bb是第一个xx和yy不一样的字符，且a≤ba \le b

则串x≤x\le串yy。

定义4.4.34.4.3 标准序定义在符号串(符号表为Σ\Sigma​)上的一个良序:

若串xx和串yy满足以下条件之一:

  1. 若∣x∣<∣y∣|x| < |y|
  2. 若∣x∣=∣y∣|x| = |y|，但在字典序上x≤yx \le y。

则串x≤x\le串yy。

若Σ={a,b,c}\Sigma = \{a,b,c\}，请仔细思考：

串字典序上的后继标准序上的后继字典序上的前驱标准序上的前驱
xaxaxaaxaaxbxbxxycyc，其中yy是xx的前驱
xbxbxbaxbaxcxcxaccc⋯xaccc\cdots不存在)xaxa
xcxcxcaxcayaya，其中yy是xx的后继xbccc⋯xbccc\cdots(不存在)xbxb

只需要在标准序上定义ε的后继是a\varepsilon的后继是a，就像是一条有开始的链一样，全部串联在一起，因此是一个良序[任何集合一定有最小元]。

然而字典序却并非如此，xbxb前面根本没有在一起。[考虑集合{b,ab,aab,aaab,aaa⋯ab}就没有最小元。\{b,ab,aab,aaab,aaa\cdots ab\}就没有最小元。​]因而只是线序而不是良序！

5. 等价关系#

定义5.1.15.1.1 等价关系是自反、对称、传递的二元关系。

等价关系RR对应的有向图GG的每一个子图都是完全图。

空集∅\varnothing上的二元关系RR是等价关系。整数域II上的模kk同余也是等价关系。

5.1 等价类#

定义5.1.25.1.2 定义关系RR关于元素aa的等价类集合是:

[a]R={x∣xRa}[a]_R = \{x|xRa\}

可以把元素aa叫做等价类[a][a]的表示元素。

定义5.1.35.1.3 关系RR的不同等价类的个数叫做关系RR的秩。如果RR的不同等价类个数是有限的，那秩就是有限的，否则就是无限的。

定理5.1.15.1.1 集合AA上有等价关系RR，aRb⇔[a]R=[b]RaRb \Leftrightarrow [a]_R =[b]_R。

并且对于每一对AA上的元素aa和bb，对于他们等价类的关系只有两种可能：

  1. [a]R=[b]R[a]_R=[b]_R
  2. [a]R∩[b]R=∅[a]_R \cap [b]_R = \varnothing

不同等价类不相交。

定理5.1.25.1.2 若在集合AA上有等价关系R1R_1和R2R_2，R1=R2⇔R1诱导的等价类集合=R2诱导的等价类集合R_1 = R_2 \Leftrightarrow R_1诱导的等价类集合=R_2诱导的等价类集合。

普通二元关系RR也可以诱导出一个等价关系R′=tsr(R)R' = tsr(R)。

能证明R′R'是最小的包含RR的等价关系。

5.2 覆盖#

定义5.2.15.2.1 给定非空集合AA和非空集合族{A1,A2,A3,⋯ ,An}\{A_1,A_2,A_3,\cdots,A_n\}，如果∪i=1nAi=A\mathop{\cup}\limits_{i=1}^{n}A_i = A，则称集合族{A1,A2,A3,⋯ ,An}\{A_1,A_2,A_3,\cdots,A_n\}是集合AA的覆盖。

若AA上有等价关系RR能构造这样一个集合族:

{[a]R∣a∈A}\{[a]_R|a\in A\}

是集合AA的一个覆盖。

5.3 划分#

5.3.1 划分π\pi与等价关系RR#

定义5.3.15.3.1 给定非空集合AA和非空集合族{A1,A2,A3,⋯ ,An}\{A_1,A_2,A_3,\cdots,A_n\}，如果:

  1. {A1,A2,A3,⋯ ,An}\{A_1,A_2,A_3,\cdots,A_n\}是集合AA的划分
  2. 对于任意的1≤i≤j≤n1\le i \le j \le n，要么Ai∩Aj=∅A_i \cap A_j = \varnothing，要么Ai=AjA_i = A_j。

则称集合族{A1,A2,A3,⋯ ,An}\{A_1,A_2,A_3,\cdots,A_n\}是集合AA​的划分。

显然集合AA上的等价划分RR可以诱导出一个AA的一个划分，即RR的等价类集合。

定义5.3.25.3.2 设非空集合AA上有等价关系RR，定义RR的等价类集合{[a]R∣a∈A}\{[a]_R|a\in A\}为一个商集A/RA/R。也叫A模RA模R。

定理5.3.15.3.1 AA上等价关系R1R_1和R2R_2相等当且仅当A/R1=A/R2A/R_1 = A/ R_2。

定理5.3.25.3.2 AA上等价关系RR可以诱导出一个划分π\pi，相反的AA上的一个划分π′\pi'也可以诱导出一个等价关系R′R'。

由一个AA上集合划分π\pi诱导出等价关系RR的方式是：

R={<x,y>∣∃B(B∈π∧x∈B∧y∈B)}=∪B∈π(B×B)R = \{<x,y>|\exists B(B \in \pi \wedge x\in B \wedge y \in B)\} = \mathop{\cup}\limits_{B\in \pi} (B \times B)

这说明非空集合AA​上的等价关系和划分其实是等价的。

注意: 在空集∅\varnothing上可以定义等价关系，却不能定义划分

5.3.2 划分的积#

定义5.3.35.3.3 如果有非空集合AA上的划分π1,π2\pi_1,\pi_2，如果π1\pi_1的每一块都在π2\pi_2的某一块中，则称π1\pi_1细分π2\pi_2。如果π1≠π2\pi_1 \ne \pi_2，则称π1\pi_1真细分π2\pi_2。

设集合FF是非空集合AA上划分的族，细分是是集合FF上的偏序关系。

定理5.3.35.3.3 如果非空集合AA上有划分π1\pi_1和π2\pi_2,对应有等价关系R1R_1和等价关系R2R_2，则有永真恒等式: π1划分π2⇔R1⊆R2\pi_1划分\pi_2 \Leftrightarrow R_1 \subseteq R_2​。

划分π\pi的大小用秩来定义(π\pi含有的不同集合个数)。等价关系RR的大小用含有的序偶个数来定义。

定义5.3.45.3.4 定义划分π1\pi_1和划分π2\pi_2的积π=π1⋅π2\pi = \pi_1 \cdot \pi_2为这样一个划分：

  1. π\pi细分π1\pi_1，π\pi细分π2\pi_2。
  2. 若有一划分π′\pi'也细分π1\pi_1和π2\pi_2，则π′\pi'细分π\pi。(π\pi是秩最小的划分)

也是细分关系的最大下界。

定理5.3.45.3.4 若划分π1\pi_1对应等价关系R1R_1，而划分π2\pi_2对应等价关系R2R_2，则**π1⋅π2\pi_1 \cdot \pi_2对应等价关系R1∩R2R_1 \cap R_2**。反过来由等价关系R1∩R2R_1\cap R_2也能得到对应的划分是π1⋅π2\pi_1 \cdot \pi_2。

定理5.3.55.3.5 划分π1\pi_1和π2\pi_2的积π\pi是唯一的。

5.3.3 划分的和#

定义5.3.55.3.5 定义划分π1\pi_1和划分π2\pi_2的和π=π1+π2\pi = \pi_1 + \pi_2​为这样一个划分：

  1. π1\pi_1细分π\pi，π2\pi_2细分π\pi。
  2. 如果有一划分π′\pi'也都细分π1\pi_1和π2\pi_2，则π\pi细分π′\pi'(π\pi是秩最大的被π1\pi_1和π2\pi_2细分的划分)

π\pi也是细分二元关系里的最小上界。

定理5.3.65.3.6 π=π1+π2\pi = \pi_1 + \pi_2对应等价关系R=t(R1∪R2)=(R1∪R2)+R = t(R_1 \cup R_2) = (R_1 \cup R_2)^+[(R1∪R2)(R_1 \cup R_2)的传递闭包]

定理5.3.75.3.7 划分π1\pi_1和π2\pi_2的和也是唯一的。

离散数学 Ch3: 二元关系
http://blog.fragments.work/posts/discretemathmatics/ch3_二元关系/
作者
Lixin WANG
发布于
2024-04-18
许可协议
CC BY-NC-SA 4.0
离散数学 Ch2: 集合
离散数学第一章: 数理逻辑