集合、关系与离散结构

三个文档的关键词为：a 有“python”，b 有“python”和“ai”，c 有“ai”。工具认为共享关键词就等价，于是 a 与 b 等价，b 与 c 等价，a 却不与 c 等价。把新文档与已有代表比较的分组程序，会因输入顺序而改变结果。问题首先是数学问题：该关系没有等价所需的性质。

集合描述成员，关系描述成立的配对，函数则是一类每个输入恰有一个输出的关系。本模块把它们连接到记录标识、分组与依赖序。你将明确规则需要哪种性质，并在失败时给出具体见证。直观图像或“相似”一词本身不能保证结构正确。

回忆检查：翻译“每个配对都满足性质”，否定“每个对象都有匹配”，并区分像与陪域。按需复习量词与函数。有限目录是教学模型，一般定义也适用于更大及无限集合。

集合（set）由成员确定，顺序和重复不重要：$\{a,b,a\}=\{b,a\}$。列表可保留重复与顺序，因此用集合替换列表可能改变问题。数据中同一观测出现两次，而不同值的集合不再记录次数。表示必须符合要研究的数量。

$x\in A$ 表示属于，$x\notin A$ 表示不属于。$A\subseteq B$ 意为 $\forall x,\ x\in A\Rightarrow x\in B$，允许相等。真子集 $A\subsetneq B$ 还要求 $A\ne B$。属于比较对象与集合；包含比较两集合的成员。成员本身是集合时，两种问题都可能出现，必须分别判断。

空集 $\varnothing$ 没有成员，是每个集合的子集，因为没有违反包含蕴含的元素。但它不自动属于每个集合。$A=\{a,b\}$ 时，$\varnothing\subseteq A$ 真而 $\varnothing\in A$ 假；$B=\{\varnothing,a\}$ 时两者都真。这区别在子集的集合中尤其重要。

并集 $A\cup B$ 包含任一集合的成员，交集 $A\cap B$ 包含两者共有成员，差集 $A\setminus B$ 包含 A 中不在 B 的成员。补集必须相对于明确全集（universe） $U$：假定 $A\subseteq U$，$A^c=U\setminus A$。没有 U，“其他所有对象”是不完整的。目录补集是目录中其余条目，并非所有可能对象。

幂集（power set） $\mathcal{P}(A)$ 是 A 的全部子集构成的集合。$A=\{a,b,c\}$ 时，有空集、三个单元素集、三个二元素集及 A 本身，共八个成员。每个原始元素可选入或不选入，所以 n 元有限集合有 $2^n$ 个子集；模块 05 系统研究该计数规则。幂集的元素是集合，并不是重复 A 的原始元素。

笛卡尔积（Cartesian product） $A\times B$ 包含 $a\in A,b\in B$ 的有序对 $(a,b)$。顺序有意义，因为两个坐标各有角色。请求集 D 与审核人集 V 的积包含候选请求—审核人配对；反向积描述审核人—请求。任何一因子为空，就没有配对，积为空。

Python 的空集写 set()，因为 {} 是字典。集合成员必须可哈希；集合的集合可用 frozenset 作成员，可变 set 不能作为成员。这是程序表示限制，不改变数学。打印顺序无保证，实验为可复现输出对元素排序。

两个集合相等当且仅当成员完全相同。证明 $A=B$，可以对任意对象证明属于 A 当且仅当属于 B，或分别证明两方向包含。只比较成员数量不够，因为不同集合可有相同基数；只检查一个元素也不够，除非它就是整个论域。

集合运算连接模块 02 的逻辑：$x\in A\cap B$ 等价于 $(x\in A)\land(x\in B)$，并集对应包含式析取。对于 $x\in U$，属于补集等价于不属于 A。因此任意候选成员上的逻辑等价能给出集合恒等式，不需要集合小到可列举。

同一全集下，德摩根律给出 $(A\cup B)^c=A^c\cap B^c$ 与 $(A\cap B)^c=A^c\cup B^c$。共同全集是前提。训练目录补集与全部记录补集的候选成员不同，不能混用；数据库筛选与数据划分尤其需要明确 U。

该全集中 $A\setminus B=A\cap B^c$，差集通常不可交换。对称差 $(A\setminus B)\cup(B\setminus A)$ 可交换，因为选取恰属于一侧的成员。变化标识报告可能需要对称差，从 A 删除的标识报告只需要单向差。名字相似不代表运算可互换。

