二元关系-PPT讲稿.ppt

《二元关系-PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《二元关系-PPT讲稿.ppt（28页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、二元关系二元关系-第1页，共28页，编辑于2022年，星期四6.4 6.4 关系的性质关系的性质-重点重点 本本节节涉涉及及到到的的关关系系，如如无无特特别别声声明明，都都是是假假定定其其前前域域和和后后域域相相同同。即即都都为为定定义义在在集集合合A A上上的的关关系系，且且A A是是非非空空集集合合。对对于于前前后后域域不不相相同同的的关关系系，其其性性质无法加以定义。质无法加以定义。6.4.1 6.4.1 关系性质的定义关系性质的定义1.1.关系性质的定义关系性质的定义第2页，共28页，编辑于2022年，星期四定义定义6.4.1-36.4.1-3设设R R是集合是集合A A上的关系，上的

2、关系，1.1.如如果果对对任任意意xxA A，都都有有R R，那那么么称称R R在在A A上上是是自自反反的的，或或称称R R具有具有自反性自反性.2.2.如果对任意如果对任意xAxA，都有，都有 R R，那么称，那么称R R在在A A上是上是反自反自 反的反的，或称，或称R R具有具有反自反性反自反性。3.3.对对任任意意x,yAx,yA，如如果果RR，那那么么 RR，则则称称关关系系R R是是对对称称的的，或称，或称R R具有具有对称性对称性；4.4.对对任任意意x,yAx,yA，如如果果RR且且RR，那那么么x xy y（或或者者,若若xy,xy,则则 与与不不全全属属于于R R），则则

3、称称关关系系R R是是反反对对称称的的，或称或称R R具有具有反对称性反对称性。5.5.对任意对任意x,y,zAx,y,zA，如果，如果RR且且RR，那么，那么RR，则称关系，则称关系R R是是传递的传递的，或称，或称R R具有具有传递性传递性。第3页，共28页，编辑于2022年，星期四例例1 1：1.1.整数集整数集I I上的上的“等于等于”关系是自反的、反对称的、对称关系是自反的、反对称的、对称的、传递的关系。的、传递的关系。“小于等于小于等于”关系是自反的、反对称的、传递的关系；关系是自反的、反对称的、传递的关系；“小于小于”关系是反自反的、反对称的、传递的关系关系是反自反的、反对称的、

4、传递的关系。2.2.幂幂集集上上的的“包包含含”关关系系关关系系是是自自反反的的、反反对对称称的的、传传递递的的关关系系。3.3.命命题题公公式式集集合合上上的的蕴蕴涵涵关关系系“”具具有有自自反反性性、反反对对称称性性和和传传递递性。性。4.4.三角形的相似关系具有三角形的相似关系具有自反自反性、对称性和传递性。性、对称性和传递性。5.5.人的集合上的人的集合上的朋友关系朋友关系具有具有自反自反性和性和对称对称性性;父子关系父子关系具有反具有反自反自反性和性和反对称性反对称性.第4页，共28页，编辑于2022年，星期四例例2：设设A是任意的是任意的非空集合，则非空集合，则 A上的全关系上的全

5、关系AA是是 自反的、对称的、传递的关系；自反的、对称的、传递的关系；A上的空关系上的空关系是是 反自反的、反对称的、对称的、传反自反的、反对称的、对称的、传 递的关系；递的关系；A上的恒等关系上的恒等关系IA是是 自反的、对称的、反对称的、传自反的、对称的、反对称的、传 递的关系。递的关系。例例3 3：设设A=1,2,3A=1,2,3，A A上的关系：上的关系：（1 1）R=,R=,则则 R R是自反的是自反的,反对称的反对称的,传递的传递的.（2 2）S=,S=,则则 S S是反自反的是反自反的,对称的对称的.第5页，共28页，编辑于2022年，星期四（3 3）U=,U=,则则 U U 是

6、是对称的对称的,反对称的反对称的,传递的传递的.（4 4）V=,V=,则则 V V 是反对称的是反对称的,传递的传递的.（5 5）T=,T=,则则 T 5T 5个性质都没有个性质都没有.2 2.“.“性质性质”在关系图和关系矩阵上的反应在关系图和关系矩阵上的反应（1 1）关系关系R R是自反的是自反的 关系图中关系图中每个节点都有环每个节点都有环 关系矩阵的主对角线上的元素全为关系矩阵的主对角线上的元素全为1 1（2 2）关系关系R R是反自反的是反自反的 关系图中关系图中每个节点都无环每个节点都无环 关系矩阵的主对角线上的元素全为关系矩阵的主对角线上的元素全为0 0第6页，共28页，编辑于2

