离散数学 - 集合

上一页
下一页

德国数学家G. 康托尔引入了集合的概念。他将集合定义为根据某些规则或描述选择的明确且可区分对象的集合。

集合理论构成了其他几个研究领域的基础，例如计数理论、关系、图论和有限状态机。在本章中，我们将介绍集合论的不同方面。

集合 - 定义

集合是不同元素的无序集合。可以使用集合括号列出其元素来显式地写出集合。如果元素的顺序改变或集合的任何元素重复，则不会对集合产生任何变化。

集合的一些例子

  • 所有正整数的集合
  • 太阳系中所有行星的集合
  • 印度所有邦的集合
  • 所有小写字母的集合

集合的表示

集合可以用两种方式表示：

  • 列举法或表格法
  • 集合构造器表示法

列举法或表格法

集合通过列出构成它的所有元素来表示。元素用大括号括起来，并用逗号分隔。

例1 - 英文字母表中的元音集合，$A = \lbrace a,e,i,o,u \rbrace$

例2 - 小于10的奇数集合，$B = \lbrace 1,3,5,7,9 \rbrace$

集合构造器表示法

集合通过指定集合元素共有的属性来定义。集合描述为$A = \lbrace x : p(x) \rbrace$

例1 - 集合$\lbrace a,e,i,o,u \rbrace$ 写作：

$A = \lbrace x : \text{x是英文字母表中的元音} \rbrace$

例2 - 集合$\lbrace 1,3,5,7,9 \rbrace$ 写作：

$B = \lbrace x : 1 \le x \lt 10 \ and\ (x \% 2) \ne 0 \rbrace$

如果元素x是集合S的成员，则表示为$x \in S$；如果元素y不是集合S的成员，则表示为$y \notin S$。

例 - 如果 $S = \lbrace1, 1.2, 1.7, 2\rbrace , 1 \in S$ 但 $1.5 \notin S$

一些重要的集合

N - 所有自然数的集合 = $\lbrace1, 2, 3, 4, .....\rbrace$

Z - 所有整数的集合 = $\lbrace....., -3, -2, -1, 0, 1, 2, 3, .....\rbrace$

Z+ - 所有正整数的集合

Q - 所有有理数的集合

R - 所有实数的集合

W - 所有整数的集合

集合的基数

集合S的基数，记为$|S|$，是集合的元素个数。这个数也称为基数。如果一个集合有无限多个元素，则它的基数是$\infty$。

例 - $|\lbrace 1, 4, 3, 5 \rbrace | = 4, | \lbrace 1, 2, 3, 4, 5, \dots \rbrace | = \infty$

如果有两个集合X和Y，

  • $|X| = |Y|$ 表示两个集合X和Y具有相同的基数。当X中的元素个数恰好等于Y中的元素个数时，就会发生这种情况。在这种情况下，存在一个从X到Y的双射函数“f”。

  • $|X| \le |Y|$ 表示集合X的基数小于或等于集合Y的基数。当X中的元素个数小于或等于Y中的元素个数时，就会发生这种情况。这里，存在一个从X到Y的单射函数“f”。

  • $|X| \lt |Y|$ 表示集合X的基数小于集合Y的基数。当X中的元素个数小于Y中的元素个数时，就会发生这种情况。这里，从X到Y的函数“f”是单射函数，但不是双射函数。

  • $如果\ |X| \le |Y| 且 |X| \ge |Y|，则 |X| = |Y|。集合X和Y通常被称为等价集合。

集合的类型

集合可以分为许多类型。其中一些是有限的、无限的、子集、全集、真子集、单元素集等等。

有限集

包含一定数量元素的集合称为有限集。

例 - $S = \lbrace x \:| \:x \in N$ 且 $70 \gt x \gt 50 \rbrace$

无限集

包含无限多个元素的集合称为无限集。

例 - $S = \lbrace x \: | \: x \in N $ 且 $ x \gt 10 \rbrace$

子集

如果集合X的每个元素都是集合Y的元素，则集合X是集合Y的子集（写成$X \subseteq Y$）。

例1 - 令，$X = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ 且 $Y = \lbrace 1, 2 \rbrace$。这里集合Y是集合X的子集，因为集合Y的所有元素都在集合X中。因此，我们可以写成$Y \subseteq X$。

例2 - 令，$X = \lbrace 1, 2, 3 \rbrace$ 且 $Y = \lbrace 1, 2, 3 \rbrace$。这里集合Y是集合X的子集（不是真子集），因为集合Y的所有元素都在集合X中。因此，我们可以写成$Y \subseteq X$。

真子集

“真子集”可以定义为“子集但不等于”。如果集合X的每个元素都是集合Y的元素，且$|X| \lt |Y|$，则集合X是集合Y的真子集（写成$ X \subset Y $）。

