离散数学/集合论

离散数学
← 介绍	集合论	集合论/页面 2 →

维基百科在 集合论 中有相关信息

介绍

集合论从一个简单的开始：它考察一个对象是否属于或不属于一个集合，这个集合是通过某种明确的方式描述的。从这个简单的开始，可以发展出一系列越来越复杂（而且有用！）的思想，这些思想导致了具有多种应用的符号和技术。

定义：集合

集合的当前定义可能听起来很模糊。一个集合可以定义为实体的无序集合，这些实体由于遵循某个规则而相关联。

'实体'可以是任何东西，字面上：数字、人、形状、城市、文本片段，...等等

关于它们都遵循的'规则'的关键事实是它必须是明确定义的。换句话说，它必须清楚地描述实体遵循的内容。例如，如果我们谈论的实体是单词，则一个明确定义的规则是

X is English

一个没有明确定义（因此不能用来定义集合）的规则可能是

X is hard to spell

其中 X 是任何单词

元素

属于给定集合的实体称为该集合的元素。例如

Henry VIII is an element of the set of Kings of England. : kings of England {Henry VIII}

集合符号

要列出集合的元素，我们将它们用大括号括起来，并用逗号隔开。例如

 $\{-3,-2,-1,0,1,2,3\}$

集合的元素也可以用语言描述

 $\{{\text{ integers between }}-3{\text{ and  }}3{\text{ inclusive}}\}$

集合生成式符号可用于描述那些难以明确列出的集合。为了表示任何特定的集合，我们使用字母 $x$

 $\{x|x{\text{ is an integer and }}|x|<4\}$

或者等效地

 $\{x|x\in \mathbb {Z} ,|x|<4\}$

符号 $\in$ 和 $\notin$ 分别表示元素的包含和排除

 ${\text{dog }}\in \{{\text{quadrupeds}}\}$ 
 ${\text{Washington DC}}\notin \{{\text{European capital cities}}\}$

集合可以包含无限个元素，例如素数集合。省略号用于表示模式的无限延续

 $\{2,3,5,7,11,\dots \}$

请注意，省略号的使用可能会导致歧义，上面的集合可以被视为可被 4 整除的整数集合，例如。

集合通常用大写字母表示： $A$ ， $B$ ，...
元素通常用小写字母表示： $x$ ， $y$ ，...

特殊集合

全集

当前上下文中所有实体的集合称为全集，或简称为宇宙。它用 $U$ 表示。

上下文可以是家庭作业练习，例如，其中全集被限制为其考虑的特定实体。此外，它可以是任何任意的问题，我们清楚地知道它在哪里应用。

空集

不包含任何元素的集合称为空集或空集。它用一对空括号表示： $\{\}$ 或符号 $\varnothing$ 表示。

定义一个不包含任何元素的集合可能看起来很奇怪。但是，请记住，人们可能会寻找问题的解决方案，在这些问题中，一开始并不清楚这些解决方案是否存在。如果事实证明没有解决方案，那么解决方案集将为空。

例如

如果 $U=\{{\text{words in the English language}}\}$ ，那么 $\{{\text{words with more than 50 letters}}\}=\varnothing$ 。

如果 $U=\{{\text{whole numbers}}\}$ ，那么 $\{x|x^{2}=10\}=\varnothing$ 。

空集的运算

对空集执行的运算（作为要操作的事物的集合）也可能令人困惑。（此类运算为空运算。）例如，空集元素的总和为零，但空集元素的乘积为一（参见空乘积）。这可能看起来很奇怪，因为空集没有元素，那么它们是加起来还是乘起来有什么关系（因为“它们”不存在）？最终，这些运算的结果更多地反映了所讨论的运算本身，而不是空集。例如，请注意，零是加法的单位元，而一是乘法的单位元。

特殊数字集

一些集合使用如此频繁，以至于它们被赋予特殊的符号。

自然数

