6 年级

集合与集合运算

集合是若干对象组成的、边界明确的集体,其中每个对象称为元素; $x \in A$ 表示 $x$ 属于 $A$ 。当 $A$ 的每个元素都属于 $B$ 时,称为子集,记作 $A \subseteq B$ 。由两个集合可以构造新的集合:并集 $A \cup B$ (属于 $A$ 或 $B$ 的元素)、交集 $A \cap B$ (同时属于两者的元素)、差集 $A \setminus B$ (属于 $A$ 但不属于 $B$ 的元素)。这些运算满足类似代数的定律,例如分配律 $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ ,而并集元素个数的计算遵循容斥原理 $|A \cup B| = |A| + |B| - |A \cap B|$ ;本文将严格证明这两条定律,并用于问卷调查数据与搜索引擎过滤器的实际场景。

直观装物品的盒子：什么东西属于哪里

设想两个部分重叠的玩具箱:盒子 $A$ 装着积木,盒子 $B$ 装着小汽车。有些玩具是"汽车积木",同时出现在两个盒子里。问" $x \in A$ ?"就是问某个具体的玩具 $x$ 是否在盒子 $A$ 里。问" $A \subseteq B$ ?"就是问盒子 $A$ 里的每一件玩具是否都能在盒子 $B$ 的某处找到。把两个盒子合成一堆,得到并集 $A \cup B$ ;只留下两个盒子都有的玩具,得到交集 $A \cap B$ ;从盒子 $A$ 中拿走那些盒子 $B$ 里也有的玩具,得到差集 $A \setminus B$ 。下面的网络小工具可以让你在两个圆之间拖动元素,实时观察这四种运算的结果。

三个集合

A, B, C

的维恩图:展示并集、两两交集以及中央的三重交集

A\cap B\cap C

。

中学形式化定义与对照表

定义: 集合、元素、子集

集合 $A$ 是由互不相同的对象组成的集体;满足 $x \in A$ 的每个对象 $x$ 称为 $A$ 的元素。当 $A$ 的每个元素也是 $B$ 的元素时,称 $A$ 是 $B$ 的子集,记作 $A \subseteq B$ ;两个集合相等当且仅当 $A \subseteq B$ 且 $B \subseteq A$ 同时成立。

A \cup B = \{x : x \in A \lor x \in B\}

并集 $A \cup B = \{x : x \in A \lor x \in B\}$ 收集了所有至少属于两个集合之一的元素。相对地,交集只保留同时属于两个集合的元素。

A \cap B = \{x : x \in A \land x \in B\}

$A=\{1,2,3\}$ 与 $B=\{2,3,4\}$ 上的集合运算
运算	定义	结果
并集 $A \cup B$	$A \cup B = \{x : x \in A \lor x \in B\}$	$\{1,2,3,4\}$
交集 $A \cap B$	$A \cap B = \{x : x \in A \land x \in B\}$	$\{2,3\}$
差集 $A \setminus B$	$A \setminus B = \{x : x \in A \land x \notin B\}$	$\{1\}$
子集 $A \subseteq B$	$A$ 的每个元素都属于 $B$	假 ( $1 \notin B$ )

大学两条关键定理及完整证明

定理: 交集对并集的分配律

对任意三个集合 $A$ 、 $B$ 、 $C$ : $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ 。

为什么成立?

正如普通代数中乘法对加法满足分配律一样,集合代数中交集对并集也满足分配律。这使得像"属于类别 $A$ ,且(正在促销 $B$ 或新品 $C$ )"这样的过滤条件,可以改写成两个更易处理、再用并集合并的过滤条件,这正是数据库与搜索引擎的查询规划器化简布尔过滤条件的方式。

证明

我们通过证明双向包含关系来说明两个集合相等,方法是取任意元素 $x_0$ 进行"元素追踪"。

