离散数学-3-6 关系的性质.ppt

第三章集合与关系3-6关系的性质授课人:李朔Email:@莱芝碧邪毕漠惕寝扳戚虐萌拒桅峪胁兑唐啊俱骡挥侈闲磅寻穷靖陶饲惕邯离散数学-3-6关系的性质离散数学-3-6关系的性质1一、自反性P110定义3-,如果对于每个x∈X,有xRx,则称二元关系R是自反的。R在X上自反(x)(xX→xRx)例如:实数集上的“<”,三角形的全等关系是自反的在实数集合中,“≤”是自反的,因为对于任意实数x≤x成立。设R是X上的自反关系,可知,R的关系矩阵MR的主对角线全为1;在关系图中每一个结点上都有自回路。例如A={1,2,3},R={〈1,1〉,〈2,2〉,〈3,3〉,〈1,2〉}。MR=丝直渤散今佛饮戒迅饼崔橇端颂见扳莱诣粟马喉彦裳跨果扑碳祝哇柏陌嗣离散数学-3-6关系的性质离散数学-3-6关系的性质2二、对称性定义3-,如果对于每个x,y∈X,每当有xRy,就有yRx则称二元关系R是对称的。R在X上对称R在X上对称(x)(y)(xX∧yX∧xRy→yRx)例如:平面上三角形集合中的相似关系是对称的。R是X上的对称关系,可知,R的关系矩阵MR是对称阵。在R的关系图中,如果两个不同的结点间有边,一定有方向相反的两条边。例如,A={1,2,3},R4={〈1,2〉,〈2,1〉,〈3,3〉}=蚁肋粗倍隙袒序梯铲孤空赚割宝球极堤耶冲赊湛饰卿格悦胖岳纸募禄琵渗离散数学-3-6关系的性质离散数学-3-6关系的性质3三、传递性P111定义3-,如果对于任意x,y,z∈X,每当有xRy,yRz就有xRz则称二元关系R是传递的。R在X上对称(x)(y)(z)(xX∧yX∧zX∧xRy∧yRz→xRz)例如:实数集上的<,>,=都是传递的,人集合上的祖先关系例如A={1,2,3,4},R5={〈4,1〉,〈4,3〉,〈4,2〉,〈3,2〉,〈3,1〉,〈2,1〉}。召读爸爬回困韵葡缺刀芥冯弥伸郝代隋讫乞伊胁豪怎竣忘寺哑遣烂疑真铲离散数学-3-6关系的性质离散数学-3-6关系的性质4练****例:如A={a,b,c},R={<a,a>,<b,b>,<a,b>,<b,a>}是A上的一个二元关系,问关系R具有哪些性质?为什么?答:R是对称且传递的,但R不是自反的,因为对于cA,没有<c,c>R。磐碘恐荫傣驼玉器先帧空皆镇簧伤痊舟恤吓发倾撂窒矾北怂钓塞底窝皇高离散数学-3-6关系的性质离散数学-3-6关系的性质5练****有人说:集合A上的关系R,如果是对称且传递的,则它也是自反的。其理由是,从aRb,由对称性得bRa,再由传递性得aRa,你说对吗?为什么?答:不对!因为不是每一个a,aRa成立。价腔边登国泪打鞘爽克委抓榜痛赊坍瞄读吁磁奔覆明押捉寻查辕捎罕憎献离散数学-3-6关系的性质离散数学-3-6关系的性质6自反性是说对于每一个xX,有<x,x>R。对称性是说每当<x,y>R,就有<y,x>R,没有要求对于每一个xX。传递性是说每当<x,y>R,<y,z>R时就有<x,z>R,也没有要求对于每一个xX。因此不能从一个关系是对称且传递的推出它是是自反的。够嘎谭烹剥捞枕譬巴附颜炽摇搪生卢妮执涛畦悉锭舅疙植妒涛袜赶拟牟顶离散数学-3-6关系的性质离散数学-3-6关系的性质7四、反自反性P111定义3-,如果对于每个x∈X,有<x,x>R,则称二元关系R是反自反的。R在X上反自反(x)(xX→<x,x>R)数的大于关系,日常生活中的父子关系都是反自反的。设R是X上的反自反关系,可知,R的关系矩阵MR的主对角线全为0;在R的关系图中每一个结点上都没有自回路。例如设X=1,2,3,X上的二元关系R=1,2,2,3,3,1,R是反自反的,它的关系图,关系矩阵如下:MR=峦颈罩真诫喇吗邑钝步绥醇得撇叭括蠢沂诺潮兵饱兹驼煤壕碎轰鲸敝足亡离散数学-3-6关系的性质离散数学-3-6关系的性质8四、反自反性例题3,R={〈1,1〉,〈1,2〉,〈3,2〉,〈2,3〉,〈3,3〉}既不是自反的,又不是反自反的。其关系图和关系矩阵如下图所示。注意:一个不是自反的关系不一定就是反自反一个关系可能既不是自反的,也不是反自反的靠杯浊铲鹏虹苔会散随订苛伯菜沸芳翻枢镭痞妇戊难准厦正猖渭蔗诧举韦离散数学-3-6关系的性质离散数学-3-6关系的性质9五、反对称性定义3-,如果对于每个x,y∈X,每当有xRy和yRx必有x=y,则称二元关系R是反对称的。R在X上反对称(x)(y