自反性和反自反性课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3-6 关系的性质,本节讨论集合X上的二元关系R的一些特殊性质。,3-6 关系的性质 本节讨论集合X上的二元关系,1,一、自反性和反自反性,1、自反性：设R是集合X上的二元关系，如果对于每一个x,X，有,R，则称R是自反的。,R在X上自反,(,x)(x,X,R),2、反自反性：设R是集合X上的二元关系，如果对于每一个x,X，有,R，则称R是反自反的。,R在X上反自反,(,x)(x,X,R),一、自反性和反自反性,2,例如，在实数集合中，,”,”,是自反的，因为对于任意实数,x,x,成立。,平面上三角形的全等关系是自反的。,例：X=a，b，c，R1=，是自反的，R2=，是反自反的，R3=，不是自反的也不是反自反的。,注意：R不是自反的，未必一定是反自反的。一个关系可能既不是自反的，也不是反自反的。,例如，在实数集合中，”是自反的，因为对于任意实数xx成,3,3、关系矩阵的特点,自反关系的关系矩阵的对角元素均为1，反自反关系的关系矩阵的对角元素均为0。,4、关系图的特点,自反关系的关系图，每个结点均有自回路，而反自反关系的关系图，每个结点均没有自回路。,3、关系矩阵的特点,4,5、结论：,R是X上的二元关系，则：,(1)R是自反关系的充要条件是I,X,R。,(2)R是反自反关系的充要条件是R,I,X,=,。,如果|X|=n，其中n个序偶为，则X上的自反关系共有2,n*n-n,个。,例,|X|=3,，X上关系共有2,9,个，而自反关系共有2,6,个。,5、结论：,5,二、对称性和反对称性,1、对称性：设R是集合X上的二元关系，如果对于每一个x，y,X，每当,R，就有,R，则称R是对称的。,R在X上对称,(,x)(,y)(x,X,y,X,R,R),2、反对称性：设R是集合X上的二元关系，如果对于每一个x，y,X，每当,R和,R必有x=y，则称R是反对称的。,R在X上反对称,(,x)(,y)(x,X,y,X,R,R,x=y),二、对称性和反对称性,6,例如，平面上三角形的相似关系是对称的。,例：,R1=，是对称的，R2=，是对称的也是反对称的，R3=，不是对称的也不是反对称的，,R4=，是反对称的。,注意：存在关系既不是对称的，也不是反对称的。也存在关系既是对称的，也是反对称的。,例如，平面上三角形的相似关系是对称的。,7,3、关系矩阵和关系图的特点,对称关系的关系矩阵是对称矩阵，即对所有i，j，r,ij,r,ji,，对称关系的关系图，任何两个不同的结点之间，或者有双向两条弧，或者没有弧。,反对称关系的关系矩阵，如果在非对角元上r,ij,1，则在其对称位置上r,ji,0，反对称关系的关系图，任何两个不同的结点之间至多有一条弧。,3、关系矩阵和关系图的特点,8,三、传递性,1、定义：设R是集合X上的二元关系，如果对于任意x，y，z,X，每当,R，,R时就有,R，则称R是传递的。,R在X上传递,(,x)(,y)(,z)(x,X,y,X,z,X,R,R,R),例：,R1=,是传递的，,R2=,也是传递的，它没有违背定义。,R3=,不是传递的。,三、传递性,9,2、定理：设R、S是A上的传递关系，则R,S也是A上的传递关系。,注意：R、S均是传递的，但R,S未必是传递的。,例：R=，S=，则R、S均是传递的，但R,S=，不是传递的。,证明：设 R,S，,R,S,，则,R，,R且,S，,S,。因为,R、S是A上的传递关系，所以,R，,S，从而,R,S，即R,S是A上的传递关系。,2、定理：设R、S是A上的传递关系，则RS也是A上的传递关,10,有人说：集合A上的关系R，如果是对称且传递的，则它也是自反的。其理由是，从aRb，由对称性得bRa，再由传递性得aRa，你说对吗？为什么？,不对！再看自反性、对称性、传递性的定义。,有人说：集合A上的关系R，如果是对称且传递的，则,11,自反性：,设R是集合X上的二元关系，如果,对于每一个x,X，有,R,，则称R是自反的。,对称性：,设R是集合X上的二元关系，如果对于每一个x，y,X，,每当,R，就有,R,，则称R是对称的。,传递性：,设R是集合X上的二元关系，如果对于任意x,y,z,X，,每当,R，,R时就有,R,，则称R是传递的。,自反性：对称性：传递性：,12,自反性是说,对于每一个x,X，有,R,。对称性是说,每当,R，就有,R,，没有要求,对于每一个x,X，,传递性是说,每当,R，,R时就有,R,，也没有要求,对于每一个x,X。,因此不能从一个关系是对称且传递的推出它是是自反的。,例如,A=a，b，c，,R=，是A上的一个二元关系，R,是对称且传递的，但R不是自反的，因为对于c,A，没有 R。,自反性是说对于每一个xX，有R。对,13,非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。空集合上的空关系则是自反的，反自反的，对称的，反对称的和传递的。,非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的。,非空集合上的空关系是反自反的，对称的，反对称的和,14,112页,例题4 设某人有三个儿子，组成集合A=T,G,H，在A上的兄弟关系具有哪些性质。,例题5 集合I=1,2,3,4，I上的关系,R=,讨论R的性质。,练习,113页(1),(2),(3),(5),112页练习,15,作业,113页(4),114页(6),作业,16,