从 1 开始的“计数”数（或整数）称为自然数。此集合有时用N表示。所以N = {1, 2, 3, ...}

注意，当我们用手写这个集合时，我们不能用粗体类型写，所以我们用黑板粗体字写一个 N： $\mathbb {N}$

整数

所有整数，正数、负数和零构成整数集。它有时用Z表示。所以Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}

在黑板粗体中，它看起来像这样： $\mathbb {Z}$

实数

如果我们将整数集扩展到包括所有小数，我们将形成实数集。实数集有时用R表示。

实数在小数点后可能有一个有限的数字（例如 3.625），或者一个无限的小数位数。在无限位数的情况下，这些位数可能

重复；例如 8.127127127...

... 或者它们可能不重复；例如 3.141592653...

黑板粗体： $\mathbb {R}$

有理数

那些小数位数有限或循环的实数称为 *有理数*。有理数集合有时用字母 **Q** 表示。

有理数始终可以写成精确的分数 *p*/ *q*；其中 *p* 和 *q* 是整数。如果 *q* 等于 1，则分数只是整数 *p*。注意，*q* 决不能等于零，因为此时该值将是未定义的。

例如：0.5、-17、2/17、82.01、3.282828... 都是有理数。

黑板粗体： $\mathbb {Q}$

无理数

如果一个数 *不能* 用分数 *p*/ *q* 精确表示，则称其为 *无理数*。

例如：√2、√3、π。

集合论练习 1

点击链接查看集合论练习 1

集合之间的关系

现在我们将研究集合之间可能存在的关系。

相等

两个集合 $A$ 和 $B$ 被称为 **相等** 当且仅当它们具有完全相同的元素。在这种情况下，我们简单地写

 $A=B$

注意关于相等集合的另外两个事实

元素列出的 *顺序* 无关紧要。

如果一个元素被 *列出多次*，则任何重复出现都将被忽略。

因此，例如，以下集合都是相等的

 $\{1,2,3\}=\{3,2,1\}=\{1,1,2,3,2,2\}$

（您可能想知道为什么有人会写出一个像 $\{1,1,2,3,2,2\}$ 的集合。您可能还记得，当我们定义 *空集* 时，我们注意到特定问题可能没有解决方案，因此需要一个空集。好吧，在这里，我们可能正在尝试几种不同的解决问题的方法，其中一些方法实际上会导致相同的解决方案。但是，当我们考虑 *不同的* 解决方案时，任何此类重复将被忽略。）

子集

如果集合 $A$ 的所有元素也是集合 $B$ 的元素，那么我们说 $A$ 是 $B$ 的 *子集*，我们写

 $A\subseteq B$

例如

在以下示例中

If  $T=\{2,4,6,8,10\}$  and  $E=\{{\text{even integers}}\}$ , then  $T\subseteq E$ 
If  $A=\{{\text{alphanumeric characters}}\}$  and  $P=\{{\text{printable characters}}\}$ , then  $A\subseteq P$ 
If  $Q=\{{\text{quadrilaterals}}\}$  and  $F=\{{\text{plane figures bounded by four straight lines}}\}$ , then  $Q\subseteq F$

请注意， $A\subseteq B$ 并不意味着 $B$ 必须包含不在 $A$ 中的额外元素；这两个集合可以相等——正如 $Q$ 和 $F$ 在上面那样。但是，如果此外 $B$ 确实包含至少一个不在 $A$ 中的元素，那么我们称 $A$ 是 $B$ 的 真子集。在这种情况下，我们将写

 $A\subset B$

在上面的例子中

 $E$  contains ... -4, -2, 0, 2, 4, 6, 8, 10, 12, 14, ... , so  $T\subset E$

 $P$  contains $, ;, &, ..., so  $A\subset P$

但 $Q$ 和 $F$ 只是说同一件事的不同方式，所以 $Q=F$

使用 $\subset$ 和 $\subseteq$ ；显然类似于在比较两个数字时使用 < 和 ≤。

