在本题中,对 中的有需对 < 1,1 >,存在<1,2> <1,3> ,以及
<1,2> ,<1,3> 对 中的有序对 <1,2> ,有 < 2,3> 以及
<1,3> ,但对 中的需对<1,3> ,< 2,3>,由于不存在< 3,x> (x )
直接根据定义不好判定该二元关系是否具有传递性,面对这样的问题,我们给出以下的二元关系传递性的等价定义:
2 二元关系传递性的等价定义及其应用
2.1.1 [9]定义 设 是 上的关系,若满足
x y z (x,y,z A <x,y> →<y,z> (<y,z> <x,z> ))则称 为 上传递的关系。
利用此定义也可以判定例1中关系 是传递的
例2已知 = ,
= ,判断 是否为传递关系。
解:对 中的有序对< a, b >,有 <b,c> 且有<a,c> ;
对 中的有序对< e, e>,有 <e,d> 且有<e,d> ;
对 中的有序对<e,d>,有<d,c> R且有<e,c> ;
对 中的有序对< a, c >,<b,c>, <e,c> ,<d,c>, ,但没有<c,x> ,所以蕴
含式的前件为假,则蕴含式为真。
因此,此关系是传递的。
2.2.1 [1]定义 设 =( ), =( )是两个关系矩阵,如果 < ,i,j=1,2,3n,则称 不超过 ,记做 ≦ ,
2.2.2[1]定理 在 上可传递的充要条件是 。
证明 必要性
任取<x,y> 有 <x,y>
t( <x,t> <t,y> )
<x,y> (因为R在A上是传递的)
所以 。
充分性 任取<x,y> ,<x,y> ,则
<x,y> <y,z> ,
<x,z>
<x,z> (因为 )
所以 在 上是传递的。
3关系图
判定二元关系的传递性还有一个方法是关系图法:
3.1.1[1]定义 设 = , 是 上的关系, 的关系图记做 , 有n个顶点 , , ,, 。如果< , > , 在 中就有一条从 到 的有向边。
关系图法判断传递性的特点:任意 ,如果 到 有边, 到 有边,则从 到 也有边的话,则关系 是传递的
- 上一篇:MATLAB拉格朗日插值算法及实现
- 下一篇:三面角的性质与应用
-
-
-
-
-
-
-
乳业同业并购式全产业链...
酸性水汽提装置总汽提塔设计+CAD图纸
十二层带中心支撑钢结构...
java+mysql车辆管理系统的设计+源代码
当代大学生慈善意识研究+文献综述
大众媒体对公共政策制定的影响
河岸冲刷和泥沙淤积的监测国内外研究现状
杂拟谷盗体内共生菌沃尔...
中考体育项目与体育教学合理结合的研究
电站锅炉暖风器设计任务书