集合的运算

                     

贡献者: 零穹

预备知识 集合

   通过 “集合” 的预备知识,我们应该知道,集合是由元素构成的。这是说,在一开始讨论集合的时候,必须先行给出一个集合,才能继续进行有关的讨论。这是说当你说集合 $A$ 时,我们已经知道了它的元素。具体而言,当谈论集合 $A$ 时,你应该马上将其理解成 $A=\{a_1,\cdots,a_n,\cdots\}$,其中花括号里的是 $A$ 的元素。既然提到集合相当于指出它的元素,那同时就能判断哪些使它的元素,哪些不是它的元素,$a$ 是 $A$ 的元素记作 $a\in A$,$a$ 不是 $A$ 的元素记作 $a\notin A$,这些都是在提到集合的时候就同时表明了的。有了集合后,一个重要的任务是其上运算的定义及运算规则,这便是本节要介绍的,本文较通常的教科书创新之处在于给出了通常集合中 “且” 和 “或” 的精确定义。

1. 与 $\land$ 和 或 $\lor$

   同样在 “集合” 里,已经知道集合间可以进行运算 $\cap$(交)、$\cup$(并)。现在来给出它们的具体定义。严格的定义需要用到两个逻辑学概念 $\land$(读作 “与”)和 $\lor$(读作 “或”)。它们仅仅代表两个函数,下面将记 $Z_2=\{0,1\}$。

定义 1 与

   称函数 $f:Z_2\times Z_2\rightarrow Z_2$ 为,若

\begin{equation} f(0,0)=0,\quad f(0,1)=0,\quad f(1,0)=0,\quad f(1,1)=1~. \end{equation}
并将与函数 $f$ 记作 $\land$。

定义 2 或

   称函数 $f:Z_2\times Z_2\rightarrow Z_2$ 为,若

\begin{equation} f(0,0)=0,\quad f(0,1)=1,\quad f(1,0)=1,\quad f(1,1)=1~. \end{equation}
并将或函数 $f$ 记作 $\lor$。

   下面的定理起着重要作用。

定理 1 与或分配律

   对任意 $a,b,c\in Z_2$,成立恒等式:

\begin{equation} \begin{aligned} \lor(\land(a,b),c)&=\land(\lor(a,c),\lor(b,c)),\\ \land(\lor(a,b),c)&=\lor(\land(a,c),\land(b,c))~. \end{aligned} \end{equation}

   证明: 我们以第一式的证明为例,读者完全可以类似的证明出第二式。证明的关键只需要代入所有可能的 $a,b,c$ 即可,由于取值只有 $0,1$,这是方便的。

   若 $c=1$,由定义 2 ,$\lor(\land(a,b),1)=1$。于是只需证明右边无论 $a,b$ 取 $0,1$ 哪个指都为 1 即可。同样由 $\lor$ 的定义,右边 $\land$ 函数的两个变量都是 1:

\begin{equation} \lor(a,1)=\lor(b,1)=1~. \end{equation}
于是由定义 1 ,右边为 $\land(1,1)=1$,即
\begin{equation} \lor(\land(a,b),1)=\land(\lor(a,1),\lor(b,1))~. \end{equation}

   若 $c=0$,那么仅当 $\land(a,b)=1$ 时左边为 1,而右边也是仅当 $a=b=1$ 时为 1。于是

\begin{equation} \lor(\land(a,b),0)=\land(\lor(a,0),\lor(b,0))~. \end{equation}
证毕!

   式 3 之所以称为分配律,是因为若记 $a\land b:=\land(a,b),a\lor b:=\lor(a,b)$,则式 3 成为

\begin{equation} \begin{aligned} (a\land b)\lor c&=(a\lor c)\land(b\lor c),\\ (a\lor b)\land c&=(a\land c)\lor(b\land c)~. \end{aligned} \end{equation}
以后将采用此记号。总结成定义和定理的形式就是:

定义 3 

   定义 $a\land b:=\land(a,b),a\lor b:=\lor(a,b)$。

定理 2 分配律

  

\begin{equation} \begin{aligned} (a\land b)\lor c&=(a\lor c)\land(b\lor c),\\ (a\lor b)\land c&=(a\land c)\lor(b\land c)~. \end{aligned} \end{equation}

