复合关系及逆关系_集合与关系_离散数学.ppt

《复合关系及逆关系_集合与关系_离散数学.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、复合关系和逆关系第1页本节讲述关系的运算二元关系是以序偶为元素的集合，除了可进行集合并、交、补等运算外，还可以进行一些新的运算。知识点：复合运算：定义计算方法证明逆运算定义计算方法证明第2页关系的定义域与值域关系R中所有序偶的第一元素x组成的集合，称为R的定义域，记作domR，即domR={x

2、(y)(R)}关系R中所有序偶的第二元素y组成的集合，称为R的值域，记作ranR，即ranR={y

3、(x)(R)}称fldR=domR∪ranR为R的域。显然

4、R是从A到B的关系，有domRA，ranRB，fldRA∪B。A={1,2,3,4}，B={a,b,c}，RA×BR={<1,a>,<1,c>,<2,c>,<3,a>,<3,c>}domR={1,2,3}ranR={a,c}fldR={1,2,3,a,c}举例定义域(domain)：值域(range)：域：第3页一、复合关系例如有3个人a,b,c，A={a,b,c}，R是A上母子关系，S是A上父女关系，∈R∧∈S即a是b的母亲,b是a的儿子;b是c的父亲，c是b的女子。

5、则a和c间就是奶奶和孙女的关系,记作R◦S,称它是R和S的复合关系。RabcSac第4页（一）定义3-7.1设X、Y、Z是三个集合，R是从X到Y的关系，S是从Y到Z的关系，则R和S的复合关系记作R◦S。R◦S={

6、xX∧zZ∧(y)(yY∧R∧S)}(俗称过河拆桥)显然，R◦S是一个新的二元关系，是从X到Z的关系。注意，如果对任意的x∈X和z∈Z，不存在y∈Y，使得xRy和ySz同时成立，则R◦S为空，否则为非空。◦R=R◦=。一、复合关系第5页A=

7、{1,2,3}B={a,b,c,d}C={x,y,z,s,t}RA×BSB×C，求R◦S（1）枚举法R={<1,b>,<2,c>,<2,d>,<3,a>}S={,,,,,}（二）复合关系的计算方法则R◦S={<1,x>,<1,z>,<2,s>,<2,y>,<2,t>,<3,y>}R◦SS◦RS◦R=第6页R={<1,b>,<2,c>,<2,d>,<3,a>}S={,,,,,

8、>}（2）有向图法（首尾相连法）RS。。。Cxyz。s1。2。3。A1。2。3。A。。。Babc。d。t。。。Cxyz。s。t第7页MR...............(aij)MS...............(bij)...

9、t>............M(cij)（3）矩阵法（矩阵逻辑积）RS11=(R11∧S11)∨(R12∧S21)∨...∨(R1n∧Sn1)=(R1k∧Sk1)(其中∧是逻辑乘,∨是逻辑加)k=1n∨RSij=(Ri1∧S1j)∨(Ri2∧S2j)∨...∨(Rin∧Snj)=(Rik∧Skj)(1≤i≤m,1≤j≤t)k=1n∨第8页010001000001110003×4。101000001001001=4×510100010110

10、10003×5（3）矩阵法（续）R={<1,b>,<2,c>,<2,d>,<3,a>}S={,,,,,}即R◦S={<1,x>,<1,z>,<2,s>,<2,y>,<2,t>,<3,y>}第9页设I是实数集合，R和S都是I上的关系，定义如下：R={

11、y=x2+3x}S={

12、y=2x+3}xx2+3x2(x2+3x)+3=2x2+6x+3RS所以R◦S={

13、y=2x2+6x+3}（4）谓词公式法第10页（一）复

14、合关系的性质关系复合运算不满足交换律，但是1.满足结合律:RA×BSB×CTC×D则(R◦S)◦T=R◦(S◦T)2.RA×BSB×CTB×C⑴R◦(S∪T)=(R◦S)∪(R◦T)⑵R◦(S∩T)(R◦S)∩(R◦T)3.R是从A到B的关系，则R◦IB=IA◦R=R二、性质第11页证明：∈(R◦S)◦T(c)(c∈C∧∈R◦S∧∈T)(c)(c∈C∧(b)(∈R∧∈S)∧∈T)(c)(b)