《离散数学关系的性质ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学关系的性质ppt课件.ppt（27页珍藏版）》请在三一办公上搜索。
1、1,4.3 关系的性质,自反性反自反性对称性反对称性传递性,2,3,自反性与反自反性,例：自反关系：A上的全域关系EA,恒等关系IA 小于等于关系LA,整除关系DA反自反关系：实数集上的小于关系 幂集上的真包含关系,4,实例,例1 A=1,2,3,R1,R2,R3是A上的关系,其中R1,R2,R3,R2自反,R3反自反,R1既不是自反也不是反自反的,5,对称性与反对称性,实例：对称关系：A上的全域关系EA,恒等关系IA和空关系 反对称关系：恒等关系IA，空关系是A上的反对称关系.,6,实例,例2 设A1,2,3,R1,R2,R3和R4都是A上的关系,其中 R1,，R2,R3,，R4,R1 对称
2、、反对称.R2 对称，不反对称.R3 反对称，不对称.R4 不对称、也不反对称.,7,传递性,实例：A上的全域关系EA,恒等关系IA和空关系 小于等于关系,小于关系，整除关系，包含关系，真包含关系,8,实例,例3 设A1,2,3,R1,R2,R3是A上的关系,其中 R1,R2,R3,R1 和 R3 是A上的传递关系 R2不是A上的传递关系,9,关系性质的充要条件,设R为A上的关系,则(1)R在A上自反当且仅当 IA R(2)R在A上反自反当且仅当 RIA=(3)R在A上对称当且仅当 R=R1(4)R在A上反对称当且仅当 RR1IA(5)R在A上传递当且仅当 RRR,10,实例,例.判断下图中关
3、系的性质,并说明理由.,(2)反自反，不是自反的；反对称，不是对称的；是传递的.,(1)不自反也不反自反；对称,不反对称；不传递.,(3)自反，不反自反；反对称，不是对称；不传递.,11,自反性证明,证明模式 证明R在A上自反 任取x,xA.R 前提 推理过程 结论,例4 证明若 IA R，则 R在A上自反.证 任取x,xA IA R 因此 R 在 A 上是自反的.,12,对称性证明,证明模式 证明R在A上对称 任取 R.R 前提 推理过程 结论,例5 证明若 R=R1,则R在A上对称.证 任取 R R 1 R 因此 R 在 A 上是对称的.,13,反对称性证明,证明模式 证明R在A上反对称
4、任取 RR.x=y 前提 推理过程 结论,例6 证明若 RR1IA,则R在A上反对称.证 任取 R R R R 1 RR 1 IA x=y 因此 R 在 A 上是反对称的.,14,传递性证明,证明模式 证明R在A上传递 任取，RR.R 前提 推理过程 结论,例7 证明若 RRR,则R在A上传递.证 任取，R R RR R 因此 R 在 A 上是传递的.,15,运算与性质的关系,16,4.4 关系的闭包,闭包定义闭包的构造方法 集合表示 矩阵表示 图表示闭包的性质,17,闭包定义,定义 设R是非空集合A上的关系,R的自反（对称或传递）闭包是A上的关系R,使得R满足以下条件：（1）R是自反的（对称
5、的或传递的）（2）RR（3）对A上任何包含R的自反（对称或传递）关系 R 有 RR.一般将 R 的自反闭包记作 r(R),对称闭包记作 s(R),传递闭包记作 t(R).,18,闭包的构造方法,定理1 设R为A上的关系,则有(1)r(R)=RR0(2)s(R)=RR1(3)t(R)=RR2R3说明：对于有穷集合A(|A|=n)上的关系,(3)中的并是有 限的.若 R是自反的，则 r(R)=R;若R是对称的，则 s(R)=R;若R是传递的，则 t(R)=R.,19,（3）t(R)RR2R3,先证RR2 t(R)成立，为此只需证明对任意的正整数n有 Rn t(R)即可。用归纳法。n1时，有 R1R
6、 t(R)。假设Rnt(R)成立，那么对任意的有 Rn+1Rn R t(RnR)t(t(R)t(R)t(R)（因为t(R)是传递的）这就证明了Rn+1 t(R)。由归纳法命题得证。,20,再证t(R)RR2成立，为此只须证明RR2是传递的。任取,，则 RR2 RR2 t(Rt)s(Rs)ts(Rt Rs)ts(Rt Rs)ts(Rt+s)RR2从而证明了RR2是传递的。,21,推论 设R为有穷集A上的关系，则存在正整数r使得 t(R)=RR2Rr,22,闭包的构造方法（续）,设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms 和 Mt,则 Mr=M+E Ms=M+M Mt=M
7、+M2+M3+E 是和 M 同阶的单位矩阵,M是 M 的转置矩阵.注意在上述等式中矩阵的元素相加时使用逻辑加.,23,闭包的构造方法（续）,设关系R,r(R),r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt 的顶点集与G 的顶点集相等.除了G 的边以外,以下述方法添加新边：(1)考察G的每个顶点,如果没有环就加上一个环，最终得到Gr.(2)考察G的每条边,如果有一条 xi 到 xj 的单向边,ij,则在G 中加一条 xj 到 xi 的反方向边，最终得到Gs.(3)考察G的每个顶点 xi,找从 xi 出发的每一条 长度不超过n的 路径，如果从 xi 到路径中任何结点 xj 没有边，就加上这条 边.当检查完所 有的顶点后就得到图Gt.,24,实例,例1 设A=a,b,c,d,R=,R和 r(R),s(R),t(R)的关系图如下图所示.,R,r(R),s(R),t(R),25,R=,r(R)=RR0=,=,s(R)=RR1=,=,t(R)=R1R2R3R4=,=,26,Mr=Ms=Mt=,27,定理7.11 设R是非空集合A上的关系，则（1）R是自反的当且仅当r(R)R。（2）R是对称的当且仅当s(R)R。（3）R是传递的当且仅当t(R)R。,
