企业官网建设流程全解析

做离散数学关系部分的题，最怕的就是"看着像、一算错"。我批改了不少作业，发现自反、对称、传递三个性质的判断，加上闭包运算和 Warshall 算法，基本占了关系章节 80% 的失分点。这篇是关系习题解析的第二篇，专门把这三块放一起说清楚：性质判定怎么保证不丢分，闭包构造背后的"最小扩充"逻辑是什么，Warshall 算法每一步到底在干嘛。适合正在学离散数学的本科生、准备考研的朋友，也适合第一次接触关系矩阵的初学者。我会把判断准则、运算步骤和完整例题全部拆开，带着你一步步推。

1. 自反、对称、传递：三条性质判定，不能光靠眼睛看

1.1 从定义到判定：三个性质分别考什么

关系 R 是集合 A 上的二元关系，三个性质的定义大家都背过：

• 自反：对任意 x∈A，都有 (x,x)∈R。
• 对称：若 (x,y)∈R，则 (y,x)∈R。
• 传递：若 (x,y)∈R 且 (y,z)∈R，则 (x,z)∈R。

背定义容易，做题翻车也容易。翻车原因通常是盯着序偶集合看，看漏了元素。我自己的习惯是：先写出关系矩阵，再下结论。比如 A={1,2,3}，R={(1,1),(1,2),(2,1)}，一眼看过去有(1,1)好像自反没问题，但 2 和 3 的主对角线位置是 0，所以 R 不自反。这种低级错误最好用矩阵法规避。

把 R 写成矩阵 M，M[i][j]=1 表示 (i,j)∈R，三条性质的判定就变成：

• 自反：主对角线全为 1，有一个 0 就否决。
• 对称：矩阵沿主对角线对称，等价于 M[i][j]=M[j][i] 恒成立，也等价于 M = M^T。
• 传递：若 M[i][j]=1 且 M[j][k]=1，则 M[i][k] 必须为 1。注意这里的 i、j、k 可以相等。

这里有个容易忽略的点：传递判定里 i、j、k 的取值互相可以重合。比如 (1,2) 和 (2,1) 都存在，就要求 (1,1) 和 (2,2) 也存在，因为 i=1,k=1 和 i=2,k=2 这两条结论是必须检查的。

1.2 用矩阵快速破除对称性的四个"近亲"概念

很多人把对称、反对称、非对称、自反这几个词混在一起。我建议做一张对照表，做题时直接对号入座。

特别注意：自反和反自反不是"非此即彼"的互斥关系？其实它们确实不可能同时成立，但可以都不成立。比如 A={1,2}，R={(1,1)}，对角线 1 有 1、2 有 0，既不自反也不反自反。对称和反对称也不是互斥的，一个关系可以同时对称又反对称——比如空关系，还有恒等关系 I_A，都是又对称又反对称的。做判断题时这个坑几乎必考。

关于传递，我见过最多的错误是用"双重循环"检查，只验证了 (x,z) 只隔了一个中间元素的情况。实际上，传递要求的是任意长度的路径都能"压缩"成直接边。判断时如果用矩阵乘法，可以记住一个等价条件：R 是传递的，当且仅当 M^2 中为 1 的位置，M 中对应位置也为 1，即 M^2 ≤ M（按位置比较）。这里 M^2 是布尔矩阵乘法下的乘积，1+1=1，不是普通数字加法。考试时如果不想做矩阵乘法，就用三层循环逐个枚举 i,j,k，最保险。

2. 闭包："最小扩充"四个字是理解一切操作的关键

2.1 为什么叫"闭包"而不叫"修补"

给定关系 R，如果它不自反、不对称、不传递，我们可以往 R 里加最少的序偶，让它变成具有对应性质的关系 R'。这个 R' 就是 R 的自反闭包、对称闭包或传递闭包。理解闭包的关键是三条：

1. R ⊆ R'，原来的关系一条不能删。
2. R' 必须具有目标性质。
3. R' 是"最小"的——在所有满足前两条的关系里，R' 包含的元素最少。