还要注意，每个集合都是全集的子集，而空集是每个集合的子集。

（你可能会对最后一句话感到好奇：空集怎么可能成为任何东西的子集，因为它不包含任何元素？这里的关键是，对于每个集合 $A$ ，空集不包含任何不在 $A$ 中的元素。所以 $\oslash \subseteq A$ 对于所有集合 $A$ 。）

最后，请注意，如果 $A\subseteq B{\text{ and }}B\subseteq A{\text{ then }}A$ 和 $B$ 必须包含完全相同的元素，因此相等。换句话说

 $A\subseteq B{\text{ and }}B\subseteq A{\text{ then }}A=B$

不相交

如果两个集合没有共同的元素，则称它们为不相交。例如

If  $A=\{{\text{even numbers}}\}$  and  $B=\{1,3,5,11,19\}$ , then  $A$  and  $B$  are disjoint sets

维恩图

维恩图可以是说明集合之间关系的一种有用方法。

在维恩图中

全集用一个矩形表示。矩形内的点代表全集中的元素；矩形外的点代表不在全集中的元素。你可以将这个矩形看作是一个'围栏'，将不需要的东西挡在外面，并将我们的注意力集中在我们正在讨论的事情上。

其他集合用循环表示，通常是椭圆形或圆形，绘制在矩形内。同样，给定循环内的点代表它所代表的集合中的元素；循环外的点代表不在集合中的元素。

在左侧，集合A和B是不相交的，因为循环没有重叠。

在右侧，A是B的子集，因为表示集合A的循环完全被循环B包围。

维恩图：实战示例

示例 1

图 3表示一个维恩图，它显示了两个集合A和B，在一般情况下，对集合之间的任何关系一无所知。

注意，表示全集的矩形被分成四个区域，分别标记为i、ii、iii和iv。

如果结果表明，关于集合A和B，可以说什么

(a) 区域ii为空？

(b) 区域iii为空？

(a) 如果区域ii为空，那么A不包含任何不在B中的元素。所以A是B的子集，图应该像上面的图 2一样重新绘制。

(b) 如果区域iii为空，那么A和B没有共同的元素，因此是不相交的。然后图应该像上面的图 1一样重新绘制。

示例 2

(a) 画一个维恩图来表示三个集合A、B和C，在一般情况下，对集合之间可能的任何关系一无所知。

(b) 现在表示U的矩形被分成多少个区域？

(c) 当这些区域的各种组合为空时，讨论集合A、B和C之间的关系。

(a) 图 4中的图显示了三个集合的一般情况，其中对它们之间任何可能的关系列一无所知。

(b) 表示U的矩形现在被分成 8 个区域，用罗马数字i到viii表示。

(c) 可能存在各种空的区域组合。在每种情况下，都可以重新绘制维恩图，以使空的区域不再包含在内。例如

如果区域ii为空，则表示A的循环应该变小，并移动到B和C内部以消除区域ii。

如果区域ii、iii和iv为空，则使A和B变小，并将它们移动，使它们都位于C内部（从而消除所有这三个区域），但以一种方式这样做，使它们仍然相互重叠（从而保留区域vi）。

如果区域iii和vi为空，则'拉开'循环A和B以消除这些区域，但保持每个循环与循环C重叠。

……等等。绘制上述每个示例的维恩图留作读者的练习。

示例 3

定义以下集合

U = {1, 2, 3, …, 10}

A = {2, 3, 7, 8, 9}

B = {2, 8}

C = {4, 6, 7, 10}

使用下面描述的两阶段技术，绘制一个维恩图来表示这些集合，并在适当的区域标记所有元素。

该技术如下

绘制一个'一般'的 3 集合维恩图，类似于示例 2中的图。

一次只遍历全集中的元素，每次只遍历一次，将每个元素输入图的适当区域。

如果需要，重新绘制图，将循环彼此移动或分开以消除任何空的区域。

