集合论

格牛

当有限集A的元素较多时，对关系R的传递闭包t（R）进行矩阵运算，还是显得很为繁琐。为此，沃舍尔①在1962年提出了t（R）的一个有效算法。
沃舍尔算法计算t（R）关系矩阵M=（mij）的步骤如下：
（1）M赋初值R的关系矩阵MR；
（2）置k=1；
（3）对所有i如果A[i，k]=1，则对j=1，2，…，n执行： A[i，j]←A[i，j]A[k，j]；
（4）k增1；
（5）如果k≤n，则转到步骤（3），否则停止。
所得的矩阵A即为关系R的传递闭包t（R）的关系矩阵。
沃舍尔算法从关系矩阵M的第一列开始到第n列结束，逐步检查其每行元素是否为1，若mij=1，则将第j行元素对应加（布尔加）到第i行元素上去。
问题：如何证明沃舍尔算法的结果就是所求的传递闭包？