第6章二元关系2.ppt

《第6章二元关系2.ppt》由会员分享，可在线阅读，更多相关《第6章二元关系2.ppt（28页珍藏版）》请在第壹文秘上搜索。

1、离离 散散 数数 学学电子科技大学电子科技大学20232023年年11 11月月7 7日星期二日星期二2 22023-11-72023-11-76.4 6.4 关系的性质关系的性质-重点重点 本节涉及到的关系，如无特别声明，都是本节涉及到的关系，如无特别声明，都是假定假定其前域和后域相同其前域和后域相同。即都为定义在集合。即都为定义在集合A A上的关系，上的关系，且且A A是非空集合是非空集合。对于前后域不相同的关系，其性。对于前后域不相同的关系，其性质无法加以定义。质无法加以定义。6.4.1 6.4.1 关系性质的定义关系性质的定义1.1.关系性质的定义关系性质的定义3 32023-11-7

2、2023-11-7定义定义6.4.1-36.4.1-3设设R R是集合是集合A A上的关系，上的关系，1.1.如果对任意如果对任意xxA A，都都有有 x,xR R，那么那么称称R R在在A A上是上是自反自反的的，或称，或称R R具有具有自反性自反性.2.2.如果对任意如果对任意xAxA，都有，都有 R R，那么称，那么称R R在在A A上是上是反自反自 反的反的，或称，或称R R具有具有反自反性反自反性。3.3.对任意对任意x,yAx,yA，如果如果RR，那么，那么 R R，则称关则称关系系R R是是对称的对称的，或称，或称R R具有具有对称性对称性；4.4.对任意对任意x,yAx,yA，

3、如果如果RR且且RR，那么，那么x xy y（或者或者,若若x xy,y,则则 与与不全属于不全属于R R），），则称则称关系关系R R是是反对称的反对称的，或称，或称R R具有具有反对称性反对称性。5.5.对任意对任意x,y,zAx,y,zA，如果，如果RR且且RR，那么，那么RR，则称关系，则称关系R R是是传递的传递的，或称，或称R R具有具有传递性传递性。4 42023-11-72023-11-7例例1 1：1.1.整数集整数集I I上的上的“等于等于”关系是自反的、反对称的、对关系是自反的、反对称的、对称的、传递的关系。称的、传递的关系。“小于等于小于等于”关系是自反的、反对称的、传

4、递的关系；关系是自反的、反对称的、传递的关系；“小于小于”关系是反自反的、反对称的、传递的关系关系是反自反的、反对称的、传递的关系。2.2.幂集上的幂集上的“包含包含”关系关系是自反的、反对称的、传递关系关系是自反的、反对称的、传递的关系的关系。3.3.命题公式集合上的蕴涵关系命题公式集合上的蕴涵关系“”具有具有自反自反性性、反对称、反对称性和性和传递传递性。性。4.4.三角形的相似关系具有三角形的相似关系具有自反自反性性、对称、对称性和性和传递传递性。性。5.5.人的集合上的人的集合上的朋友关系朋友关系具有具有自反自反性和性和对称对称性性;父子关系父子关系具有反具有反自反自反性和性和反对称性

5、反对称性.5 52023-11-72023-11-7例例2：设设A是任意的是任意的非空非空集合集合，则则 A上的全关系上的全关系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=,则则

6、 S S是反自反的是反自反的,对称的对称的.6 62023-11-72023-11-7（3 3）U=,U=,则则 U U 是是对称的对称的,反对称的反对称的,传递的传递的.（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是反自反的是反自反的 关系图中关系图中每