这个"最小"约束非常关键。以自反闭包为例，A={1,2,3}，R={(2,2)}。为了让 R 自反，必须把 (1,1)、(3,3) 加进来，同时 (2,2) 本来就有。结果 r(R)={(1,1),(2,2),(3,3)}，这其实就是恒等关系。你当然可以多加很多乱七八糟的序偶让 R 自反，但那不叫闭包，因为不满足最小性。

数学上，自反闭包写作 r(R)=R∪I_A，对称闭包 s(R)=R∪R^(-1)，传递闭包 t(R) 的形式稍微复杂，是 R∪R²∪R³∪……。闭包运算一眼看去像是"打补丁"，但它和"随便补"的本质区别就在于这个并集是刚刚好，不掺多余的东西。

2.2 自反闭包和对称闭包：并上一个集合并完事

自反闭包最简单：R 缺哪些主对角线元素，就把 I_A（单位矩阵，主对角线全 1，其他全 0）并上去。矩阵视角就是 M_r = M ∨ I，布尔加法按位置取 OR。

对称闭包就是把所有"反向缺的边"补上。比如 (1,2)∈R 但 (2,1)∉R，那就把 (2,1) 加进来。矩阵操作是 M_s = M ∨ M^T。注意这里不要犯一个常见的错：以为对称闭包就是把矩阵"镜像翻转"，其实如果正反都有了，就不需要额外操作，用 OR 正好能处理这种情况。

我拿个例子算一遍：A={1,2,3}，R={(1,1),(1,2),(2,3)}。

• r(R) = {(1,1),(1,2),(2,3)} ∪ {(1,1),(2,2),(3,3)} = {(1,1),(1,2),(2,2),(2,3),(3,3)}。
• s(R) = R ∪ R^(-1) = {(1,1),(1,2),(2,3)} ∪ {(1,1),(2,1),(3,2)} = {(1,1),(1,2),(2,1),(2,3),(3,2)}。

自反加对称的同时做，就是 r(s(R)) 或者 s(r(R))，这两个结果是一样的。具体算的时候可以分两步走：先做自反再做对称。要记住，先做哪个都行，因为这两者交换不影响结果，但很多教材不会强调这点，导致学生以为闭包只能按顺序做。

2.3 传递闭包为什么不能"并一次"或者"并两次"解决

传递闭包是三个闭包里唯一的硬骨头。R 不传递，你当然可以检查所有"长度 2 的路径"并把对应的直接边补上，但补完之后，新补的边可能又和旧边形成新的长度 2 路径，还得再补。这个过程可能反复进行。

这就是为什么 t(R) = R ∪ R² ∪ R³ ∪ … 而不是只并到 R²。R² 的定义是：R² 中存在 (i,k) 当且仅当存在某个 j 使得 (i,j)∈R 且 (j,k)∈R。也就是说 R² 把"走两步能到"的关系全部提取出来。R³ 就是"走三步能到"。传递闭包要把所有"有限多步能到"的关系全部算进去，所以是所有这些的并。

但集合 A 只有 n 个元素，一条路径如果长度达到 n（即经过 n+1 个顶点），中间必然有重复顶点，可以删掉中间圈变成更短路径。所以最长有效路径不会超过 n-1 条边，于是并集只需要到 Rⁿ 就够了。这个上界很重要，考试选择题经常问"传递闭包最多并到 R 的几次方"，答案就是 |A|。

我们继续用上面的例子：R={(1,1),(1,2),(2,3)}。

• R²：找所有两步路径。(1,1),(1,2)→(1,2)；(1,2),(2,3)→(1,3)。所以 R²={(1,2),(1,3)}。
• R³：三步路径。R² 与 R 复合，可以看成以 R² 为第一步、R 为第二步。 (1,2),(2,3)→(1,3)，再加上 R² 里的 (1,3) 和 R 里以 3 为起点的边（没有），所以 R³={(1,3)}。
• R⁴ 及以后不会再扩。

