Haskell 集合数学 SQL C#

IT 中的数学 #2：文氏图

Sander Rossel

5.00/5 (14投票s)

2015年11月7日

CPOL

7分钟阅读

26143

使用文氏图可视化集合。

大家好，欢迎回到“IT 中的数学”系列第二部分。我收到了很多积极的反馈，所以我想我应该继续我正在做的事情。这篇帖子将接着第一部分的内容，所以如果你还没有读过，我建议你现在就去读，然后再继续。

这是本文中我将使用的符号的快速备忘单
显式定义： $A = \{a, b, c\}$
隐式定义： $A = \{x | \text{ x is a letter in the alphabet}\}$
a 是 A 的元素： $a \in A$
a 不是 A 的元素： $a \notin A$
A 是 B 的子集： $A \subset B$
空集： $\emptyset$

文氏图

正如我承诺的那样，我们将使用这篇帖子来组合集合。在我们这样做之前，让我们看看如何可视化集合。我们可以使用文氏图。文氏图尽可能简单（尽管它们也可以相当复杂）。每个集合都由一个圆圈表示。该图可以说明所表示集合之间的关系。

让我们来看一个例子。我们有两个集合， $A = \{a, b, c\}$ 和 $B = \{d, e, f\}$ 。让我们在文氏图中展示它们。

当两个集合没有共同元素时，或者对于每一个 $x \in A$ 都满足 $x \notin B$ ，我们说这两个集合是*不相交*的。

现在假设 $A \subset B$ (A 是 B 的子集)。我们可以在文氏图中展示这一点，你会立即认出来的。

当 A 是 B 的子集时，B 完全覆盖 A。

在接下来的章节中，我们将组合集合并使用文氏图来可视化我们感兴趣的元素。

交集

假设我们有两个集合， $A = \{a, b, c, d\}$ 和 $B = \{c, d, e, f\}$ 。如果我问你哪些元素既在 A 中又在 B 中，你会回答 c 和 d。

这被称为 A 和 B 的*交集*。
我们可以写成 $A \cap B$ 。
在这个例子中，我们可以说 $A \cap B = \{c, d\}$
更正式地说，我们说 $A \cap B = \{x | x \in A \text{ and } x \in B\}$ 。
而“and”的符号实际上是 $\land$ ，所以要完全形式化

$A \cap B = \{x | x \in A \land x \in B\}$

呼，这看起来很像数学！你应该这样读：“A 和 B 的交集是所有 x 的集合，其中 x 是 A 的元素 *且* x 是 B 的元素。”
这是文氏图，它很好地可视化了这一点。交集是粗黑线部分，即 A 和 B 重叠的部分。

A Venn diagram of an intersection — 交集文氏图

有了交集，我们可以给出不相交集的正式定义。当 $A \cap B = \emptyset$ 时，A 和 B 是不相交的。

此外，我们可以说对于任何集合 A，都满足 $A \cap \emptyset = \emptyset$ 。
同样 $A \cap A = A$ 。
并且当 $A \subset B$ 时， $A \cap B = A$ (请查看子集文氏图)。

Union

两个集合的交集是 x 的集合，其中 x 在 A *并且*在 B 中。类似地，两个集合的*并集*是 A *或* B 中的元素的集合。所以当我们有 $A = \{a, b, c, d\}$ 和 $B = \{c, d, e, f\}$ 时，A 和 B 的并集是 $\{a, b, c, d, e, f\}$ (没有重复)。

我们可以将 A 和 B 的并集写成 $A \cup B$ 。
就像 $\land$ 是“and”的符号一样， $\lor$ 是“or”的符号。所以并集的正式定义如下

$A \cup B = \{x | x \in A \lor x \in B\}$

将其读作“A 和 B 的并集是所有 x 的集合，其中 x 是 A 的元素 *或* x 是 B 的元素。”
在文氏图中，并集基本上就是两个集合（粗黑线部分）。

A Venn diagram of an overlapping union — 重叠并集的文氏图

与交集不同，不相交集的并集不是空集（请注意，两个集合都有粗黑线）。

现在对于任何集合 A，都有 $A \cup \emptyset = A$ 。
同样， $A \cup A = A$ 。
同样，当 $A \subset B$ 时， $A \cup B = B$ (请查看子集文氏图)。

全集和补集

当我们讨论集合时，我们通常不会孤立地讨论这个集合。当我告诉你，不吸烟者寿命更长时，你明白他们比吸烟者寿命更长。你也明白不吸烟者和吸烟者加起来就是世界人口。在这种情况下，我们说我们有一个不吸烟者集合，在一个*全集*（所有人类）中。我们用大写字母 U 表示全集。

对于每一个集合 $A_1, A_2, A_3... A_n$ ，都有 $A_n \subset U$ 。
这很有道理，因为 U 代表了我们希望在我们的案例中考虑的所有元素。没有任何集合可以包含不属于所有元素一部分的元素。

在文氏图中，我们绘制一个矩形作为全集，并在其中绘制所有集合。在下面的例子中，N 是不吸烟者集合，U 是包含所有人的全集。