阴影图可以沟通恒等式，但仍需说明前提。两集合有四种成员情况：都不属于、仅 A、仅 B、两者都属于。表达式选择某些区域。比较全部区域的选择给出有限逻辑证明；绘几个样本点只是说明。必须说明提供的是哪种证据。

证明包含的写法是：“取任意 $x\in A$，根据定义与假设推出 $x\in B$。”除非在证明反向或使用可逆等价步骤，不应先假设 $x\in B$。如果使用 $A\subseteq B$、$B\subseteq C$ 等额外前提来证明 $A\subseteq C$，应清楚列出它们。

实验检查一个三元素全集的所有子集，是对实现与预测的有用检验，却不自行证明所有集合的恒等式。上面的任意成员论证覆盖一般陈述，包括无限集合。计算与证明可互相支持，但回答不同范围的问题。

从 A 到 B 的二元关系（binary relation）是子集 $R\subseteq A\times B$，选择哪些有序配对成立。$xRy$ 是 $(x,y)\in R$ 的简写。D 上的关系满足 $R\subseteq D\times D$，可比较同类对象。有限关系可用布尔表表示：行是第一坐标，列是第二坐标，真格表示属于 R。

四种常见性质：自反（reflexive）为 $\forall x\in D,\ xRx$；对称（symmetric）为 $\forall x,y\in D,\ xRy\Rightarrow yRx$；反对称（antisymmetric）为 $\forall x,y\in D,\ (xRy\land yRx)\Rightarrow x=y$；传递（transitive）为 $\forall x,y,z\in D,\ (xRy\land yRz)\Rightarrow xRz$。每条是量化要求，失败见证形状不同。

缺失对角配对否定自反；正向存在而反向不存在否定对称；不同对象的双向配对否定反对称；$xRy,yRz$ 成立而 $xRz$ 缺失的链否定传递。看起来奇怪的配对不一定是反例，必须准确违反公式。

反对称不是“从不对称”。它允许同一对象的两个方向，也不要求不同对象之间有任何方向。相等关系同时对称与反对称，因为相关对象必相等，不会出现不同对象的双向配对。关系也可能两性质都没有。应记公式而非按“反”字直觉猜测。

开头关键词规则也不传递：a 与 b 共享，b 与 c 共享，a 与 c 不共享。对称性不能修复。若文档没有关键词，它与自身也不共享，因此在包含这种文档的论域上还不自反。限制为非空关键词文档能消除此自反失败，却不解决传递问题。

非空 D 上，空关系不自反，却对称、反对称、传递，因为相应前件永不成立。全关系 $D\times D$ 自反、对称、传递，只有 D 至多一个成员时反对称。空 D 上四性质都空真成立。这些边界情况直接来自量词逻辑。

性质必须对明确论域检查，包括没有出现在任何存储配对中的对象。只对已出现对象检查自反，可能漏掉另一个对象缺失的对角。实验把论域与配对集分别输入。一般定理要证明任意相关配对或三元组都满足；有限表可通过完整枚举确立该表的性质。

等价关系（equivalence relation）自反、对称、传递，形式化“为这个目的视作相同”。字面相等是一例，不同记录也可按某个键等价。等价只关于该键或表示，不自动证明对应人、事件或物理对象相同。

x 的等价类（equivalence class）为 $[x]=\{y\in D:xRy\}$。自反使 $x\in[x]$，类非空。如果 $y\in[x]$，对称与传递给出 $[y]=[x]$，因此任何成员可作代表而不改变类。换代表只是换标签，不会生成新类。

为何两类不能部分重叠？若 $z\in[x]\cap[y]$，则 $xRz,yRz$。对称给 $zRy$，传递给 $xRy$。任意 $u\in[x]$，对称给 $yRx$，再由传递得 $yRu$，故 $u\in[y]$；反向包含同理。所以重叠就相等。这正是关键词分组缺失的数学保护。

不同等价类构成 D 的划分（partition）：块非空、两两不交、并集为 D。自反让每个对象属于自身类，因而覆盖论域。反过来，划分可定义“属于同一块”的关系；块归属唯一，保证自反、对称、传递。两种描述表达同一结构。

