《第四章 二元关系-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,
