二元关系的传递性(2)
时间:2019-09-18 12:47 来源:毕业论文 作者:毕业论文 点击:次
在本题中，对 中的有需对 < 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个顶点 ， ， ，， 。如果< ， > ， 在 中就有一条从 到 的有向边。 关系图法判断传递性的特点：任意 ，如果 到 有边， 到 有边，则从 到 也有边的话，则关系 是传递的 (责任编辑：qin) |