(正向, $\subseteq$ ) 设 $x_0 \in A \cap (B \cup C)$ 。由交集的定义,这意味着 $x_0 \in A$ 且 $x_0 \in B \cup C$ 。由并集的定义, $x_0 \in B \cup C$ 意味着 $x_0 \in B$ 或 $x_0 \in C$ 。分两种情形讨论。情形1: $x_0 \in B$ 。结合 $x_0 \in A$ ,得到 $x_0 \in A \cap B$ 。情形2: $x_0 \in C$ 。结合 $x_0 \in A$ ,得到 $x_0 \in A \cap C$ 。无论哪种情形, $x_0$ 都属于 $x_0 \in A \cap B$ 或属于 $x_0 \in A \cap C$ ,因此 $x_0 \in (A \cap B) \cup (A \cap C)$ 。

(反向, $\supseteq$ ) 设 $x_0 \in (A \cap B) \cup (A \cap C)$ 。由并集的定义,这意味着 $x_0 \in A \cap B$ 或 $x_0 \in A \cap C$ 。若 $x_0 \in A \cap B$ ,则 $x_0 \in A$ 且 $x_0 \in B$ ,从而 $x_0 \in B \cup C$ (因为 $x_0$ 属于 $B$ ,故属于 $B$ 或 $C$ ),于是 $x_0 \in A \cap (B \cup C)$ 。若 $x_0 \in A \cap C$ ,则 $x_0 \in A$ 且 $x_0 \in C$ ,从而 $x_0 \in B \cup C$ ,同样得到 $x_0 \in A \cap (B \cup C)$ 。

由于左边的每个元素都属于右边,反之亦然,两个集合含有完全相同的元素,故 $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ 成立,证明完毕。

定理: 两个集合的容斥原理

对任意两个有限集合 $A$ 与 $B$ : $|A \cup B| = |A| + |B| - |A \cap B|$ ,其中 $|A|$ 、 $|B|$ 、 $|A \cap B|$ 、 $|A \cup B|$ 分别表示各集合的元素个数。

为什么成立?

简单地把 $|A|$ 与 $|B|$ 相加,会把同时属于两个集合的元素重复计算一次,因此再减去 $|A \cap B|$ 一次就纠正了这次重复计算。这正是从问卷调查数据中读取双圆维恩图背后的算术:在询问至少喜欢咖啡或茶其中一种的人数时,同时喜欢两者的人不能被重复计算。

证明

关键思路是把 $A \cup B$ 拆成三个两两不相交的部分,再各计数一次。

首先,用另一个集合来划分每个集合: $A = (A \setminus B) \cup (A \cap B)$ 与 $B = (B \setminus A) \cup (A \cap B)$ 。在这两个等式中,右边的两部分互不相交,因为 $(A\setminus B) \cap (A \cap B) = \varnothing$ (不在 $B$ 中的元素不可能同时在 $B$ 中),同理 $(B\setminus A) \cap (A \cap B) = \varnothing$ 。由于有限集合的大小等于其两两不相交划分各部分大小之和,由此得到 $|A| = |A \setminus B| + |A \cap B|$ 与 $|B| = |B \setminus A| + |A \cap B|$ 。

接下来注意到 $A \cup B$ 本身可以拆成三个两两不相交的部分: $A \cup B = (A \setminus B) \cup (B \setminus A) \cup (A \cap B)$ 。事实上 $A\setminus B$ 、 $B\setminus A$ 、 $A\cap B$ 两两不相交(属于 $A\setminus B$ 的元素不属于 $B$ ,因而也不属于 $A \cap B$ 或 $B \setminus A$ ;其余情形同理),且它们的并集恰好就是属于 $A$ 或属于 $B$ 的全部元素。按此划分计数即得 $|A \cup B| = |A \setminus B| + |B \setminus A| + |A \cap B|$ 。

最后代入:由 $|A| = |A \setminus B| + |A \cap B|$ 得 $|A \setminus B|$ $= |A| - |A\cap B|$ ,由 $|B| = |B \setminus A| + |A \cap B|$ 得 $|B \setminus A|$ $= |B| - |A\cap B|$ 。将两者代入 $|A \cup B| = |A \setminus B| + |B \setminus A| + |A \cap B|$ 得 $|A \cup B| = (|A| - |A\cap B|) + (|B| - |A\cap B|) + |A\cap B| = |A| + |B| - |A\cap B|$ ,这正是 $|A \cup B| = |A| + |B| - |A \cap B|$ 。证明完毕。

大学实际应用与典型例题

