离散数学基础:集合与关系的运算

思维导图

并

定义

$$\begin{array}{rl}& R\cup S=\{<a,b>|<a,b>\in R\vee <a,b>\in S\}\end{array}$$

关系矩阵

$$\begin{array}{rl}& M_{R\cup S}=M_R\vee M_S=[r_{ij}\vee s_{ij}]\end{array}$$

性质

$$\begin{array}{rl}& \text{单位元： 空关系}\end{array}$$

$$\begin{array}{rl}& \text{零元：全关系}\end{array}$$

$$\begin{array}{rl}& \text{关系并满足交换律}\end{array}$$

$$\begin{array}{rl}& \text{关系并满足结合律}\end{array}$$

$$\begin{array}{r}\text{关系并的单调性：关系并保持子集关系}\\ A\subseteq B,C\subseteq D\Rightarrow A\cup B\subseteq C\cup D\\ A\subseteq C,B\subseteq C\iff A\cup B\subseteq C\end{array}$$

$$\begin{array}{rl}& \text{关系并对关系交有分配律}\end{array}$$

$$\begin{array}{r}\text{关系并对关系差不满足分配律}\\ A\cup B-A\cup C\subseteq A\cup (B-C)\end{array}$$

交

定义

$$\begin{array}{rl}& R\cap S=\{<a,b>|<a,b>\in R\wedge <a,b>\in S\}\end{array}$$

关系矩阵

$$\begin{array}{rl}& M_{R\cap S}=M_R\wedge M_S=[r_{ij}\wedge s_{ij}]\end{array}$$

性质

$$\begin{array}{rl}& \mathrm{单}\mathrm{位}\mathrm{元}：\mathrm{全}\mathrm{关}\mathrm{系}\end{array}$$

$$\begin{array}{rl}& \text{零元： 空关系}\end{array}$$

$$\begin{array}{rl}& \text{关系交满足交换律}\end{array}$$

$$\begin{array}{rl}& \text{关系交满足结合律}\end{array}$$

$$\begin{array}{r}\text{关系交的单调性：关系交保持子集关系}\\ A\subseteq B,C\subseteq D\Rightarrow A\cap B\subseteq C\cap D\\ C\subseteq A,C\subseteq B\iff C\subseteq A\cup B\end{array}$$

$$\begin{array}{rl}& \text{关系交对关系并有分配律}\end{array}$$

$$\begin{array}{r}\text{关系交对关系差有分配律}\end{array}$$

差

定义

$$\begin{array}{rl}& R-S=\{<a,b>|<a,b>\in R\wedge <a,b>\notin S\}\end{array}$$

关系矩阵

$$\begin{array}{rl}& M_{R-S}=M_R\ominus M_S=[r_{ij}\ominus s_{ij}]\end{array}$$

$$\begin{array}{rl}& \text{运算}\ominus ：0\ominus 0=0\ominus 1=1\ominus 1=0，1\ominus 0=1\end{array}$$

性质

$$\begin{array}{rl}& \text{左零单位： 全关系}\end{array}$$

$$\begin{array}{rl}& \text{右单位元： 空关系}\end{array}$$

$$\begin{array}{rl}& \text{左零元： 空关系}\end{array}$$

$$\begin{array}{rl}& \text{右零元： 全关系}\end{array}$$

$$\begin{array}{rl}& \text{关系差不满足交换律}\end{array}$$

$$\begin{array}{rl}& \text{关系差不满足结合律}\end{array}$$

$$\begin{array}{rl}& \text{关系差无单调性：关系差不保持子集关系}\end{array}$$

$$\begin{array}{r}\text{关系差对关系并没有分配律}:\\ A-(B\cup C)\subseteq (A-B)\cup (A-C)\end{array}$$

$$\begin{array}{r}\text{关系差对关系交没有分配律}:\\ (A-B)\cap (A-C)\subseteq A-(B\cap C)\end{array}$$

$$\begin{array}{r}\text{关系差对关系交、关系并有反分配律}:\\ A-(B\cup C)=(A-B)\cap (A-C)\\ A-(B\cap C)=(A-B)\cup (A-C)\end{array}$$

复合

定义

$$\begin{array}{rl}& S\circ R=\{<a,c>|\mathrm{\exists }b\in B(<a,b>\in R\wedge <b,c>\in S)\}\end{array}$$

关系矩阵

$$\begin{array}{rl}& M_{R\circ S}=M_R\odot M_S\end{array}$$

$$\begin{array}{rl}& \text{逻辑积运算}\odot \text{：与矩阵乘法本质相同，}\\ & \text{只是将其中的加法、乘法分别用}\\ & \text{逻辑或}\vee \text{(逻辑加法) 、逻辑与}\wedge \text{(逻辑减法)替代}\end{array}$$

备注

$$\begin{array}{rl}& \text{本课程采用逆序复合}\end{array}$$

性质

$$\begin{array}{rl}& \text{单位元：恒等关系}\end{array}$$

$$\begin{array}{rl}& \text{零元： 空关系}\end{array}$$

$$\begin{array}{rl}& \text{关系复合不满足交换律}\end{array}$$

$$\begin{array}{rl}& \text{关系复合满足结合律}\end{array}$$

$$\begin{array}{rl}& \text{关系复合的单调性：关系复合保持子集关系}\\ & R\subseteq S,U\subseteq W\to U\circ R\subseteq W\circ S\end{array}$$

$$\begin{array}{rl}& \text{关系复合对关系并有分配律}\end{array}$$

$$\begin{array}{r}\text{关系复合对关系交没有分配律}:\\ (R\cap S)\circ T\subseteq (R\circ T)\cap (S\circ T)\end{array}$$

补

定义

$$\begin{array}{rl}\bar{R}& =\{<a,b>\in A\times B|<a,b>\notin R\}\\ & =A\times B-R\end{array}$$

关系矩阵

$$\begin{array}{rl}& M_{\bar{R}}=\overline{M_R}=[\overline{r_{ij}}]\end{array}$$

性质

$$\begin{array}{rl}& \text{关系补的单调性：关系补运算保持相反的子集关系}\end{array}$$

$$\begin{array}{rl}& \text{关系补对关系并没有分配律}:\overline{A\cup B}\subseteq \bar{A}\cup \bar{B}\end{array}$$

$$\begin{array}{rl}& \text{关系补对关系交有分配律}\end{array}$$

$$\begin{array}{rl}& \text{关系补对关系差没有分配律}:\bar{A}-\bar{B}\subseteq \overline{A-B}\end{array}$$

$$\begin{array}{rl}& \text{关系补对关系复合有分配律}\end{array}$$

$$\begin{array}{rl}& \text{关系逆与关系补有交换律(两个一元运算)}\end{array}$$

逆

定义

$$\begin{array}{rl}& R^{-1}=\{<b,a>|<a,b>\in R\}\end{array}$$

关系矩阵

$$\begin{array}{rl}& M_{R^{-1}}=(M_R{)}^T\end{array}$$

性质

$$\begin{array}{rl}& \text{关系逆的单调性：关系逆运算保持子集关系}\end{array}$$

$$\begin{array}{rl}& \text{关系逆对关系并有分配律}\end{array}$$

$$\begin{array}{rl}& \text{关系逆对关系交有分配律}\end{array}$$

$$\begin{array}{rl}& \text{关系逆对关系差有分配律}\end{array}$$

$$\begin{array}{rl}& \text{关系逆对关系复合有分配律}\end{array}$$

$$\begin{array}{rl}& \text{关系逆与关系补有交换律(两个一元运算)}\end{array}$$