商集（quotient set） $D/R$ 是不同等价类的集合。其成员是类，程序可存储方便的代表标签。代表上的运算要能定义在商集上，必须保证换用同类代表不会改变预期结果的值或类别。模运算将在后面使用此条件。

固定确定性键的相等产生等价：$xRy$ 当 $k(x)=k(y)$。相等提供三条公理。例如去除首尾空格并进行大小写折叠，按明确规范化规则分组名字。但这可能合并同名不同人，或丢失应用需要的区别。标签的数学等价与键是否合适是不同问题。

相似规则若不传递，不应称输出为等价类。可选其他聚类目标，或改为链连通，但后者改变规则：a 与 c 可能通过 b 连通，却没有直接共享关键词。修复应明确声明并按用途评估，不能悄悄求传递闭包后仍称直接相似。

偏序（partial order）自反、反对称、传递，记作 $x\preceq y$。它描述顺序，而非等价的可互换归属。若 $x\preceq y$ 或 $y\preceq x$ 则可比。全序（total order）要求偏序中每对都可比。“偏”允许不可比，不表示公理偶尔才成立。

包含是幂集上的偏序：每集包含自身，互相包含推出相等，包含链可传递。在 $\mathcal{P}(\{a,b\})$ 中，$\{a\}$ 与 $\{b\}$ 不可比。把它们排进一个列表，是额外选择排序，不是发现它们间的包含关系。

有限偏序的哈斯图（Hasse diagram）省略自环与传递可推出的边。若 $x\prec y$ 且没有论域对象严格位于其间，则从 x 向上画覆盖边到 y。向上路径表示其他比较；缺少直接边不意味着比较假，只要有路径。两个方向都无向上路径的对象不可比。

最小元（least element）在每个对象之下；极小元（minimal element）没有不同的更小对象。最小必极小，但有不可比对象时极小未必最小。可有多个极小，若有最小则唯一：两个最小元互相相关，反对称使它们相等。最大与极大是反向概念。

只取 $\{a\},\{b\},\{a,b\}$ 的论域，两单元素集都极小，但都不是最小，因为各自不在另一之下。全集最大。因此“选择最小合格项”的需求可能还需处理并列或不可比；偏序本身未必给唯一选择。

严格序去掉相等：$x\prec y$ 意为 $x\preceq y$ 且 $x\ne y$。由偏序得到的严格关系反自反且传递，但不自反，故不能用前述非严格偏序公理直接把 $<$ 分类成偏序。合适的严格序可添加相等得到非严格序；先说明约定再检查。

依赖可通过可达性形成序：同一对象或存在指向路径时，前者先于后者。要保证不同对象反对称，必须排除有向环。模块 07 研究图与拓扑序。当前先区分直接依赖对与传递可达关系；直接边表即使描述合理依赖，也未必自身传递。

应用可同时有等价和序：相同标签分组形成等价类，再按先决关系排序是另一结构。相等本身既等价又偏序，但只有至多一元素论域上是全序。因此应读公理，不要以为结构类别永不重叠。

函数 $f:A\to B$ 的图为 $G_f=\{(x,f(x)):x\in A\}\subseteq A\times B$。它是每个 A 输入恰有一个 B 输出的特殊关系。一般关系可无输出或有多个输出，所以并非每个关系是函数。列出图仍必须声明 A、B。

单射（injective）要求任意输入满足 $f(x)=f(y)\Rightarrow x=y$，不同输入输出不同。满射（surjective）到 B 要求每个 $b\in B$ 都有 $x\in A$ 使 $f(x)=b$，它依赖陪域。双射（bijective）同时满足两者，每个陪域成员恰有一个原像。

逆关系反转 $G_f$ 的每个配对。它在整个 B 上是函数当且仅当 f 双射：满射为每个逆输入提供输出，单射保证唯一。单射可只在其像上有逆函数；不单射时逆关系有多输出，任选一个需要额外规则，不是唯一逆。

实数平方函数满足 $f(-2)=f(2)=4$，不单射。限制为非负实数到非负实数后双射，逆为平方根。论域限制是数学选择。丢弃属性的特征映射也可能合并不同记录；没有额外信息或假设，后续算法无法仅由特征唯一重建区别。

唯一标识每条记录的键应在记录论域上单射，却不必覆盖全部可能标识字符串，未用标识很正常。标签映射可故意多对一，因为多记录属于同一类。把标签当唯一标识就是混淆用途；需要哪种性质应由规格决定。

