离散数学3-6关系的性质和3-7复合关系.ppt

离散数学DiscreteMathematics,陈明Email:mingchen_gang,信息科学与工程学院,二零一一年十月,1、序偶：记作2、笛卡尔积：记作AB3、关系：序偶的集合；前域、值域4、X到Y的关系，X上的关系5、关系的表示：关系矩阵、关系图,回顾,1,，,设A-2,-1,0,1,3-6关系的性质,一、自反性和反自反性1、自反性：设R是集合X上的二元关系，如果对于每一个xX，有R，则称R是自反的。R在X上自反(x)(xXR)2、反自反性：设R是集合X上的二元关系，如果对于每一个xX，有R，则称R是反自反的。R在X上反自反(x)(xXR),例如，在实数集合中，”是自反的，因为对于任意实数xx成立。平面上三角形的全等关系是自反的。例：X=a，b，c，R1=，R2=，R3=，注意：R不是自反的，未必一定是反自反的。一个关系可能既不是自反的，也不是反自反的。,3、关系矩阵的特点自反关系的关系矩阵的对角元素均为1，反自反关系的关系矩阵的对角元素均为0。4、关系图的特点自反关系的关系图，每个结点均有自回路，而反自反关系的关系图，每个结点均没有自回路。,5、结论(两个充要条件)R是X上的二元关系，则：(1)R是自反关系的充要条件是IXR；(2)R是反自反关系的充要条件是RIX=。,1、对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当R，就有R，则称R是对称的。R在X上对称(x)(y)(xXyXRR)2、反对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当R和R必有x=y，则称R是反对称的。R在X上反对称(x)(y)(xXyXRRx=y),二、对称性和反对称性,例如，平面上三角形的相似关系是对称的。例：R1=，R2=，R3=，R4=，注意：存在关系既不是对称的，也不是反对称的。也存在关系既是对称的，也是反对称的。,3、关系矩阵和关系图的特点对称关系的关系矩阵是对称矩阵，即对所有i，j，rijrji；对称关系的关系图，任何两个不同的结点之间，或者有双向两条弧，或者没有弧。反对称关系的关系矩阵，如果在非对角元上rij1，则在其对称位置上rji0，反对称关系的关系图，任何两个不同的结点之间至多有一条弧。,1、定义：设R是集合X上的二元关系，如果对于任意x，y，zX，每当R，R时就有R，则称R是传递的。R在X上传递(x)(y)(z)(xXyXzXRRR)例：R1=,是传递的，R2=,也是传递的，它没有违背定义。R3=,不是传递的。,三、传递性,2、定理：设R、S是A上的传递关系，则RS也是A上的传递关系。,注意：R、S均是传递的，但RS未必是传递的。例：R=，S=，则R、S均是传递的，但RS=，不是传递的。,证明：设RS，RS，则R，R且S，S。因为R、S是A上的传递关系，所以R，S，从而RS，即RS是A上的传递关系。,综合练习：集合A上的关系R，如果是对称且传递的，则它也是自反的。其理由是，从aRb，由对称性得bRa，再由传递性得aRa，你说对吗？为什么？,不对！再看自反性、对称性、传递性的定义。,自反性：设R是集合X上的二元关系，如果对于每一个xX，有R，则称R是自反的。,对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当R，就有R，则称R是对称的。,传递性：设R是集合X上的二元关系，如果对于任意x,y,zX，每当R，R时就有R，则称R是传递的。,自反性是说对于每一个xX，有R。对称性是说每当R，就有R，没有要求对于每一个xX，传递性是说每当R，R时就有R，也没有要求对于每一个xX。因此不能从一个关系是对称且传递的推出它是是自反的。,例如A=a，b，c，R=，是A上的一个二元关系，R是对称且传递的，但R不是自反的，因为对于cA，没有R。,非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。空集合上的空关系则是自反的，反自反的，对称的，反对称的和传递的。非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的。,112页例题4设某人有三个儿子，组成集合A=T,G,H，在A上的兄弟关系具有哪些性质。例题5集合I=1,2,3,4，I上的关系R=,讨论R的性质。,3-7复合关系和逆关系,本节讲述关系的运算。,一、复合关系引例：（1）若设R是兄妹关系，S是母子关系，则R与S的复合T是舅甥关系。（2）如R是父子关系，R与R复合是祖孙关系。,1、复合关系(关系的复合运算)定义3-7.1：设X、Y、Z是三个集合，R是X到Y的关系，S是Y到Z的关系，则RS称为R和S的复合关系，表示为RS=xXzZ(y)(yYRS)从R和S求RS，称为关系的合成运算。,说明：R与S能进行复合的前提是R的值域所属集合Y与S前域所属集合Y是同一个集合。例：X=1，2，3，4，5，Y=3，4，5，Z=1，2，3，R是X到Y的关系，S是Y到Z的关系：R=|x+y=6=，S=y-z=2=，则RS=，另可以用推导：x+y=6，y-z=2，消去y得x+z=4例：集合X=x，y，z，d，e，R=，S=，则RS=，SR=，RR=，SS=,例题1：令R=，S=，试求RS，SR，R(SR)，(RS)R，RR，SS，RRR。解：RS=，SR=，R(SR)=(RS)R=RR=，SS=，RRR=，关系的复合运算不满足交换律，满足结合律。,例题2：设R1和R2是集合X=0，1，2，3上的关系，R1=|j=I+1或j=I/2，R2=|I=j+2试求R1R2，R2R1，R1R2R1，R1R1，R1R1R1。解：R1=,R2=,R1R2=,R2R1=,R1R2R1=,R1R1=,R1R1R1=,关系的n次幂：设R是X上的二元关系，nN，则关系的n次幂R(n)定义为：(1)R(0)=x；(2)R(n+1)=R(n)R说明：如果R是X到Y的关系，且XY，则R2是无意义的，因为RR是无法复合的。,定理：设R是集合X上的二元关系，m，nN，则(1)R(m)R(n)=R(m+n)(称第一指数律)(2)(R(m)(n)=R(mn)(称第二指数律)此定理证明可以用数学归纳法加以证明。,说明：第三指数律(RS)(n)=R(n)S(n)一般是不成立的。因为：(RS)(2)=(RS)(RS)=R(SR)S，R(2)S(2)=(RR)(SS)=R(RS)S，只要交换律不成立，第三指数律不成立。,例：设X=1，2，3，4，5，X上关系R为R=,，则：R(0)=x=,，R(1)=RR(2)=,R(3)=,R(4)=,R(5)=,2、复合关系矩阵：设集合X=x1，x2，xm，Y=y1，y2，yn，Z=z1，zP，R是X到Y的关系，其关系矩阵MR=(uij)mn，S是Y到Z的关系，其关系矩阵MS=(vjk)np，复合关系RS是X到Z的关系，其关系矩阵MRS=(wik)mp，则wik=(uijvjk)。,例题3：给定集合A=1，2，3，4，5，在A上定义两个关系。R=，S=，。求RS和SR的矩阵。解：010000010000001010000000100001MRS=0001010000=01000000000100000000000000000000000001000100000010000010100000000MSR=1000000010=01000010000000001000000000000000000,3、复合关系的性质(1)复合运算结合律设R、S、T分别是X到Y、Y到Z、Z到D的关系，则(RS)T=R(ST)证明：(RS)TzZ，RS，T，yY，R，S，TR，STR(ST)所以(RS)TR(ST)类似可以证R(ST)(RS)T，从而(RS)T=R(ST),(2)复合运算与，的关系设R是从集合X到Y的关系，S和T均为Y到Z的关系，U是Z到D的关系，则R(ST)=RSRTR(ST)RSRT(ST)U=SUTU(ST)USUTU证明：R(ST)yY，R(y，z)STR(ST)(RS)(RT)RSRT)RSRT从而R(ST)=RSRT,1、逆关系定义3-7.2：设R是集合X到Y的二元关系，如将R中每一序偶中的元素顺序互换，所得到的集合称为R的逆关系，记作Rc=|R。说明：Rc的关系矩阵是R的关系矩阵的转置，Rc的关系图是将R的关系图中的弧改变方向。例：设某集合X=x，y，z，X上的关系R=，则Rc=，,二、逆关系,例题4：给定集合X=a，b，c，R是X上的二元关系。R的关系矩阵101MR=110111求Rc和RRc的关系矩阵。解：111MRc=011101101111111MRRc=110011=111111101111,2、定理3-7.1：设R，R1和R2均是A到B的二元关系，则(1)(Rc)c=R(2)(R1R2)c=R1cR2c(3)(R1R2)c=R1cR2c(4)(AB)c=BA(5)(R)c=RcR=AB-R(6)(R1-R2)c=R1c-R2c证明：(2)(R1R2)cR1R2R1R2R1cR2cR1cR2c,3、定理3-7.2：设R是X到Y的关系，S是Y到Z的关系，则(RS)c=ScRc。证明：(RS)cRS(y)(yYRS)(y)(yYRcSc)ScRc,例：X=x，y，z，Y=1，2，3，4，5，R是X上关系，S是X到Y的关系。R=，S=，则RS=，Rc=，Sc=，ScRc=，可验证：ScRc=(RS)c,4、定理3-7.3：设R是X上的二元关系，则(1)R是对称的，当且仅当R=Rc(2)R是反对称的，当且仅当RRcIx证明：(1)因为R是对称的，故RRRc，所以R=Rc。反之，若R=Rc，因为RRcR，所以R是对称的。(2)设R是反对称的，RRcRRcRR，因为R是反对称的，所以x=y，故RRcIx。反之，若RRcIx，RRc有Ix，即x=y。又RRcRRcRR，但x=y，故R是反对称的。,即当R和R时，必有x=y。,作业,P113:(2);(3);(6).P119:(2)a,b;(4)b,d.,1、关系的性质自反性、反自反性；对称性、反对称性；传递性；2、复合关系逆关系,回顾,