离散数学课件：第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反自反关系：实数集上的小于关系反自反关系：实数集上的小于关系 幂集上的真包含关系幂集上的真包含关系非自反非自反 与与 反自反反自反，

2、 非反自反非反自反与与自反自反 的区别的区别3实例实例例例1 A=1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中R1,R2,R3R2自反自反, R3反自反反自反, R1既既不是自反不是自反也也不是反自反不是反自反的的4对称性与反对称性对称性与反对称性定义定义 设设R为为A上的关系上的关系, (1)称称R为为A上上对称对称的关系，是指的关系，是指R满足满足 ： x y( x,yA xRy yRx ), (2)称称R为为A上的上的反反对称对称关系，是指关系，是指R满足：满足： x y( x,yA xRy xy yR x ) 或等价地或等价地： x y( x,yA xRy yR

3、x x=y) .实例：实例：对称关系：对称关系：A上的全域关系上的全域关系EA, 恒等关系恒等关系IA和和空关系空关系反对称关系：反对称关系：恒等关系恒等关系IA，空关系空关系5实例实例例例2 设设A1,2,3, R1, R2, R3和和R4都是都是A上的关系上的关系, R1,， R2, R3,， R4, R1 对称、反对称对称、反对称. R2 对称，不反对称对称，不反对称. R3 反对称，不对称反对称，不对称. R4 不对称、也不反对称不对称、也不反对称.6传递性传递性 定义定义 设设R为为A上的关系上的关系,称称R是是A上的上的传递传递关系，是关系，是指指R是满足：是满足： x y z(

4、x,y,zA xRy yRz xRz),满足传递性的关系实例满足传递性的关系实例： A上的上的全域关系全域关系EA,恒等关系恒等关系IA和和空关系空关系 小于等于关系小于等于关系, 小于关系，整除关系，包含关系，小于关系，整除关系，包含关系， 真包含关系真包含关系7实例实例例例3 设设A1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3R1 和和 R3 是是A上的传递关系上的传递关系 R2不是不是A上的传递关系上的传递关系8关系性质的充要条件关系性质的充要条件设设R为为A上的关系上的关系, 则则 (1) R在在A上上自反自反当且仅当当且仅当 IA R (

5、2) R在在A上上反自反反自反当且仅当当且仅当 RIA= (3) R在在A上上对称对称当且仅当当且仅当 R=R 1 (4) R在在A上上反对称反对称当且仅当当且仅当 RR 1 IA (5) R在在A上上传递传递当且仅当当且仅当 R R R 提示：提示： 利用利用 关系矩阵关系矩阵和和关系图关系图来帮助理解来帮助理解9关系性质判别方法关系性质判别方法自反自反反自反反自反对称对称反对称反对称传递传递集合表集合表达式达式IA RRIA=R=R 1 RR 1 IA R R R关系关系矩阵矩阵主对主对角线角线元素元素全是全是1主对角主对角线元素线元素全是全是0矩阵是对称矩阵是对称矩阵矩阵若若rij1,

6、且且ij, 则则rji0凡凡M2中中1所在位置所在位置,M中相应中相应位置也是位置也是1关系图关系图每个每个顶点顶点都有都有环环每个顶每个顶点点都没都没有有环环如果两个顶如果两个顶点之间有边点之间有边, 一定是双向一定是双向边边(无单边无单边)如果两点如果两点之间有边之间有边, 则则只有只有单单向边向边(无双无双向边向边)如果顶点如果顶点 xi 到到xk可可达达, 则从则从 xi到到 xk 有边有边 10实例实例例例8 判断下图中关系的性质判断下图中关系的性质, 并说明理由并说明理由.(b) 反自反；非对称的，反对称；反自反；非对称的，反对称； 是传递的是传递的.(a) 非自反也非反自反；对称

7、非自反也非反自反；对称, 不反对称；不传递不反对称；不传递.(c) 自反；非对称，反对称；不传递自反；非对称，反对称；不传递. 11自反性证明自反性证明证明模式证明模式 证明证明R在在A上自反上自反 任取任取x, x A . R 前提前提 推理过程推理过程 结论结论例例4 证明若证明若 IA R ，则则 R在在A上自反上自反. 证证 任取任取x, x A IA R 因此因此 R 在在 A 上是自反的上是自反的.12对称性证明对称性证明证明模式证明模式 证明证明R在在A上对称上对称 任取任取 R . R 前提前提 推理过程推理过程 结论结论例例5 证明若证明若 R=R 1 , 则则R在在A上对称

