关系的性质-集合与关系-离散数学

关系的性质第1页本节将研究关系的一些性质，它们在关系的研究中起着重要的作用。这是本章最重要的一节。本节中所讨论的关系都是集合A上的关系。本节要点：五个性质：自反性、反自反性--自己和自己的关系对称性、反对称性–两个元素之间的关系传递性--三个元素之间的关系相关证明第2页定义：设R是集合A上的关系，若对于任意x∈A都有x,x∈R(xRx)，则称R是A中的自反关系。即R是A中自反的(x)(xAx,x∈R)该定义表明在自反关系R中，除其他序偶外，必须包括有全部由每个x∈A所组成的相同元素的序偶。一、自反性非（不是）自反的(x)(xA∧x,xR)例如：设X={a,b,c},R1={a,a,b,b,c,c,a,b}R2={a,a,b,b,a,b}例如：相等关系(=)，小于等于关系()，包含关系()等是自反关系。是自反关系。不是自反关系。第3页定义：设R是集合A上的关系，若对于任意x∈A都有x,x∈R(xRx)，则称R是A中的自反关系。即R是A中自反的(x)(xAx,x∈R)从关系矩阵看自反性：从关系有向图看自反性：1？？？1？？？1具有自反性的关系的关系矩阵和关系图的特点。1。2。3主对角线都为1。每个结点都有环。思考：具有自反性的关系与恒等关系有何区别于联系？第4页定义：设R是集合A上的关系，若对于任意的x∈A都有x,xR，则称R为A中的反自反关系。即R是A中反自反的(x)(xAx,xR)该定义表明了，一个反自反的关系不应包括有任何相同元素的序偶。二、反自反性非（不是）反自反的(x)(xA∧x,xR)例如：设X={a,b,c},R1={a,b,b,c}R2=={a,a,a,b,b,c}不相等关系()，小于关系()，真包含关系()，父子关系是反自反关系。是反自反关系。不是反自反关系第5页定义：设R是集合A上的关系，若对于任意的x∈A都有x,xR，则称R为A中的反自反关系。即R是A中反自反的(x)(xAx,xR)从关系矩阵看反自反性：从关系有向图看反自反性：0？？？0？？？0具有反自反性的关系的关系矩阵和关系图的特点1。。2。3主对角线都为0。每个结点都无环。第6页R1、R3、R4是自反的，R2、R5、R8均是反自反关系。注意：任何一个不是自反的关系，未必是反自反的，任何一个不是反自反的关系，未必是自反的，如R6、R7非自反，也非反自反。存在既不是自反的也不是反自反的关系。例1。2。。1。2。。1。2。。1。2。。33331。2。。1。2。。1。2。。1。2。。3333R2R1R3R4R5R6R7R8自反反自反反自反反自反自反自反非自反非反自反非自反非反自反第7页定义：R是集合A上的关系，若对任何x,y∈A，若有x,yR，必有y,xR，则称R为A中的对称关系。R是A上对称的(x)(y)((xA∧yA∧x,yR)y,xR)在有对称性的关系中，若有序偶x,y，必有序偶y,x。例如：设集合A={1,2,3}有下列关系：1）R1={1,1,1,2,1,3,2,1,2,2,3,1}2）R2={1,1,1,2,2,1,2,2,3,1}三、对称性非（不是）对称的(x)(y)(xA∧yA∧x,yR∧y,xR)例如：朋友关系，同学关系，同乡关系，不相等关系()是对称关系，相等关系(=)？？？。是对称关系不是对称关系第8页定义：R是集合A上的关系，若对任何x,y∈A，若有x,yR，必有y,xR，则称R为A中的对称关系。R是A上对称的(x)(y)((xA∧yA∧x,yR)y,xR)从关系矩阵看对称性：从关系有向图看对称性：？101？101？对称性的关系矩阵和关系图的特点以主对角线为对称的矩阵。在两个不同的结点之间，若有边的话，则有方向相反的两条边。1。2。。3是否有环对对称性无影响。第9页定义:设R为集合A上的关系，若对任何x,y∈A，有x,yR和y,xR，就有x=y，则称R为A中的反对称关系。R是A上反对称的(x)(y)((xA∧yA∧x,yR∧y,xR)x=y)(x)(y)((xA∧yA∧x,yR∧xy)y,xR)四、反对称性讨论定义：（1）前件x,yR∧y,xR为“T”，则x=y为“T”，R是对称的。（2）前件为x,yR∧y,xR为“F”，有三种情况，后件不论是真还是假，命题为“T”，即R是对称的。第10页定义:设R为集合A上的关系，若对任何x,y∈A，有x,yR和y,xR，就有x=y，则称R为A中的反对称关系。R是A上反对称的(x)(y)((xA∧yA∧x,yR∧y,xR)x=y)(x)(y)((xA∧yA∧x,yR∧xy)y,xR)例如：设集合A={1,2,3}有下列关系：1）R1={1,1,1,2,1,3,2,2}2）R2={1,1,1,2,2,1,2,2,3,1}四、反对称性非反对称的(x)(y)(xA∧yA∧x,yR∧y,xR∧xy)例如：小于等于关系()，包含关系()，上下级关系，父子关系等是反对称关系。是反对称关系不是反对称关系第11页定义:设R为集合A上的关系，若对任何x,y∈A，有x,yR和y,xR，就有x=y，则称R为A中的反对称关系。R是A上反对称的(x)(y)((xA∧yA∧x,yR∧y,xR)x=y)(x)(y)((xA∧yA∧x,yR∧xy)y,xR)从关系矩阵看反对称性：从关系有向图看反对称性:？000？110？具有反对称性的关系的关系矩阵和关系图的特点以主对角线为对称的两个元素中最多有一个1。两个不同的结点之间最多有一条边。1。2。。3第12页1。2。。1。2。。1。2。。1。2。。33331。2。。1。2。。1。2。。1。2。。3333R2R1R3R4R5R6R7R8对称与反对称不是完全对立的，有些关系它既是对称也是反对称的，如空关系R4、恒等关系R8、关系R9。任何不是对称的关系未必一定是反对称的关系，反之亦然。存在既不是对称也不是反对称的关系。如关系R7反对称反对称反对称反对称反对称对称对称对称对称非对称非反对称1。2。。3R9反对称对称第13页有无既是对称的也是反对称的对称的是两元素之间有双向边或0边，反对称是指两元素之间有单向边或0边，所以既是对称的也是反对称的就是两元素之间有0边，即是恒等关系的子集。第14页定义:R是A中关系，对任何x,y,z∈A，若有x,yR和y,zR，就有x,zR，则称R为A中的传递关系。即R在A上传递(x)(y)(z)((xA∧yA∧zA∧x,yR∧y,zR)x,zR)五、传递性非（不是）传递的(x)(y)(z)(xA∧yA∧zA∧x,yR∧y,zR∧x,zR)讨论定义：（1）前件x,yR∧y,zR为“T”，后件x,zR为“T”，R是可传递的。（2）前件为“F”，有三种情况，后件不论是真还是假，命题为“T”，即R是可传递的。例如：设集合A={1,2,3}有下列关系：1）R1={1,1,1,2,1,3}2）R2={1,2}3）R3={1,2,2,3}如：相等关系(=)，小于等于关系()，包含关系()，上下级是传递关系。是传递的是传递的不是传递的第15页定义:R是A中关系，对任何x,y,z∈A，若有x,yR和y,zR，就有x,zR，则称R为A中的传递关系。即R在A上传递(x)(y)(z)((xA∧yA∧zA∧x,yR∧y,zR)x,zR)从关系关系图和关系矩阵中不易看清是否有传递性。有时，必须直接根据传递的定义来检查。123五、传递性第16页R1、R3、R4、R5、R8均是传递的关系。传递传递传递传递传递例1。2。。1。2。。1。2。。1。2。。33331。2。。1。2。。1。2。。1。2。。3333R2R1R3R4R5R6R7R8非传递非传递非传递第17页自反性反自反性对称性传递性反对称性每个结点都有环主对角线全是1每个结点都无环主对角线全是0不同结点间如果有边，则有方向相反的两条边是以对角线为对称的矩阵不同结点间，最多有一条边以主对角线为对称的位置不会同时为1若有边a,b,b,c,则有边a,c。或者定义的前件为假。若aij=1,且ajk=1,则aik=1从关系的矩阵从关系的有向图性质判定:第18页下面归纳这八个关系的性质：Y-有N-无自反性反自反性对称性反对称性传递性R1YNNYYR2NYNYNR3YNYNYR4NYNYY1。2。。1。2。。1。2。。333R2R1R31。2。。3R4第19页自反性反自反性对称性反对称性传递性R5YNYYYR6NNYNNR7YNYNYR8NYYYY1。2。。1。2。。33R6R7R8恒等关系是自反的、对称的、反对称的、传递的。全关系是自反的、对称的、传递的。空关系是反自反的、对称的、反对称的、传递的。若X=Φ，则X上的空关系Φ：自反、反自反的、对称的、反对称的、传递的。1。2。。3R51。2。。3第20页关系性质的证明方法在二元关系中，由于关系的性质的定义全部都是按“若…则…”来描述的，因此，在证明关系具有某种性质时，应采用离散数学中特有的按定义证明方法即证明时，首先叙述定义的前半部分“若…”，将这部分的内容称为“附加的已知条件”，此时利用该“附加的已知条件”和题目本身所给的已知条件证明出定义的后半部分“则…”，这部分的内容称为定义中的结论。这种证明问题的方法在于：证明时不能单纯利用题目所给的已知条件，而应同时利用定义中的“已知”，推出的并非整个定义，而是定义中的结论。这与一般的证明思路：已知→中间结果→结论是完全不同的。总之，在关系这一章中，可以说所有的证明几乎都采用按定义证明方法。第21页2.反自反性(x)(xAx,xR)关系性质的证明方法1.自反性(x)(xAx,x∈R)任取xA，中间过程任取xA，中间过程3.对称性(x)(y)((xA∧yA∧x,yR)y,xR)任取x,yA，假设x,yR，中间过程y,xRx,xRx,xR第22页4.反对称性任取x,yA，假设x,yR，y,xR，中间过程x＝y或者任取x,yA，x≠y，假设x,yR，中间过程y,xR5.传递性任取x,y,zA，假设x,yR，y,zR，中间过程x,zR(x)(y)((xA∧yA∧x,yR∧y,xR)x=y)(x)(y)((xA∧yA∧x,yR∧xy)y,xR)(x)(y)(z)((xA∧yA∧zA∧x,yR∧y,zR)x,zR)第23页练习1:令I是整数集合，I上关系R定义为：R={x,y|x-y能被3整除}，求证R是自反、对称和传递的。证明：⑴证自反性：任取x∈I，(要证出x,xR)因x-x=0，0能被3整除，所以有x,x∈R，故R自反。⑵证对称性：任取x,y∈I，设x,y∈R，(要证出y,xR)由R定义得x-y能被3整除，即x-y=3n(n∈I)，y-x=-(x-y)=-3n=3(-n)，∵-n∈I，∴y,x∈R,所以R对称。