离散数学：r03关系c

1、1n关系的概念及运算关系的概念及运算n关系的性质关系的性质n关系的闭包运算关系的闭包运算n等价关系等价关系n序关系序关系 关系关系2 3.3 关系的闭包运算关系的闭包运算n设设R是是A上的二元关系，如果有另一个关系上的二元关系，如果有另一个关系R满足：满足：R 是是自反自反的的(对称的，可传递的对称的，可传递的)；R R ；对于任何对于任何自反自反的的(对称的，可传递的对称的，可传递的)关系关系R ，如果有如果有R R ，就有就有R R ，则称关系则称关系 R 为为R的的自反自反(对称，传递对称，传递)闭包闭包（reflexive closure, symmetric closure, tra

2、nsitive closure）。记为：）。记为：r(R), (s(R), t(R)。3关系的闭包运算关系的闭包运算定理定理1：设：设R是是A上的二元关系，如果上的二元关系，如果R是自反的，当且仅当是自反的，当且仅当r(R)=R；R是对称的，当且仅当是对称的，当且仅当s(R)=R；R是传递的，当且仅当是传递的，当且仅当t(R)=R；例例. 设设A=a,b，分别求以下，分别求以下A上的二元关系的自反、对称和上的二元关系的自反、对称和 传递闭包。传递闭包。 (1) R=, ； (2) S=AA ； (3) T= 。解：解：(1) r(R) = s(R) = t(R) = R ; (2) r(S)

3、= s(S) = t(S) = S ; (3) r(T) =, , s(T) = t(T) = T4关系的闭包运算关系的闭包运算定理定理2：n设设R是是A上的二元关系，则上的二元关系，则r(R)=RIA。证明：证明： 令令R =RIA ， (i) 对任意的对任意的xA，因为有因为有IA ，故故R ，所所以以R 在在A上是自反的。上是自反的。(ii) 又又R RIA ，即即R R 。(iii) 若有自反关系若有自反关系R 且且R R ，显然有显然有IA R ，于是于是 RIA R ，即即 R R 。 所以所以r(R)=RIA 。5关系的闭包运算关系的闭包运算n设设R是是A上的二元关系，则上的二元

4、关系，则s(R)=RR-1。证明：令证明：令R =RR-1， (i) 设设R ,则则R或或R-1 即即R-1或或R，故故RR-1 =R ， 所以所以R 是对称的。是对称的。 (ii) 因为因为R RR-1，即即R R 。(iii) 设设R 是对称的，且是对称的，且R R ,对任意的对任意的R ，则则 R或或R-1。当当R时，有时，有R ； 当当R-1时，有时，有R，则则R ， 又因为又因为R 对称，所以对称，所以R ，因此，因此，R R 。所以所以s(R)=RR-1。6关系的闭包运算关系的闭包运算231( )iit RRRRR 设设R是是A上的二元关系，则上的二元关系，则111( ),( )i

5、iststs tiiiiRRix yRy zRs tx yRy xRx zRRRRx zRRii RRR 证证明明：令令。任任取取那那么么必必存存在在正正整整数数，使使得得，则则有有所所以以即即是是传传递递的的。12111211121(),k,.,.,.,.,kkkkkiiiARRRRRx yRRRR RRAxxxx xRxxRxyRRRx xRxxRxyR 任任取取 上上的的传传递递关关系系且且现现证证明明。任任取取则则存存在在某某正正整整数数 使使得得而而由由复复合合运运算算的的定定义义可可知知： 中中存存在在元元素素使使得得。因因为为，所所以以有有，。又又因因1,( )iiRx yRRR

6、t RR 为为是是传传递递的的，所所以以，从从而而。综综上上所所述述有有。关系的闭包运算关系的闭包运算8关系的闭包运算关系的闭包运算传递闭包传递闭包对称闭包对称闭包自反闭包自反闭包UUI上的不等于关系上的不等于关系 UUU全域关系全域关系UUI上的小于等于关系上的小于等于关系 I上的小于关系上的小于关系例：设例：设A=a,b,c，RA2，且给定，且给定R=,， 求求r(R)，s(R)，t(R)。解：解：r(R)=, s(R)=, t(R)=, 9用关系图求用关系图求R的闭包：的闭包：设设G是集合是集合A上的二元关系上的二元关系R的有向图，则的有向图，则 r(R): G中每一结点加自回路；中每一

7、结点加自回路； s(R): 添加对称弧；添加对称弧； t(R): 若有从若有从a到到b的非零长度的路径，则添加从的非零长度的路径，则添加从a到到b的弧。的弧。关系的闭包运算关系的闭包运算关系的闭包运算关系的闭包运算 定理定理3：设：设R是有限集合是有限集合A上的二元关系且上的二元关系且|A|=n，那么有，那么有102( )nt RRRR 22122222( ),( )( ),inninnnnnkkt RRRRRRRRiRRRRRRiiRRRRRRx yAx yRRRknx yRkx yRknAxa 证证明明：已已知知现现证证明明显显然然有有。证证明明，为为此此，需需要要证证明明对对于于任任何何

8、，如如有有必必存存在在正正整整数数，使使得得。采采用用反反证证法法：假假设设 是是满满足足的的最最小小正正整整数数，且且，则则 中中存存在在元元素素序序列列0111121,kkkaaayx aa aayR ，使使得得关系的闭包运算关系的闭包运算11011112111()2|,(0),()()kkijiijjikjkijikjtAna aaaaaijkx aa aaaa aayRx aRayRx yRx yRtikjkjikkknRR 由由于于，则则中中必必有有相相同同者者，不不妨妨设设，于于是是，得得到到那那么么，即即，其其中中。这这与与 的的最最小小性性相相矛矛盾盾，于于是是。故故有有22(

9、 )nnnRRRRt RRRR 成成立立。综综上上所所述述，。12关系的闭包运算关系的闭包运算定理定理4：设：设R是是A上的二元关系，则有上的二元关系，则有 (a)如果如果R是自反的，那么是自反的，那么s(R)和和t(R)都是自反的；都是自反的； (b)如果如果R是对称的，那么是对称的，那么r(R)和和t(R)都是对称的；都是对称的； (c)如果如果R是传递的，那么是传递的，那么r(R)是传递的；是传递的；注意注意: : (c) 中中s(R)不一定传递，不一定传递， 如如 R=, s(R)=,13关系的闭包运算关系的闭包运算关系关系R的自反，对称，传递闭包可以进一步复合，有如下定理：的自反，对

10、称，传递闭包可以进一步复合，有如下定理：定理定理5：设：设A是集合，是集合，R是是A上的二元关系，则上的二元关系，则 (a) rs(R) = sr(R)， (b) rt(R) = tr(R)， (c) st(R) ts(R)。证明：证明：()As RI( )( )asr R1()()AARIRI11()()AARIRI1ARRI( )As RI( )rs R14(b) rt(R) = tr(R)因为因为IAR=RIA=R，对一切对一切nN，(IA)n=IA，可得可得11( )()ijAijtr RRI i()() ()()iAAAARIRIRIRI 1( )()()iAAitr Rt RIRI

11、1()iijAAjRIRI111( )( )ijiAAAijiRIRIt RIrt R15(c) st(R) ts(R) 如果如果R1 R2，则则s(R1) s(R2)，t(R1) t(R2)(作业作业)， 又又R s(R)，则则t(R) ts(R)，st(R) sts(R)， 而而s(R)是对称的，则是对称的，则ts(R)是对称的，则是对称的，则sts(R)=ts(R)， 所以所以st(R) ts(R)。 st(R) ts(R) 例如，整数集合例如，整数集合I上的小于关系上的小于关系“”，st()=s()=ts()=t()=II=U(全域关系全域关系)16n关系的概念及运算关系的概念及运算n

12、关系的性质关系的性质n关系的闭包运算关系的闭包运算n等价关系等价关系n序关系序关系 关系关系17集合的覆盖和划分集合的覆盖和划分n若把一个集合若把一个集合A分成若干个叫做分块的非空子集，使得分成若干个叫做分块的非空子集，使得A中中每个元素至少属于一个分块，那么这些分块的全体构成的集每个元素至少属于一个分块，那么这些分块的全体构成的集合叫做合叫做A的一个的一个覆盖覆盖(cover)。如果。如果A中每个元素属于且仅属中每个元素属于且仅属于一个分块，那么这些分块的全体构成的集合叫做于一个分块，那么这些分块的全体构成的集合叫做A的一个的一个划分划分(partition)。n等价定义为：令等价定义为：令

13、A为给定非空集合，为给定非空集合，S=S1,S2,.,Sn，其中其中Si A，Si不为空集不为空集(i=1,2,.n)且且S1S2.Sn=A，集合集合S则称为集合则称为集合A的的覆盖覆盖。此外，如果。此外，如果Si和和Sj交为空集，这里交为空集，这里i不不等于等于j，则称则称S为为A的的划分划分。18集合的覆盖和划分集合的覆盖和划分n划分的元素划分的元素Si称为划分称为划分的的块块(block)，如果划分是有限集合，如果划分是有限集合，则不同块的个数称为划分的则不同块的个数称为划分的秩秩；若划分是无限集合，则它的；若划分是无限集合，则它的秩是无限的。划分的秩就是划分的大小。秩是无限的。划分的秩

14、就是划分的大小。n对于有限集合对于有限集合A，秩为，秩为1的划分称为的划分称为A的最小划分，秩为的最小划分，秩为|A|的的划分称为划分称为A的最大划分。的最大划分。19集合的覆盖和划分集合的覆盖和划分例如，例如，A=a,b,c，则则S=a,b,b,c,Q=a,a,b,a,c,D=a,b,c,G=a,b,c,E=a,b,c,F=a,a,c,覆盖覆盖划分最小划分最大划分既不是覆盖，也不是划分若是划分，则必是覆盖；若是覆盖，则不一定是划分。20等价关系等价关系n设设R为定义在集合为定义在集合A上的一个关系，若上的一个关系，若R是是自反的自反的、对称的对称的和和传递的传递的，则，则R称为称为等价关系等

15、价关系(equivalence relation)。 如三角形集合上三角形的相似关系，某一班级中的同学关系。如三角形集合上三角形的相似关系，某一班级中的同学关系。例：设集合例：设集合A=1,2,3,4，A上关系上关系R=,。验证验证R是是A上等价关系。上等价关系。21等价关系等价关系例：设例：设I为整数集合，为整数集合，R=|xy(mod k)(模模k同余关系同余关系)，证明证明R是等价关系。是等价关系。证明：设任意证明：设任意a,b,cI(i)：因为因为a-a=k*0，所以所以R，即，即R是自反的；是自反的；(ii)：若若ab(mod k)，a-b=kt(tI)，则则b-a=-kt，所以所以

16、ba(mod k)，即，即R是对称的；是对称的； (iii)：若若ab(mod k)，bc(mod k)，则则a-b=kt， b-c=ks(tI，sI)， a-c=a-b+b-c=k(t+s)，所以所以ac(mod k)，即即R是传递的。是传递的。 因此因此R是是A上的等价关系。上的等价关系。22等价关系等价关系定理定理1：设：设R是是A上的二元关系，设上的二元关系，设R=tsr(R)是是R的自反对称传的自反对称传递闭包，那么递闭包，那么R是是A上的等价关系，称为上的等价关系，称为R诱导的等价关系诱导的等价关系；如果如果R”是任意等价关系，且是任意等价关系，且R R”，那么那么R R”。即即R是是包含包含R的最小等价关系。的最小等价关系。证明：证明：r(R)是自反的，所以是自反的，所以sr(R)是自