不要从输入集合A的元素开始，然后是集合B，然后是集合C – 你可能会错过元素或将它们包含两次！

解决方案

在绘制三个空循环的图后，它看起来像图 4（但没有罗马数字！），遍历U中的十个元素 - 数字 1 到 10 - 对每个元素问三个问题；就像这样

第一个元素：1

你在A中吗？不

你在B中吗？不

你在C中吗？不

对所有三个问题的回答都是'否'，这意味着数字 1 在所有三个循环之外。所以在适当的区域（图 4中的区域编号i）中写入它。

第二个元素：2

你在A中吗？是

你在B中吗？是

你在C中吗？不

是，是，否：所以数字 2 在A和B内，但在C之外。然后放在区域iii中。

……以此类推，对元素 3 到 10 进行操作。

生成的图看起来像图 5。

最后一步是检查图中是否存在空的区域 - 在这种情况下，我们称之为图 4中的iv、vi和vii区域 - 然后重新绘制图以消除这些区域。当我们这样做时，我们将清楚地看到三个集合之间的关系。

所以我们需要

拉开B和C，因为它们没有共同的元素。

将B推到A内，因为它在A之外没有元素。

最终结果如图6所示。

维恩图中的区域和真值表

也许你已经意识到，在维恩图中添加一个额外的集合会使表示全集的矩形被划分的区域数量加倍。这给了我们一个非常简单的模式，如下所示

使用一个集合循环，将只有两个区域：循环的内部和外部。

使用两个集合循环，将有四个区域。

使用三个循环，将有八个区域。

……等等。

不难理解为什么应该是这样。我们在图中添加的每个新循环都会将每个现有区域分成两个，从而将区域总数加倍。

在A中吗？	在B中吗？	在C中吗？
Y	Y	Y
Y	Y	N
Y	N	Y
Y	N	N
N	Y	Y
N	Y	N
N	N	Y
N	N	N

但还有另一种看待这个问题的方法，那就是，在上面示例 3的解决方案中，我们对每个元素问了三个问题：你在 A 中吗？你在 B 中吗？和你在 C 中吗？现在，对每个问题显然有两个可能的答案：是和否。当我们将这些问题的答案组合在一起时，一个接一个，那么总共有 2³ = 8 种可能的答案集。这八种可能的答案组合中的每一种都对应于维恩图上的一个不同区域。

完整的答案集非常类似于一个真值表 - 这是逻辑中的一个重要概念，它处理可能为真或假的语句。右侧的表格显示了 3 个集合A、B和C的八种可能的答案组合。

你会发现研究每列中 Y 和 N 的模式会很有帮助。

当你向下阅读C列时，字母在每一行都会改变：Y、N、Y、N、Y、N、Y、N

向下阅读B列时，字母在每隔一行都会改变：Y、Y、N、N、Y、Y、N、N

向下阅读A列时，字母每四行都会改变：Y、Y、Y、Y、N、N、N、N

集合论练习 2

点击链接查看集合论练习 2

集合运算

正如我们可以用“加”、“减”、“乘”和“除”等运算将两个数字组合成第三个数字一样，我们也可以用多种方法将两个集合组合成第三个集合。我们将再次从维恩图开始，维恩图展示了两个集合 *A* 和 *B* 的一般位置，我们对它们之间可能的关系没有任何信息。

在A中吗？	在B中吗？	区域
Y	Y	iii
Y	N	ii
N	Y	iv
N	N	i

右侧表格中的前两列显示了对两个集合 *A* 和 *B* 的问题“你在 *A* 中吗？”和“你在 *B* 中吗？”的四种可能的答案集合；第三列中的罗马数字显示了 *图 7* 中维恩图中对应的区域。

交集

两个循环重叠的区域 *iii*（对应于“是”后跟“是”的区域）称为集合 *A* 和 *B* 的 *交集*。它用 *A* ∩ *B* 表示。所以我们可以将交集定义如下