t(R) = R ∪ R² ∪ R³ = {(1,1),(1,2),(2,3),(1,3)}。

这个结果我也建议用图来验证：1→2→3，同时 1 有自环，那么从 1 出发两步能到 3，传递闭包里就应该有 (1,3)。这种"图论视角"在检查传递闭包结果时非常好用。

3. Warshall 算法：它为什么比"傻算 R² 再并"快

3.1 算法的核心思路：允许中间顶点逐步"解禁"

用定义算传递闭包要先算 R²、R³……最高到 Rⁿ，每个矩阵乘法是 O(n³)，加起来 O(n⁴)。Warshall 算法用一层巧妙的动态规划把复杂度降到了 O(n³)，而且特别适合手算和编程实现。

它的思想可以概括为：逐步允许路径经过编号更靠前的中间顶点。设 A={1,2,...,n}，用 W[k][i][j] 表示"从 i 到 j 是否存在一条路径，使得路径上所有中间顶点的编号都不超过 k"。注意是中间顶点，起点和终点不算。

初始时，W[0] 就是关系矩阵本身，因为不允许经过任何中间顶点，只能一步直达。然后从 k=1 开始到 k=n，每一轮都在问一个问题：现在允许经过编号为 k 的顶点，会不会让某些原来不可达的 (i,j) 变得可达？会的话就把它更新成 1。

更新规则只有一个：

W[k][i][j] = W[k-1][i][j] ∨ (W[k-1][i][k] ∧ W[k-1][k][j])

翻译成人话：i 能到 j，要么之前就能到，要么现在发现"先到 k，再从 k 到 j"这条路通了。这个公式看着简单，但藏着一个非常重要的编程细节：k 循环必须放最外层。如果你把 k 放最内层，那么你在处理 k=2 的时候，用到的 W[i][k] 和 W[k][j] 可能还没经过 k=1 的更新，路径的传递性就断了，算出来的是错的。

3.2 手工走一遍三层循环：用 3×3 矩阵演示

直接看一个完整例子。设 A={1,2,3}，关系矩阵为：

M = 0 1 0 0 0 1 1 0 0

这个关系表示 1→2，2→3，3→1，是个循环。它的传递闭包应该是所有位置都可达，因为 1 能到 2、3、1，2 能到 3、1、2，3 能到 1、2、3，最终全 1 矩阵。看 Warshall 怎么一步步算出来。

准备一个工作矩阵 W，初始等于 M：

k=0: 0 1 0 0 0 1 1 0 0

k=1，允许经过顶点 1。对每个 i,j，检查 W[i][1] 和 W[1][j]。现在 W[2][1]=0，W[1][2]=1，所以从 2 出发不能先到 1，没更新；W[3][1]=1，W[1][2]=1，所以 3→1→2 通了，W[3][2] 变成 1；W[3][1]=1，W[1][3]=0，所以 3→3 不更新。第一轮后：

k=1: 0 1 0 0 0 1 1 1 0

k=2，允许经过顶点 2。W[1][2]=1，W[2][3]=1，所以 1→2→3 通，W[1][3]=1；W[3][2]=1（这轮开始前已经是 1），W[2][3]=1，所以 3→2→3 通，W[3][3]=1。这一轮结束：

k=2: 0 1 1 0 0 1 1 1 1

k=3，允许经过顶点 3。W[1][3]=1，W[3][1]=1，所以 1→3→1 通，W[1][1]=1；W[1][3]=1，W[3][2]=1，所以 1→3→2 通，W[1][2]=1（本来就是）；W[2][3]=1，W[3][1]=1，所以 2→3→1 通，W[2][1]=1；W[2][3]=1，W[3][2]=1，所以 2→2 通，W[2][2]=1。最终：

k=3: 1 1 1 1 1 1 1 1 1

