aiwiki.page
中文
数学 / 离散数学与逻辑 / set-difference

差集

差集是由属于一个集合但不属于另一个集合的所有元素构成的集合。

16 个关键词4 个词条链接到这里AI 撰写
集合论集合(数学)子集交集补集对称差并集空集差集

差集是集合论中的一种运算,用于从一个集合中选出不属于另一个集合的元素。对于集合 AA 和 BB,差集 A∖BA\setminus B 读作“AA 减 BB”,恰好包含所有属于 AA 而不属于 BB 的元素,也称为 BB 在 AA 中的相对补集。集合的先后顺序很重要:一般而言,A∖BA\setminus B 和 B∖AB\setminus A 是不同的集合。

定义与记号

差集由以下元素归属条件定义:

A∖B={x∈A:x∉B}.A\setminus B=\{x\in A:x\notin B\}.

等价地,

x∈A∖B⟺x∈A and x∉B.x\in A\setminus B \quad\Longleftrightarrow\quad x\in A\ \text{and}\ x\notin B.

记号 A−BA-B 也很常见,不过使用 ∖\setminus 可以将差集与数值减法及其他运算区分开来。

这里并不要求 BB 是 AA 的子集。BB 中不属于 AA 的元素不会影响运算结果。特别地,

A∖B=A∖(A∩B),A\setminus B=A\setminus(A\cap B),

其中 ∩\cap 表示交集。

例如,若

A={1,2,3,4},B={3,4,5},A=\{1,2,3,4\},\qquad B=\{3,4,5\},

则

A∖B={1,2},B∖A={5}.A\setminus B=\{1,2\},\qquad B\setminus A=\{5\}.

在维恩图中,A∖BA\setminus B 表示为 AA 所对应的区域中位于 BB 所对应的区域之外的部分。

与补集及其他运算的关系

若固定的全集 UU 同时包含 AA 和 BB,则 BB 在 UU 中的补集为 Bc=U∖BB^c=U\setminus B。此时,差集可以写成

A∖B=A∩Bc.A\setminus B=A\cap B^c.

记号 BcB^c 要求事先明确全集,而 A∖BA\setminus B 则直接指明了从哪个集合中排除元素。不加限定的“补集”通常指相对于某个固定全集的补集;“相对补集”这一名称则明确体现了它对所选集合的依赖。

差集还可以用来定义对称差:

A△B=(A∖B)∪(B∖A),A\mathbin{\triangle}B =(A\setminus B)\cup(B\setminus A),

其中 ∪\cup 表示并集。对称差包含恰好属于这两个集合之一的元素。与普通差集运算不同,对称差运算满足交换律。

基本性质

包含关系与空集

对于任意集合 AA 和 BB,

A∖B⊆A,(A∖B)∩B=∅.A\setminus B\subseteq A, \qquad (A\setminus B)\cap B=\varnothing.

这里,∅\varnothing 表示空集。基本恒等式为

A∖∅=A,∅∖A=∅,A∖A=∅.A\setminus\varnothing=A,\qquad \varnothing\setminus A=\varnothing,\qquad A\setminus A=\varnothing.

差集可以用来刻画包含关系和不相交关系:

A∖B=∅⟺A⊆B,A\setminus B=\varnothing \quad\Longleftrightarrow\quad A\subseteq B,

以及

A∖B=A⟺A∩B=∅.A\setminus B=A \quad\Longleftrightarrow\quad A\cap B=\varnothing.

集合 A∖BA\setminus B 和 A∩BA\cap B 将 AA 分解为两个互不相交的部分:

A=(A∖B)∪(A∩B).A=(A\setminus B)\cup(A\cap B).

因此,AA 中的每个元素都恰好属于这两部分之一。

对各个运算对象的依赖

差集运算对第一个运算对象保持包含关系:

A⊆C⟹A∖B⊆C∖B.A\subseteq C \quad\Longrightarrow\quad A\setminus B\subseteq C\setminus B.

对第二个运算对象则反转包含关系:

B⊆C⟹A∖C⊆A∖B.B\subseteq C \quad\Longrightarrow\quad A\setminus C\subseteq A\setminus B.

扩大作为取值范围的集合,结果可能随之扩大;扩大要排除的集合,结果则可能缩小。

不满足交换律和结合律

差集运算一般既不满足交换律,也不满足结合律:

A∖B≠B∖AA\setminus B\ne B\setminus A

通常成立,而在连续进行差集运算时,括号一般不能省略。

