代数集合数学

IT中的数学 #3：集合代数

Sander Rossel

4.86/5 (6投票s)

2015年11月13日

CPOL

6分钟阅读

22804

代数和集合代数入门。

大家好，欢迎回来！我在上一篇文章中已经宣布了本篇文章的主题：集合代数。所以，代数很难，令人望而生畏。至少人们是这么说的（嗯哼），让我们摆脱这种想法。如果你明白了我的梗，我很抱歉。

如果你还没有阅读我之前的文章，我强烈建议你阅读，因为这篇文章将接续之前的内容。

以下是上一篇文章中介绍的符号的快速备忘单。
交集： $A \cap B = \{x | x \in A \land x \in B\}$
并集： $A \cup B = \{x | x \in A \lor x \in B\}$
全集 U：我们考虑的所有元素的集合。
绝对补集（或简称补集）： $A^c = \{x | x \in U \land x \notin A\}$
B中A的相对补集： $B \cap A^c = A \setminus B$

代数

到底什么是代数？它是关于符号、运算以及操作这些运算的规则的研究。初等代数，例如，就是一套关于数字运算（+、-、/、*）的规则。同样， $\cap, \cup$ 和 $A^c$ 是对集合进行的运算，而用于操作它们的规则则被称为集合代数。

这些规则可以帮助我们简化公式。那么，让我们开始吧。

交换律

考虑以下加法：2 + 3。我敢肯定我们都知道答案是 5，如果我们把数字换成 3 + 2，答案也不会改变。更抽象地说，我们可以说对于任意两个数字 x 和 y，都有 $x + y = y + x$ 。
当一个运算中操作数（即对运算执行的对象）的顺序不影响运算结果时，我们称该运算是可交换的。

乘法（在实数上）也是可交换的，因为 $2 \cdot 3 = 3 \cdot 2$ （你可能习惯于看到 x 或 * 作为乘法符号，但你应该还记得高中时使用的 $\cdot$ ）。减法不可交换，因为 $3 - 2 \neq 2 - 3$ ，除法也不可交换， $2/3 \neq 3/2$ 。

在处理集合时，我们可以说 $A \cap B = B \cap A$ 和 $A \cup B = B \cup A$ 。这意味着 $\cap$ 和 $\cup$ 都是可交换的。

结合律

当在单个公式中执行相同运算的顺序不影响公式结果时，我们说该运算是可结合的。例如 $(1 + 2) + 3 = 1 + (2 + 3)$ 。先计算 1 + 2 再加 3，还是先计算 2 + 3 再加到 1 上，结果都是 6，这并不重要。
乘法也同样如此，因为 $(2 \cdot 3) \cdot 4 = 2 \cdot (3 \cdot 4)$ ，但减法和除法则不然， $(10 - 8) - 2 \neq 10 - (8 - 2)$ 和 $(16/4)/2 \neq 16/(4/2)$ 。

在集合方面，我们发现 $\cap$ 和 $\cup$ 都是可结合的，因为 $(A \cap B) \cap C = A \cap (B \cap C)$ 和 $(A \cup B) \cup C = A \cup (B \cup C)$ 。

这意味着可以省略括号，消除对运算符优先级的任何混淆。

有了交集和并集的交换律和结合律，我们现在可以简化
$C \cap (D \cap A) \cap B$
为 $A \cap B \cap C \cap D$
或 $C \cup (D \cup A) \cup B$
为 $A \cup B \cup C \cup D$ 。
当我们结合交集和并集时，也可以进行简化。 $D \cap (C \cup (B \cup A))$ 可以简化为 $(A \cup B \cup C) \cap D$ 。请注意，我们仍然需要括号来定义 $\cap$ 和 $\cup$ 运算的顺序。

现在我们可以对任意数量的集合进行交集或并集运算，因为我们不必担心操作数或运算符的顺序。 $A_1 \cap A_2 \cap A_3...$ 很快就会变得很麻烦。所以，假设我们有 $A_1$ 到 $A_{100}$ 。所有这些集合的交集或并集现在可以表示如下：
$\displaystyle\bigcup_{i=1}^{100} A_i$ 或 $\displaystyle\bigcap_{i=1}^{100} A_i$
而在行内，它们看起来像 $\cup_{i=1}^{100} A_i$ 和 $\cap_{i=1}^{100} A_i$ 。

有时我们不知道集合有多少个。特别是当一个集合是无限集合时，上述表示法是不可行的。我们现在可以使用索引符号来对集合内的所有集合进行交集或并集运算。
$\displaystyle\bigcap_{i \in I} A_i$ 或 $\displaystyle\bigcup_{i \in I} A_i$
$\cap_{i \in I} A_i$ 和 $\cup_{i \in I} A_i$ 基本上意味着“对于集合 I 中的每个集合 i 进行交集/并集”（可以想象成 C# 中 List of Lists 的 foreach 循环）。