集合运算是两种日常工具的支柱。在问卷调查分析中,喜欢产品 $A$ 与产品 $B$ 的受访者的双圆维恩图要用 $|A \cup B| = |A| + |B| - |A \cap B|$ 来解读:总关注人数并非简单相加,因为属于 $A \cap B$ 的人会被重复计算。在搜索引擎与电商过滤器中,组合"类别 $A$ "与"正在促销 $B$ "(用 AND)正是交集 $A \cap B$ ,用 OR 组合正是并集 $A \cup B$ ,用 NOT 排除某标签正是差集 $A \setminus B$ ;分配律 $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ 正是查询规划器能把" $A$ 且( $B$ 或 $C$ )"改写成"( $A$ 且 $B$ )或( $A$ 且 $C$ )"而不改变结果的原因。

例题: 用容斥原理解读问卷调查

某学校对 $120$ 名学生进行问卷调查。 $70$ 人说会踢足球, $45$ 人说会打篮球, $25$ 人说两项都会。请问至少会一项运动的学生有多少人?两项都不会的学生有多少人?

解答

设 $A$ 为踢足球的学生集合, $B$ 为打篮球的学生集合,则 $|A| = 70$ , $|B| = 45$ , $|A \cap B| = 25$ 。

由上面证明的容斥定理, $|A \cup B| = |A| + |B| - |A \cap B|$ 。代入数值: $|A \cup B| = 70 + 45 - 25 = 90$ 。所以至少会一项运动的学生有 $90$ 人。

由于调查总数为 $120$ ,两项都不会的学生数就是 $A \cup B$ 在全体 $120$ 名学生中的补集: $120 - 90 = 30$ 。

注意常见错误是直接相加 $70+45=115$ :这会把两项都会的 $25$ 人重复计算,这正是定理要减去一次 $|A \cap B|$ 的原因。

例题: 用分配律化简搜索过滤器

某在线商店的商品目录是一个产品集合 $U$ 。设 $A$ 为"属于鞋类类别", $B$ 为"正在促销", $C$ 为"新品上架"。顾客的过滤条件是"属于鞋类,且(正在促销或新品上架)",即 $A \cap (B \cup C)$ 。请说明这与分别运行两个更简单的过滤器再合并结果得到的产品列表相同,并解释为什么搜索引擎更偏好后一种形式。

解答

由上面证明的分配律, $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ 。这里取 $A=$ 鞋类、 $B=$ 促销、 $C=$ 新品,应用得到: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ 。

左边 $A \cap (B \cup C)$ 描述一个合并后的单一过滤器:先构造由所有促销或新品组成的集合 $B \cup C$ ,再与鞋类求交。右边描述两个独立的简单过滤器,"促销鞋类"( $A\cap B$ )与"新品鞋类"( $A \cap C$ ),再用并集合并结果。

由于定理保证两边列出的产品完全相同,查询规划器可以自由选择更快的执行方式。运行两个简单的单条件过滤器(各自可使用针对某一类别预先建好的快速索引)再用并集合并,通常比直接求值"与中嵌或"的表达式更便宜,因此实际的搜索引擎会在执行前把查询改写成右边的形式。

具体来说,若鞋类 $=\{1,2,3,4,5\}$ 、促销 $=\{2,4,6\}$ 、新品 $=\{1,4,7\}$ ,则 $B\cup C=\{1,2,4,6,7\}$ 且 $A\cap(B\cup C)=\{1,2,4\}$ ;分别地 $A\cap B=\{2,4\}$ 、 $A\cap C=\{1,4\}$ ,其并集同样是 $\{1,2,4\}$ ,确认两种算法结果一致。

设 $A=\{2,4,6,8\}$ 。下列哪个说法正确?

某班有 $30$ 名学生; $18$ 人喜欢数学, $15$ 人喜欢物理, $9$ 人两者都喜欢。至少喜欢其中一门的学生有多少人?

某购物网站可以按"品牌 $A$ " OR "低于50美元( $B$ )"过滤。计算显示结果的是哪种集合运算?

设 $A=\{1,2,3\}$ 、 $B=\{2,3\}$ 、 $C=\{3,4\}$ ,等式 $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ 是否成立,公共值是多少?

参考文献

Paul R. Halmos (1960). Naive Set Theory
Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications