3.7 关系的闭包运算

CHAPTER03集合3.7关系的闭包运算课程大纲CONTENTS01闭包的定义与求解•自反闭包

•对称闭包

•传递闭包02例题解析•闭包求解实例

•经典关系图分析03重要定理•闭包的等价性证明

•集合论公式与有限性04高级求解方法•关系矩阵法：布尔矩阵运算求解闭包

•Warshall算法：高效计算传递闭包05闭包运算的性质•闭包运算的顺序性：自反对称传递闭包的顺序影响

•运算的保序性与单调性分析什么是关系的闭包？核心问题一个二元关系通常不一定天然具备某些重要的特殊性质，例如：•自反性(Reflexivity)

•对称性(Symmetry)

•传递性(Transitivity)关键：如何通过添加最少的有序对，使该关系满足这些性质？引入案例设集合A={1,2,3}，关系R定义为：R={<1,1>,<1,2>,<2,1>}❌问题：R不具有自反性。✅解决方案：添加缺失的自环{<2,2>,<3,3>}，得到新关系R'，此时R'具备了自反性。闭包的意义闭包操作的本质，是在保持原关系基本结构的前提下，通过最小程度的扩展，“补全”缺失的逻辑关联。它是一种“完备化”的逻辑工具：将一个可能残缺、不完美的关系，变成了满足特定逻辑公理体系要求的、更易于分析和使用的新关系。定义3.29：闭包的正式定义设R是集合X上的二元关系，寻找一个关系R'满足以下三个核心条件：01.核心性质R'必须是自反的、对称的，或传递的。这是闭包的首要数学特征。02.包含关系R⊆R'，即闭包R'必须包含原关系R的所有有序对，是原关系的超集。03.最小性原则对任意满足前两个条件的关系R''，必有R'⊆R''。即R'是满足要求的最小关系。自反闭包(ReflexiveClosure)r(R)=R∪IX对称闭包(SymmetricClosure)s(R)=R∪R-1传递闭包(TransitiveClosure)t(R)=R∪R²∪R³∪...自反闭包r(R)的求解方法目标：补充缺失元素，使非自反关系变得自反集合运算r(R)=R∪IA操作：在关系R的序偶集合中，添加所有在集合A中缺失的“自环序偶”(x,x)。关系图视角检查并补全自环操作：逐一检查关系图中的每一个节点，如果节点没有从自身指向自身的“自环”，则添加一个自环。关系矩阵视角对角线全置为1操作：在关系矩阵MR中，无论主对角线上原有的元素是0还是1，将其全部统一修改为1。对称闭包s(R)的求解方法集合运算s(R)=R∪R⁻¹操作：在关系R的序偶集合中，检查每一个单向序偶<x,y>，并将其对应的反向序偶<y,x>补充加入到集合中。关系图法操作：遍历关系图中的每一条有向边。如果只存在从节点x指向节点y的单向边，而不存在y到x的边，则在图中增加一条从y到x的反向有向边。关系矩阵法操作：确保矩阵是对称矩阵。即对矩阵中的所有元素，如果第i行第j列的元素M[i,j]=1，则必须将第j行第i列的元素置为1，以满足M=Mᵀ(M的转置)。传递闭包t(R)的求解方法🎯目标：通过扩充有序对、添加直接边或调整矩阵元素，使关系具备传递性。集合运算视角公式定义：t(R)=R∪R²∪R³∪...操作：若存在<x,y>和<y,z>，则必须添加<x,z>。重复此过程直到没有新序偶加入。关系图视角基于“路径”的直观理解操作：若存在从x到y和y到z的边，且无x到z的直接边，则需为其添加一条直接边。关系矩阵视角基于布尔矩阵的逻辑运算操作：确保对任意i,j,k，若矩阵元素M[i,j]=1且M[j,k]=1，则必有M[i,k]=1。这与矩阵的布尔幂运算相对应。传递闭包概念示意：路径与直达边例题3.34：闭包求解题目：设集合A={a,b,c}，且在A上定义二元关系R={<a,a>,<b,b>,<a,c>}。请分别求出R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)。自反闭包r(R)自反闭包要求集合中每个元素都存在自环。观察关系R，元素c缺少自环，需补充。解：

r(R)={<a,a>,<b,b>,<a,c>,<c,c>}对称闭包s(R)对称闭包要求若有边<x,y>，则必有反向边<y,x>。现有边<a,c>，缺少反向边。解：

s(R)={<a,a>,<b,b>,<a,c>,<c,a>}传递闭包t(R)传递闭包要求若有<x,y>和<y,z>，则必有<x,z>。R中所有有序对均不满足可推导的传递条件，因此R本身已传递。解：

t(R)={<a,a>,<b,b>,<a,c>}=R例题3.35：利用集合运算求闭包题目：设集合P={1,2,3,4}，二元关系R={<1,2>,<1,3>,<2,4>,<3,4>}，试利用序偶集合运算，分别求出R的自反闭包、对称闭包和传递闭包。自反闭包r(R)定义公式：r(R)=R∪IP计算结果：{<1,2>,<1,3>,<2,4>,<3,4>,<1,1>,<2,2>,<3,3>,<4,4>}对称闭包s(R)定义公式：s(R)=R∪R-1计算结果：{<1,2>,<1,3>,<2,4>,<3,4>,<2,1>,<3,1>,<4,2>,<4,3>}传递闭包t(R)定义公式：t(R)=R∪R²∪R³∪R⁴其中R²={<1,4>},更高次幂无新序偶。计算结果：{<1,2>,<1,3>,<2,4>,<3,4>,<1,4>}定理3.13：闭包与原关系的等价性设R是集合X上的二元关系，那么：01.R是自反的，当且仅当r(R)=R。02.R是对称的，当且仅当s(R)=R。03.R是传递的，当且仅当t(R)=R。必要性·Necessity如果关系R已经具备了某种性质（自反、对称或传递），根据闭包“包含原关系且具有该性质的最小关系”的定义，R自身就是满足该定义的最小关系，因此它的闭包就是它自己。充分性·Sufficiency若R的某种闭包等于它本身，即r(R)=R(或s(R)=R,t(R)=R)。由于闭包运算的结果一定具备对应的性质，因此可以直接推出原关系R也具有该性质。定理3.14：闭包的集合表示公式01.自反闭包(ReflexiveClosure)r(R)=R∪IX其中IX为集合X上的恒等关系02.对称闭包(SymmetricClosure)s(R)=R∪R-1其中R-1为关系R的逆关系03.传递闭包(TransitiveClosure)t(R)=R∪R²∪R³∪...也记作R⁺(R的传递闭包)证明思路(ProofIdea)要证明上述公式成立，需验证它们满足闭包定义的三个核心条件：

1.具有性质：结果关系必须分别具备自反性、对称性、传递性；

2.包含原关系：原关系R必须是结果关系的子集；

3.最小性：结果关系必须是满足上述两个条件的所有关系中最小的那一个。定理3.15：有限集上传递闭包的有限性设X是含有n个元素的有限集合，R是X上的二元关系，则存在一个正整数k≤n，使得：t(R)=R∪R²∪R³∪...∪Rᵏ核心结论在有限集上，传递闭包的计算不需要无限进行下去，最多计算到Rⁿ即可。这为算法实现提供了理论依据和明确的迭代上限。证明思路(鸽巢原理)假设存在一条长度p>n的路径，根据鸽巢原理，序列中必有重复的节点。可以“短路”掉这部分重复节点，得到一条更短的路径。因此，集合中任意两点之间的最长简单路径长度不超过集合的元素个数n。利用关系矩阵求传递闭包核心算法原理传递闭包的关系矩阵由原矩阵的各次布尔幂累加得到，是一种非常适合程序化计算的经典方法：Mt(R)=MR+MR(2)+...+MR(n)•定义：MR(k)表示关系矩阵MR的k次布尔幂。

•规则：矩阵元素加法为逻辑“或”(OR)，乘法为逻辑“与”(AND)。例题3.36演算已知集合与关系：

设集合A={a,b,c,d}，关系R={<a,b>,<b,a>,<b,c>,<c,d>}。

通过计算矩阵M(R)的1至4次布尔幂并进行逻辑加，即可求得传递闭包。最终传递闭包t(R)：

{<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}Warshall算法：高效计算传递闭包算法背景当集合元素较多时，直接进行矩阵幂运算来求解传递闭包非常繁琐且效率较低。Warshall算法提供了一种时间复杂度为O(n³)的更高效的方法，通过迭代更新来计算。核心思想依次将图中的每个节点k视为中间节点，检查所有节点对(i,j)是否存在路径i→k→j。若存在，则直接建立一条i到j的直接路径（在矩阵中置为1），从而逐步构建出完整的传递闭包。执行步骤1.初始化：设结果矩阵A为原关系矩阵M。

2.迭代更新：遍历每个中间节点k，若存在路径i->k且k->j，则令A[i,j]=1。

3.终止条件：所有节点作为中间节点检查完毕后，A即为t(R)。算法优势与特点相比直接计算矩阵幂，Warshall算法不仅在代码实现上更简洁，且避免了重复的矩阵乘法运算。该算法不涉及算术运算，仅包含简单的逻辑“或”操作，非常适合计算机处理。例题3.37：Warshall算法演示输入矩阵M[0100][1010][0001][0000]图的邻接矩阵表示

寻找从节点i到j的所有路径执行步骤1.初始化：令辅助矩阵A等于输入矩阵M。2.第1次迭代(i=1)：检查第1列，找到A[j,1]=1的行j=2，将第2行与第1行进行逻辑加(OR)。3.第2次迭代(i=2)：检查第2列，找到A[j,2]=1的行j=1,2，将第1、2行分别与第2行逻辑加。4.第3次迭代(i=3)：检查第3列，找到A[j,3]=1的行j=1,2，将第1、2行分别与第3行逻辑加。5.第4次迭代(i=4)：检查第4列，找到A[j,4]=1的行j=1,2,3，将第1、2、3行分别与第4行逻辑加。输出矩阵A[1111][1111][0001][0000]图的传递闭包矩阵

A[i,j]=1表示i可达j定理3.16：闭包运算的顺序设R是集合X上的二元关系，则：01rs(R)=sr(R)自反闭包的对称闭包

等于对称闭包的自反闭包02rt(R)=tr(R)自反闭包的传递闭包

等于传递闭包的自反闭包03ts(R)⊇st(R)传递闭包的对称闭包

包含对称闭包的传递闭包💡重要启示闭包运算的顺序并非总是可交换的，特别是涉及传递闭包和对称闭包时，ts(R)总是包含st(R)，但反之不一定成立。本节核心知识点回顾闭包的定义在关系代数中，闭包是指：最小的、包含原关系、并具有特定性质（如自反性、对称性、传递性）的关系。三种基本闭包•自反闭包r(R)：为原关系图中所有缺少自环的顶点添加自环。

•对称闭