和我预判的全 1 矩阵一致。手算的时候，每一轮可以只在"行 k 和列 k 有 1 的位置"附近找更新，不需要 9 个位置全扫一遍——虽然全扫也就 9 个位置，但 n 大了之后，这个观察能显著减少计算量。具体说：某一轮 k，只有那些满足 W[i][k]=1 的 i 所在的行，以及满足 W[k][j]=1 的 j 所在的列，它们的交叉点才可能被更新。其他位置看都不用看。

3.3 用 Python 把 Warshall 写出来，顺便做验证

学离散数学的人很多是计算机方向，顺手写个代码验证是好事，也能加深对算法的理解。下面的实现严格按 Warshall 的公式来，用布尔矩阵直接操作：

def warshall(M): n = len(M) W = [row[:] for row in M] # 深拷贝，别动原矩阵 for k in range(n): for i in range(n): if W[i][k] == 1: # 小优化：没路到 k 就不用管 for j in range(n): if W[k][j] == 1: W[i][j] = 1 return W M = [ [0, 1, 0], [0, 0, 1], [1, 0, 0] ] print(warshall(M)) # 输出 [[1, 1, 1], [1, 1, 1], [1, 1, 1]]

这段代码把 Warshall 优化成了 i 循环里先判断 W[i][k]。注意到我没有显式写 W[i][j] = W[i][j] or (W[i][k] and W[k][j])，因为一旦 W[i][k] 和 W[k][j] 都为 1，W[i][j] 必置 1，原来是否为 1 不影响结果。这个写法更接近手算的思考方式。考试不考编程，但是学编程的同学建议跑一遍，把矩阵换成任意关系，自己多测几组。

4. 习题实战：性质判定、三种闭包、Warshall 一次算到位

4.1 综合题：给定关系 R，先判断性质再求三种闭包

题目：A={1,2,3,4}，R={(1,2),(2,3),(2,4),(3,1),(4,3)}。

第一步，写关系矩阵。行和列都按 1,2,3,4 排：

1 2 3 4 1 0 1 0 0 2 0 0 1 1 3 1 0 0 0 4 0 0 1 0

判断自反：对角线 1,1,1,1 位置分别是 0,0,0,0，全 0，反自反成立，自反不成立。

判断对称：看 M[1][2]=1 但 M[2][1]=0，不对称；同时对 (3,1),(1,3)，(4,3),(3,4) 也不对称。反对称呢？检查所有 i≠j 位置，M[i][j] 和 M[j][i] 不能同时为 1。这里没有一对同时为 1 的，所以反对称成立。注意"不对称"和"反对称"是两回事，这题恰好既不对称又反对称。

判断传递：最稳的办法是算 M²，然后逐位置比 M²≤M。先布尔乘法算 M²。只看能产生 1 的位置：

• (1,2) 和 (2,3) → (1,3)； (1,2) 和 (2,4) → (1,4)。
• (2,3) 和 (3,1) → (2,1)。
• (2,4) 和 (4,3) → (2,3)。
• (3,1) 和 (1,2) → (3,2)。
• (4,3) 和 (3,1) → (4,1)。

所以 M² 里为 1 的位置是 {(1,3),(1,4),(2,1),(2,3),(3,2),(4,1)}。现在检查这些位置在 M 里是否为 1：(1,3) 在 M 里是 0，立刻可以判定 R 不传递。不用再看后面了。如果要找齐传递闭包，就继续算。

求自反闭包 r(R)：把对角线全补成 1。得到 r(R)={(1,1),(1,2),(2,2),(2,3),(2,4),(3,1),(3,3),(4,3),(4,4)}。注意 (2,2) 原来没有，(1,1)、(3,3)、(4,4) 原来也没有，一共补 4 个元素。

求对称闭包 s(R)：把所有反向边补上。R 里的边反向：(2,1),(3,2),(4,2),(1,3),(3,4)。所以 s(R) 就是原来 5 条加上这 5 条，共 10 条：{(1,2),(2,3),(2,4),(3,1),(4,3),(2,1),(3,2),(4,2),(1,3),(3,4)}。这里注意 (2,4) 的反向是 (4,2)，不要因为 2 和 4 写反了漏掉。

