2.1 集合与运算：用成员关系描述对象范围

一个访问控制策略里有三份名单：项目成员、被冻结用户、临时审计员。需求是“允许未被冻结的项目成员，以及值班审计员读取日志”。若名单的范围和运算没有写清楚，同一个“非冻结用户”可能被理解成全公司用户，也可能只指项目成员。

集合论先解决两个问题：讨论哪些对象，以及哪些对象属于当前集合。

集合由成员决定

集合是对象的无序汇集。记号：

x ∈ A     x 是 A 的元素
x ∉ A     x 不是 A 的元素

集合的外延原则是：两个集合相等，当且仅当它们拥有完全相同的元素。

A = B  ⇔  ∀x (x ∈ A ↔ x ∈ B)

因此：

{1, 2, 3} = {3, 2, 1}
{1, 1, 2} = {1, 2}

顺序和重复次数不属于数学集合的身份。若业务关心顺序，应使用序列；关心重复次数，应使用多重集合。这一区分在第三课会落到程序数据结构和 SQL。

两种常用表示法

列举法

P = {read, write, delete}

适合有限且元素不多的集合。

描述法

E = {n ∈ ℤ | n 是偶数}

竖线读作“满足”。描述法应写明元素从哪个论域取值。只写 {x | x > 0} 会留下 x 是整数、实数还是其他对象的歧义。

现代公理化集合论也不允许用任意性质毫无限制地“收集所有对象”；本卷不展开公理体系，但养成在已知集合中筛选的写法更安全：

{x ∈ U | P(x)}

空集、单元素集和嵌套层次

空集记为 ∅ 或 {}，没有任何元素：

∀x (x ∉ ∅)

{∅} 不是空集，它包含一个元素，这个元素恰好是空集：

|∅| = 0
|{∅}| = 1

还要区分元素与单元素集：

1 ∈ {1, 2}
{1} ⊆ {1, 2}

1 和 {1} 位于不同结构层次。JSON 中的数字 1 与数组 [1] 也不能互换。

子集与真子集

A ⊆ B  ⇔  ∀x (x ∈ A → x ∈ B)

空集是任何集合的子集，因为不存在一个空集元素能违反条件。

若 A ⊆ B 且 A ≠ B，则 A 是 B 的真子集，常记为 A ⊊ B。不同教材也可能使用 ⊂，但该符号有时表示普通子集，有时表示真子集；使用前应声明约定。

证明集合相等的常用方法是双向包含：

A = B  ⇔  (A ⊆ B) ∧ (B ⊆ A)

四种基本运算

给定论域 U，并要求 A ⊆ U、B ⊆ U：

A ∪ B = {x ∈ U | x ∈ A ∨ x ∈ B}
A ∩ B = {x ∈ U | x ∈ A ∧ x ∈ B}
A \ B = {x ∈ U | x ∈ A ∧ x ∉ B}
Aᶜ    = {x ∈ U | x ∉ A}

• 并集 A ∪ B：至少属于其中一个；
• 交集 A ∩ B：同时属于二者；
• 差集 A \ B：属于 A 但不属于 B；
• 补集 Aᶜ：相对于已声明论域 U 不属于 A。

补集必须依赖论域。例如 A={2,4}：

若 U={1,2,3,4,5}，Aᶜ={1,3,5}
若 U=ℤ，Aᶜ 是除 2、4 外的全部整数

不写 U，补集就没有唯一结果。

用成员资格证明恒等式

证明德·摩根律：

(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ

任取 x ∈ U：

x ∈ (A ∪ B)ᶜ
⇔ x ∉ A ∪ B
⇔ ¬(x ∈ A ∨ x ∈ B)
⇔ (x ∉ A ∧ x ∉ B)
⇔ (x ∈ Aᶜ ∧ x ∈ Bᶜ)
⇔ x ∈ Aᶜ ∩ Bᶜ

由于任意 x 在两边的成员资格相同，两集合相等。维恩图能帮助形成直觉，但成员资格链条给出了可检查的证明。

常用集合恒等式

交换律：A ∪ B = B ∪ A
        A ∩ B = B ∩ A

结合律：(A ∪ B) ∪ C = A ∪ (B ∪ C)
        (A ∩ B) ∩ C = A ∩ (B ∩ C)

分配律：A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
        A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

吸收律：A ∪ (A ∩ B) = A
        A ∩ (A ∪ B) = A

这些规律来自成员资格对应的命题逻辑规律。证明时把 x ∈ ... 翻译成 ∧、∨、¬，就能复用上一章的等价变换。

回到访问控制策略

定义：

M：项目成员
F：被冻结用户
A：值班审计员
U：本项目可识别的全部用户

允许读取日志的用户集合：

(M \ F) ∪ A

这里还隐藏一个业务选择：被冻结的审计员是否仍可读取？当前公式允许，因为 A 在差集之外。如果冻结应覆盖所有角色，应写：

(M ∪ A) \ F

两个公式只差括号，政策含义却不同。集合表达式使这个差异可以被评审和测试。

用 Python 3 标准库构造一个被冻结的值班审计员 u2，差异就能直接运行检查：

universe = {"u1", "u2", "u3", "u4"}
members = {"u1", "u2"}
frozen = {"u2", "u4"}
auditors = {"u2", "u3"}
assert (members | frozen | auditors) <= universe

role_exception = (members - frozen) | auditors
deny_all_roles = (members | auditors) - frozen
print(sorted(role_exception))  # ['u1', 'u2', 'u3']
print(sorted(deny_all_roles))   # ['u1', 'u3']
assert role_exception - deny_all_roles == auditors & frozen

第一条规则比第二条多放行的，恰好是 A ∩ F 中的被冻结审计员。这里每份名单都属于同一论域，并假设来自同一时刻的可信状态；数学运算正确不证明名单及时。Python 的空集合应写成 set()，{} 会创建字典，别把数学排版直接当语法。

完成检查

给定：

U={1,2,3,4,5,6}
A={1,2,3}
B={3,4,5}
C={2,4,6}

1. 计算 (A ∪ B) ∩ C；
2. 计算 A \ (B ∪ C)；
3. 用成员资格证明 A \ (B ∪ C) = (A \ B) ∩ (A \ C)；
4. 找出 {1} ∈ { {1}, {2} } 与 {1} ⊆ { {1}, {2} } 的真假；
5. 为“停用状态覆盖任何角色”的权限规则写出集合表达式。

参考资料

• Open Logic Project