8、上对称. 证证 任取任取 R R 1 R 因此因此 R 在在 A 上是对称的上是对称的.13反对称性证明反对称性证明证明模式证明模式 证明证明R在在A上反对称上反对称 任取任取 R R . x=y 前提前提 推理过程推理过程 结论结论例例6 证明若证明若 RR 1 IA , 则则R在在A上反对称上反对称. 证证 任取任取 R R R R 1 RR 1 IA x=y 因此因此 R 在在 A 上是反对称的上是反对称的.14传递性证明传递性证明证明模式证明模式 证明证明R在在A上传递上传递 任取任取， R R . R 前提前提 推理过程推理过程 结论结论例例7 证明若证明若 R R R , 则则R在

9、在A上传递上传递. 证证 任取任取， R R R R R 因此因此 R 在在 A 上是传递的上是传递的.15关系的运算与性质的保持关系的运算与性质的保持自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R1 1 R1R2 R1R2 R1 R2 R1 R2 关系运算与性质保持 举例16对对 R1R2 ： 不能保持不能保持反对称性反对称性 ：R1=, R2 =传递性：传递性： R1=, R2 = 对对 R1 R2 ：不能保持不能保持 自反性：自反性：R1=, , R2 =, ; R1-R2 =, 传递性：传递性：R1=, , R2 = ; R1-R2 =, , 对对R1 R2 ：

10、不能保持不能保持 反自反：反自反：R1=R2 =, ;对称性：对称性：R1=, ，R2 = ;反对称：反对称：R1=, ，R2 =， ;传递性：传递性：R1=, ，R2 =， ;174.4 关系的闭包关系的闭包n闭包定义闭包定义n闭包的构造方法闭包的构造方法 集合表示集合表示 矩阵表示矩阵表示 图表示图表示n闭包的性质闭包的性质 18闭包定义闭包定义 定义定义 设设R是非空集合是非空集合A上的关系上的关系, R的的自反自反（对称对称或或传递传递）闭包闭包是是A上上满足满足以以下条件下条件的关系的关系R ：（1）R 是自反的（是自反的（对称对称的或的或传递传递的）的）（2）R R （3）对）对A

11、上上任何包含任何包含R的自反的自反（对称对称或或传递传递）关关系系 R 有有 RR . 一般将一般将 R 的自反闭包记作的自反闭包记作 r(R), 对称闭包记作对称闭包记作 s(R), 传递闭包记作传递闭包记作 t(R). 显然显然：若若 R是自反的，则是自反的，则 r(R)=R; 若若R是对称的，则是对称的，则 s(R)=R; 若若R是传递的，则是传递的，则 t(R)=R. 19闭包的构造方法闭包的构造方法定理定理4.4 设设R为为A上的关系上的关系, 则有则有 (1) r(R) = RR0 = RIA(2) s(R) = RR 1(3) t(R) = RR2R3对于对于有穷集合有穷集合A

12、(|A|=n) 上的关系上的关系, (3)中参与中参与并的集合并的集合最多到最多到Rn. 记关系记关系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 的转置的转置矩阵矩阵. 注意在上述等式中矩阵的元素相加时注意在上述等式中矩阵的元素相加时使用逻使用逻辑加辑加.】20闭包的构造方法（闭包的构造方法（关系矩阵法关系矩阵法）21闭包的构造方法（闭包的构造方法（关系图法关系图法）记关系记关系R, r(R), s(R), t(R)的关系图分别为的关系图分别为G, Gr , Gs , Gt , 则则Gr, Gs, Gt 的顶点集与的顶点集与G 的顶点集相等；此外，除了的顶点集相等；此外，除了G 的边以外的边以外, 以下以下述方法添加新边可得到各闭包的关系图：述方法添加新边可得到各闭包的关系图： 为为G没有环没有环的顶点加一个环，最终得到的顶点加一个环，最终得到Gr . 考察考察G的边的边, 若仅存在若仅存在 从从xi 到到 xj （ij）的单向边的单向边, 则加入一则加入一条从条从 xj 到到 xi 的反向边，最终得到的反向边，最终得到Gs. 考察考察G的的