1340 字
7 分钟
[离散数学] 第一章 集合论

定义1.2.4 以集合为元素的集合称为集族#

A1,A2,A3\large A_1,A_2,A_3为集合,则{A1,A2,A3}\large \left \{ A_1,A_2,A_3 \right \}为一个集族。若令I={1,2,3}\large I=\left \{ 1,2,3 \right \},则iI\large \forall i\in Ii\large i确定了一个唯一的集合Ai\large A_i

集族{A1,A2,A3}\large \left \{ A_1,A_2,A_3 \right \}又常写成{Ai}iI\large \left \{ A_i \right \} _{i\in I},即I\large I中元素i\large i确定的那些集形成的集族

定义1.2.5#

集合S\large S的所有子集(包括空集\large \varnothingS\large S本身)形成的集族称为S\large S的幂集,并记为2S\large 2^{S},或P(S)\large \mathscr{P}(S)

(P\large \mathscr{P}是字母P\large P)

于是,2S={AAS}\large 2^{S}=\left \{ A | A\subseteq S \right \}

例: 设S={1,2,3}\large S= \left \{ 1,2,3 \right \},则2S={,{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}}\large 2^{S}=\left \{\varnothing ,\left \{ 1 \right \} \left \{ 2 \right \} \left \{ 3 \right \} \left \{ 1,2 \right \} \left \{ 1,3 \right \} \left \{ 2,3 \right \} \left \{ 1,2,3 \right \} \right \}

S\large S有八个子集

区分\large \varnothing{}\large \left \{ \varnothing \right \}#

2={}\large 2^{\varnothing}=\left \{ \varnothing \right \}

\large \varnothing为空集,而{}\large \left \{ \varnothing \right \}是一个集族,这个集族仅有一个元素,就是空集。

因此,{}\large \varnothing \neq \left \{ \varnothing \right \},但{}\large \varnothing \in \left \{ \varnothing \right \}{}\large \varnothing \subseteq \left \{ \varnothing \right \} (因为空集是任何集合的子集)。集{,{}}\left \{ \varnothing , \left \{ \varnothing \right \} \right \}含有两个元素。

多个集合的并集#

A1A2An\large A_1 \cup A_2 \cup \cdots \cup A_n缩写为i=1nAi\large \bigcup\limits_{i=1}^{n}A_i

A1,A2,,An,\large A_1,A_2,\cdots ,A_n,\cdots是一个集合的无穷序列,则它们的并集缩写为n=1An\large \bigcup\limits_{n=1}^{\infty}A_n其定义为n=1An={xnN 使得 xAn}\large \bigcup\limits_{n=1}^{\infty}A_n=\left \{ x | \exists n \in N\text{ 使得 }x\in A_{n} \right \}N\large N是自然数之集

{Al}lI\large \left \{ A_l \right \} _{l\in I}是任一集族,则集族中那些集之并集记为l=IAl\large \bigcup\limits_{l=I}A_l 并且l=IAl={xlI 使得 xAl}\large \bigcup\limits_{l=I}A_l= \left \{ x | \exists l \in I \text{ 使得 }x\in A_{l} \right \}

多个集合的交集#

A1A2An=i=1nAn={xi{1,2,,n},xAi}\large A_1 \cap A_2 \cap \cdots \cap A_n=\bigcap\limits_{i=1}^{n}A_n=\left \{ x | \forall i \in \left \{ 1,2,\cdots ,n \right \} ,x\in A_{i} \right \}

A1A2An=n=1An={xnN,xAn}\large A_1 \cap A_2 \cap \cdots \cap A_n \cap \cdots=\bigcap\limits_{n=1}^{\infty}A_n=\left \{ x | \forall n \in N ,x\in A_{n} \right \}

集族{Al}lI\large \left \{ A_l \right \} _{l\in I}各集的交记为l=IAl={xξI 使得 xAξ}\large \bigcap\limits_{l=I}A_l=\left \{ x | \forall \xi \in I\text{ 使得 }x\in A_{\xi} \right \}

定理1.3.3#

A\large A为任一集合,{Bl}lI\large \left \{ B_l \right \} _{l\in I}为任一集族,则

A(l=IBl)=l=I(ABl)A(l=IBl)=l=I(ABl)\begin{aligned} \large A \cap \left ( \bigcup\limits_{l=I}B_l \right ) &=\large \bigcup\limits_{l=I} \left ( A\cap B_{l} \right ) \\\\ \large A \cup \left ( \bigcap\limits_{l=I}B_l \right ) &=\large \bigcap\limits_{l=I} \left ( A\cup B_{l} \right ) \end{aligned}

其中I\large I \neq \varnothing

交并运算满足分配律#

A(BC)=(AB)(AC)A(BC)=(AB)(AC)\begin{aligned} \large A \cap \left ( B \cup C \right )&=\large \left ( A \cap B \right ) \cup \left ( A \cap C \right ) \\\\ \large A \cup \left ( B \cap C \right )&=\large \left ( A \cup B \right ) \cap \left ( A \cup C \right ) \end{aligned}

定理 1.3.5 吸收律#

