离散数学 | 4 集合与集合运算

4.1 集合

集合（set）是若干对象（object）或元素（element）或成员（member）汇集在一起形成的整体。集合通常用大写字母表示，如A、B、C…元素通常用小写字母表示，如a、b、c…集合中某个元素被列出多次或元素之间调换顺序并不改变集合，体现了集合的互异性与无序性。

【补充】该定义对集合的表述是直观的，但后来导致了著名的罗素悖论（Russell's Paradox）。该悖论的核心问题是：设有一个集合A，它包含所有不包含自身的集合，那么A是否包含自身？显然，无论怎样回答均会导致逻辑矛盾。罗素悖论的发现对数学基础产生了深远影响，被认为是数学史上的第三次重大危机，促使数学家发展更严格的公理化集合论，如ZFC公理系统等。

必须存在一个底层全集U（universal set），它可以被明确声明，也可以是默认隐含的。全集是当前讨论范围内所有对象构成的集合，所有讨论的集合都是全集的子集。常用的全集有实数集R，自然数集N，整数集Z，正整数集Z+，有理数集Q，复数集C等。

集合有两种最基本的表示方法：

• 列举法（roster method）：将集合中所有的元素逐一写在大括号 {} 中（注：在列举无穷或数量较多但有规律的项时，使用 ... 来明确表示规律的延续）
• 描述法（set builder）：通过谓词来指定集合，S={x∣P(x)}，S 等于所有满足P(x) 的 x 构成的集合

【提醒】集合的元素可以是集合。例如对于集合 A={1,{1}} 有：1∈A，{1}∈A。

集合A与集合B相等（equal），当且仅当∀x(x∈A↔x∈B)，记作A=B。

集合A是集合B的子集（subset），即A包含于B或B包含A，当且仅当∀x(x∈A→x∈B)，记作A⊆B。集合A是集合B的非子集，当且仅当∃x(x∈A∧) ，记作。任何集合是自身的子集。

集合A是集合B的真子集（proper subset），即A真包含于B或B真包含A，则有A⊆B但，当且仅当∀x(x∈A→x∈B)∧∃x(x∈B∧)，记作A⊂B。

空集（void set / null set / empty set）是没有任何元素的集合，具有唯一性，记作 {} 或∅。空集是任何集合的子集。

【例】空集是任何集合的子集：

断言 "x∈∅ " 总是假的，因此∀x[x∈∅→x∈A] 总是真的，所以 ∅⊆A ，即空集是任何集合的子集。

集合A的所有子集构成的集合即为A的幂集（power set），记作P(A)，则有P(A)={x∣x⊆A}。

【提醒】某个集合既可以作为其他集合的元素，也可以作为其他集合的子集。例如对于集合A={∅,{∅}}有：∅∈A，∅⊆A，{∅}∈A，{∅}⊆A，{{∅}}⊆A。

集合A中不同元素的个数即为A的基数（cardinality），记作∣A∣ 。如果集合的基数为自然数，则该集合为有限集（finite）；否则该集合为无限集（infinite）。

【结论】如果∣A∣=n，那么。

从组合数学角度解释，若A有n个元素，当构造A的子集时，对于A中的每个元素都有“选”或“不选”两种选择。依据乘法原理，共有种不同的选择方式，每种选择方式对应唯一的子集。

【辨析】对于 n∈N ，一个有序 n 元组（ordered n-tuples）或序列（sequence）或长度为 n 的列表（list of length n）记作。它的第一个元素是​，以此类推。相较于集合，有序n元组中某个元素重复出现或元素之间调换顺序会改变该有序n元组。

给定一个谓词P与一个论域D，P(x) 的真值集（truth sets of predicates）记作 {x∈D∣P(x)}。真值集本质是满足谓词与论域条件的元素的集合。

集合表示与量词结合的简写方式：