有限集合间单射说明源大小不超过目标，双射说明大小相同。但大小相同不使每个函数双射：实际规则仍可碰撞并遗漏输出。无限集合中，真子集也可能与原集双射，有限“严格更少”的直觉不能自动延伸。

可数性（countability）预览：$n\mapsto2n$ 把含零自然数双射到偶自然数，虽然后者是真子集。整数可列为 $0,1,-1,2,-2,\ldots$；有理数可按整数分子、正分母组织并跳过重复。这些可数无限。实数不可数，完整对角线论证留作额外证明练习，不是本实验先修。

实用结业技能是检查明确映射，说明保留哪些信息，逆转是否唯一且在目标论域上完整。关系、等价类与序提供另外的结构表示；先选择符合问题的数学对象，再选处理算法。

使用 Python 3.11 或更新版本，按需阅读 Python 入门。无需包。集合上的 &、|、- 分别为交、并、差，并非标量算术。每个实验解释预测、结果结构与故障或变化。每次十分：预测三分，解释四分，诊断三分。

四十分钟：列出 {0,1,2} 的八个子集，预测子集有序三元组数量，再运行。脚本在这一个全集的全部三元组上比较分配律与补集恒等式。解释为何有 512 组、为何排序输出，以及一般证明为何仍需任意成员论证。把德摩根右侧的交改成并，保存失败 A、B 并修复。

下载 lab1_set_identities.py

"""Exhaustive checks over one small universe, not a general set-theoretic proof."""
from itertools import combinations, product


def subsets(items):
    return [set(part) for k in range(len(items) + 1) for part in combinations(items, k)]


def main():
    universe = {0, 1, 2}
    choices = subsets(sorted(universe))
    print("Power set:", [sorted(s) for s in choices])
    checks = 0
    for a, b, c in product(choices, repeat=3):
        assert a & (b | c) == (a & b) | (a & c)
        assert universe - (a | b) == (universe - a) & (universe - b)
        checks += 1
    print("Distributivity and De Morgan agree for", checks, "triples in this universe.")
    a, b = {0, 1}, {1, 2}
    print("A union B:", sorted(a | b), "intersection:", sorted(a & b))
    print("A minus B:", sorted(a - b), "B minus A:", sorted(b - a))
    print("{} is a dict; set() is an empty set.")
    print("General identities still require a proof for arbitrary membership.")


if __name__ == "__main__":
    main()

Power set: [[], [0], [1], [2], [0, 1], [0, 2], [1, 2], [0, 1, 2]]
Distributivity and De Morgan agree for 512 triples in this universe.
A union B: [0, 1, 2] intersection: [1]
A minus B: [0] B minus A: [2]
{} is a dict; set() is an empty set.
General identities still require a proof for arbitrary membership.

四十分钟：预测同奇偶、距离至多一、$\le$、$<$ 的四性质。运行并逐条把见证对照定义。将论域改成 (0,1,2,3)，运行前预测新见证。最后相等关系显示对称与反对称可以并存。探索器可直接创造缺失对角、反向与传递失败。

下载 lab2_relations.py

"""Return one explicit witness for each failed property on a finite domain."""
from itertools import product


def failures(domain, relation):
    pairs = list(product(domain, repeat=2))
    triples = product(domain, repeat=3)
    return {
        "reflexive": next(((x, x) for x in domain if (x, x) not in relation), None),
        "symmetric": next(((x, y) for x, y in pairs if (x, y) in relation and (y, x) not in relation), None),
        "antisymmetric": next(((x, y) for x, y in pairs if x != y and (x, y) in relation and (y, x) in relation), None),
        "transitive": next(((x, y, z) for x, y, z in triples if (x, y) in relation and (y, z) in relation and (x, z) not in relation), None),
    }


def main():
    domain = (0, 1, 2)
    rules = {
        "same parity": lambda x, y: x % 2 == y % 2,
        "distance at most one": lambda x, y: abs(x - y) <= 1,
        "less than or equal": lambda x, y: x <= y,
        "strictly less": lambda x, y: x < y,
    }
    for name, rule in rules.items():
        relation = {(x, y) for x, y in product(domain, repeat=2) if rule(x, y)}
        result = failures(domain, relation)
        print(name)
        for property_name, witness in result.items():
            print(" ", property_name + ":", "holds" if witness is None else f"fails at {witness}")
    identity = {(x, x) for x in domain}
    assert all(witness is None for witness in failures(domain, identity).values())
    print("Identity is both symmetric and antisymmetric.")