两个集合 *A* 和 *B* 的 *交集*，写成 *A* ∩ *B*，是属于 *A* **且** 属于 *B* 的元素的集合。

（请注意，在符号逻辑中，一个类似的符号， $\scriptstyle \wedge$ ，用于用 **AND** 运算符连接两个逻辑命题。）

例如，如果 *A* = {1, 2, 3, 4} 且 *B* = {2, 4, 6, 8}，则 *A* ∩ *B* = {2, 4}。

那么，我们可以说，我们已经使用 *交集运算* 将两个集合组合成第三个集合。

并集

以类似的方式，我们可以将两个集合的 *并集* 定义如下

两个集合 *A* 和 *B* 的 *并集*，写成 *A* ∪ *B*，是属于 *A* **或** 属于 *B*（或两者都属于）的元素的集合。

然后，并集由 *图 7* 中的区域 *ii*、*iii* 和 *iv* 表示。

（再次，在逻辑中，一个类似的符号， $\scriptstyle \vee$ ，用于用 **OR** 运算符连接两个命题。）

因此，例如，{1, 2, 3, 4} ∪ {2, 4, 6, 8} = {1, 2, 3, 4, 6, 8}。

然后你会看到，为了进入交集，一个元素必须对 *两个* 问题都回答“是”，而为了进入并集，*任何一个* 答案都可以是“是”。

∪ 符号看起来像“并集”的首字母，也像一个可以容纳很多物品的杯子。 ∩ 符号看起来像一个洒了的东西的杯子，不能容纳很多物品，或者可能是“n”，代表“交集”。注意不要混淆这两个符号。

差集

两个集合 *A* 和 *B* 的 *差集*（也称为 *A* 和 *B* 的 *集合论差集*，或 *B* 在 *A* 中的 *相对补集*）是 **属于** *A* **但不属于** *B* 的元素的集合。

这写成 *A* - *B*，或者有时写成 *A* \ *B*。

然后，差集中的元素是那些对第一个问题“你在 *A* 中吗？”回答“是”，但对第二个问题“你在 *B* 中吗？”回答“否”的元素。这种答案组合位于上述表格的第 2 行，对应于 *图 7* 中的区域 *ii*。

例如，如果 *A* = {1, 2, 3, 4} 且 *B* = {2, 4, 6, 8}，则 *A* - *B* = {1, 3}。

补集

到目前为止，我们已经考虑了 *两个* 集合组合成第三个集合的运算：*二元* 运算。现在我们来看一个 *一元* 运算，它只涉及 *一个* 集合。

**不** 属于集合 *A* 的元素的集合称为 *A* 的 *补集*。它写成 *A*′（或者有时写成 *A*^C，或 ${\bar {A}}$ ）。

显然，这是对问题“你在 *A* 中吗？”回答“否”的元素的集合。

例如，如果 **U** = **N** 且 *A* = {奇数}，则 *A*′ = {偶数}。

请注意 *补集* 这个词的拼写：它的字面意思是“互补的项目或物品”；换句话说，“完成”的东西。所以，如果我们已经有了 *A* 的元素，*A* 的补集就是 *完成* 全集的集合。

集合运算的性质

1. 交换律

$A\cup B=B\cup A$

$A\cap B=B\cap A$

2. 结合律

$A\cup (B\cup C)=(A\cup B)\cup C$

$A\cap (B\cap C)=(A\cap B)\cap C$

3. 分配律

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

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

4. 补集的特殊性质

$(A')'=A$

$U'=\phi$

$\phi '=U$

$A\cap B'=A-B$

5. 德·摩根定律

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

$(A\cup B)'=A'\cap B'$ .

总结

交集：属于A和属于B的元素	并集：属于A或属于B（或两者都属于）的元素
差集：属于A而不属于B的元素	对称差集：属于A或属于B但不属于两者的元素
补集：不属于A的元素