离散数学3-7复合关系和逆关系3-8关系的闭包.

离散数学DiscreteMathematics山东科技大学信息科学与工程学院3-6关系的性质兄弟关系师生关系一、自反性和反自反性1、自反性：设R是集合X上的二元关系，如果对于每一个xX，有x，xR，则称R是自反的。R在X上自反(x)(xXx，xR)2、反自反性：设R是集合X上的二元关系，如果对于每一个xX，有x，xR，则称R是反自反的。R在X上反自反(x)(xXx，xR)例如，在实数集合中，””是自反的，因为对于任意实数xx成立。平面上三角形的全等关系是自反的。例：X={a，b，c}，R1={a，a，b，b，c，c，a，b，c，a}R2={a，b，b，c，c，a}R3={a，a，b，c}注意：R不是自反的，未必一定是反自反的。一个关系可能既不是自反的，也不是反自反的。3、关系矩阵的特点自反关系的关系矩阵的对角元素均为1；反自反关系的关系矩阵的对角元素均为0。4、关系图的特点自反关系的关系图，每个结点均有自回路；反自反关系的关系图，每个结点均没有自回路。5、结论：R是X上的二元关系，则：(1)R是自反关系的充要条件是IXR。(2)R是反自反关系的充要条件是RIX=。二、对称性和反对称性1、对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当x，yR，就有y，xR，则称R是对称的。R在X上对称(x)(y)(xXyXx,yRy,xR)2、反对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当x，yR和y，xR必有x=y，则称R是反对称的。R在X上反对称(x)(y)(xXyXx,yRy,xRx=y)例如，平面上三角形的相似关系是对称的。例：R1={1，1，2，3，3，2}R2={1，1，3，3}R3={2，2，2，3，3，2，3，1}R4={2，2，2，3，3，1}注意：存在关系既不是对称的，也不是反对称的。也存在关系既是对称的，也是反对称的。3、关系矩阵和关系图的特点对称关系的关系矩阵是对称矩阵，即对所有i，j，rij＝rji；对称关系的关系图，任何两个不同的结点之间，或者有双向两条弧，或者没有弧。反对称关系的关系矩阵，如果在非对角元上rij＝1，则在其对称位置上rji＝0反对称关系的关系图，任何两个不同的结点之间至多有一条弧。三、传递性1、定义：设R是集合X上的二元关系，如果对于任意x，y，zX，每当x，yR，y，zR时就有x，zR，则称R是传递的。R在X上传递(x)(y)(z)(xXyXzXx,yRy,zRx,zR)例：R1={x,y,z,x,z,y}是传递的，R2={x,b,c,d}也是传递的，它没有违背定义。R3={x,b,b,x}不是传递的。2、定理：设R、S是A上的传递关系，则RS也是A上的传递关系。注意：R、S均是传递的，但RS未必是传递的。例：R={a，b}，S={b，c}，则R、S均是传递的，但RS={a，b，b，c}不是传递的。证明：设x,yRS，y,zRS，则x,yR，y,zR且x,yS，y,zS。因为R、S是A上的传递关系，所以x,zR，x,zS，从而x,zRS，即RS是A上的传递关系。综合练习：集合A上的关系R，如果R是对称且传递的，则它也是自反的。其理由是，从aRb，由对称性得bRa，再由传递性得aRa。你说对吗？为什么？不对！再看自反性、对称性、传递性的定义。自反性：设R是集合X上的二元关系，如果对于每一个xX，有x，xR，则称R是自反的。对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当x，yR，就有y，xR，则称R是对称的。传递性：设R是集合X上的二元关系，如果对于任意x,y,zX，每当x，yR，y，zR时就有x，zR，则称R是传递的。•自反性是说对于每一个xX，有x，xR。•对称性是说每当x，yR，就有y，xR，没有要求对于每一个xX，•传递性是说每当x，yR，y，zR时就有x，zR，也没有要求对于每一个xX。•因此不能从一个关系是对称且传递的推出它是是自反的。例如A={a，b，c}，R={a,a，b,b，a,b，b,a}是A上的一个二元关系，R是对称且传递的，但R不是自反的，因为对于cA，没有c,cR。112页例题4设某人有三个儿子，组成集合A={T,G,H}，在A上的兄弟关系具有哪些性质。例题5集合I={1,2,3,4}，I上的关系R={1,1,1,3,2,2,3,3,3,1,3,4,4,3,4,4}讨论R的性质。小结关系的定义及表示关系的性质自反性反自反性对称性反对称性传递性作业P113:(2)(3)(6)3-7复合关系和逆关系本节讲述关系的运算。一、复合关系引例：（1）a、b、c三人，a、b是兄妹关系，b、c是母子关系，则a、c是舅甥关系；（2）若设R是兄妹关系，S是母子关系，则R与S的复合T是舅甥关系。（3）如R是父子关系，R与R复合是祖孙关系。一、复合关系1、复合关系(关系的复合运算)定义3-7.1：设X、Y、Z是三个集合，R是X到Y的关系，S是Y到Z的关系，则RS称为R和S的复合关系，表示为RS={x,zxXzZ(y)(yYx,yRy,zS)}从R和S求RS，称为关系的合成运算。说明：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|x+y=6}={1，5，2，4，3，3}，S={y，zy-z=2}={3，1，4，2，5，3}，则RS={1，3，2，2，3，1}另可以用推导：∵x+y=6，y-z=2，消去y得x+z=4例：集合X={x，y，z，d，e}，R={x，y，y，y，z，d}，S={d，y，y，e，z，x}，则RS={x，e，y，e，z，y}，SR={d，y，z，y}，RR={x，y，y，y}，SS={d，e}例题1：令R={1，2，3，4，2，2}，S={4，2，2，5，3，1，1，3}，试求RS，SR，R(SR)，(RS)R，RR，SS，RRR。解：RS={1，5，3，2，2，5}SR={4，2，3，2，1，4}R(SR)={3，2}(RS)R={3，2}RR={1，2，2，2}SS={4，5，3，3，1，1}RRR={1，2，2，2}关系的复合运算不满足交换律，满足结合律。例题2：设R1和R2是集合X={0，1，2，3}上的关系，R1={i，j|j=i+1或j=i/2}，R2={i，j|i=j+2}试求R1R2，R2R1，R1R2R1，R1R1，R1R1R1。解：R1={0,1,1,2,2,3,0,0,2,1}R2={2,0,3,1}R1R2={1,0,2,1}R2R1={2,1,2,0,3,2}R1R2R1={1,1,1,0,2,2}R1R1={0,2,1,3,1,1,0,1,0,0,2,2}R1R1R1={0,3,0,1,1,2,0,2,0,0,2,3,2,1}关系的n次幂：设R是X上的二元关系，nN，则关系的n次幂R(n)定义为：(1)R(0)=x；(2)R(n+1)=R(n)R说明：如果R是X到Y的关系，且X≠Y，则R2是无意义的，因为RR是无法复合的。例：设X={1，2，3，4，5}，X上关系R为R={1,2,2,1,2,3,3,4,4,5}，则：R(0)=x={1,1,2,2,3,3,4,4,5,5}，R(1)=RR(2)={1,1,2,2,1,3,2,4,3,5}R(3)={1,2,2,1,1,4,2,3,2,5}R(4)={1,1,2,2,1,5,2,4,1,3}R(5)={1,2,1,4,2,1,2,3,2,5}2、复合关系矩阵：设集合X={x1，x2，…，xm}，Y={y1，y2，…，yn}，Z={z1，…，zP}，R是X到Y的关系，其关系矩阵MR=(uij)m×n，S是Y到Z的关系，其关系矩阵MS=(vjk)n×p，复合关系RS是X到Z的关系，其关系矩阵MRS=(wik)m×p∨和∧运算•逻辑加∨：0∨0＝00∨1＝11∨0＝11∨1＝1•逻辑乘∧：0∧0＝00∧1＝01∧0＝01∧1＝12、复合关系矩阵：设集合X={x1，x2，…，xm}，Y={y1，y2，…，yn}，Z={z1，…，zP}，R是X到Y的关系，其关系矩阵MR=(uij)m×n，S是Y到Z的关系，其关系矩阵MS=(vjk)n×p，复合关系RS是X到Z的关系，其关系矩阵MRS=(wik)m×p，则wik=(uijvjk)。j=1nMR的第i行和MS的第k列对应的元素，先做逻辑乘，再做逻辑加∨例题3：给定集合A={1，2，3，4，5}，在A上定义两个关系。R={1，2，2，2，3，4}，S={1，3，2，5，3，1，4，2}。求RS和SR的矩阵。解：010000010000001010000000100001MRS=0001010000=01000000000100000000000000000000000001000100000010000010100000000MSR=1000000010=01000010000000001000000000000000000二、逆关系1、逆关系定义3-7.2：设R是集合X到Y的二元关系，如将R中每一序偶中的元素顺序互换，所得到的集合称为R的逆关系，记作Rc={y，x|x，yR}。说明：Rc的关系矩阵是R的关系矩阵的转置，Rc的关系图是将R的关系图中的弧改变方向。例：设某合X={x，y，z}，X上的关系R={x，x，z，x，z，y}，则Rc={x，x，x，z，y，z}例题4：给定集合X={a，b，c}，R是X上的二元关系。R的关系矩阵101MR=110111求Rc和RRc的关系矩阵。解：111MRc=011101101111111MRRc=110011=1111111011112、定理3-7.1：设R，R1和R2均是A到B的二元关系，则(1)(Rc)c=R(2)(R1∪R2)c=R1c∪R2c(3)(R1∩R2)c=R1c∩R2c(4)(A×B)c=B×A(5)(R)c=RcR=A×B-R(6)(R1-R2)c=R1c-R2c证明：(2)x，y(R1∪R2)cy，xR1∪R2y，xR1y，xR2x，yR1cx，yR2cx，yR1c∪R2c3、定理3-7.2：设R是X到Y的关系，S是Y到Z的关系，则(RS)c=ScRc。证明：z，x(RS)cx，zRS(y)(yYx，yRy，zS)(y)(yYy，xRcz，ySc)z，xScRc例