A(AB)=AA(AB)=A\begin{aligned} \large A \cap \left ( A \cup B \right )&=\large A \\\\ \large A \cup \left ( A \cap B \right )&=\large A \end{aligned}

差集 定义 1.3.4#

A\large AB\large B为两个任意的集合,由属于A\large A但不属于B\large B的一切元素构成的集合称为A\large AB\large B的差集,并记为A\B\large A \backslash B

A\B={xxA 且 xB}\large A \backslash B=\left \{ x | x \in A \text{ 且 }x \notin B \right \}

A\large AB\large B没有的元素

差集分配律 定理 1.3.6#

A,B,C\large A,B,C为任意三个集合,则A(B\C)=(AB)\(AC)\large A\cap \left ( B \backslash C \right )=\left (A\cap B \right ) \backslash \left ( A\cap C \right )

差集不满足交换律#

A\BB\A\large A\backslash B \neq B \backslash A

定理 1.3.7#

(A\B)B=ABA\large \left ( A\backslash B \right )\cup B=A\Leftrightarrow B\subseteq A

对称差#

定义1.3.5 A\B\large A\backslash BB\A\large B\backslash A的并集称为A\large AB\large B的对称差,记为AΔB\large A \Delta B

AΔB=(A\B)(B\A)={xxAB 且 xAB}={xxA 或 xB 但 xAB}\large A \Delta B=\left ( A\backslash B\right )\cup \left ( B\backslash A \right )=\left \{ x | x\in A\cup B \text{ 且 }x\notin A\cap B \right \}=\left \{ x | x\in A \text{ 或 }x\in B \text{ 但 }x\notin A\cap B \right \}

说白了就是A\large AB\large B不同时含有的元素

对称差性质 定理 1.3.8#

AΔB=BΔA 满足交换律(AΔB)ΔC=AΔ(BΔC) 满足结合律AΔA=AΔ=A\begin{aligned} &\large A \Delta B =\large B \Delta A \text{ 满足交换律} \\ &\large \left ( A \Delta B \right )\Delta C=\large A \Delta \left ( B \Delta C \right ) \text{ 满足结合律} \\ &\large A \Delta A=\varnothing \\ &\large A \Delta \varnothing = A \end{aligned}

交运算关于对称差满足分配律

A(BΔC)=(AB)Δ(AC)\large A \cap \left ( B \Delta C \right )=\left ( A \cap B \right )\Delta\left ( A \cap C \right )

余集 定义 1.4.1#

S\large S是一个集合,AS\large A\subseteq S,差集S\A\large S\backslash A称为集A\large A对集S\large S的余集,记为Ac\large A^{c},即Ac=S\A\large A^{c}=S\backslash A

余集也称为补集,有的使用CSA\large C_{S}A表示A\large AS\large S的余集(本人高中就学的这种写法)

性质#

S\large SS\large S的余集Sc\large S^{c}为空集,即

CSS=Sc=\large C_{S}S=S^{c}=\varnothing

c=S(CS=S)\large \varnothing^{c}=S\left ( C_{S}\varnothing =S \right )

AAc=\large A\cap A^{c}=\varnothing,即CSAA=\large C_{S}A\cap A=\varnothing

AAc=S\large A\cup A^{c}=S,即ACSA=S\large A\cup C_{S}A=S

定理 1.4.1#

并集的余集等于各余集的交集 (ξIAξ)c=ξIAξc\large \left ( \bigcup\limits_{\xi \in I}A_{\xi} \right )^{c}=\bigcap\limits_{\xi \in I}A_{\xi}^{c}

定理 1.4.2#

交集的余集等于各余集的并集 (ξIAξ)c=ξIAξc\large \left ( \bigcap\limits_{\xi \in I}A_{\xi} \right )^{c}=\bigcup\limits_{\xi \in I}A_{\xi}^{c}

定理1.4.1和1.4.2称为De Morgan\large \text{De Morgan}公式。在有限的形式下,我们有公式

(AB)c=AcBc\large \left ( A\cup B \right )^{c}=A^{c}\cap B^{c}

(AB)c=AcBc\large \left ( A\cap B \right )^{c}=A^{c}\cup B^{c}

余集,差集,对称差之间的联系 定理 1.4.3#

A\large AB\large B都是S\large S的子集,则

A\B=ABc\large A\backslash B=A\cap B^{c}

AΔB=(ABc)(BAc)\large A\Delta B=\left( A\cap B^{c} \right )\cup \left ( B\cap A^{c} \right )

Ac=SΔA\large A^{c}=S\Delta A

对偶原理#

若有关集的并、交及余集运算的某一关系式成立,如果将式中的记号,,,\large \cup ,\cap ,\subseteq ,\supseteq分别换成,,,\large \cap ,\cup ,\supseteq ,\subseteq,等号保持不变,并将式中每个集换成它们的余集,由此得到的关系式一定成立

[离散数学] 第一章 集合论
https://a1kari8.github.io/posts/discrete_math_set/
作者
A1kari8
发布于
2025-01-04
许可协议
CC BY-NC-SA 4.0