《离散数学-耿素云PPT(第5版) 4.3-4.ppt》由会员分享，可在线阅读，更多相关《离散数学-耿素云PPT(第5版) 4.3-4.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4.3 关系的性质关系的性质n自反性自反性n反自反性反自反性n对称性对称性n反对称性反对称性n传递性传递性1自反性与反自反性自反性与反自反性定义定义设设R为为A上的关系上的关系,(1)若若 x(xA R),则称则称R在在A上是上是自反自反的的.(2)若若 x(xA R),则称则称R在在A上是上是反自反反自反的的.实例：实例：反关系：反关系：A上的全域关系上的全域关系EA,恒等关系恒等关系IA小于等于关系小于等于关系LA,整除关系整除关系DA反自反关系：实数集上的小于关系反自反关系：实数集上的小于关系幂集上的真包含关系幂集上的真包含关系2实例实例例例1A=1,2,3,R1,R2,R3是是A上的关
2、系上的关系,其中其中R1,R2,R3R2自反自反,R3反自反反自反,R1既不是自反也不是反自反的既不是自反也不是反自反的3对称性与反对称性对称性与反对称性定义定义设设R为为A上的关系上的关系,(1)若若 x y(x,yARR),则称则称R为为A上上对称对称的关系的关系.(2)若若x y(x,yARRx=y),则称则称R为为A上的上的反对称反对称关系关系.实例：实例：对称关系：对称关系：A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空和空关系关系反对称关系：恒等关系反对称关系：恒等关系IA，空关系是空关系是A上的反对上的反对称关系称关系.4实例实例例例2设设A1,2,3,R1,R2,R3
3、和和R4都是都是A上的关系上的关系,其中其中R1,，R2,R3,，R4,R1对称、反对称对称、反对称.R2对称，不反对称对称，不反对称.R3反对称，不对称反对称，不对称.R4不对称、也不反对称不对称、也不反对称.5传递性传递性 定义定义设设R为为A上的关系上的关系,若若 x y z(x,y,zARRR),则称则称R是是A上的上的传递传递关系关系.实例：实例：A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系小于等于关系小于等于关系,小于关系，整除关系，包含关系，小于关系，整除关系，包含关系，真包含关系真包含关系6实例实例例例3设设A1,2,3,R1,R2,R3是是A上的关系上
4、的关系,其中其中R1,R2,R3R1和和R3是是A上的传递关系上的传递关系R2不是不是A上的传递关系上的传递关系7关系性质的充要条件关系性质的充要条件设设R为为A上的关系上的关系,则则(1)R在在A上上自反自反当且仅当当且仅当IA R(2)R在在A上上反自反反自反当且仅当当且仅当RIA=(3)R在在A上上对称对称当且仅当当且仅当R=R 1(4)R在在A上上反对称反对称当且仅当当且仅当RR 1 IA(5)R在在A上上传递传递当且仅当当且仅当R R R8关系性质判别关系性质判别自反自反反自反反自反对称对称反对称反对称传递传递表达式表达式 IA RRIA=R=R 1RR 1 IA R R R关系关系
5、矩阵矩阵主对主对角线角线元素元素全是全是1主对角主对角线元素线元素全是全是0矩阵是对称矩阵是对称矩阵矩阵若若rij1,且且ij,则则rji0对对M2中中1所在位置所在位置,M中相应中相应位置都是位置都是1关系图关系图 每个每个顶点顶点都有都有环环每个顶每个顶点都没点都没有环有环如果两个顶如果两个顶点之间有边点之间有边,是一对方向是一对方向相反的边相反的边(无单边无单边)如果两点如果两点之间有边之间有边,是一条有是一条有向边向边(无双无双向边向边)如果顶点如果顶点 xi 连通到连通到xk,则从则从 xi到到 xk 有边有边9实例实例例例8判断下图中关系的性质判断下图中关系的性质,并说明理由并说明
6、理由.(b)反自反，不是自反的；反对称，不是对称的；反自反，不是自反的；反对称，不是对称的；是传递的是传递的.(a)不自反也不反自反；对称不自反也不反自反；对称,不反对称；不传递不反对称；不传递.(c)自反，不反自反；反对称，不是对称；不传递自反，不反自反；反对称，不是对称；不传递.10自反性证明自反性证明证明模式证明模式证明证明R在在A上自反上自反任取任取x,x A.R前提前提推理过程推理过程结论结论例例4证明若证明若IA R，则则 R在在A上自反上自反.证证任取任取x,x A IA R 因此因此R 在在A 上是自反的上是自反的.11对称性证明对称性证明证明模式证明模式证明证明R在在A上对称
7、上对称任取任取 R.R前提前提推理过程推理过程结论结论例例5证明若证明若R=R 1,则则R在在A上对称上对称.证证任取任取 R R 1 R 因此因此R 在在A 上是对称的上是对称的.12反对称性证明反对称性证明证明模式证明模式证明证明R在在A上反对称上反对称任取任取 R R.x=y 前提前提推理过程推理过程结论结论例例6证明若证明若RR 1 IA,则则R在在A上反对称上反对称.证证任取任取 R R R R 1 RR 1 IA x=y因此因此R 在在A 上是反对称的上是反对称的.13传递性证明传递性证明证明模式证明模式证明证明R在在A上传递上传递任取任取，R R.R 前提前提推理过程推理过程结论
8、结论例例7证明若证明若R R R,则则R在在A上传递上传递.证证任取任取，R R R R R 因此因此R 在在A 上是传递的上是传递的.14运算与性质的关系运算与性质的关系自反性自反性反自反性反自反性对对称性称性反反对对称性称性传递传递性性R1 1R1R2R1R2R1 R2R1 R2154.4 关系的闭包关系的闭包n闭包定义闭包定义n闭包的构造方法闭包的构造方法 集合表示集合表示 矩阵表示矩阵表示 图表示图表示n闭包的性质闭包的性质 16闭包定义闭包定义定义定义设设R是非空集合是非空集合A上的关系上的关系,R的的自反（对自反（对称称或或传递）闭包传递）闭包是是A上的关系上的关系R,使得使得R
9、满足满足以下条件：以下条件：（1）R 是自反的（对称的或传递的）是自反的（对称的或传递的）（2）R R（3）对）对A上任何包含上任何包含R的自反（对称或传递）的自反（对称或传递）关系关系R 有有RR.一般将一般将R 的自反闭包记作的自反闭包记作r(R),对称闭包记作对称闭包记作s(R),传递闭包记作传递闭包记作t(R).17闭包的构造方法闭包的构造方法定理定理1设设R为为A上的关系上的关系,则有则有(1)r(R)=RR0(2)s(R)=RR 1(3)t(R)=RR2R3说明：说明：对于有穷集合对于有穷集合A(|A|=n)上的关系上的关系,(3)中的并最多中的并最多不超过不超过Rn.若若R是自反
10、的，则是自反的，则r(R)=R;若若R是对称的，则是对称的，则s(R)=R;若若R是传递的，则是传递的，则t(R)=R.18设关系设关系R,r(R),s(R),t(R)的关系矩阵分别为的关系矩阵分别为M,Mr,Ms 和和Mt,则则Mr=M+E Ms=M+MMt=M+M2+M3+E 是和是和M 同阶的单位矩阵同阶的单位矩阵,M是是M 的转置矩阵的转置矩阵.注意在上述等式中矩阵的元素相加时使用逻辑加注意在上述等式中矩阵的元素相加时使用逻辑加.闭包的构造方法（续）闭包的构造方法（续）19闭包的构造方法（续）闭包的构造方法（续）设关系设关系R,r(R),s(R),t(R)的关系图分别记为的关系图分别记
11、为G,Gr,Gs,Gt,则则Gr,Gs,Gt 的顶点集与的顶点集与G 的顶点集相等的顶点集相等.除了除了G 的的边以外边以外,以下述方法添加新边：以下述方法添加新边：考察考察G的每个顶点的每个顶点,如果没有环就加上一个环，最如果没有环就加上一个环，最终得到终得到Gr.考察考察G的每条边的每条边,如果有一条如果有一条xi 到到xj 的单向的单向边边,ij,则在则在G中加一条中加一条xj 到到xi 的反方向边，最终得到的反方向边，最终得到Gs.考察考察G的每个顶点的每个顶点xi,找从找从xi 出发的每一条路径，出发的每一条路径，如果从如果从xi 到路径中任何结点到路径中任何结点xj 没有边，就加上这条没有边，就加上这条边边.当检查完所有的顶点后就得到图当检查完所有的顶点后就得到图Gt.20实例实例例例1设设A=a,b,c,d,R=,R和和r(R),s(R),t(R)的关系图如下图所示的关系图如下图所示.Rr(R)s(R)t(R)21