a={1,2,3,4}上的关系r={<1,1>,<1,2>,<1,4>,<2,1>,<2,2>,<3,2>,<3,4>,<4,2>,<4,4>}\n从键盘输入关系r的矩阵,计算其自反闭包、对称闭包和传递
时间: 2023-05-31 10:20:21 浏览: 1244
离散数学-关系,集合,求自反闭包,对称闭包,传递闭包
### 回答1:
题目中给出的是一个集合a和关系r,其中集合a有元素1、2、3、4,关系r是一个有序对的集合,其中有(1,1)、(1,2)、(1,4)、(2,1)、(2,2)、(3,2)、(3,4)、(4,2)、(4,4)这些有序对。从键盘输入关系r的矩阵,计算其自反闭包、对称闭包和传递闭包。
### 回答2:
首先,将输入的关系r转化为矩阵形式,如下所示:
1 2 3 4
1 1 1 0 1
2 1 1 0 1
3 0 1 0 1
4 0 1 0 1
其中,矩阵中第 i 行第 j 列的元素表示 a 中第 i 个元素和第 j 个元素之间的关系,1 代表有关系,0 代表无关系。
计算自反闭包,需要将矩阵中的每个对角线元素改为 1,即 r 中元素 <1,1>、<2,2>、<3,3>、<4,4> 后的矩阵为:
1 2 3 4
1 1 1 0 1
2 1 1 0 1
3 0 1 1 1
4 0 1 0 1
可以发现,此时的矩阵已经成为自反关系,因为每个元素与自己之间都有关系。
计算对称闭包,需要将矩阵中对称位置的元素都修改为相同的值,让其成为对称关系,即将矩阵中的下三角部分镜像到上三角,并采用相对应的值,其结果为:
1 2 3 4
1 1 1 0 1
2 1 1 1 1
3 0 1 1 1
4 1 1 1 1
可以发现,此时的矩阵已经成为对称关系,因为如果 a 与 b 有关系,那么 b 与 a 也一定有关系。
计算传递闭包,需要通过矩阵的乘法来实现。设 r2 表示关系 r 的平方,即 r2=rxr,可以通过矩阵乘法来计算得到。然后,将 r2 的元素与 r 中的元素合并,得到新的矩阵,重复这个过程直到新得到的矩阵不再改变为止,即可得到传递闭包。
经过计算得到 r2 矩阵为:
1 2 3 4
1 2 3 0 3
2 2 3 0 3
3 1 2 0 2
4 1 2 0 2
合并后的矩阵为:
1 2 3 4
1 2 3 0 3
2 2 3 1 3
3 1 2 0 2
4 1 2 0 2
再重复这个过程,得到的矩阵不再变化,其结果为:
1 2 3 4
1 2 3 0 3
2 2 3 1 3
3 1 2 0 2
4 1 2 0 2
可以发现,此时的矩阵已经成为传递关系,因为如果 a 与 b、b 与 c 都有关系,那么 a 与 c 也一定有关系。
因此,最终得到的结果是:
自反闭包为:{<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,4>,<2,1>,<2,4>,<3,2>,<3,4>,<4,2>}
对称闭包为:{<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,4>,<3,2>,<4,1>,<4,2>,<4,3>}
传递闭包为:{<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,2>,<3,4>,<4,2>}
### 回答3:
关系r={<1,1>,<1,2>,<1,4>,<2,1>,<2,2>,<3,2>,<3,4>,<4,2>,<4,4>}是定义在集合a={1,2,3,4}上的二元关系,其中<r1,r2>表示集合中的元素r1和r2具有某种关联。
首先,关系r的矩阵可以表示为:
1 1 0 1
1 1 0 0
0 1 0 1
0 1 1 1
其中1表示关联存在,0表示关联不存在。
计算自反闭包时,需要将关系矩阵中的所有不自反的元素变成自反的,即<r1,r1>加入关系r中。因此,关系r的自反闭包为:
{<1,1>,<1,2>,<1,4>,<2,1>,<2,2>,<3,2>,<3,4>,<4,2>,<4,4>}
计算对称闭包时,需要将关系矩阵中的所有不对称的关联在矩阵中对称的位置加入关系r中,即如果存在<r1,r2>,则加入<r2,r1>。因此,关系r的对称闭包为:
{<1,1>,<1,2>,<1,4>,<2,1>,<2,2>,<2,4>,<3,2>,<3,4>,<4,1>,<4,2>,<4,4>}
计算传递闭包时,需要将关系矩阵中的所有不传递的关联在关系矩阵中传递的位置加入关系r中,即如果存在<r1,r2>和<r2,r3>,则加入<r1,r3>。因此,关系r的传递闭包为:
{<1,1>,<1,2>,<1,4>,<2,1>,<2,2>,<2,4>,<3,2>,<3,4>,<4,1>,<4,2>,<4,4>,<1,4>,<3,2>,<3,4>}
这里得到了关系r的自反闭包、对称闭包和传递闭包,分别为:
自反闭包:{<1,1>,<1,2>,<1,4>,<2,1>,<2,2>,<3,2>,<3,4>,<4,2>,<4,4>}
对称闭包:{<1,1>,<1,2>,<1,4>,<2,1>,<2,2>,<2,4>,<3,2>,<3,4>,<4,1>,<4,2>,<4,4>}
传递闭包:{<1,1>,<1,2>,<1,4>,<2,1>,<2,2>,<2,4>,<3,2>,<3,4>,<4,1>,<4,2>,<4,4>,<1,4>,<3,2>,<3,4>}
以上分别为对应的自反矩阵、对称矩阵和传递矩阵。其中,自反闭包、对称闭包和传递闭包都是原始关系r的超集。
阅读全文