离散数学：第4章 二元关系与函数2

1、14.3 关系的性质关系的性质n自反性自反性n反自反性反自反性n对称性对称性n反对称性反对称性n传递性传递性2自反性与反自反性自反性与反自反性定义定义 设设R为为A上的关系上的关系, (1) 若若 x(xA R), 则称则称R在在A上是上是自反自反的的.(2) 若若 x(xA R), 则称则称R在在A上是上是反自反反自反的的.实例：实例：自反关系：自反关系：A上的全域关系上的全域关系EA, 恒等关系恒等关系IA 小于等于关系小于等于关系LA, 整除关系整除关系DA反自反关系：实数集上的小于关系反自反关系：实数集上的小于关系 幂集上的真包含关系幂集上的真包含关系3实例实例例例1 A=1,2,3,

2、 R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3R1既不是自反也不是反自反的既不是自反也不是反自反的R2自反自反, R3反自反反自反, 4对称性与反对称性对称性与反对称性定义定义 设设R为为A上的关系上的关系, (1) 若若 x y(x,yARR), 则称则称R为为A上上对称对称的关系的关系. (2) 若若 x y(x,yARx y R), 则称则称R为为A上的上的反对称反对称关系关系实例：实例： 对称关系：对称关系：A上的全域关系上的全域关系EA, 恒等关系恒等关系IA和空和空关系关系 反对称关系：恒等关系反对称关系：恒等关系IA，空关系是空关系是A上的反对上的

3、反对称关系称关系. 5实例实例例例2 设设A1,2,3, R1, R2, R3和和R4都是都是A上的关系上的关系, 其中其中 R1, R2, R3, R4, R1 对称、反对称对称、反对称. R2 对称，不反对称对称，不反对称. R3 反对称，不对称反对称，不对称. R4 不对称、也不反对称不对称、也不反对称.6传递性传递性 定义定义 设设R为为A上的关系上的关系, 若若 x y z(x,y,zARRR),则称则称R是是A上的上的传递传递关系关系.实例：实例： A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系 小于等于关系小于等于关系, 小于关系，整除关系，包含关系，小于关

4、系，整除关系，包含关系， 真包含关系真包含关系7实例实例R1 是是A上的传递关系上的传递关系 R2不是不是A上的传递关系上的传递关系R3 是是A上的传递关系上的传递关系例例3 设设A1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中R1, , R2,R3, 8关系性质的充要条件关系性质的充要条件设设R为为A上的关系上的关系, 则则 (1) R在在A上上自反自反当且仅当当且仅当 IA R (2) R在在A上上反自反反自反当且仅当当且仅当 RIA= (3) R在在A上上对称对称当且仅当当且仅当 R=R 1 (4) R在在A上上反对称反对称当且仅当当且仅当 RR 1 IA (5)

5、R在在A上上传递传递当且仅当当且仅当 R R R 9关系性质判别关系性质判别自反自反反自反反自反对称对称反对称反对称传递传递表达式表达式 IA RRIA=R=R 1 RR 1 IA R R R关系关系矩阵矩阵主对主对角线角线元素元素全是全是1主对角主对角线元素线元素全是全是0矩阵是对称矩阵是对称矩阵矩阵若若rij1, 且且ij, 则则rji0对对M2中中1所在位置所在位置,M中相应中相应位置都是位置都是1关系图关系图 每个每个顶点顶点都有都有环环每个顶每个顶点都没点都没有环有环如果两个顶如果两个顶点之间有边点之间有边, 是一对方向是一对方向相反的边相反的边(无单边无单边)如果两点如果两点之间有

6、边之间有边, 是一条有是一条有向边向边(无双无双向边向边)如果顶点如果顶点 xi 连通到连通到xk , 则从则从 xi到到 xk 有边有边 10实例实例例例8 判断下图中关系的性质判断下图中关系的性质, 并说明理由并说明理由.(2)反自反，不是自反的；反对称，不是对称的；反自反，不是自反的；反对称，不是对称的； 是传递的是传递的.(1)不自反也不反自反；对称不自反也不反自反；对称, 不反对称；不传递不反对称；不传递.(3)自反，不反自反；反对称，不是对称；不传递自反，不反自反；反对称，不是对称；不传递. 11自反性证明自反性证明证明模式证明模式 证明证明R在在A上自反上自反 任取任取x, x

7、A . R 前提前提 推理过程推理过程 结论结论例例4 证明若证明若 IA R ，则则 R在在A上自反上自反. 证证 任取任取x, x A IA R 因此因此 R 在在 A 上是自反的上是自反的.12实例实例n设 ,在A上定义二元关系R如下： 证明：R是A上的自反关系。证证：对于任意的ZZAZvuyxyuxvRvuyx,其中Ayx ,Ryxyxyxxy,13对称性证明对称性证明证明模式证明模式 证明证明R在在A上对称上对称 任取任取 R . R 前提前提 推理过程推理过程 结论结论例例5 证明若证明若 R=R 1 , 则则R在在A上对称上对称. 证证 任取任取 R R 1 R 因此因此 R 在