if __name__ == "__main__":
    main()

same parity
  reflexive: holds
  symmetric: holds
  antisymmetric: fails at (0, 2)
  transitive: holds
distance at most one
  reflexive: holds
  symmetric: holds
  antisymmetric: fails at (0, 1)
  transitive: fails at (0, 1, 2)
less than or equal
  reflexive: holds
  symmetric: fails at (0, 1)
  antisymmetric: holds
  transitive: holds
strictly less
  reflexive: fails at (0, 0)
  symmetric: fails at (0, 1)
  antisymmetric: holds
  transitive: holds
Identity is both symmetric and antisymmetric.

四十分钟：预测规范化姓名组与两种贪心关键词分组。运行后解释差异。固定键相等形成等价类，直接关键词相似不会。不要把规范化姓名称为已验证个人身份。添加第五条名为 Ada 但属于另一个人的记录，解释代码对键仍数学正确，却不适合识别人。

下载 lab3_grouping.py

"""Equality of a declared key is an equivalence; shared keywords need not be."""


def main():
    records = (("r1", "Ada"), ("r2", " ADA "), ("r3", "Lin"), ("r4", "LIN"))
    groups = {}
    for identifier, name in records:
        key = name.strip().casefold()
        groups.setdefault(key, []).append(identifier)
    print("Groups by stripped, case-folded name:", groups)
    print("This key defines equality of labels, not proof of personal identity.")
    keywords = {"a": {"python"}, "b": {"python", "ai"}, "c": {"ai"}}

    def related(x, y):
        return bool(keywords[x] & keywords[y])

    print("a~b:", related("a", "b"), "b~c:", related("b", "c"), "a~c:", related("a", "c"))
    assert related("a", "b") and related("b", "c") and not related("a", "c")

    def greedy(order):
        result = []
        for item in order:
            for group in result:
                if related(item, group[0]):
                    group.append(item)
                    break
            else:
                result.append([item])
        return result

    print("Representative grouping, order a,b,c:", greedy(("a", "b", "c")))
    print("Representative grouping, order b,a,c:", greedy(("b", "a", "c")))
    print("Repair: use an explicit equivalence key or declare a different clustering objective.")


if __name__ == "__main__":
    main()

Groups by stripped, case-folded name: {'ada': ['r1', 'r2'], 'lin': ['r3', 'r4']}
This key defines equality of labels, not proof of personal identity.
a~b: True b~c: True a~c: False
Representative grouping, order a,b,c: [['a', 'b'], ['c']]
Representative grouping, order b,a,c: [['b', 'a', 'c']]
Repair: use an explicit equivalence key or declare a different clustering objective.

练习 1–12 预算 110 分钟，每题五分；可选两题额外 25 分钟。失败性质给出满足前提、违反结论的输入；证明要说明论域并使用任意成员或完整逻辑论证。

完成九道自动选择题与一道书面解释。反馈指出混淆时回看定义；熟悉名称不能代替量化规则。

必读十五分钟：在 MIT Mathematics for Computer Science 链接教材中阅读基本集合与二元关系定义。把一个成员恒等式改写成逻辑式并比较子集记法。

必读二十分钟：阅读等价关系与偏序讨论，并排写公理，解释变化的公理如何改变用途。自己画四对象包含图。高级可数性在此可选。

选读：官方 Python 集合文档 帮助比较可变集合与 frozenset，并区别空集与空字典。本课图与教学例子为原创。

成员定义集合运算，任意成员论证证明恒等式。关系选择配对，量化公理决定结构。等价产生可互换块的划分；偏序提供可能不可比的比较。函数增加唯一输出，双射允许整个陪域上的唯一逆转。

结业任务：证明一个补集恒等式，带失败见证分类三对象关系，画有不可比对的哈斯图，并判断列出的函数有无完全逆。练习六十分、实验解释三十分、测验十分包括书面自评。修正后解释每个失败先修技能。

模块 04 研究直接证明、反证、归纳与程序不变式。起始技能是取任意对象、应用定义、写出范围与论证一致的结论。保留成员与奇偶证明作为范例。