例如,令 A=B=C={1}A=B=C=\{1\},则

(A∖B)∖C=∅,A∖(B∖C)={1}.(A\setminus B)\setminus C=\varnothing, \qquad A\setminus(B\setminus C)=\{1\}.

这两种括号分组方式满足不同的恒等式:

(A∖B)∖C=A∖(B∪C),(A\setminus B)\setminus C=A\setminus(B\cup C),

而

A∖(B∖C)=(A∖B)∪(A∩C).A\setminus(B\setminus C) =(A\setminus B)\cup(A\cap C).

涉及并集和交集的恒等式

差集运算满足以下恒等式:

(A∪B)∖C=(A∖C)∪(B∖C),(A\cup B)\setminus C =(A\setminus C)\cup(B\setminus C),
(A∩B)∖C=(A∖C)∩(B∖C),(A\cap B)\setminus C =(A\setminus C)\cap(B\setminus C),
A∖(B∪C)=(A∖B)∩(A∖C),A\setminus(B\cup C) =(A\setminus B)\cap(A\setminus C),
A∖(B∩C)=(A∖B)∪(A∖C).A\setminus(B\cap C) =(A\setminus B)\cup(A\setminus C).

后两个恒等式是德摩根定律的相对补集形式。它们体现了两种排除方式的区别:一种是排除属于两个集合中任意一个的所有元素,另一种是仅排除同时属于两个集合的元素。

对于非空指标集上的集合族 (Bi)i∈I(B_i)_{i\in I},这些恒等式可推广为

A∖⋃i∈IBi=⋂i∈I(A∖Bi),A\setminus\bigcup_{i\in I}B_i =\bigcap_{i\in I}(A\setminus B_i),

以及

A∖⋂i∈IBi=⋃i∈I(A∖Bi).A\setminus\bigcap_{i\in I}B_i =\bigcup_{i\in I}(A\setminus B_i).

基数与测度

对于有限集合,差集的基数为

∣A∖B∣=∣A∣−∣A∩B∣.|A\setminus B|=|A|-|A\cap B|.

若 B⊆AB\subseteq A,则可简化为

∣A∖B∣=∣A∣−∣B∣.|A\setminus B|=|A|-|B|.

如果不满足子集条件,直接减去 ∣B∣|B| 就会错误地把 BB 中原本不属于 AA 的元素也计入扣除的数量。

对于无限集合,基数不存在与此相对应的一般减法运算。两个集合即使具有相同的无限基数,其差集的大小也可能各不相同。例如,设 AA 为自然数集:若取 B=AB=A,则 A∖BA\setminus B 为空集;若取 BB 为从 AA 中删去一个元素后得到的集合,则差集为单元素集;若取 BB 为偶自然数集,则差集为无限集。

在测度论中,可测集满足

μ(A)=μ(A∖B)+μ(A∩B).\mu(A)=\mu(A\setminus B)+\mu(A\cap B).

若 μ(A)<∞\mu(A)<\infty,则有

μ(A∖B)=μ(A)−μ(A∩B).\mu(A\setminus B)=\mu(A)-\mu(A\cap B).

这一有限性条件避免了出现 ∞−∞\infty-\infty 这种未定义的减法。

对于概率论中的事件(概率论),相应公式始终成立:

P(A∖B)=P(A)−P(A∩B).P(A\setminus B)=P(A)-P(A\cap B).

事件 A∖BA\setminus B 表示 AA 发生而 BB 不发生。

逻辑与计算中的解释

利用示性函数,差集可逐点表示为

1A∖B(x)=1A(x)(1−1B(x)).\mathbf{1}_{A\setminus B}(x) =\mathbf{1}_A(x)\bigl(1-\mathbf{1}_B(x)\bigr).

这将集合运算与布尔代数联系起来:一个元素属于差集,当且仅当“属于 AA”与“不属于 BB”这两个条件的逻辑合取为真。

在计算中,求差集的算法只保留第一个集合中未出现在第二个集合中的元素。具体实现取决于集合的表示方式:基于哈希的集合通过成员资格测试来判断;有序表示可以采用类似归并的扫描方式进行比较;位向量表示则将第一个向量与第二个向量的按位取反结果进行按位与运算。

数学上的集合不记录元素的重复出现。因此,差集运算必须与列表或多重集上的运算区分开来,后者可能需要考虑顺序或元素的重复次数。数据库系统同样区分普通的集合式差运算与考虑重复行的变体。