如何判断传递性离散数学

2023-10-23 12:17:30 178次

问题描述：

离散数学怎么判断传递性

2023-10-23 12:17:30

例如:R2计算传递闭包如下:

R2={(1,2),(2,3)}

存在上述情况,把(1,3)加入形成R2

R2={(1,2),(2,3),(1,3)}

所有计算结束与R2不同,所以不是传递关系.若R2是{(1,2),(2,3),(1,3)}则是传递关系.

而R和R1计算结果不变,所以是传递的. 扩展资料

传递关系判断离散数学中有定理可以判断,通过矩阵变换等.

定理算比较麻烦,可以如下计算,其实是计算传递闭包与原关系是否一样,一样则是传递关系,否则不是传递关系.就是关系中一个元素的第二个分量若与另外一个元素的第一个分量相同,则把前者的第一分量与后者的.第二个分量组成元素加入关系中.

直到所有这样的情形找出,计算完毕。

2023-10-23 12:17:30

所谓传递就是：

在R中，每当xRy，yRz，就必定有xRz。

符号表示就是：有<a,b>,<b,c>那么就一定有<a,c>

我们用个例子来说明吧。

设A={a,b,c} 判断下列关系是否有传递性：

R1={<a,b>,<b,a>,<a,a>}

R2={<a,b>,<c,c>}

R1就没有传递性。

因为存在<b,a>,<a,b>但是不存在<b,b>

R2却有传递性。

因为不存在某个关系的第一序偶和另一个的第二序偶相同。

即<×××,a>,<a,×××>的情形