求传递闭包 t(R)：可以用 Warshall，建议在矩阵上做。初始矩阵和前面一样，四轮迭代之后，我把每一步更新后新增的 1 标出来：

• k=1：允许经过 1。W[2][3]=1 且 W[3][1]=1，所以 2→3→1 通，W[2][1]=1；W[4][3]=1 且 W[3][1]=1，所以 W[4][1]=1。矩阵更新为 0→1 的位置是 (2,1)、(4,1)。
• k=2：允许经过 2。W[1][2]=1 且 W[2][3]=1，所以 W[1][3]=1；W[1][2]=1 且 W[2][4]=1，所以 W[1][4]=1；W[1][2]=1 且 W[2][1]=1，所以 W[1][1]=1；W[3][1]=1 且 W[1][2]=1，所以 W[3][2]=1（原来没有）；W[4][1]=1 且 W[1][2]=1，所以 W[4][2]=1。这轮新增 (1,1),(1,3),(1,4),(3,2),(4,2)。
• k=3：允许经过 3。W[2][3]=1 且 W[3][1]=1 → W[2][1] 已有；W[2][3]=1 且 W[3][2]=1 → W[2][2]=1；W[4][3]=1 且 W[3][1]=1 → W[4][1] 已有；W[4][3]=1 且 W[3][2]=1 → W[4][2] 已有；W[1][3]=1 且 W[3][1]=1 → W[1][1] 已有；W[1][3]=1 且 W[3][2]=1 → W[1][2] 已有。真正新增只有 (2,2)。
• k=4：允许经过 4。W[1][4]=1 且 W[4][3]=1 → W[1][3] 已有；W[1][4]=1 且 W[4][2]=1 → W[1][2] 已有；W[2][4]=1 且 W[4][3]=1 → W[2][3] 已有；W[2][4]=1 且 W[4][2]=1 → W[2][2] 已有；W[4][4] 是 0，没有新增。

最终 W 全貌：

1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0

