离散数学43关系的性质.pptxVIP

1 自反性与反自反性 定义4.14 设R为A上的关系,  (1) 若x(x∈A→x,xR), 则称R在A上是自反的. (2) 若x(x∈A→x,xR), 则称R在A上是反自反的. 自反：A上的全域关系EA, 恒等关系IA, 小于等于关系LA, 整除关系DA 反自反：实数集上的小于关系、幂集上的真包含关系. R2自反, R3 反自反, R1既不自反也不反自反. 例1 A = {a, b, c}, R1, R2, R3 是 A上的关系, 其中 R1 = {a,a,b,b} R2 = {a,a,b,b,c,c,a,b} R3 = {a,c} 2 对称性与反对称性 例2 设A＝{a,b,c}, R1, R2, R3和R4都是A上的关系, 其中  R1＝{a,a,b,b}， R2＝{a,a,a,b,b,a} R3＝{a,b,a,c}， R4＝{a,b,b,a,a,c} 定义4.15 设R为A上的关系, (1) 若xy(x,y∈A∧x,y∈R→y,x∈R), 则称R为A上 对称的关系.(2) 若xy(x,y∈A∧x,y∈R∧y,x∈R→x=y), 则称R 为A上的反对称关系.实例 对称：A上的全域关系EA, 恒等关系IA和空关系 反对称：恒等关系IA，空关系是A上的反对称关系 R1 对称、反对称. R2 对称，不反对称. R3 反对称，不对称. R4 不对称、也不反对称 3 传递性 例3 设A＝{a, b, c}, R1, R2, R3是A上的关系, 其中 R1＝{a,a,b,b} R2＝{a,b,b,c} R3＝{a,c} 定义4.16 设R为A上的关系, 若 xyz(x,y,z∈A∧x,y∈R∧y,z∈R→x,z∈R),则称R是A上的传递关系.实例：A上的全域关系 EA, 恒等关系 IA 和空关系 , 小 于等于关系, 小于关系, 整除关系, 包含关系, 真包含关系 R1 和 R3 是A上的传递关系, R2不是A上的传递关系. 4 关系性质的充要条件 设 R 为 A 上的关系, 则 (1) R 在 A 上自反当且仅当 IA R (2) R 在 A 上反自反当且仅当 R∩IA= (3) R 在 A 上对称当且仅当 R=R1 (4) R 在 A 上反对称当且仅当 R∩R1IA  (5) R 在 A 上传递当且仅当 R∘RR  5 自反性证明 证明模式 证明 R 在 A 上自反 任取 x, xA  ……… ………..…. …….  x, xR 前提 推理过程 结论 例4 证明若 IA R ，则 R 在 A 上自反. 证 任取x, xA  x, x IA  x, xR 因此 R 在 A 上是自反的. 6 对称性证明 证明模式 证明 R 在 A 上对称 任取x, y x, yR …… ………..…. …….  y, xR 前提 推理过程 结论 例5 证明若 R=R1 , 则 R 在A上对称. 证 任取x, y x, yR  y, xR 1  y, xR 因此 R 在 A 上是对称的. 7 反对称性证明 证明模式 证明 R 在 A 上反对称 任取x, y x, yRy, xR  ………..……….  x=y 前提 推理过程 结论 例6 证明若 R∩R1IA , 则 R 在 A 上反对称. 证 任取x, y x, yR y, xR  x, yR x, yR 1  x, yR∩R 1  x, yIA  x=y 因此 R 在 A 上是反对称的. 8 传递性证明 证明模式 证明 R 在 A上传递 任取x, y，y, z x, yRy, zR …..……….  x, zR 前提