例 - 令，$X = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ 且 $Y = \lbrace 1, 2 \rbrace$。这里集合$Y \subset X$，因为Y中的所有元素也包含在X中，并且X至少比集合Y多一个元素。

全集

它是特定上下文或应用中所有元素的集合。该上下文或应用中的所有集合本质上都是这个全集的子集。全集表示为$U$。

例 - 我们可以将$U$定义为地球上所有动物的集合。在这种情况下，所有哺乳动物的集合是$U$的子集，所有鱼类的集合是$U$的子集，所有昆虫的集合是$U$的子集，等等。

空集或空集

空集不包含任何元素。它表示为$\emptyset$。由于空集中的元素数量是有限的，因此空集是有限集。空集或空集的基数为零。

例 - $S = \lbrace x \:| \: x \in N$ 且 $7 \lt x \lt 8 \rbrace = \emptyset$

单元素集或单元集

单元素集或单元集只包含一个元素。单元素集表示为$\lbrace s \rbrace$。

例 - $S = \lbrace x \:| \:x \in N,\ 7 \lt x \lt 9 \rbrace$ = $\lbrace 8 \rbrace$

相等集

如果两个集合包含相同的元素，则称它们相等。

例 - 如果$A = \lbrace 1, 2, 6 \rbrace$ 且 $B = \lbrace 6, 1, 2 \rbrace$，则它们相等，因为集合A的每个元素都是集合B的元素，集合B的每个元素都是集合A的元素。

等价集

如果两个集合的基数相同，则它们称为等价集合。

例 - 如果$A = \lbrace 1, 2, 6 \rbrace$ 且 $B = \lbrace 16, 17, 22 \rbrace$，则它们是等价的，因为A的基数等于B的基数。即$|A| = |B| = 3$

重叠集

至少有一个公共元素的两个集合称为重叠集。

对于重叠集：

  • $n(A \cup B) = n(A) + n(B) - n(A \cap B)$

  • $n(A \cup B) = n(A - B) + n(B - A) + n(A \cap B)$

  • $n(A) = n(A - B) + n(A \cap B)$

  • $n(B) = n(B - A) + n(A \cap B)$

例 - 令，$A = \lbrace 1, 2, 6 \rbrace$ 且 $B = \lbrace 6, 12, 42 \rbrace$。有一个公共元素“6”，因此这些集合是重叠集。

不相交集

如果两个集合A和B没有任何公共元素，则它们称为不相交集。因此，不相交集具有以下性质：

  • $n(A \cap B) = \emptyset$

  • $n(A \cup B) = n(A) + n(B)$

例 - 令，$A = \lbrace 1, 2, 6 \rbrace$ 且 $B = \lbrace 7, 9, 14 \rbrace$，没有一个公共元素，因此这些集合是重叠集。（此处原文有误，应为不相交集）

文氏图

文氏图由约翰·文恩于1880年发明，是一种示意图，显示不同数学集合之间所有可能的逻辑关系。

例子

Venn Diagram

集合运算

集合运算包括集合并、集合交、集合差、集合补和笛卡尔积。

集合并

集合A和B的并集（记作$A \cup B$）是属于A、属于B或同时属于A和B的元素的集合。因此，$A \cup B = \lbrace x \:| \: x \in A\ OR\ x \in B \rbrace$。

例 - 如果$A = \lbrace 10, 11, 12, 13 \rbrace$ 且 B = $\lbrace 13, 14, 15 \rbrace$，则$A \cup B = \lbrace 10, 11, 12, 13, 14, 15 \rbrace$。（公共元素只出现一次）

Set Union

集合交

集合A和B的交集（记作$A \cap B$）是同时属于A和B的元素的集合。因此，$A \cap B = \lbrace x \:|\: x \in A\ AND\ x \in B \rbrace$。

例 - 如果$A = \lbrace 11, 12, 13 \rbrace$ 且 $B = \lbrace 13, 14, 15 \rbrace$，则$A \cap B = \lbrace 13 \rbrace$。

Set Intersection

集合差/相对补集

集合A和B的集合差（记作$A – B$）是只属于A而不属于B的元素的集合。因此，$A - B = \lbrace x \:| \: x \in A\ AND\ x \notin B \rbrace$。

例 - 如果$A = \lbrace 10, 11, 12, 13 \rbrace$ 且 $B = \lbrace 13, 14, 15 \rbrace$，则$(A - B) = \lbrace 10, 11, 12 \rbrace$ 且 $(B - A) = \lbrace 14, 15 \rbrace$。这里，我们可以看到$(A - B) \ne (B - A)$

Set Difference

集合的补集

集合A的补集（记作$A’$）是不属于集合A的元素的集合。因此，$A' = \lbrace x | x \notin A \rbrace$。

更具体地说，$A'= (U - A)$，其中$U$是包含所有对象的全集。