2. 属于 $\in$ 的数值化

   在精确定义集合的交和并前,还需要引入一种特定的函数,它将元素和集合的关系数值化了,不妨称为集合上的坐标函数。

定义 4 

   设 $X$ 是集合,则称函数 $f_X$ 是集合 $X$ 上的坐标,若

\begin{equation} f_X(x)=\left\{\begin{aligned} &1,\quad x\in X,\\ &0,\quad x\notin X~. \end{aligned}\right. \end{equation}
并称 $f_X(x)$ 是元素 $x$ 关于 $X$ 的坐标

   元素的坐标其实就表达了元素是否属于对应的集合。由于坐标函数的取值是 $0,1$,所以可以将其和逻辑与或的关系联系起来。

定义 5 简记约定

   当集合的坐标函数和逻辑与或函数连用时,直接记 $x\in X:=f_X(x)$。

   这一约定并不会引起混乱,它仅仅在符号 $\in$ 和 $\land,\lor$ 同时出现在一个表达时中时被采用。例如 $x\in X\land y\in Y=f_X(x)\land f_Y(y)$。

   利用这一约定,则可将定理 2 翻译成下面定理

定理 3 

   设 $X,Y,Z$ 是三个集合,则成立

\begin{equation} \begin{aligned} &(x\in X\land y\in Y)\lor z\in Z=(x\in X\lor z\in Z)\land(y\in Y\lor z\in Z),\\ & \left(x\in X\lor y\in Y \right) \land z\in Z=(x\in X\land z\in Z)\lor(y\in Y\land z\in Z)~. \end{aligned} \end{equation}

   定义交和并的原材料已经制备完成了,接下来就可以造出交并的严格形式了。

3. 交 $\cap$,并 $\cup$

定义 6 交集

   设 $X,Y$ 是两集合,称集合

\begin{equation} \{z|z\in X\land z\in Y=1 \}~ \end{equation}
为 $X,Y$ 的交集,记作 $X\cap Y$。

   这事实上表达了交集的元素同时属于两集合这样的概念。

定义 7 并集

   设 $X,Y$ 是两集合,称集合

\begin{equation} \{z|z\in X\lor z\in Y=1 \}~ \end{equation}
为 $X,Y$ 的并集,记作 $X\cup Y$。

   这事实上表达了并集的元素至少属于两集合之一这样的概念。

定理 4 

  

\begin{equation} \begin{aligned} f_{X\cap Y}(z)&=f_X(z)\land f_Y(z),\\ f_{X\cup Y}(z)&=f_X(z)\lor f_Y(z)~. \end{aligned} \end{equation}

   证明:以第一式证明为例:

\begin{equation} \begin{aligned} &f_{X\cap Y}(z)=1\overset{定义 4 }{\Leftrightarrow} z\in (X\cap Y)\overset{定义 6 ,定义 5 }{\Leftrightarrow}f_X(z)\land f_Y(z)=1~.\\ &f_{X\cap Y}(z)=0\overset{定义 4 }{\Leftrightarrow} z\notin (X\cap Y)\overset{定义 6 ,定义 5 }{\Leftrightarrow}f_X(z)\land f_Y(z)=0~.\\ \end{aligned} \end{equation}

   证毕!

推论 1 

  

\begin{equation} \begin{aligned} f_{\bigcap_\alpha X_\alpha}(z)&=\underset{\alpha}{\land} f_{X_\alpha}(z),\\ f_{\bigcup_\alpha X}(z)&=\underset{\alpha}{\lor} f_{X_\alpha}(z)~. \end{aligned} \end{equation}

   使用数学归纳法证明即可。

4. 运算性质

   现在,我们就可以严格的证明集合的交运算和并运算的分配律了。

定理 5 交并的分配律

   设 $X,Y,Z$ 是三个集合,则成立

\begin{equation} \begin{aligned} &(X\cap Y)\cup Z=(X\cup Z)\cap (Y\cup Z),\\ &(X\cup Y)\cap Z=(X\cap Z)\cup (Y\cap Z)~. \end{aligned} \end{equation}

   证明:定义 6 定义 7 ,只需证明

\begin{equation} \begin{aligned} z\in (X\cap Y)&\lor z\in Z=1\\ &\Updownarrow\\ (z\in X\cup Z)&\land (z\in Y\cup Z)=1~. \end{aligned} \end{equation}
\begin{equation} \begin{aligned} z\in (X\cup Y)&\land z\in Z=1\\ &\Updownarrow\\ (z\in X\cap Z)&\lor (z\in Y\cap Z)=1~. \end{aligned} \end{equation}
定理 4 定义 5 式 17 式 18 等式左边可写为
\begin{equation} \begin{aligned} z\in (X\cap Y)\lor z\in Z&=(z\in X\land z\in Y)\lor z\in Z,\\ (z\in X\cup Z)\land (z\in Y\cup Z)&=(z\in X\lor z\in Y)\land (z\in Y\lor z\in Z),\\ z\in (X\cup Y)\lor z\in Z&=(z\in X\lor z\in Y)\land z\in Z,\\ (z\in X\cap Z)\lor (z\in Y\cap Z)&=(z\in X\land z\in Y)\lor (z\in Y\land z\in Z)~. \end{aligned} \end{equation}
于是只需证明
\begin{equation} \begin{aligned} (z\in X\land z\in Y)&\lor z\in Z=1\\ &\Updownarrow\\ (z\in X\lor z\in Y)&\land (z\in Y\lor z\in Z)=1,\\ \\ (z\in X\lor z\in Y)&\land z\in Z=1\\ &\Updownarrow\\ (z\in X\land z\in Y)&\lor (z\in Y\land z\in Z)=1~. \end{aligned} \end{equation}

   由定理 3 式 20 成立。

   证毕!

定理 6 对偶原理(de Morgan 定理)

\begin{equation} \begin{aligned} S\backslash \bigcup_\alpha A_\alpha&=\bigcap_\alpha(S\backslash A_\alpha),\\ S\backslash \bigcap_\alpha A_\alpha&=\bigcup_\alpha(S \backslash A_\alpha)~,\\ \end{aligned} \end{equation}

   在证明之前,首先明确,$x \in A\backslash B$ 等价于 $f_A(x)=1,f_B(x)=0$.

   证明:这里的对偶是指:定理中的两式已知其中之一,便可推得另一式。以第一式成立为例,那么

\begin{equation} \begin{aligned} S\backslash \bigcap_\alpha (S\backslash A_\alpha)&=S\backslash \left(S\backslash\bigcup_\alpha A_\alpha \right) =\bigcup_\alpha A_\alpha,\\ \Downarrow\\ S\backslash \bigcap_\alpha A_\alpha&=S\backslash \bigcap_\alpha (S\backslash (S\backslash A_\alpha))=\bigcup_\alpha (S\backslash A_\alpha)~. \end{aligned} \end{equation}

   于是我们只需证明第一式即可。这只需证明

\begin{equation} \begin{aligned} f_S(x)=1,&\quad f_{\bigcup_\alpha A_\alpha}(x)=0\\ &\Updownarrow\\ f_{\bigcap_\alpha (S\backslash A_\alpha)}(x)&=1~. \end{aligned} \end{equation}
推论 1 ,只需证明
\begin{equation} \begin{aligned} f_S(x)=1,&\quad \underset{\alpha}{\lor}f_{A_\alpha}(x)=0\\ &\Updownarrow\\ \underset{\alpha}{\land}f_{(S\backslash A_\alpha)}(x)&=1~. \end{aligned} \end{equation}
这可证明如下
\begin{equation} \begin{aligned} f_S(x)=1,&\quad \underset{\alpha}{\lor}f_{A_\alpha}(x)=0\\ \Updownarrow\\ f_S(x)=1,&\quad f_{A_\alpha}(x)=0,\quad\forall \alpha\\ \Updownarrow\\ f_{S\backslash A_\alpha}(x)=1,&\quad\forall \alpha\\ \Updownarrow\\ \underset{\alpha}{\land}f_{(S\backslash A_\alpha)}(x)&=1~. \end{aligned} \end{equation}
证毕!

   总结一下本文的内容,引入逻辑与或的概念并定义集合的坐标函数,我们可以将集合中的概念严格定义一遍而避免使用 “或” 和 “且” 这样模糊的概念,并且在证明集合运算的两个性质做到清楚了当。

                     

© 小时科技 保留一切权利