二元关系中传递性的若干研究.doc

二元关系中传递性的若干研究第28卷第2期2011年6月苏州科技学院(自然科学版)journalofsuzhouuniversityofscienceandtechnology(naturalscience)v01.28no.2jun.2011二元关系中传递性的若干研究汪小燕(安徽工业大学计算机学院,安徽马鞍山243032)摘要:二元关系的传递性有时不好判断,通过对二元关系传递性定义的深入分析,给出了传递性判断的等价定义及定理,利用该等价定义及定理可以较快地实现二元关系传递性的判定.关键词:二元关系;传递性;恒等关系中图分类号:0158文献标识码:a文章编号:16720687(2011)02003703传递性是二元关系中的一个重要性质,判断一个二元关系是否具有传递性.在有些情况下比较困难.传递性的判断可以直接根据定义,也可以结合关系图或关系矩阵来判断i】-5,而利用关系图或关系矩阵判断传递性,有可能导致遗漏了某些序偶,出现误判.文献【6通过对二元关系传递性定义的深入分析,对传递性的前提条件进行补充,给出一种与文献71等价的定义形式,利用该等价定义可以较好地实现二元关系传递性的判定.而二元关系中,通常包含有类似于,>这样的序偶,文中研究了这一类序偶是否对传递性有影响,并在文献6】的基础上给出了传递性等价的定义和定理以及传递性的相关理论.1相关理论定义1二元关系是集合,b的笛卡尔积的子集,是有序对的集合,即=,y>lxa八yb),当a=时称为集合(或b)上的二元关系.定义2ta设尺是集合到】,的关系,s为y到z的关系,则称尺.s为尺和is的复合关系,表示为r.s=<,z>lxx八八(y)(yy八<,),>r八<y,>5)定义3rnr为集合上的二元关系,对于任意0,b,ca,当<ct,6>r且<6,c>r时,有<口,c>r,称为上的传递关系.或者说在a上具有传递性.实现传递性的判定一般按照定义3中的条件依次对中的每一序对<0,6>,检查是否存在序对<6,c>,以及<口,c>er.当存在序对<6,c>r时,容易判定<0,c>r或<0,c>簪r;当不存在序对<6,c>r时,由于在定义3的条件中没有明确给出这一情况,直接根据定义3有时不好判定二元关系的传递性.文献【6】通过对定义3的分析,给出以下关于传递性的等价定义.定义4阍r为集合a上的二元关系,如果对于v<0,6>r,有<6,c>隹r,或<6,c>r且<,c>r,则称尺为上的传递关系,或者说在a上具有传递性.定理18】设尺为上的关系.则尺在a上传递当且仅当.尺.定义5设r是集合a上的二元关系,对于每一个a,>r,且对于任意,ya,如果),则,岳r,则尺称为中的恒等关系,记作厶.2传递性质的新理论定义6设是集合a上的二元关系,若=,>a且,>rl,则称为r中的第一元素和第二元素相等的序偶的集合.收稿日期2010一l112【基金项目】安徽省教育厅自然科学基金资助项目(kj2009b074z);计算机软件新技术国家重点实验室开放课题基金资助项目(kfkt2010b02)【作者简介汪小燕(1974一),女,安徽桐城人,副教授,硕士,研究方向为:数据挖掘,粗糙集理论.38苏州科技学院(自然科学版)2011丘定理2设是集合a上的二元关系,设尺=,如果具有传递的性质,则r一定是传递关系.证明如果为空集,定理2显然成立.若不为空集,对任意0,ba,若有<.,d>r,且<,6>r或<6,n>r,按照复合的定义,就一定有<,6>r或<6,>r.因此,判断尺是否具有传递性,可以不考虑中的所有序偶.定理2指出判断集合上的二元关系是否具有传递性,可以不考虑中的所有序偶.因此,结合定义4给出以下传递性判断的等价定义.定义7尺为集合上的二元关系,设尺:尺一,如果对于:v<,6>r,有<6,c>甓r,或<6,c>r且<.c>r,则称为a上的传递关系或者说r在a上具有传递性.定义7也可以表达成如下蕴含的形式.定义8r为上的二元关系,设尺=尺,尺在上传递铮(v0)(vb)(vc)(口a八bacaarb八brcc).定理3r为a上的二元关系,设r=r一,则r在a上传递当且仅当r.尺.证明由定理1及定理2可证.在二元关系中,如果不为空集,则应用定义7,定义8或者定理3都可以很快地判定r的传递性.比文献68花费的时间少,如果为空集,则文中的判断方法和文献【6,文献8一样.例1设集合a=1,2,3,4),r是a上的二元关系,尺=<1,1>,<1,2>,<1,3>,<2,3>,<3,3>,<4,4>试判定r的传递性.解应用传递性的等价定义7,由于r=(<1,2>,<1,3>,<2,3>l对尺中的序对<1,2>,有<2,3>r且<1,3>r;对r中的序对<1,3>,没有<3,x>r(va);对中的序对<2,3>,没有<3,>er(va);因此.该二元关系是传递的.对例1采用定理3判断如下:由于r=<1,2>,<1,3>,<2,3>),则尺.r=<1,3>,而<1,3>)c_r,因此,该二元关系是传递的.推论1r为a上的二元关系,如果r厶,则r一定是传递关系.证明如果厶,则r=尺一咖,而=,所以.r,根据定理3知是传递关系.推论2尺为a上的二元关系,如果ir一:1(表示集合的基数),则r一定是传递关系.证明如果ir一l_1,设r=r一,则尺中只有一个序偶,所以尺.尺=咖,根据定理3知推论2成立.推论3尺为a上的二元关系,且尺为传递关系,令c=厶一,如果将关系c中的任何一个序偶添加到r中,都不会改变尺的传递性质.推论4r为a上的二元关系,且r为传递关系,设r:尺一,mrr是关系r的关系矩阵,对任意口,ba,且6,<,6>r,并且在韵第b行与第口列都没有1,如果将序偶<0,6>添加到r中,则r的传递性质不会改变.推论5尺为上的二元关系,且r为传递关系,:尺一,令b=r.r,如果bn=rk,则将中的任何一个序偶删除.都不会改变r的传递性质.推论6r为上的二元关系,且为传递关系,设r=r一,mr,是关系的关系矩阵,对任意,ba,且0b,<口,6>r,并且在,的第b行与第口列没有1,如果将序偶<0,6>从尺中删除,则r的传递性质不会改变.推论7尺为4上的二元关系且为反自反的关系,对0,ba,若有<口,6>er,且<6,r,则一定不是传递关系.证明假设是传递关系,由于<0,6>r,且<6,口>r,则<口,口>r,<6,6>r,这与r是反自反的关系矛盾.所以推论7成立.推论8尺为上的二元关系且尺,若r为反自反和对称的关系,则一定不是传递关系.证明由推论7可证.定理4r为上的二元关系,r=,令.,如果尺是传递关系,则一定是传递关系.证明假设b不是传递关系,存在序偶,y>b,<y,>b,而,z>隹b,因为是传递关系,根据定理第2期汪小燕:二元关系中传递性的若干研究393,则r.rc_r,即bc_r,所以,y>r,>r,又因为=一,则,y>r,>r,一定会存在,>rtor,即,>b,与假设矛盾,故定理4成立.定理5r为a上的二元关系,r=一,令b=rtor,如果是传递关系,且尺r,则rub一定是传递关系.证明设r=rub,则r=urub,由于不影响关系的传递性,所以只需要证明u尺具有传递性质,由于b是传递关系,则西b_cbr.又因为b.r_cr,所以.r.而复合运算满足结合性,所以,曰or=(.r).r=尺to(r.r)=.br,另外.r=bc_r,因此具有传递性质,即ub一定是传递关系.例2设集合a=1,2,3,4,尺是上的二元关系,:<1,l>,<2,2>,<1,2>,<2,3>,<3,4>,<1,4>lr=r一1r,b=r.r,试判定ub的传递性.解由于r=f<l,2>,<2,3>,<3,4>,<1,4>,则b=r.r=<1,3>,<2,4>),显然具有传递性.而r=<1,4>,根据定理5知rub具有传递性.推论9r为上的二元关系,r=一,令b=r.r,如果,则rub一定是传递关系.证明由于b厶,所以b是传递关系,设,>是b中的任意序偶,若在中不存在序偶,y>,则.=c_rr,若在r中存在序偶,y>,则,y>b.r,所以b.尺,由定理5可证该推论成立.3结语二元关系中通常包含有类似于,>这样的序偶,笔者对传递性的定义进行研究,提出在判断二元关系的传递性时,可以直接判断一的传递性,提高了传递性的判断效率,并给出了传递性的新理论和相关证明.新的理论对于传递性的判断有一定的指导意义.参考文献:1】郭树林.有限集上可传递二元关系的矩阵判别方法【j】.南京t程学院,2003,1(1):6772.【2韩俊英.基于矩阵的二元关系研究jj.甘肃农业大学,2004,39(4):467469.3】张玲萍.利用关系矩阵判断二元关系的传递性j1.宝鸡文理学院:自然科学版,2006,26(4):276278【4】孙凤芝.二元关系传递性的矩阵判别法ji.大庆师范学院,2008,28(5):7478【5吴鹏.有限集上二元关系传递性的矩阵判别法.i.成都大学:自然科学版,2009,28(2):122125.【6】杨思春,王小林.二元关系传递性研究j1.微机发展,2003,13(10):8889.7】左孝凌,李为鉴,刘永才.离散数学(m】.上海:上海科学技术文献m版社,1982.【8】耿素云,屈婉玲.离散数学m】.北京:高等教育出版社,2005:8892.studiesonthetransmissionofbinaryrelationwangxiaoyan(schoolofcomputerscience,anhuiuniversityoftechnology,maanshan243032,china)abstract:thetransmissionofabinaryrelationisdifficulttodecide.basedonthoro