例 - 如果$A = \lbrace x \:| \: x\ \: {属于奇数集合} \rbrace$，则$A' = \lbrace y\: | \: y\ \: {不属于奇数集合} \rbrace$

Complement Set

笛卡尔积/叉积

n个集合$A_1, A_2, \dots A_n$的笛卡尔积记作$A_1 \times A_2 \dots \times A_n$，可以定义为所有可能的序对$(x_1, x_2, \dots x_n)$，其中$x_1 \in A_1, x_2 \in A_2, \dots x_n \in A_n$

例 - 如果我们取两个集合$A = \lbrace a, b \rbrace$ 且 $B = \lbrace 1, 2 \rbrace$，

集合 A 和 B 的笛卡尔积记作 − $A \times B = \lbrace (a, 1), (a, 2), (b, 1), (b, 2)\rbrace$

集合 B 和 A 的笛卡尔积记作 − $B \times A = \lbrace (1, a), (1, b), (2, a), (2, b)\rbrace$

幂集

集合 S 的幂集是 S 的所有子集（包括空集）的集合。集合 S 的基数为 n，则其幂集的基数为 $2^n$。幂集记作 $P(S)$。

示例 −

对于集合 $S = \lbrace a, b, c, d \rbrace$，让我们计算其子集 −

  • 包含 0 个元素的子集 − $\lbrace \emptyset \rbrace$（空集）

  • 包含 1 个元素的子集 − $\lbrace a \rbrace, \lbrace b \rbrace, \lbrace c \rbrace, \lbrace d \rbrace$

  • 包含 2 个元素的子集 − $\lbrace a, b \rbrace, \lbrace a,c \rbrace, \lbrace a, d \rbrace, \lbrace b, c \rbrace, \lbrace b,d \rbrace,\lbrace c,d \rbrace$

  • 包含 3 个元素的子集 − $\lbrace a ,b, c\rbrace,\lbrace a, b, d \rbrace, \lbrace a,c,d \rbrace,\lbrace b,c,d \rbrace$

  • 包含 4 个元素的子集 − $\lbrace a, b, c, d \rbrace$

因此，$P(S)=$

$\lbrace \quad \lbrace \emptyset \rbrace, \lbrace a \rbrace, \lbrace b \rbrace, \lbrace c \rbrace, \lbrace d \rbrace, \lbrace a,b \rbrace, \lbrace a,c \rbrace, \lbrace a,d \rbrace, \lbrace b,c \rbrace, \lbrace b,d \rbrace, \lbrace c,d \rbrace, \lbrace a,b,c \rbrace, \lbrace a,b,d \rbrace, \lbrace a,c,d \rbrace, \lbrace b,c,d \rbrace, \lbrace a,b,c,d \rbrace \quad \rbrace$

$| P(S) | = 2^4 = 16$

注意 − 空集的幂集也是空集。

$| P (\lbrace \emptyset \rbrace) | = 2^0 = 1$

集合的划分

集合 S 的划分是由 n 个不相交子集 $P_1, P_2, \dots P_n$ 组成的集合，满足以下三个条件 −

  • $P_i$ 不包含空集。

    $\lbrack P_i \ne \lbrace \emptyset \rbrace\ \forall\ 0 \lt i \le n \rbrack$

  • 这些子集的并集必须等于整个原集合。

    $\lbrack P_1 \cup P_2 \cup \dots \cup P_n = S \rbrack$

  • 任意两个不同子集的交集为空集。

    $\lbrack P_a \cap P_b = \lbrace \emptyset \rbrace,\ \forall\ a \ne b\ 且\ n \ge a,\: b \ge 0 \rbrack$

示例

设 $S = \lbrace a, b, c, d, e, f, g, h \rbrace$

一种可能的划分是 $\lbrace a \rbrace, \lbrace b, c, d \rbrace, \lbrace e, f, g, h \rbrace$

另一种可能的划分是 $\lbrace a, b \rbrace, \lbrace c, d \rbrace, \lbrace e, f, g, h \rbrace$

贝尔数

贝尔数给出了划分集合的方法数。它们用 $B_n$ 表示，其中 n 是集合的基数。

示例 −

设 $S = \lbrace 1, 2, 3\rbrace$，$n = |S| = 3$

不同的划分有 −

1. $\emptyset , \lbrace 1, 2, 3 \rbrace$

2. $\lbrace 1 \rbrace , \lbrace 2, 3 \rbrace$

3. $\lbrace 1, 2 \rbrace , \lbrace 3 \rbrace$

4. $\lbrace 1, 3 \rbrace , \lbrace 2 \rbrace$

5. $\lbrace 1 \rbrace , \lbrace 2 \rbrace , \lbrace 3 \rbrace$

因此 $B_3 = 5$

打印页面
上一页
下一页
广告