第6章二元关系2.ppt

离 散 数 学,电子科技大学,2023年11月7日星期二,2023/11/7,6.4 关系的性质-重点,本节涉及到的关系，如无特别声明，都是假定其前域和后域相同。即都为定义在集合A上的关系，且A是非空集合。对于前后域不相同的关系，其性质无法加以定义。,6.4.1 关系性质的定义,1.关系性质的定义,2023/11/7,定义6.4.1-3设R是集合A上的关系，1.如果对任意xA，都有R，那么称R在A上是自反的，或称R具有自反性.,2.如果对任意xA，都有 R，那么称R在A上是反自 反的，或称R具有反自反性。,3.对任意x,yA，如果R，那么 R，则称关系R是对称的，或称R具有对称性；4.对任意x,yA，如果R且R，那么xy（或者,若xy,则 与不全属于R），则称关系R是反对称的，或称R具有反对称性。,5.对任意x,y,zA，如果R且R，那么R，则称关系R是传递的，或称R具有传递性。,2023/11/7,例1：1.整数集I上的“等于”关系是自反的、反对称的、对称的、传递的关系。“小于等于”关系是自反的、反对称的、传递的关系；“小于”关系是反自反的、反对称的、传递的关系。2.幂集上的“包含”关系关系是自反的、反对称的、传递的关系。3.命题公式集合上的蕴涵关系“”具有自反性、反对称性和传递性。4.三角形的相似关系具有自反性、对称性和传递性。5.人的集合上的朋友关系具有自反性和对称性;父子关系具有反自反性和反对称性.,2023/11/7,例2：设A是任意的非空集合，则 A上的全关系AA是 自反的、对称的、传递的关系；A上的空关系是 反自反的、反对称的、对称的、传 递的关系；A上的恒等关系IA是 自反的、对称的、反对称的、传 递的关系。,例3：设A=1,2,3，A上的关系：,（1）R=,则 R是自反的,反对称的,传递的.（2）S=,则 S是反自反的,对称的.,2023/11/7,（3）U=,则 U 是对称的,反对称的,传递的.（4）V=,则 V 是反对称的,传递的.（5）T=,则 T 5个性质都没有.,2.“性质”在关系图和关系矩阵上的反应,（1）关系R是自反的 关系图中每个节点都有环 关系矩阵的主对角线上的元素全为1,（2）关系R是反自反的 关系图中每个节点都无环 关系矩阵的主对角线上的元素全为0,2023/11/7,(3)关系R是对称的 关系图中任何一对结点之间，要么有方向相反的两条边，要么无边 关系矩阵为对称矩阵(4)关系R是反对称的 关系图中任何一对结点之间，至多有一条边；R的关系矩阵满足 rijrji0，i,j=1,2,n，ij。(5)关系R是传递的 图中,任何三个节点x,y,z(可以相同)之间，若从x到y有一条边存在,从y到z有一条边存在,则从x到z一定有一条边存在.,关系矩阵中,如果rij1且rjk1,则rik1,2023/11/7,有:反自反性和反对称性,有:反自反性和反对称性,有:自反性,反对称性和传递性,例 A=1,2,3上关系:,2023/11/7,设Aa,b,c,试判断如下图所示A上关系的性质：,例,图(a)的关系是自反的、对称的、反对称的、传递的关系,图(b)的关系是具备反自反的、对称的、反对称的、传递的关系,图(c)的关系是具备对称的、反对称的、传递的关系,图(d)的关系是不具备任何的性质关系,图(e)的关系是具备自反的、对称的、传递的关系,图(f)的关系是具备反自反的、反对称的、传递的关系,图(g)的关系是具备反自反的、反对称的关系,图(h)的关系是具备反自反的、反对称的、传递的关系,2023/11/7,注:,(3)存在既是对称也是反对称的关系；,(1)非空集合A上的关系,若有自反性,则一定没有反自反性;反知,若有反自反性,则一定没有自反性;(2)存在既不是对称也不是反对称的关系；,(4)非空集合A上的空关系具有反自反性、对称性、反对称性和传递性；,(5)空集上的空关系5个性质都具有.,2023/11/7,总结,2023/11/7,反自反,关系性质的证明方法,自反,任取xA，,中间过程,任取xA，,中间过程,对称,任取x,yA，假设R，,中间过程,R。,R。,R。,2023/11/7,关系性质的证明方法(续),反对称,任取x,yA，假设R，R，,中间过程,xy。,或者,任取x,yA，xy，假设R，,中间过程,R。,传递,任取x,y,zA，假设R，R，,中间过程,R。,2023/11/7,定理6.4.1 设R是集合A上的二元关系，则：（1）R是自反的IAR；（2）R是反自反的RIA；（3）R是对称的RR-1；（4）R是反对称的RR-1IA；（5）R是传递的RR R。,6.4.2 关系性质的判断定理,2023/11/7,证明（4）,“”设R是反对称的。对任意RR-1，则R且R-1，即：R且R由于R是反对称的，则 ab 所以，IA，即 RR-1IA。“”设RR-1IA。对任意a,bA，若R且R，则有：R且R-1，即：RR-1。又因RR-1IA，所以，IA，即ab。即R是反对称的。,2023/11/7,“”设R是传递的。对任意RR，根据“”的定义，必存在bA，使得R且R，由R的传递性，有：R。所以，RRR。“”设RRR。对任意a,b,cA，若R并且R，则有：RR，因 RRR，所以，R，即R是传递的。,证明（5）,2023/11/7,定理6.4.2 设R,S是定义在A上的二元关系，则：(1)若R,S是自反的，则R-1,RS,RS,RS也是自反的；(2)若R,S是反自反的，则R-1,RS,RS也是反自反的。(3)若R,S是对称的，则R-1,RS,RS也是对称的。(4)若R,S是反对称的，则R-1,RS也是反对称的。(5)若R,S是传递的，则R-1,RS也是传递的。,6.4.3 关系性质的保守性,注意：（1）逆运算与交运算具有较好的保守性；（2）并运算、差运算和复合运算的保守性较差。,2023/11/7,例 试举例说明:（1）R和S是反自反、反对称和传递的，但是，RoS不一定具备反自反性，反对称性；RS不一定具有反对称性和传递性；（2）R和S是自反、对称和传递的，但是RoS不一定是对称和传递的，R-S不一定是自反和传递的。,解（1）“不”的例：设A=1,2,3,A上关系 R=,，S=,。显然R,S都是反自反的、反对称的、传递的。,2023/11/7,解（续）,则 RoS=,，不具备反自反性和反对称性；RS=,，不具备传递性和反对称性；（2）“不”的例：设A=1,2,3,A上关系 R=,S=,显然R,S都是自反的、对称的、传递的。此时，RoS=,不具备对称性和传递性；R-S=,不具备自反性和传递性；,2023/11/7,1.闭包的定义,定义6.5.1 设R是定义在A上的关系，若存在A上的另一个关系R，满足：（1）R是自反的(对称的、或传递的)；（2）对任何自反的(对称的、或传递的)关系R，如果R R，就有R R，则称为R的自反闭包(对称闭包、或传递闭包)，分别记为r(R)(s(R)或t(R)。从定义可以看出，关系的闭包是增加最少元素，使其具备所需性质的扩充。,6.5 关系的闭包运算,2023/11/7,2.闭包的简单性质,关系R有自反性 r(R)=R关系R有对称性 S(R)=R关系R有传递性 t(R)=R,3.闭包的计算,定理6.5.1 设R是集合A上的二元关系，则：（1）r(R)RIA。（2）s(R)RR-1。,（3）t(R)，若|A|n，则t(R)。,2023/11/7,例:设集合A=1,2,3,4，A上关系 R=,（1）画出R的关系图；（2）求出r(R),s(R),t(R),并画出其相应的关系图。解:（1）R的关系图见下图；,2023/11/7,（续）（2）,r(R)=,；s(R)=,；r(R)，s(R)的关系图分别如下：,2023/11/7,（续）（2）R=,R2=,；R3=,；R4=,=R2；所以t(R)=,。t(R)的关系图分别如下：,2023/11/7,例:求下列关系的r(R),s(R)和t(R)。（1）定义在整数集Z上的“”关系；（2）定义在整数集Z上的“”关系。,解:（1）定义在Z上的“”关系的 r(R)为“”，s(R)为“”，t(R)为“”；（2）定义在Z上的“=”关系的 r(R)为“=”，s(R)为“=”，t(R)为“=”。,2023/11/7,6.6 本章总结,序偶和笛卡儿积的概念二元关系的概念和表示关系的交、并、补、差运算、复合运算和逆运算关系性质的定义、关系性质的判定、关系性质的证明和关系性质的保守性；关系的自反、对称、和传递闭包的概念及计算。,2023/11/7,习 题,2328页1-16,Thank You!,