现在，有了全集这个概念，我们可以说我们想要所有不在任何集合 A 中的元素。我们称之为 A 的*补集*，并记作 $A^c$ 。在下面的文氏图中，白色部分代表 $A^c$ 。

我们现在可以正式定义补集

$A^c = \{ x | x \in U \land x \notin A \}$

不言而喻，但是 $\emptyset^c = U$ 和 $U^c = \emptyset$ 。
不那么明显的是 $(A^c)^c = A$ 。这很有意义，因为我们首先取所有不是 A 的元素（A 的补集），然后我们取所有不是结果集合中的元素，但这实际上就是 A。试着在文氏图中画出来，你就会明白我的意思了。

相对于全集的补集称为*绝对补集*。补集也可以相对于其他集合。例如，当没有定义全集并且我们有集合 A 和 B 时，B 中 A 的相对补集是 B 中不在 A 中的元素集合。这表现为 $B \cap A^c$ 或 $A \setminus B$ 。

$A \setminus B = \{ x | x \in B \land x \notin A \}$

在文氏图中， $A \ B$ 的样子如下

组合集合

我们现在可以使用交集、并集和补集来组合集合。例如，假设我们的全集 U 是地球上所有生物。在 U 中，我们有集合 M（包含所有哺乳动物）、B（包含所有鸟类）和 E（包含所有产卵动物）。形式上
$U = \{ x | \text{x is an animal} \}$
$M = \{ x | x \in U \land \text{x is a mammal} \}$
$B = \{ x | x \in U \land \text{x is a bird} \}$
$E = \{ x | x \in U \land \text{x lays eggs} \}$
给出以下文氏图，我们可以得出一些结论。

A Venn diagram with multiple sets — 多集文氏图

我们可以看到，所有鸟都会产卵。有些哺乳动物也会产卵。没有动物既是鸟又是哺乳动物。正如你所见，文氏图非常有用。
现在假设我们想要所有产卵的哺乳动物集合，以及所有鸟类。这是集合 $(M \cap E) \cup B$ 。也就是说，我们取 M 和 E 的交集，然后将结果与 B 进行并集。在文氏图中，我们可以看到这个集合（红色部分）。

现在我们可以通过交集、并集和补集来得到所有集合的组合。这并不总是容易的，但它是可能的。

一些代码

正如我承诺的那样，我将保持实用。那么这一切的实际用途是什么呢？嗯，大多数语言都允许你使用这些确切的功能！

例如，看看这个 SQL 表达式。

(SELECT 1
UNION SELECT 2
UNION SELECT 3)
INTERSECT
(SELECT 3
UNION SELECT 4)

那会返回什么？它只返回 3，因为 3 是两个集合的元素。这个例子也展示了 UNION 操作符。基本上，这是一个集合 $(\{1\} \cup \{2\} \cup \{3\}) \cap (\{3\} \cup \{4\})$ 。

SQL 也知道补集。

(SELECT 1
UNION SELECT 2
UNION SELECT 3)
EXCEPT
(SELECT 3
UNION SELECT 4)

这里发生的是，我们有一个（隐含的）全集 $U = \{1, 2, 3, 4\}$ ，EXCEPT 是补集。所以这个查询基本上是公式 $\{3, 4\}^c$ 。
我们也可以说 U 未定义，这是 $\{3, 4\}$ 在 $\{1, 2, 3\}$ 中的相对补集： $\{3, 4\} \setminus \{1, 2, 3\} = \{1, 2\}$ 。

那么 C# 呢？在我上一篇文章中，我们看到了 HashSet<T>，但我现在不打算用它。我将只使用 List<T>，因为 LINQ 提供了各种用于处理集合的扩展方法。请注意，HashSet<T> 除了 LINQ 方法之外，还有自己的方法。

List<int> a = new List<int>();
a.Add(1);
a.Add(2);
a.Add(3);

List<int> b = new List<int>();
b.Add(3);
b.Add(4);

List<int> intersect = a.Intersect(b).ToList();
List<int> union = a.Union(b).ToList();
List<int> except = a.Except(b).ToList();

你可能会想，这在 Haskell 中看起来是什么样的（因为我上次也给你展示了 Haskell），但实际上并没有太大区别。

Prelude> import Data.List
Prelude Data.List> [1, 2, 3] `intersect` [3, 4]
[3]
Prelude Data.List> [1, 2, 3] `union` [3, 4]
[1,2,3,4]
Prelude Data.List> [1, 2, 3] \\ [3, 4]
[1,2]

我实际上在日常工作中需要这些东西。这并不难，有时它是一个明确的业务需求。例如，我需要来自荷兰、比利时和卢森堡（BeNeLux）的所有销售订单。这真的只是一个并集！我也需要交集，给我所有不在某个客户列表中的荷兰客户。还有所有非荷兰客户呢？这只是补集！

下次我想继续讨论代数，特别是集合代数。听起来会让你做噩梦吗？别担心，我会温柔的！

下次见！

文章 IT 中的数学 #2：文氏图最初发布在 Sander's bits。