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

《离散数学3-6关系的性质和3-7复合关系》由会员分享，可在线阅读，更多相关《离散数学3-6关系的性质和3-7复合关系（39页珍藏版）》请在金锄头文库上搜索。

1、离散数学离离 散散 数数 学学 Discrete Mathematics陈明 Email:mingchen_信息科学与工程学院二零一一年十月离散数学1、序偶：记作 2、笛卡尔积：记作AB 3、关系：序偶的集合；前域、值域 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是反自

2、反的。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是反自反关系的充要

3、条件是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

4、，rijrji；对称关系的关系图，任何两个不同的结点之间，或者有双向两条弧，或者没有弧。反对称关系的关系矩阵，如果在非对角元上 rij1，则在其对称位置上rji0，反对称关系的关系图，任何两个不同的结点之间至多有一条弧 。 离散数学1、定义：设R是集合X上的二元关系，如果对于任 意x，y，zX，每当R，R时就有 R，则称R是传递的。R在X上传递 (x)(y)(z)(xXyXzXRR R)例： R1=,是传递的， R2=,也是传递的，它没有违背定义。R3=,不是传递的。 三、传递性离散数学2、定理：设R、S是A上的传递关系，则RS也 是A上的传递关系。 注意：R、S均是传递的，但RS未必是传递的

5、。 例：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

6、是集合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。离散数学非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。空集合上的空关系则是自反的，反自反的，对称的，反对称的和传递的。非空集合上的全域关系是自反的，对称的和传递的，但不是反

7、自反的和反对称的。离散数学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，称为关系的合成运算。离

8、散数学说明：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=，关系的复合运算不满足交换律，满足结合律

9、。离散数学例题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)(称第一指数律)

10、(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的关

11、系，其关系矩阵MS=(vjk)np，复合关系RS是X到Z的关系，其关系矩阵MRS=(wik)mp，则wik=(uijvjk)。j=1n离散数学例题3：给定集合A=1，2，3，4，5，在A上定义两个关 系。R=，S=， ，。求RS和SR的矩阵。 解： 0 1 0 0 0 0 0 1 0 0 0 0 0 0 10 1 0 0 0 0 0 0 0 1 0 0 0 0 1 M RS= 0 0 0 1 0 1 0 0 0 0 = 0 1 0 0 00 0 0 0 0 0 1 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 1 0 0 0 1 0 0 0 0

12、 0 0 1 00 0 0 0 1 0 1 0 0 0 0 0 0 0 0 M SR= 1 0 0 0 0 0 0 0 1 0 = 0 1 0 0 00 1 0 0 0 0 0 0 0 0 0 1 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0离散数学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均

13、为Y到Z的关系，U是Z到D的 关系，则 R(ST)=RSRT R(ST)RSRT (ST)U=SUTU (ST)USUTU 证明：R(ST) yY，R(y，z)ST R(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上的

14、二元关系。R 的关系矩阵1 0 1 M R= 1 1 01 1 1 求Rc和RRc的关系矩阵。 解： 1 1 1 M Rc= 0 1 11 0 11 0 1 1 1 1 1 1 1 M RRc = 1 1 0 0 1 1 = 1 1 11 1 1 1 0 1 1 1 1离散数学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= Rc R= AB - R (6)(R1-R2)c=R1c-R2c 证明：(2)(R1R2)cR 1R2R1R2 R1c R 2c R1cR2c离散数学3、定理3-