离散数学43关系的性质PPT课件.pptx

1
对称性与反对称性
例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>}
设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 不对称、也不反对称
第1页/共21页
2
传递性
例3 设A＝{a, b, c}, R1, R2, R3是A上的关系, 其中 R1＝{<a,a>,<b,b>} R2＝{<a,b>,<b,c>} R3＝{<a,c>}
设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上的传递关系.
第2页/共21页
3
关系性质的充要条件
设 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
第3页/共21页
4
自反性证明
证明模式 证明 R 在 A 上自反
任取 x,
xA  ……… ………..…. …….  <x, x>R
前提 推理过程 结论
例4 证明若 IA R ，则 R 在 A 上自反.
证 任取x, xA  <x, x> IA  <x, x>R 因此 R 在 A 上是自反的.
第4页/共21页
5
对称性证明
证明模式 证明 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 上是对称的.
第5页/共21页
6
反对称性证明
证明模式 证明 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 上是反对称的.
第6页/共21页
7
传递性证明
证明模式 证明 R 在 A上传递
任取<x, y>，<y, z>
<x, y>R<y, z>R …..……….  <x, z>R
前提 推理过程 结论
例7 证明若 R∘RR , 则 R 在 A 上传递.
证 任取<x, y>，<y, z>
<x, y>R <y, z>R  <x, z>