《第四章 二元关系-2nd-zhou课件》由会员分享,可在线阅读,更多相关《第四章 二元关系-2nd-zhou课件(28页珍藏版)》请在金锄头文库上搜索。
1、第四章 二元关系,2/45,2/45,回顾,关系的定义和性质 关系的表示方法 关系图 关系矩阵 关系的运算 关系的合成 关系合成的规则 关系的幂,4.3关系的性质,定义:设R为A上的二元关系,(1)若对每个 ,皆有 ,则称R为自反的。用式子来表述即是: R是自反的,(2)若对每个 ,皆有 ,则称R为反自反的。用式子来表述即是: R是反自反的,关系的性质,(3) 对任意的 ,若 ,则 ,就称R为对称的。用式子来表述即是: R是对称的,(4) 对任意的 ,若 且 , 则x=y,就称R为反对称的。用式子来表述即是: R是反对称的,关系的性质,关系的性质,例1:考虑自然数集合上的普通相等关系“=”,大
2、于关系“”和大于等于关系“ ”具有的性质。,解:,(1) “=”关系是自反的、对称的、反对称的、可传递的;,(2)“”关系是反自反的、反对称的、可传递的;,(3)“ ”关系是自反的、反对称的、可传递的。,例2:空集上的二元关系的性质。,自反的、对称的、反对称的、反自反的、可传递的,区分概念:空关系vs空集上的关系,空关系:对于任何集合A, 称空集为A上的空关系.,性质:若A非空,空关系是反自反的,对称的,反对称的,可传递的; 若A是空集,该空关系是自反的,反自反的,对称的,反对称的,可传递的,空集上的关系:自反的,反自反的,对称的,反对称的, 可传递的。在空集上可定义任意元关系。,关系性质成立
3、的充要条件,定理7.9 设R为A上的关系, 则 (1) R 在A上自反当且仅当 IA R (2) R 在A上反自反当且仅当 RIA = (3) R 在A上对称当且仅当 R=R1 (4) R 在A上反对称当且仅当 RR1 IA (5) R 在A上传递当且仅当 RR R,证明,证明 只证(1)、(3)、(4)、(5) (1) 必要性 任取, 由于R 在A上自反必有 IA x,yAx=y R 从而证明了IAR 充分性. 任取x, 有 xA IA R 因此 R 在A上是自反的.,证明,(3) 必要性. 任取, R R R1 所以 R = R1 充分性. 任取, 由R = R1得R R1 R 所以R在A
4、上是对称的,证明,(4) 必要性. 任取, 有 RR1 RR1 RR x=y x,yA IA 这就证明了RR1IA 充分性. 任取, RR RR1 RR1 IA x=y 从而证明了R在A上是反对称的.,证明,(5) 必要性. 任取有 RR t (RR) R 所以 RR R 充分性. 任取,R, 则 RR RR R 所以 R 在 A上是传递的,关系性质的三种等价条件,关系的性质和运算之间的联系,15/45,15/45,四、关系的闭包运算,闭包的定义:给定集合X,R是X中的二元关系。如果有另一个关系 满足,(1) 是自反的(对称的、可传递的); (2) (3)对于任何自反的(对称的、可传递的)关系
5、 ,如果 ,则,则称关系 为R的自反的(对称的,可传递的)闭包。 并用r(R)表示的R自反闭包,用s(R)表示R的对称闭包,用t(R)表示R的可传递闭包。,16/45,16/45,四、关系的闭包运算,定理:给定集合X,R是X中的关系。于是可有 (a) 当且仅当 ,R才是自反的。 (b) 当且仅当 ,R才是对称的。 (c) 当且仅当 ,R才是传递的。,证明:仅给出(a)的证明过程 由闭包的定义可知 ,又由于R是包含了R的自反关系,根据自反闭包的定义有 。因此有 。 反之,如果 ,则由自反闭包定义可知R是自反的。,17/45,17/45,四、关系的闭包运算,定理:设R为A上的关系, 则有 (1)
6、r(R)=RR0 (2) s(R)=RR1 (3) t(R)=RR2R3 说明:对有穷集A(|A|=n)上的关系, (3)中的并最多不超过Rn,证 只证(1)和(3). (1) 由IA=R0RR0 知 RR0是自反的, 且满足RRR0 设R 是A上包含R的自反关系, 则有RR 和IA R . 从而有 RR0R. RR0满足闭包定义, 所以r(R)=RR0.,18/45,18/45,四、关系的闭包运算,(3) 先证 RR2 t(R)成立. 用归纳法证明对任意正整数n 有Rn t(R). n=1时有R1=R t(R). 假设Rnt(R)成立, 那么对任意的 Rn+1=RnR t ( RnR) t
7、(t(R)t(R) t(R) 这就证明了Rn+1t(R). 由归纳法命题得证.,再证 t(R) RR2成立, 为此只须证明RR2传递. 任取, 则 RR2RR2 t (Rt)s(Rs) t s (RtRs ) t s (Rt+s ) RR2 从而证明了RR2是传递的.,19/45,19/45,四、关系的闭包运算,在整数集合中,小于关系“”的自反闭包是“”;恒等关系IX的自反闭包是IX。不等关系“”的自反闭包是全域关系;空关系的自反闭包是恒等关系。,在整数集合中,小于关系“”的对称闭包是不等关系“”;小于或等于关系“”的对称闭包是全域关系;恒等关系IX的对称闭包是IX;不等关系“”的对称闭包是不
8、等关系“”。,20/45,20/45,四、关系的闭包运算,解:,21/45,21/45,四、关系的闭包运算,定理:设X是集合,R是X中的二元关系,于是有 (1)如果R是自反的,那么s(R),t(R)也是自反的; (2)如果R是对称的,那么r(R),t(R)也是对称的; (3)如果R是可传递的,那么r(R)也是可传递的。,22/45,四、关系的闭包运算,23/45,四、关系的闭包运算,证明(3):,24/45,24/45,四、关系的闭包运算,定理:设X是集合,R是集合中的二元关系,于是有,证明:,25/45,25/45,四、关系的闭包运算,证明(b):因为 , ,而对于所有的 有 ,以及 。根据这些关系式,可有,于是,26/45,26/45,四、关系的闭包运算,证明(c):如果 ,则 ,,根据对称闭包的定义,有 。首先构成上式两侧的可传递闭包,再依次构成两侧的对称闭包,可以求得 以及 。而ts(R)是对称的,所以 ,从而有 。,27/45,27/45,四、关系的闭包运算,注意: (1)通常用R+表示R的可传递闭包t(R),并读作“R加”。 (2)通常用R*表示R的自反可传递闭包tr(R),并读作“R星”。,作业,88页2,5(1,3,5,6,7) 89页9,11,12,13(2,3) 90页18,21,22(1,3,5,7,9,11) 91页25,26,27,