所以 t(R)={(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(4,1),(4,2),(4,3)}。我建议顺手画一个有向图验证：1→2→3→1 形成一个环，2→4→3 也并入环内，而 3 只能到 1 和 2，4 能到 3、1、2。整体看，从 1、2 可以到达所有顶点；3、4 能到 1 和 2，3 和 4 互相不能到（3→4 需要 3→1→2→4，但 3 不能先到 1 吗？3→1→2→4 确实通了，W[3][4] 为什么是 0？这里要特别注意：W[3][4] 在这一题里是 0。从 3 出发：3→1，1→2，2→4，路径是存在的，但传递闭包要求 (3,4)∈R³，可是 R 里 3 有到 1 的边，1 有到 2 的边，2 有到 4 的边，三步确实能到 4，所以应该通。那 W[3][4] 为什么是 0？我上面算错了，回看 k=2 轮：W[1][4]=1，如果 W[3][1]=1，那么 W[3][4] 应该等于 1。但当时 W[3][1] 确实是 1，W[1][4] 是 1，为什么没更新？因为我在 k=2 轮检查的是 W[i][2] 和 W[2][j]，4 作为 j 时 W[2][4]=1，但 i=3 时 W[3][2] 是 0，所以过不了 k=2 这一关。到了 k=3 轮，W[1][3]=1，W[3][4] 呢？W[3][4] 在 W[3][2] 变成 1 之后，其实 k=2 轮末尾已经可以通过 3→2→4 到达，也就是 W[3][4] 应该在 k=2 轮就变成 1。我再核一遍：k=2 轮开始，W[3][2] 还是 0，k=2 轮内 W[3][1]=1、W[1][2]=1 使 W[3][2]=1，但这一轮里 W[3][2] 更新后 W[2][4]=1，所以 3→2→4 应该也通。只是我前面计算这轮时只写了 W[3][2]=1，没有顺势写 W[3][4]=1。在矩阵编程实现中，这个"连带更新"是自动发生的，因为程序按行处理时会用更新后的值。手算时如果不注意，就会漏。正确的最终矩阵里 (3,4)=1。经修正，最终 t(R) 应包含 (3,4)。（这就是手算 Warshall 最容易踩的坑，我在第 5 章还会专门说。）

其实这个题目选得稍微复杂了点，4 阶矩阵手算容易乱。但正因为乱，才能暴露出手算 Warshall 的一个典型误区：在同一轮 k 的内部，更新顺序会影响你是否能及时发现后续可用的新路径。严谨的做法是，每一轮都先复制一份"上一轮矩阵"做判断，本轮所有更新互不影响；如果边算边改，可能会出现后面用到了本轮刚更新的值，这本身不改变最终答案，但需要你非常小心地把每一轮的所有新增项都列完，否则容易漏。

4.2 小结论证明：为什么 r(s(R)) = s(r(R))

闭包运算并不总是可以交换，但自反闭包和对称闭包是可以交换的。题目常让你证明 r(s(R)) = s(r(R))。

证明思路很直接：r(s(R)) = s(R) ∪ I_A = (R ∪ R^(-1)) ∪ I_A。另一方面 s(r(R)) = (R ∪ I_A) ∪ (R ∪ I_A)^(-1)。注意到 I_A^(-1) = I_A，所以 (R ∪ I_A)^(-1) = R^(-1) ∪ I_A。于是 s(r(R)) = R ∪ I_A ∪ R^(-1) ∪ I_A = R ∪ R^(-1) ∪ I_A。两边结果相同。

这类证明题考的不是技巧，而是你对集合运算和闭包定义的熟悉度。遇到类似题，第一步永远是"把闭包写成集合表达式的形式"，然后展开、合并。不要试图用自然语言糊弄，集合表达式写出来，证明就完成了一半。

4.3 反过来问：已知闭包，反推原关系能不能唯一

有这样一种题：已知 r(R) 等于某个集合，问 R 有多少种可能。这种题考查闭包定义的"最小性"理解。比如 A={1,2}，r(R)={(1,1),(1,2),(2,1),(2,2)}，也就是全关系。问 R 可以是什么？

因为 r(R) 只是把对角线上缺的补上了，没有动非对角线的元素，所以 R 的非对角线元素必须和 r(R) 一致：也就是 (1,2) 和 (2,1) 都得在 R 里。对角线可以随便选，(1,1) 和 (2,2) 各有 2 种，所以 R 有 4 种可能：固定非对角线的两条，对角线任意。这里如果不理解"闭包只是补对角线"，就会漏解或多解。

5. 做题最容易踩的五个坑，以及我怎么避开的

5.1 传递判断只用两层循环，忘了 j 和 i、k 可重合

我见过有同学判断传递时这样写伪代码："for i, for j, if (i,j) in R, then for k, if (j,k) in R then check (i,k)"，这个其实是三层循环，没问题。问题是有些人内心默认 i,j,k 是三个不同的值，于是 (1,1) 这类自环就完全不参与传递检查。但传递定义里没有要求 i,j,k 互不相同。比如 R={(1,1),(1,2)}，(1,1) 和 (1,2) 都在 R 中，按传递定义要求 (1,2) 在 R 中，确实满足；但有些题目就需要你特别注意自环作为"中转站"的情况。比如 R={(1,2),(2,2)}，(2,2) 和 (2,2) 是同一个元素，它作为中间元素要求 (2,2) 存在，这是满足的；而 (1,2) 和 (2,2) 推出 (1,2) 存在，也满足，所以这个关系其实是传递的。你要是潜意识里把 j 限定成"不能等于 i 和 k"，就会误判。

最稳的检查方法还是用 M²≤M 的条件。布尔矩阵乘法会把所有 i,j,k 的组合（包括相等的）都覆盖到，不会漏。

5.2 Warshall 的 k 循环位置放错，结果全乱

Warshall 算法正确性的关键，是每一轮允许的中间顶点集合是逐步扩大的。这个过程必须是"串行"的：先只允许 1 号顶点做中间点，算完整个矩阵；再允许 1 和 2 号顶点，再算一遍；以此类推。如果内层循环是 j，外层是 i，中间夹着 k，那某个 (i,j) 的更新可能使用了尚未完全更新的行或列，导致路径信息传递断掉。

我建议记一句话：在 Warshall 里，k 永远是"阶段"，不是"位置"。k=1 是一整个阶段，这个阶段里允许所有路径经过点 1；k=2 是下一个阶段，允许经过点 1 或点 2。阶段不能倒着来，也不能插在位置循环里。

5.3 手算时用了本轮刚更新的值，导致漏算或者重复算

这个坑我第 4 章的例题里已经踩过一次。手算 Warshall，严格做法是每一轮开始前，拿上一轮的矩阵作为"只读"依据。计算机程序里容易做到，因为代码里可以在更新时用新值（只要外层 k 循环顺序对，最终结果一样）。但手算时，如果你一边用上一轮 W[i][k] 判断，一边又在本轮把新的 W[i][k] 写进去做后续判断，很可能漏掉本该本轮出现的新传递路径。

我的建议是：手算时，每一轮先单独标出"哪些格子本轮要变 1"，"为什么变 1"的理由写在旁边，等这一轮全部找完之后再统一写进矩阵。不要找一个改一个，不然改到一半忘了哪个是旧值哪个是新值。如果你发现某个格子同时被两个理由标记，比如 (i,j) 既因为路径 i→k→j 通又因为 i→其他→j 通，那就写"已通"，别重复加。

5.4 求对称闭包时，忘记原来正反都有的边不能加两次

对称闭包的并集 R∪R^(-1) 用的是集合的并，不是多重集合的叠加。有人求 s(R) 时，把 (1,2) 加了一遍，又把反向 (2,1) 加了一遍，结果写成"两条 (1,2)"。集合不允许重复元素。更隐蔽的错是：R 里恰好同时有 (1,2) 和 (2,1)，求对称闭包时，有人还在 R^(-1) 里各加了一遍，最后写成了 4 个元素。并集运算会自然去重，你只要记住 s(R) 的元素个数最大是 n²，不会超过 n²，重复写一定是自己笔误。

5.5 把布尔运算和数值运算混在一起

关系矩阵的乘法、加法都是布尔运算：1+1=1，1×1=1，没有进位，没有 2。有些同学在算 M² 时，算出某个位置是 1+1=2，然后写了个 2，再判断传递时又说"2 大于 1，算通"。这个习惯不好，因为后续所有操作都以 0/1 判断，一旦出现 2，要么看成错误要么对不上。建议从一开始就用"∨"和"∧"而不是"+"和"×"，至少在草稿上写成 1∨1=1 的样子，防止自己手滑按普通矩阵乘法去算。

排错技巧：做完一道传递闭包大题，有一个很好的自查方法——把最终的 t(R) 画成有向图，然后任意取一个长度大于 1 的路径，验证它的起点终点序偶是否都在 t(R) 里。如果有一条路径起点终点不在，那说明闭包还没闭合，答案一定错了。这个方法对 4 阶及以下的小矩阵尤其快，比自己硬看矩阵要直观得多。

6. 从闭包到可达性：Warshall 在图论里的邻居

6.1 可达矩阵就是特殊关系下的传递闭包

计算机相关专业后面学图论时，会遇到"可达矩阵"这个概念。给定有向图，可达矩阵 P 的定义是：P[i][j]=1 当且仅当从顶点 i 出发存在一条长度大于等于 1 的有向路径到达顶点 j。这和传递闭包几乎是一回事，只是传递闭包还允许长度 0 的路径（也就是自反性有时要额外处理）。

具体关系是：如果直接用图的邻接矩阵 M 跑 Warshall，得到的结果里 P[i][i] 可能是 1 也可能不是。比如一个 1 到 2 到 3 的单向链，1 不能回到 1，所以 P[1][1]=0；但 2 能到 3 不能回 2，所以 P[2][2]=0；只有成环的顶点可达自己。如果需要自反意义上的可达性，就把对角线手动置 1。很多算法题的"判断图是否强连通"，本质就是看可达矩阵是否全 1 矩阵。

6.2 用 Warshall 判断强连通，比 Floyd 更省事

很多同学一看到"任意两点是否可达"就想到 Floyd 算法，然后煞有介事地初始化 dist 数组、写三重循环、比较距离大小。但其实我们只需要布尔的可达性，不需要具体最短路径长度，Warshall 的布尔版本完全够用，而且写起来短得多。Floyd 是 Warshall 的扩展版，区别在于 Floyd 保留距离信息，Warshall 只保留"是否可达"。

所以遇到"判断有向图是否强连通""求可达矩阵"这类问题，第一反应应该是 Warshall，而不是 Floyd。很多教材在讲完关系闭包之后紧接着讲图论，这个衔接点就在这里。

6.3 一个实际的小场景：课程先修关系中的影响传播

离散数学的关系闭包不是只活在习题里。比如培养方案里课程之间有先修关系：A 的先修是 B，B 的先修是 C，那么通过传递闭包，系统自动推导出 C 也是 A 的间接先修。这种"间接依赖"的推理在数据库的依赖关系分析、软件包依赖管理、推荐系统的二跳关系补全里都会用到。你以后写代码分析依赖树时，递归自己写容易爆栈，不如先算一个闭包矩阵，然后 O(1) 查询两个节点是否间接依赖。

我在做某模拟项目的依赖解析时，就是把依赖图转成矩阵，跑一次 Warshall，然后所有"是否间接依赖"的查询全变成了查表。当时 1000 多个节点的图，O(n³) 在启动时算一次，后面查询飞快。这个经验让我对闭包的理解从"考试题"变成了"实用工具"，也希望你学这一节时，别只盯着考试看。

7. 我个人总结的一套做题流程，供你直接抄

做了大量离散数学关系部分的题目之后，我形成了一套固定解题流程，写在这里：

1. 拿到关系 R，先决定用"序偶集合"还是"关系矩阵"。题目元素少于等于 4 个，矩阵更方便；元素更多，看具体问什么。但凡涉及传递闭包，无条件用矩阵和 Warshall。
2. 判断三个性质时，先看自反和反自反（看对角线，一眼出结果），再看对称和反对称（看非对角线对称性），最后看传递（算 M² 或跑三层循环）。这个顺序是从便宜到贵，避免一开始就算矩阵乘法。
3. 求闭包时，自反和对称用并集公式，传递闭包直接上 Warshall。不要先算 R²、R³ 再并，效率低，而且 4 阶以上矩阵 R²、R³ 容易算错。
4. 算完一定要验证。小矩阵画有向图，检查有没有"两步能到但闭包矩阵没有"的地方；大矩阵抽查几条路径。
5. 遇到"闭包的性质""闭包运算是否交换"这类证明题，把闭包展开成集合表达式，用集合运算律推，不要空想。

这套流程是我以前被 4 阶矩阵的 Warshall 漏算折腾过之后总结的。一开始我也图省事，算到一半凭感觉补，结果答案错了都不知道错在哪。后来老老实实每轮先标记再更新，准确率立刻上来了。

最后再分享一个小技巧：如果你手边有 Python 环境，把第 3 章那段 warshall 函数存下来，以后做离散数学作业时，所有传递闭包题都可以拿来核对答案。这不是提倡你依赖代码，而是把它当计算器——就像你用计算器验证加减乘除一样，确定自己手算的每一步是对的。这样多核对几次，你对 Warshall 各个阶段的矩阵状态就会有更好的手感，考试时哪怕没有电脑，也能比较自信地算出正确结果。