• ∀x(x∈S→P(x))可简写为∀x∈S(P(x))
• ∃x(x∈S∧P(x)) 可简写为∃x∈S(P(x))

4.2 集合运算

集合论（set theory）中的运算子是依据命题演算（propositional calculus）中相应的运算子来定义的。

4.2.1 并集、交集、补集、差集、对称差

在全集U的基础上，定义如下：

• 集合A与集合B的并集（union），记作A∪B，是集合{x∣x∈A∨x∈B}
• 集合A与集合B的交集（intersection），记作A∩B，是集合{x∣x∈A∧x∈B}；如果交集是空集，则称A和B不相交（disjoint）
• 集合A的补集（complement），记作或，是集合{x∣¬(x∈A)}
• 集合A与集合B的差集（difference）或集合B相对于A的补集，记作 A−B，是集合{x∣x∈A∧}
• 集合A与集合B的对称差（symmetric difference），记作 A⊕B，是集合 (A−B)∪(B−A)={x∣(x∈A∧)∨(x∈B∧)}

这五种运算与逻辑等价式的联系：

4.2.2 广义并集与广义交集

由于并集与交集满足交换律与结合律，可将它们从作用于集合的有序对（A,B）推广到作用于集合的序列（A,B,C…），甚至作用于无序的集合族（sets of sets）X={A∣P(A)}。

【补充】集合族X={A∣P(A)}：X是集合的集合，即X中的每个元素A 均为集合集合，P(A) 是筛选出满足条件的集合的谓词。

广义并集与广义交集的表示：

• ：集合族X中所有集合的并
• ：集合族X中所有集合的交

4.2.3 加法原理

加法原理（the addition principle）或容斥原理（the inclusion-exclusion principle）：如果 A 和 B 是有限集，那么∣A∪B∣=∣A∣+∣B∣−∣A∩B∣。

推广到n个集合，如果为有限集，那么：

4.2.4 笛卡尔积

集合A与集合B的笛卡尔积（cartesian product），是所有有序对 <a,b> 构成的集合（其中 a∈A 且 b∈B，顺序固定），记作A×B，即A×B={<a,b>∣a∈A∧b∈B}。笛卡尔积本质是一个集合，其内部元素为有序对。任何集合与空集的笛卡尔积均为空集。

如果A={a,b}，B={x,y,z}，则A×B={<a,x>,<a,y>,<a,z>,<b,x>,<b,y>,<b,z>}。

【提醒】A×B与B×A一般不相等，除非A=B或A、B中某个集合为空集。

【结论】如果∣A∣=m且∣B∣=n，那么∣A×B∣=m×n=∣A∣×∣B∣。

从组合数学角度解释，A有m个元素，每个元素都可以作为有序对的第一个分量；对于 A 中的每个元素，B有n个元素可以作为第二个分量。依据乘法原理，共有m×n种组合方式，每种组合方式对应唯一的有序对。

集合的笛卡尔积为n元笛卡尔积（cartesian product of n sets），记作，是有序 n 元组构成的集合，其中，即。

【提醒】(A×B)×C与A×B×C一般不相等，前者的元素为<<a,b>,c>，后者的元素为<a,b,c>。

4.2.5 集合运算的代数性质

定律名称	公式表达式
交换律
结合律
分配律
吸收律
幂等律
零律
同一律
补律
排中律
矛盾律
余补律
德摩根律

【结论】证明集合恒等式A=B的三种方法：

• 双向包含法：分别证明A⊆B和B⊆A
• 逻辑等价变换法：用描述法表示集合A、B，将集合运算翻译为逻辑运算，使用命题逻辑的等价变换将A、B化简为相同的逻辑表达式
• 成员表法：使用类似于命题逻辑中的真值表证明

【例】用双向包含法证明(A∩B)∪(A∩C)=A∩(B∪C):

【例】用逻辑等价变化法证明

【例】用成员表法证明(A∪B)−C= (A−C)∪(B−C)：