（2）s?R??R?R?i?1
?（3）t?R???R，t?R?通常也记作R。
i?1证明 （1）令R'?R?IX，
?x?X，因为x,x?IX，故x,x?R，于是R在X上是自反的。
''又R?R?IX即R?R。若有自反关系R??且R???R，显然有R???IX，于是
R???R?I?X'?1'' ，所以 r?R??R?1?1R?XI。
（2）令R?R?R， 因为 (R?R)'?R?1?(R?1)?1?R?1?R?R?R?1
所以R是对称的。
若R??是对称的且R???R，
?x,y?R，则x,y?R或x,y?R'?1。
当x,y?R时，x,y?R??； 当x,y?R?1时，y,x?R，y,x?R??，x,y?R??。
?1因此 R'?R??，故 s?R??R?R'?ii?1。
'（3）令R??R，先证R是传递的。
?x,y?R，y,z?R，则存在自然数k,l，有 x,y?R，y,z?R，因此
x,z?Rk?l?i?1''kl??R，所以，R是传递的。
'i'显然，R?R。若有传递关系R??且R???R，
?x,y?R，则存在自然数m，有 x,a,a,a2?,11,ma?1'x,y?Rm，则 ?ai?X(i?1,2,?,m?1)，使得
,?y'R，因此x,a1,a1,a2,?,am?1,y?R??，由于R??是传递关系，
则x,y?R??，所以R???R。故
t?R???R。
i?1?i}求例3.8.1 设X?{x,y,z}，R是X上的二元关系，R?{x,y,y,z,z,x，r?R?,s?R?,t?R?。
解 r?R??R?IX??x,y,y,z,z,x,x,x,y,y,z,zs?R??R?R?1?
??x,y,y,z,z,x,y,x,z,y,x,z?
为了求得t?R?，先写出
94
MR?0??0???1?0??0???11001000??1?0??0??0??1?1???0???02001MR21??0?0??
即
R?2?x,z,y,x,z,y?0??1???0001?1??0??0?0??0????11000??1??1?0??0????00100? ?0?1??MR3?M2R?MRR?3?x,x,y,y,z,z?1??0???0?0100??0??0?0??1????11000??0??1?0??0????11000??1?0??MR4?MR3?MRR5424??x,y,y,z,z,x??RR?R?R?R
继续这个运算有：
R?R???R2543n?1
R?R???R
363n?3R?R???R ?n?1,2,??
t?R???R?R?R?R???R?R?R
i?1?i23233n?2 ??x,y,y,z,z,x,x,z,y,x,z,y,x,x,y,y,z,z闭包t?R?不必计算到对R的无限大次复合，而最多不超过n次复合。
?
从以上例题中看到，若X有限，譬如含有n个元素，那么求取X上二元关系R的传递定理3.8.3 设X是含有n个元素的集合，R是X上的二元关系，则存在一个正整数k?n，使得t?R???R
i?1ki证明 设xi,xj?X，记t?R??R。
若xiRxj，则存在整数p?0，使得xiRxj成立，既存在序列a1,a2,?ap?1，
ai?X(i?1,2,?,m?1)，有xiRa1,a1Ra2,?,ap?1Rxj。
?P?设满足上述条件的最小p大于n，不妨xi?a0,xj?ap，则序列中必有0?t?q?s?p，使得at?aq或aq?as。不妨at?aq，此时序列就成为
95
xiRa1,a1Ra2,?,at?1Rat，atRaq?1,?,ap?1Rxj ????????????????????t个(p?q)个这表明xiRxj存在，其中k?t?p?q?p?(q?t)?p，这与p是最小的假设矛盾，所以，
p?n不成立，即p?n。
kk所以 t?R???R （k?n）
i?1i一般地，取t?R???R，式中的n给出了复合次数的上限。
i?1ni例3.8.2 设A?{a,b,c}，给定A上的关系R?{a,a,a,b,b,c,c,c}，求t?R?。 解 t?R???R
i?13iMR?1??0???010010020??1 ?1??1001??1 ?1??MR2?1??0???00??1??1?0???1???0MR3?1??0???01001??1??1?0??1????0?1??0???01001000??1??1?0??1????01??1 ?1??1001??1?1??所以
M
t?R?即 t?R??{a,a,a,b,a,c,b,c,c ,c}为计算元素较多的有限集合X上二元关系R的传递闭包， Warshall在1962年提出了一个
有效的算法（假定集合X含有n个元素）：
（１） 置新矩阵M：?MR；
（２） 置i：?1；
（３） 对j?1,2,?,n，若rji?1（MR???，则置rjk：?rjk?rik，k?1,2,?,n； ?rij?m?n）
（４） i：?i?1；
（５） 如果i?n，则转到步骤（3），否则停止。 例3.8.3 已知M?1??0???01000???1，求R。 ?1??R 解 按照Warshall算法，从MR出发，只要遵循“置行查列遍寻真(1)，见真行上析当今(i)，
96
行推列移下右再，行穷列尽闭包成(MR?)”便可直接求得MR?R?。
对集合上关系R，首先将其关系矩阵M?1??0???01000??1 ?1??赋予M：
M?MR而后的每后一次循环重复操作， 均在前一次操作结果的矩阵M上进行。
置当今行为第1行，查看第1列中1，对有1的行进行改写，改写方法是：将当今行 的元素与列中有1的行的元素分别做析取。对本例，i?1时，第1列中只有r11?1，将第一行与第一行各对应元素进行逻辑加，仍记于第一行：
?1?0???01000??1??1?0???1???01000??1； ?1??置当今行为第2行， 查看第2列中1， 对有1的行进行改写。对本例，i?2时，第二列
中r12?1，将第二行与第一行各对应元素进行逻辑加，仍记于第一行：
?1??0???01001??1； ?1??i?3时，置当今行为第3行，重复上述操作并结束。对本例，第三列中r13?1,r23?1,r33?1，
将第三行分别与第一行、第二行、第三行各对应元素进行逻辑加，仍分别记于第一行、第二行、
第三行：
?1??0???0?1001??1 ?1??,c得 R?{a,a,a,b,a,c,b,c,c。 }结果与例3.8.2一致。
传递闭包R在语法分析中有很多应用，先以下列说明/
例3.8.4 设有一字母表V?{A,B,C,D,e,d,f}并给定下面六条规则：
A?Af,B?Dde,C?eA?B,B?De,D?Bf?
R为定义在V上的二元关系且xiRxj，即是从xi出发用一条规则推出一串字符，使其第一个字
符恰为xj。说明每个字母连续应用上述规则可能推出的头字符。
解
97
MR?1?0??0???0?0??0?0?100100000000000100000001000000000000??0?0??0? 0??0?0??则xiRxj表示从xi出发，经过多次连续推导而得的字符串，其第一个字符恰为xj的关系，此关系即是R?。按照Warshall算法计算的过程中，i?5时，由于第五行的元素都等于零，M的赋值不变。i?3,i?6,i?7时，由于第3、6、7列各元素均为零，M的赋值不变。经计算得
?1?0??0???0?0??0?0?11010000??0100?0010??0100?00000??00000?00000??010000? MR? 0因此R?{A,A,A,B,A,D,B,B,B,D,C,e,D,B,D,D}。
这说明应用给定的六条规则，从A出发推导的头字符有A,B,D三种可能，而从B出发推导的头字符有B,D两种可能，而从D推出的头字符有B,D两种可能，从C出发推导的头字符
只可能为e。
从一种性质的闭包关系出发，求取另一种性质的闭包关系，具有以下运算律： 定理3.8.4 设R是集合X上的二元关系，则
（1）rs?R??sr?R? （2）rt?R??tr?R? （3）ts?R??st?R?
证明 （1）sr?R??s?r?R???s?IX?R???IX?R???IX?R?
??IX?R???IX?R?1?1这里，IX?IX。
??1?1??I?X?R?R?1?IX?s?R??r?s?R???rs?R?
（2）tr?R??t?IX?R????IX?R?i?1??ii?j????IX??R? i?1?j?1??i?IX???Ri?1j?1j?IX??R?IX?t?R??r?t?R???rt?R?
ii?1k这里，IX?R?R?IX?R，IX?IX（k?1,2,?）。
98