集合的运算

贡献者：零穹

预备知识　集合

　　通过 “集合” 的预备知识，我们应该知道，集合是由元素构成的。这是说，在一开始讨论集合的时候，必须先行给出一个集合，才能继续进行有关的讨论。这是说当你说集合 $A$ 时，我们已经知道了它的元素。具体而言，当谈论集合 $A$ 时，你应该马上将其理解成 $A = {a_{1}, \dots, a_{n}, \dots}$ ，其中花括号里的是 $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} \to Z_{2}$ 为与，若

\begin{matrix} (1) & f (0, 0) = 0, f (0, 1) = 0, f (1, 0) = 0, f (1, 1) = 1 . \end{matrix}

并将与函数

f

记作

\land

。

定义 2　或

　　称函数 $f : Z_{2} \times Z_{2} \to Z_{2}$ 为或，若

\begin{matrix} (2) & f (0, 0) = 0, f (0, 1) = 1, f (1, 0) = 1, f (1, 1) = 1 . \end{matrix}

并将或函数

f

记作

\lor

。

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

定理 1　与或分配律

　　对任意 $a, b, c \in Z_{2}$ ，成立恒等式：

\begin{matrix} (3) & \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{matrix}

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

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

\begin{matrix} (4) & \lor (a, 1) = \lor (b, 1) = 1 . \end{matrix}

于是由定义 1 ，右边为

\land (1, 1) = 1

，即

\begin{matrix} (5) & \lor (\land (a, b), 1) = \land (\lor (a, 1), \lor (b, 1)) . \end{matrix}

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

\begin{matrix} (6) & \lor (\land (a, b), 0) = \land (\lor (a, 0), \lor (b, 0)) . \end{matrix}

证毕！

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

\begin{matrix} (7) & \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{matrix}

以后将采用此记号。总结成定义和定理的形式就是：

定义 3　

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

定理 2　分配律

\begin{matrix} (8) & \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{matrix}

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

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

定义 4　

　　设 $X$ 是集合，则称函数 $f_{X}$ 是集合 $X$ 上的坐标，若

\begin{matrix} (9) & f_{X} (x) = {\begin{aligned} 1, x \in X, \\ 0, x \notin X . \end{aligned} \end{matrix}

并称

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{matrix} (10) & \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), \\ (x \in X \lor y \in Y) \land z \in Z = (x \in X \land z \in Z) \lor (y \in Y \land z \in Z) . \end{aligned} \end{matrix}

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

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

定义 6　交集

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

\begin{matrix} (11) & {z | z \in X \land z \in Y = 1} \end{matrix}

为

X, Y

的交集，记作

X \cap Y

。

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

定义 7　并集

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

\begin{matrix} (12) & {z | z \in X \lor z \in Y = 1} \end{matrix}

为

X, Y

的并集，记作

X \cup Y

。

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

定理 4　

\begin{matrix} (13) & \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{matrix}

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

\begin{matrix} (14) & \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{matrix}

　　 证毕！

推论 1　

\begin{matrix} (15) & \begin{aligned} f_{⋂_{α} X_{α}} (z) & = \underset{α}{\land} f_{X_{α}} (z), \\ f_{⋃_{α} X} (z) & = \underset{α}{\lor} f_{X_{α}} (z) . \end{aligned} \end{matrix}

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

4. 运算性质

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

定理 5　交并的分配律

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

\begin{matrix} (16) & \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{matrix}

　　 证明：由定义 6 ，定义 7 ，只需证明

\begin{matrix} (17) & \begin{aligned} z \in (X \cap Y) & \lor z \in Z = 1 \\ ⇕ \\ (z \in X \cup Z) & \land (z \in Y \cup Z) = 1 . \end{aligned} \end{matrix}

和

\begin{matrix} (18) & \begin{aligned} z \in (X \cup Y) & \land z \in Z = 1 \\ ⇕ \\ (z \in X \cap Z) & \lor (z \in Y \cap Z) = 1 . \end{aligned} \end{matrix}

由定理 4 和定义 5 ，式 17 和式 18 等式左边可写为

\begin{matrix} (19) & \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{matrix}

于是只需证明

\begin{matrix} (20) & \begin{aligned} (z \in X \land z \in Y) & \lor z \in Z = 1 \\ ⇕ \\ (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 \\ ⇕ \\ (z \in X \land z \in Y) & \lor (z \in Y \land z \in Z) = 1 . \end{aligned} \end{matrix}

　　由定理 3 ，式 20 成立。

　　 证毕！

定理 6　对偶原理（de Morgan 定理）

\begin{matrix} (21) & \begin{aligned} S ∖ ⋃_{α} A_{α} & = ⋂_{α} (S ∖ A_{α}), \\ S ∖ ⋂_{α} A_{α} & = ⋃_{α} (S ∖ A_{α}), \end{aligned} \end{matrix}

　　在证明之前，首先明确， $x \in A ∖ B$ 等价于 $f_{A} (x) = 1, f_{B} (x) = 0$ .

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

\begin{matrix} (22) & \begin{aligned} S ∖ ⋂_{α} (S ∖ A_{α}) & = S ∖ (S ∖ ⋃_{α} A_{α}) = ⋃_{α} A_{α}, \\ ⇓ \\ S ∖ ⋂_{α} A_{α} & = S ∖ ⋂_{α} (S ∖ (S ∖ A_{α})) = ⋃_{α} (S ∖ A_{α}) . \end{aligned} \end{matrix}

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

\begin{matrix} (23) & \begin{aligned} f_{S} (x) = 1, & f_{⋃_{α} A_{α}} (x) = 0 \\ ⇕ \\ f_{⋂_{α} (S ∖ A_{α})} (x) & = 1 . \end{aligned} \end{matrix}

由推论 1 ，只需证明

\begin{matrix} (24) & \begin{aligned} f_{S} (x) = 1, & \underset{α}{\lor} f_{A_{α}} (x) = 0 \\ ⇕ \\ \underset{α}{\land} f_{(S ∖ A_{α})} (x) & = 1 . \end{aligned} \end{matrix}

这可证明如下

\begin{matrix} (25) & \begin{aligned} f_{S} (x) = 1, & \underset{α}{\lor} f_{A_{α}} (x) = 0 \\ ⇕ \\ f_{S} (x) = 1, & f_{A_{α}} (x) = 0, \forall α \\ ⇕ \\ f_{S ∖ A_{α}} (x) = 1, & \forall α \\ ⇕ \\ \underset{α}{\land} f_{(S ∖ A_{α})} (x) & = 1 . \end{aligned} \end{matrix}

证毕！

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

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。

集合的运算

1. 与 ∧ 和 或 ∨

定义 1 与

定义 2 或

定理 1 与或分配律

定义 3

定理 2 分配律

2. 属于 ∈ 的数值化

定义 4

定义 5 简记约定

定理 3

3. 交 ∩，并 ∪

定义 6 交集

定义 7 并集

定理 4

推论 1

4. 运算性质

定理 5 交并的分配律

定理 6 对偶原理（de Morgan 定理）

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

定义 1　与

定义 2　或

定理 1　与或分配律

定义 3　

定理 2　分配律

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

定义 4　

定义 5　简记约定

定理 3　

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

定义 6　交集

定义 7　并集

定理 4　

推论 1　

定理 5　交并的分配律

定理 6　对偶原理（de Morgan 定理）