分配律

分配律 很难用语言来描述。只需记住乘法对加法是分配的，这意味着 $3 \cdot (4 + 5) = (3 \cdot 4) + (3 \cdot 5)$ 。更一般地说， $x(y + z) = xy + xz$ （字母之间的乘法符号经常被省略）。

$\cap$ 对 $\cup$ 是分配的，这意味着
$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

同样， $\cup$ 对 $\cap$ 是分配的，所以
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

我们现在可以证明 $(A \cap B) \cap (A \cup B) = A \cap B$ 。当我们对 $(A \cap B) \cap (A \cup B)$ 应用分配律时，得到 $((A \cap B) \cap A) \cup ((A \cap B) \cap B)$ 。
这里再次显示，但带有颜色（和非数学符号），以便你可以跟随一切去向
(A n B) n (A u B) = ((A n B) n A) u ((A n B) n B)。
应用交换律和结合律，我们现在可以进一步简化
$((A \cap B) \cap A) \cup ((A \cap B) \cap B) = (A \cap A \cap B) \cup (A \cap B \cap B)$ .
在上一篇文章 IT中的数学 #2：维恩图中，我们已经看到 $A \cap A = A$ 和 $A \cup A = A$ 。这被称为幂等性，并且可以（两次）应用于此处进行进一步简化。
$(A \cap A \cap B) \cup (A \cap B \cap B) = (A \cap B) \cup (A \cap B) = A \cap B$

让我们重复一下

$(A \cap B) \cap (A \cup B)$

分配律

$((A \cap B) \cap A) \cup ((A \cap B) \cap B)$

结合律

$(A \cap B \cap A) \cup (A \cap B \cap B)$

交换律

$(A \cap A \cap B) \cup (A \cap B \cap B)$

幂等性

$(A \cap B) \cup (A \cap B)$

幂等性

$A \cap B$

因此，我们可以利用分配律、结合律、交换律和幂等性来简化一个相当复杂的公式！不幸的是，这样做并不那么容易……

其他属性

不幸的是，我们还没有完成。还有一些其他的属性，其中一些我们已经遇到过，我想在此一一说明。

首先是吸收律，它指出 $A \cap (A \cup B) = A$ 和 $A \cup (A \cap B) = A$ 。

我们已经看到所谓的零元素，即空集 $\emptyset$ 。就像数字一样（ $x + 0 = x$ , $x - 0 = x$ 和 $x \cdot 0 = 0$ ），有一些规则来处理 $\emptyset$ 。幸运的是，它们并不难。
$A \cap \emptyset = \emptyset$ 和 $A \cup \emptyset = A$ 。

当定义了全集 U 时，我们可以说：
$A \cap U = A$ 和 $A \cup U = U$ 。

我之前已经展示过，双重补集会返回原集： $(A^c)^c = A$ 。
另外， $A \cap A^c = \emptyset$ 和 $A \cup A^c = U$ 。

德摩根定律

最后，我们将介绍德摩根定律，它以发明者、英国数学家奥古斯都·德摩根的名字命名。
假设我的博客只能被那些没有学过数学或 IT 的人阅读。设 $A = \{x | \text{x has studied maths}\}$ ，设 $B = \{x | \text{x has studied IT}\}$ 。那么现在可以阅读我博客的人是没有学过数学或 IT 的人： $(A \cup B)^c$ 。我也可以说没有学过数学的人和没有学过 IT 的人可以阅读我的博客： $A^c \cap B^c$ 。但这是同一批人！
在下面的维恩图中，这由白色部分表示。

A Venn diagram of De Morgan's Law — 德摩根定律的维恩图

简而言之， $(A \cup B)^c = A^c \cap B^c$ 。

现在假设我的博客可能只被那些没有同时学过数学和 IT 的人阅读。所以那是 $(A \cap B)^c$ 。或者我们可以说没有学过数学并且没有学过 IT 的人， $A^c \cup B^c$ 。同样，这也是同一批人。在维恩图中，它是 A 和 B 不重叠的部分（几乎所有地方）。

因此，这意味着 $(A \cap B)^c = A^c \cup B^c$ 。

现在让我们来看另一个简化公式的例子。假设我们有 $B \cap (A \cap B)^c$ 。所以，让我们先应用德摩根定律： $B \cap (A \cap B)^c = B \cap (A^c \cup B^c)$ 。现在你可能会认出这是分配律的一个漂亮模式！所以让我们应用分配律， $B \cap (A^c \cup B^c) = (B \cap A^c) \cup (B \cap B^c)$ 。这很好，因为我们知道 $B \cap B^c = \emptyset$ 。现在我们知道 $(B \cap A^c) \cup \emptyset = B \cap A^c$ 。也许你会记得我上一篇文章中的内容，这就是 $B \setminus A$ 。就这么简单！