8、在 A 上是对称的上是对称的.14实例实例n设 ,在A上定义二元关系R如下： 证明：R是A上的对称关系。证证：对于任意的ZZAZvuyxyuxvRvuyx,其中Rvuyx,Ryxvuvxuyyuxv,15反对称性证明反对称性证明证明模式证明模式 证明证明R在在A上反对称上反对称 任取任取 R R . x=y 前提前提 推理过程推理过程 结论结论例例6 证明若证明若 RR 1 IA , 则则R在在A上反对称上反对称. 证证 任取任取 R R R R 1 RR 1 IA x=y 因此因此 R 在在 A 上是反对称的上是反对称的.16传递性证明传递性证明证明模式证明模式 证明证明R在在A上传递上传递

9、 任取任取， R R . R 前提前提 推理过程推理过程 结论结论例例7 证明若证明若 R R R , 则则R在在A上传递上传递. 证证 任取任取， R R R R R 因此因此 R 在在 A 上是传递的上是传递的.17运算与性质的关系运算与性质的关系自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R1 1 R1R2 R1R2 R1 R2 R1 R2 184.4 关系的闭包关系的闭包n闭包定义闭包定义n闭包的构造方法闭包的构造方法 集合表示集合表示 矩阵表示矩阵表示 图表示图表示n闭包的性质闭包的性质 19闭包定义闭包定义 定义定义 设设R是非空集合是非空集合A上的关系上的

10、关系, R的的自反（对自反（对称称或或传递）闭包传递）闭包是是A上的关系上的关系R , 使得使得R 满足以满足以下条件：下条件：（1）R 是自反的（对称的或传递的）是自反的（对称的或传递的）（2）R R （3）对）对A上任何包含上任何包含R的自反（对称或传递）的自反（对称或传递）关系关系 R 有有 RR . 一般将一般将 R 的自反闭包记作的自反闭包记作 r(R), 对称闭包记作对称闭包记作 s(R), 传递闭包记作传递闭包记作 t(R). 20闭包的构造方法闭包的构造方法定理定理1 设设R为为A上的关系上的关系, 则有则有 (1) r(R) = RR0 (2) s(R) = RR 1 (3)

11、 t(R) = RR2R3说明：说明： 对于有穷集合对于有穷集合A (|A|=n) 上的关系上的关系, (3)中的并最多中的并最多 不超过不超过 Rn. 若若 R是自反的，则是自反的，则 r(R)=R; 若若R是对称的，则是对称的，则 s(R)=R; 若若R是传递的，则是传递的，则 t(R)=R. 21设关系设关系R, r(R), s(R), t(R)的关系矩阵分别为的关系矩阵分别为M, Mr, Ms 和和 Mt , 则则 Mr = M + E Ms = M + M Mt = M + M2 + M3 + E 是和是和 M 同阶的单位矩阵同阶的单位矩阵, M是是 M 的转置矩阵的转置矩阵. 注意

12、在上述等式中矩阵的元素相加时使用逻辑加注意在上述等式中矩阵的元素相加时使用逻辑加.闭包的构造方法（续）闭包的构造方法（续）22关系矩阵的加法CcccccccccbbbbbbbbbaaaaaaaaaBAnmnnmmnmnnmmnmnnmm.212222111211212222111211212222111211对应元素相加元素相加是逻辑加对应元素相加元素相加是逻辑加(逻辑或逻辑或) ijijba ijc23闭包的构造方法（续）闭包的构造方法（续）设关系设关系R, r(R), s(R), t(R)的关系图分别记为的关系图分别记为G, Gr, Gs, Gt , 则则Gr, Gs, Gt 的顶点集与的

13、顶点集与G 的顶点集相等的顶点集相等. 除了除了G 的边以外的边以外, 以下述方法添加新边：以下述方法添加新边： 考察考察G的每个顶点的每个顶点, 如果没有环就加上一个环，最如果没有环就加上一个环，最终得到终得到Gr . 考察考察G的每条边的每条边, 如果有一条如果有一条 xi 到到 xj 的单的单向边向边, ij, 则在则在G中加一条中加一条 xj 到到 xi 的反方向边，最终的反方向边，最终得到得到Gs. 考察考察G的每个顶点的每个顶点 xi, 找从找从 xi 出发的每一条路出发的每一条路径，如果从径，如果从 xi 到路径中任何结点到路径中任何结点 xj 没有边，就加上没有边，就加上这条边这条边. 当检查完所有的顶点后就得到图当检查完所有的顶点后就得到图Gt . 24实例实例例例1 设设A=a,b,c,d, R=, R和和 r(R), s(R), t(R)的关系图如下图所示的关系图如下图所示. Rr(R)s