7、个节点都无环每个节点都无环 关系矩阵的主对角线上的元素全为关系矩阵的主对角线上的元素全为0 07 72023-11-72023-11-7(3)关系关系R是对称的是对称的 关系图中任何一对结点之间，关系图中任何一对结点之间，要么有方向相反的两条边，要么无边要么有方向相反的两条边，要么无边 关系矩关系矩阵为阵为对称矩阵对称矩阵(4)关系关系R是反对称的是反对称的 关系图中关系图中任何一对结点之任何一对结点之间，至多有一条边；间，至多有一条边；R的关系矩阵满足的关系矩阵满足 rijrji0，i,j=1,2,n，ij。(5)关系关系R是是传递传递的的 图中图中,任何三个节点任何三个节点x,y,z(x,

8、y,z(可可以相同以相同)之间，若从之间，若从x x到到y y有一条边存在有一条边存在,从从y y到到z z有有一条边存在一条边存在,则从则从x x到到z z一定有一条边存在一定有一条边存在.关系矩阵中关系矩阵中,如如果果r rijij1 1且且r rjkjk1,1,则则r rikik1 18 82023-11-72023-11-7S0 1 0M0 0 11 0 0有有:反自反性和反对称性反自反性和反对称性132有有:反自反性和反对称性反自反性和反对称性有有:自反性自反性,反对反对称性和称性和传递性传递性312例例 A=1,2,3A=1,2,3上关系上关系:9 92023-11-72023-1

9、1-7设设A Aa,b,c,a,b,c,试判断如下图所示试判断如下图所示A A上关系的性质：上关系的性质：例例a ab bc c(a)(a)a ab bc c(b)(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)的关系是具备对

10、称的关系是具备对称的、反对称的、传递的的、反对称的、传递的关系关系图图(d)(d)的关系是不具备任的关系是不具备任何的性质关系何的性质关系图图(e)(e)的关系是具备自反的关系是具备自反的、对称的、传递的关的、对称的、传递的关系系图图(f)(f)的关系是具备反自的关系是具备反自反的、反对称的、传递反的、反对称的、传递的关系的关系图图(g)(g)的关系是具备反自的关系是具备反自反的、反对称的关系反的、反对称的关系图图(h)(h)的关系是具备反自的关系是具备反自反的、反对称的、传递的反的、反对称的、传递的关系关系10102023-11-72023-11-7注注:(3)(3)存在既是对称也是反对称的

11、关系；存在既是对称也是反对称的关系；(1)非空集合非空集合A上的关系上的关系,若有自反性若有自反性,则一定没有反自则一定没有反自反性反性;反知反知,若有反自反性若有反自反性,则一定没有自反性则一定没有自反性;(2)存在既不是对称也不是反对称的关系；存在既不是对称也不是反对称的关系；(4)(4)非空集合非空集合A A上的上的空关系空关系具有反自反性、对称性、具有反自反性、对称性、反对称性和传递性；反对称性和传递性；(5)(5)空空集上的集上的空关系空关系5 5个性质都具有个性质都具有.11112023-11-72023-11-7总结总结自反自反 反自反反自反对称对称反对称反对称传递传递定定义义

12、x,xR R x,x R R x,yR RR R x,yRyRxR Rx x=y y x,yRRR RR R关关系系图图每个每个结点结点都有都有环环每个结每个结点都无点都无环环每对结点间每对结点间或有方向相或有方向相反的两条边，反的两条边，或无任何边或无任何边每对结点间至每对结点间至多有一条边存多有一条边存在在任三个结点任三个结点x,y,zx,y,z，若从若从x x到到y y有边，从有边，从y y到到z z有边，则从有边，则从x x到到z z一定有边一定有边关系关系矩阵矩阵对角对角线上线上全为全为1 1对角线对角线上全为上全为0 0对称矩阵对称矩阵r rijij r rjiji=0,=0,i,

13、j=1,2,i,j=1,2,n,n,i ij j如如r rijij1 1且且r rjkjk1 1则则r rikik1 112122023-11-72023-11-72.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。13132023-11-72023-11-7关系性质的证明方法关系性质的证明方法(续续)4.4.反对称反对称任取任取x,yx,y A A，假设，假设 R R，R R，中间过程中间

14、过程x 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。14142023-11-72023-11-7定理定理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 关系性质的判断定理关系性质的判断定理15152023-

15、11-72023-11-7证明证明（4 4）“”设设R R是反对称的。是反对称的。对对任意任意 RRa,bRR-1-1，则，则RR且且 Ra,bR-1-1，即：即：RR且且 Rb,aR由于由于R R是反对称的是反对称的，则，则 a ab b 所以，所以，a,bIIA A，即，即 RRRR-1-1 I IA A。“”设设RRRR-1-1 I IA A。对对任意任意a,ba,bAA，若若RR且且 RaR，则有：则有：RR且且 Ra,bR-1-1，即：，即：RRRR-1-1。又因又因RRRR-1-1 I IA A，所以，所以，IIA A，即，即a ab b。即即R R是反对称的。是反对称的。1616

16、2023-11-72023-11-7“”设设R R是传递的。是传递的。对任意对任意 Ra,cR R R，根据根据“”的定义，的定义，必存在必存在bAbA，使得使得 Ra,bR且且 Rb,cR，由由R R的传递性，有的传递性，有：Ra,cR。所以，所以，R R R R R R。“”设设R R R R R R。对任意对任意a,b,ca,b,cAA，若若 Ra,bR并且并且 Rb,cR，则有：则有：RR R R，因因 R R R R R R，所以，所以，RR，即即R R是传递的。是传递的。证明（证明（5 5）17172023-11-72023-11-7定理定理6.4.2 6.4.2 设设R R,S S是定义在是定义在A A上的二元关系，则：上的二元关系，则：(1)(1)若若R,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