7、022年，星期四(3)关关系系R是是对对称称的的 关关系系图图中中任任何何一一对对结结点点之之间间，要要么么有有方方向向相相反反的的两两条条边边，要要么么无无边边 关关系系矩矩阵阵为为对对称称矩阵矩阵(4)关关系系R是是反反对对称称的的 关关系系图图中中任任何何一一对对结结点点之之间间，至多有一条边；至多有一条边；R的关系矩阵满足的关系矩阵满足 rijrji0，i,j=1,2,n，ij。(5)关关系系R是是传传递递的的 图图中中,任任何何三三个个节节点点x,y,z(x,y,z(可可以以相相同同)之之间间，若若从从x x到到y y有有一一条条边边存存在在,从从y y到到z z有有一一条条边边存存

8、在在,则从则从x x到到z z一定有一条边存在一定有一条边存在.关系矩阵中关系矩阵中,如果如果r rijij1 1且且r rjkjk1,1,则则r rikik1 1第7页，共28页，编辑于2022年，星期四有有:反自反性和反对称性反自反性和反对称性132有有:反自反性和反对称性反自反性和反对称性有有:自自反反性性,反反对对称称性和性和传递性传递性312例例 A=1,2,3A=1,2,3上关系上关系:第8页，共28页，编辑于2022年，星期四设设A Aa,b,c,a,b,c,试判断如下图所示试判断如下图所示A A上关系的性质：上关系的性质：例例a ab bc c(a(a)a ab bc c(b(

9、b)a ab bc c(c(c)a ab bc c(d(d)a ab bc c(e(e)a ab bc c(f(f)a ab bc c(g(g)a ab bc c(h(h)图图(a)(a)的关系是自反的、对的关系是自反的、对称的、反对称的、传递的称的、反对称的、传递的关系关系图图(b)(b)的关系是具备反自的关系是具备反自反的、对称的、反对称的、反的、对称的、反对称的、传递的关系传递的关系图图(c)(c)的关系是具备对称的、的关系是具备对称的、反对称的、传递的关系反对称的、传递的关系图图(d)(d)的关系是不具备任何的的关系是不具备任何的性质关系性质关系图图(e)(e)的关系是具备自反的、的关

10、系是具备自反的、对称的、传递的关系对称的、传递的关系图图(f)(f)的关系是具备反自的关系是具备反自反的、反对称的、传递的反的、反对称的、传递的关系关系图图(g)(g)的关系是具备反自反的关系是具备反自反的、反对称的关系的、反对称的关系图图(h)(h)的关系是具备反自反的关系是具备反自反的、反对称的、传递的关系的、反对称的、传递的关系第9页，共28页，编辑于2022年，星期四注注:(3)(3)存在既是对称也是反对称的关系；存在既是对称也是反对称的关系；(1)非空集合非空集合A上的关系上的关系,若有自反性若有自反性,则一定没有反自反性则一定没有反自反性;反知反知,若有反自反性若有反自反性,则一定

11、没有自反性则一定没有自反性;(2)存在既不是对称也不是反对称的关系；存在既不是对称也不是反对称的关系；(4)(4)非空集合非空集合A A上的上的空关系空关系具有反自反性、对称性、具有反自反性、对称性、反对称性和传递性；反对称性和传递性；(5)(5)空空集上的集上的空关系空关系5 5个性质都具有个性质都具有.第10页，共28页，编辑于2022年，星期四总结总结自反 反自反对称反对称传递定义RRRRRRx=yRRR关系图每个结点都有环每个结点都无环每 对结 点间或 有方 向相反的两条边，或无任何边每对结点间至多有一条边存在任三个结点x,y,z，若从x到y有边，从y到z有边，则从x到z一定有边关系矩

12、阵对 角线 上全为1对角线上全为0对称矩阵rijrji=0,i,j=1,2,n,ij如rij1且rjk1则rik1第11页，共28页，编辑于2022年，星期四2.2.反自反反自反关系性质的证明方法关系性质的证明方法1.1.自反自反任取任取x x A A，中间过程中间过程任取任取x x A A，中间过程中间过程3.3.对称对称任取任取x,yx,y A A，假设假设 R R，中间过程中间过程 R R。R R。R R。第12页，共28页，编辑于2022年，星期四关系性质的证明方法关系性质的证明方法(续续)4.4.反对称反对称任取任取x,yx,y A A，假设，假设 R R，R R，中间过程中间过程x

13、 xy y。或者或者任取任取x,yx,y A A，xyxy，假设假设 R R，中间过程中间过程 R R。5.5.传递传递任取任取x,y,zx,y,z A A，假设，假设 R R，R R，中间过程中间过程 R R。第13页，共28页，编辑于2022年，星期四定理定理6.4.1 设设R是集合是集合A上的二元关系，则：上的二元关系，则：（1）R是自反的是自反的IA R；（2）R是反自反的是反自反的RIA；（3）R是对称的是对称的RR-1；（4）R是反对称的是反对称的RR-1 IA；（5）R是传递的是传递的R R R。6.4.2 6.4.2 关系性质的判断定理关系性质的判断定理第14页，共28页，编辑

14、于2022年，星期四证明证明（4 4）“”设设R R是反对称的。是反对称的。对对任意任意RRRR-1-1，则，则RR且且RR-1-1，即：即：RR且且RR由于由于R R是反对称的是反对称的，则，则 a ab b 所以，所以，IIA A，即，即 RRRR-1-1 I IA A。“”设设RRRR-1-1 I IA A。对对任意任意a,ba,bAA，若，若RR且且 RaR，则有：，则有：RR且且RR-1-1，即：，即：RRRR-1-1。又因又因RRRR-1-1 I IA A，所以，所以，IIA A，即，即a ab b。即即R R是反对称的。是反对称的。第15页，共28页，编辑于2022年，星期四“”

15、设设R R是传递的。是传递的。对任意对任意RR R R，根据，根据“”的定义，的定义，必存在必存在bAbA，使得，使得RR且且RR，由由R R的传递性，有的传递性，有：RR。所以，。所以，R R R R R R。“”设设R R R R R R。对任意对任意a,b,ca,b,cAA，若，若RR并且并且RR，则有：则有：RR R R，因因 R R R R R R，所以，所以，RR，即即R R是传递的。是传递的。证明（证明（5 5）第16页，共28页，编辑于2022年，星期四定理定理6.4.2 6.4.2 设设R R,S S是定义在是定义在A A上的二元关系，则：上的二元关系，则：(1)(1)若若R

16、,SR,S是是自自反反的的，则则R R-1-1,RS,RS,R,RS,RS,R S S也也是是自自反的反的；(2)(2)若若R,SR,S是是反反自自反反的的，则则R R-1-1,RS,RS,RS,RS也也是是反反自自反反的。的。(3)(3)若若R,SR,S是是对称的对称的，则，则R R-1-1,RS,RS,RS,RS也是也是对称的对称的。(4)(4)若若R,SR,S是是反对称的，反对称的，则则R R-1-1,RS,RS也是也是反对称的反对称的。(5)(5)若若R,SR,S是是传递的传递的，则，则R R-1-1,RS,RS也是也是传递的。传递的。6.4.3 6.4.3 关系性质的保守性关系性质的

17、保守性注意：注意：（1 1）逆运算与交运算具有较好的保守性；）逆运算与交运算具有较好的保守性；（2 2）并运算、差运算和复合运算的保守性较差。）并运算、差运算和复合运算的保守性较差。第17页，共28页，编辑于2022年，星期四例例 试举例说明试举例说明:（1 1）R R和和S S是是反反自自反反、反反对对称称和和传传递递的的，但但是是，RoSRoS不不一一定定具具备备反反自自反反性性，反反对对称称性性；RSRS不不一一定定具具有有反对称性和传递性；反对称性和传递性；（2 2）R R和和S S是是自自反反、对对称称和和传传递递的的，但但是是RoSRoS不不一一定定是对称和传递的，是对称和传递的，

18、R-SR-S不一定是自反和传递的。不一定是自反和传递的。解解解解 （1 1）“不不”的例：的例：设设A=1,2,3,AA=1,2,3,A上关系上关系 R=,R=,，S=,S=,。显然显然R,SR,S都是反自反的、反对称的、传递的。都是反自反的、反对称的、传递的。第18页，共28页，编辑于2022年，星期四解（续）解（续）则则 RoS=,RoS=,，不具备反自反性和反对称性；不具备反自反性和反对称性；RS=,RS=,，不具备传递性和反对称性；不具备传递性和反对称性；（2 2）“不不”的例：的例：设设A=1,2,3,AA=1,2,3,A上关系上关系 R=,R=,S=,S=,显然显然R,SR,S都是

19、自反的、对称的、传递的。都是自反的、对称的、传递的。此时，此时，RoS=,RoS=,不具备对称性和传递性；不具备对称性和传递性；R-S=,R-S=,不具备自反性和传递性；不具备自反性和传递性；第19页，共28页，编辑于2022年，星期四1.1.闭包的定义闭包的定义定义定义6.5.1 设设R是定义在是定义在A上的关系，若上的关系，若存在存在A上的另一上的另一个关系个关系R，满足：，满足：（1）R是是自反的自反的(对称的对称的、或、或传递的传递的)；（2）对任何）对任何自反的自反的(对称的对称的、或、或传递的传递的)关系关系R，如果，如果R R，就有，就有R R，则称为，则称为R的的自反闭包自反闭

20、包(对称闭对称闭包包、或、或传递闭包传递闭包)，分别记为，分别记为r(R)(s(R)或或t(R)。从定义可以看出，从定义可以看出，关系的闭包是增加最少元素，使其关系的闭包是增加最少元素，使其具备所需性质的扩充。具备所需性质的扩充。6.5 6.5 关系的闭包运算关系的闭包运算第20页，共28页，编辑于2022年，星期四2.2.闭包的简单性质闭包的简单性质关系关系R有自反性有自反性 r(R)=R关系关系R有有对称对称性性 S(R)=R关系关系R有有传递传递性性 t(R)=R3.3.闭包的计算闭包的计算定理定理6.5.1 设设R是集合是集合A上的二元关系，则：上的二元关系，则：（1）r(R)RIA。

21、（2）s(R)RR-1。（3）t(R)，若，若|A|n，则，则t(R)。第21页，共28页，编辑于2022年，星期四例例:设集合设集合A=1,2,3,4，A上关系上关系 R=,（1）画出）画出R的关系图；的关系图；（2）求出）求出r(R),s(R),t(R),并画出其相应的关系图。并画出其相应的关系图。解解:（1）R的关系图见下图；的关系图见下图；2 24 41 13 3第22页，共28页，编辑于2022年，星期四（续）（续）（2 2）r(R)=,r(R)=,；s(R)=,s(R)=,；r(R)r(R)，s(R)s(R)的关系图分别如下：的关系图分别如下：r(R)s(R)r(R)s(R)1 1

22、2 23 34 41 12 23 34 4第23页，共28页，编辑于2022年，星期四（续）（续）（2 2）R=,R R2 2=,=,；R R3 3=,=,；R R4 4=,=,=R R2 2；所以所以t(R)=,3,4t(R)=,。t(R)t(R)的关系图分别如下：的关系图分别如下：t(R)t(R)1 12 23 34 42 24 41 13 3第24页，共28页，编辑于2022年，星期四例例:求下列关系的求下列关系的r(R),s(R)和和t(R)。（1）定义在整数集定义在整数集Z上的上的“”关系；关系；（2）定义在整数集定义在整数集Z上的上的“”关系。关系。解解:（1）定义在定义在Z上的上

23、的“”关系的关系的 r(R)为为“”，s(R)为为“”，t(R)为为“”；（2）定义在定义在Z上的上的“=”关系的关系的 r(R)为为“=”，s(R)为为“=”，t(R)为为“=”。第25页，共28页，编辑于2022年，星期四6.6 6.6 本章总结本章总结1.1.序偶和笛卡儿积的概念序偶和笛卡儿积的概念2.2.二元关系的概念和表示二元关系的概念和表示3.3.关关系系的的交交、并并、补补、差差运运算算、复复合合运运算算和和逆逆运运算算4.4.关关系系性性质质的的定定义义、关关系系性性质质的的判判定定、关关系系性性质质的证明和关系性质的保守性；的证明和关系性质的保守性；5.5.关系的自反、对称、和传递闭包的概念及计算。关系的自反、对称、和传递闭包的概念及计算。第26页，共28页，编辑于2022年，星期四习习 题题23232828页页1-161-16第27页，共28页，编辑于2022年，星期四第28页，共28页，编辑于2022年，星期四