Home 数学 离散数学 离散数学基础

离散数学基础 - 整理: --- 排列与组合 --- 组合计数基本原理 --- 排列组合计数问题 --- 递推关系式 --- 关系 --- 集合与关系的运算 --- 函数 --- 代数系统

# 思维导图

集合与关系的运算

# 并

# 定义

R∪S={<a,b>∣<a,b>∈R∨<a,b>∈S}\begin{aligned}& R\cup S =\{<a,b>|<a,b>\in R\ \ \lor <a,b>\in S\}\end{aligned}

# 关系矩阵

MR∪S=MR∨MS=[rij∨sij]\begin{aligned}& M_{R\cup S} = M_R \lor M_S = [r_{ij}\lor s_{ij}]\end{aligned}

# 性质

单位元： 空关系\begin{aligned}&\text{单位元： 空关系}\end{aligned}

零元：全关系\begin{aligned}&\text{零元：全关系}\end{aligned}

关系并满足交换律\begin{aligned}&\text{关系并满足交换律}\end{aligned}

关系并满足结合律\begin{aligned}&\text{关系并满足结合律}\end{aligned}

关系并的单调性：关系并保持子集关系A⊆B,C⊆D⇒A∪B⊆C∪DA⊆C,B⊆C⇔A∪B⊆C\begin{aligned}\text{关系并的单调性：关系并保持子集关系}\\ A\subseteq B,C\subseteq D \Rightarrow A\cup B\subseteq C\cup D\\ A\subseteq C,B\subseteq C \Leftrightarrow A\cup B\subseteq C\end{aligned}

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

关系并对关系差不满足分配律A∪B−A∪C⊆A∪(B−C)\begin{aligned}\text{关系并对关系差不满足分配律}\\ A\cup B-A\cup C\subseteq A\cup(B-C)\end{aligned}

# 交

# 定义

R∩S={<a,b>∣<a,b>∈R∧<a,b>∈S}\begin{aligned}& R\cap S =\{<a,b>|<a,b>\in R\ \ \land <a,b>\in S\}\end{aligned}

# 关系矩阵

MR∩S=MR∧MS=[rij∧sij]\begin{aligned}& M_{R\cap S} = M_R \land M_S = [r_{ij}\land s_{ij}]\end{aligned}

# 性质

单位元：全关系\begin{aligned}& 单位元：全关系 \end{aligned}

零元： 空关系\begin{aligned}&\text{零元： 空关系}\end{aligned}

关系交满足交换律\begin{aligned}&\text{关系交满足交换律}\end{aligned}

关系交满足结合律\begin{aligned}&\text{关系交满足结合律}\end{aligned}

关系交的单调性：关系交保持子集关系A⊆B,C⊆D⇒A∩B⊆C∩DC⊆A,C⊆B⇔C⊆A∪B\begin{aligned}\text{关系交的单调性：关系交保持子集关系}\\ A\subseteq B,C\subseteq D \Rightarrow A\cap B\subseteq C\cap D\\ C\subseteq A,C\subseteq B \Leftrightarrow C\subseteq A\cup B\end{aligned}

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

关系交对关系差有分配律\begin{aligned}\text{关系交对关系差有分配律}\end{aligned}

# 差

# 定义

R−S={<a,b>∣<a,b>∈R∧<a,b>∉S}\begin{aligned}& R- S =\{<a,b>|<a,b>\in R\ \ \land <a,b>\notin S\}\end{aligned}

# 关系矩阵

MR−S=MR⊖MS=[rij⊖sij]\begin{aligned}& M_{R- S} = M_R \ominus M_S = [r_{ij}\ominus s_{ij}]\end{aligned}

运算⊖：0⊖0=0⊖1=1⊖1=0，1⊖0=1\begin{aligned}&\text{运算}\ominus：0\ominus0=0\ominus1=1\ominus1=0，1\ominus0=1\end{aligned}

# 性质

左零单位： 全关系\begin{aligned}&\text{左零单位： 全关系}\end{aligned}

右单位元： 空关系\begin{aligned}&\text{右单位元： 空关系}\end{aligned}

左零元： 空关系\begin{aligned}&\text{左零元： 空关系}\end{aligned}

右零元： 全关系\begin{aligned}&\text{右零元： 全关系}\end{aligned}

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

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

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

关系差对关系并没有分配律:A−(B∪C)⊆(A−B)∪(A−C)\begin{aligned}\text{关系差对关系并没有分配律}:\\ A-(B\cup C) \subseteq (A-B)\cup(A-C)\end{aligned}

关系差对关系交没有分配律:(A−B)∩(A−C)⊆A−(B∩C)\begin{aligned}\text{关系差对关系交没有分配律}:\\ (A-B)\cap(A-C) \subseteq A-(B\cap C)\end{aligned}

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

# 复合

# 定义

S∘R={<a,c>∣∃b∈B(<a,b>∈R∧<b,c>∈S)}\begin{aligned}& S\circ R=\{<a,c>|\exists b\in B(<a,b>\in R\land <b,c>\in S)\}\end{aligned}

# 关系矩阵

MR∘S=MR⊙MS\begin{aligned}& M_{R\circ S} = M_R \odot M_S\end{aligned}

逻辑积运算⊙：与矩阵乘法本质相同，只是将其中的加法、乘法分别用逻辑或∨(逻辑加法) 、逻辑与∧(逻辑减法)替代\begin{aligned}&\text{逻辑积运算}\odot\text{：与矩阵乘法本质相同，}\\& \text{只是将其中的加法、乘法分别用}\\& \text{逻辑或}\lor\text{(逻辑加法) 、逻辑与}\land\text{(逻辑减法)替代}\end{aligned}

# 备注

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

# 性质

单位元：恒等关系\begin{aligned}&\text{单位元：恒等关系}\end{aligned}

零元： 空关系\begin{aligned}&\text{零元： 空关系}\end{aligned}

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

关系复合满足结合律\begin{aligned}&\text{关系复合满足结合律}\end{aligned}

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

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

关系复合对关系交没有分配律:(R∩S)∘T⊆(R∘T)∩(S∘T)\begin{aligned}\text{关系复合对关系交没有分配律}:\\ (R\cap S)\circ T \subseteq (R\circ T)\cap(S\circ T)\end{aligned}

# 补

# 定义

R‾={<a,b>∈A×B∣<a,b>∉R}=A×B−R\begin{aligned} \overline R &=\{<a,b>\in A\times B|<a,b>\notin R\}\\& =A\times B-R\end{aligned}

# 关系矩阵

MR‾=MR‾=[rij‾]\begin{aligned}& M_{\overline R}=\overline{M_R}=[\overline{r_{ij}}]\end{aligned}

# 性质

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

关系补对关系并没有分配律:A∪B‾⊆A‾∪B‾\begin{aligned}&\text{关系补对关系并没有分配律}: \overline{A\cup B} \subseteq \overline{A}\cup\overline{B}\end{aligned}

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

关系补对关系差没有分配律:A‾−B‾⊆A−B‾\begin{aligned}&\text{关系补对关系差没有分配律}: \overline{A}-\overline{B}\subseteq\overline{A-B}\end{aligned}

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

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

# 逆

# 定义

R−1={<b,a>∣<a,b>∈R}\begin{aligned}& R^{-1}=\{<b,a>|<a,b>\in R\}\end{aligned}

# 关系矩阵

MR−1=(MR)T\begin{aligned}& M_{R^{-1}}=(M_R)^T\end{aligned}

# 性质

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

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

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

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

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

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