关系和其运算.ppt

《关系和其运算.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、关系及其运算离散数学－集合论南京大学计算机科学与技术系回顾集合的基本概念集合及其描述集合相等、子集关系幂集、笛卡尔乘积集合运算交并补、广义交、广义并集合恒等式集合相关命题的证明方式提要关系的定义关系的表示关系的运算0-1矩阵运算关系的性质有序对（Orderedpair）(a,b)是集合{{a},{a,b}}的简写次序的体现(x,y)=(u,v)iffx=u且y=v若{{x},{x,y}}={{u},{u,v}}，则{x}={u}或{x}={u,v},因此x=u。假设yv(1)若x=y,左边={{x}},而vx,

2、右边{{x}};(2)若xy,则必有{x,y}={u,v},但y既非u,又非v,矛盾。笛卡尔乘积（CartesianProduct）对任意集合A,B笛卡尔积AB={(a,b)

3、aA,bB}例：{1,2,3}{a,b}={(1,a),(3,a),(3,a),(1,b),(2,b),(3,b)}若A，B是有限集合，

4、AB

5、=

6、A

7、

8、B

9、例题A={1,2},(A)×A=?

10、A

11、=m,

12、B

13、=n,

14、A×B

15、=?（二元）关系的定义若A,B是集合,从A到B的一个关系是AB的一个子集.集合,可以是空集集合的元素

16、是有序对关系意味着什么？两类对象之间建立起来的联系！从A到B的二元关系笛卡尔乘积的子集“从A到B的关系”R；RAB若A=B：称为“集合A上的（二元）关系”例子常用的数学关系：不大于、整除、集合包含等网页链接、文章引用、相互认识特殊的二元关系集合A上的空关系:空关系即空集全域关系EA:EA={(x,y)

17、x,yA}恒等关系IA:IA={(x,x)

18、xA}函数是一种特殊的关系函数f:ABR={(x,f(x))

19、xA}是一个从A到B的一个关系关系的表示假设A={a,b,c,d},B={α,β,γ}//假设为

20、有限集合集合表示:R1={(a,β),(b,α),(c,α),(c,γ)}0-1矩阵有向图abcdadcbAB二元关系和有向图关系RABA和B是集合有序对集合(x,y)R若A=B,R中存在序列：(x1,x2),(x2,x3),…,(xn-1,xn)有向图(VD,ED)顶点集VD=AB有向边集ED从x到y有一条边图D中存在从x1到xn的长度为n-1的通路关系的运算（1）关系是集合,所有的集合运算对关系均适用例子:自然数集合上:“<”“=”等同于“”自然数集合上:“”“”等同于“=”自然数集

21、合上:“<”“>”等同于关系的运算（2）与定义域和值域有关的运算domR={x

22、y(x,y)R}ranR={y

23、x(x,y)R}fldR=domRranRRA={(x,y)

24、xAxRy}RR[A]={y

25、x(xA(x,y)R)}=ran(RA)ranR例：A={1,2,3,4,5},B={1,3,5,6},A上关系R：R={(1,2),(1,4),(2,3),(3,5),(5,2)},求RB、R[B]、R(1)和R(2)关系的运算（3）逆运算R-1={(x,y)

26、(y,x)R}注

27、意:如果R是从A到B的关系,则R-1是从B到A的。(R-1)-1=R例子：(R1R2)-1=R1-1R2-1(x,y)(R1R2)-1(y,x)(R1R2)(y,x)R1或(y,x)R2(x,y)R1-1或(x,y)R2-1关系的运算（4）关系的复合（合成,Composition）设R1AB,R2BC,R1与R2的复合（合成）,记为R2⃘R1,定义如下：R2⃘R1={(a,c)AC

28、bB((a,b)R1(b,c)R2)}复合关系的图示(a,c)R2⃘R1当且仅当a

29、A,cC,且存在bB，使得(a,b)R1,(b,c)R2abcR1R2关系的复合运算：举例设A={a,b,c,d},R1,R2为A上的关系，其中：R1={(a,a),(a,b),(b,d)}R2={(a,d),(b,c),(b,d),(c,b)}则：R2⃘R1={(a,d),(a,c),(a,d)}R1⃘R2={(c,d)}R12={(a,a),(a,b),(a,d)}关系的复合运算的性质（1）结合律给定R1AB,R2BC,R3CD,则：(R3⃘R2)⃘R1=R3⃘(R2⃘R1)证明左右两个集合

30、相等.关系的复合运算的性质（2）复合关系的逆关系给定R1AB,R2BC,则：(R2⃘R1)-1=R1-1⃘R2-1同样，证明左右两个集合相等(x,y)(R2⃘R1)-1(y,x)R2⃘R1tB((y,t)R1(t,x)R2)tB((t,y)R1-1(x,t)R2-1)(x,y)R2-1⃘R1-1关系的复