《东南大学离散数学课件》由会员分享，可在线阅读，更多相关《东南大学离散数学课件（46页珍藏版）》请在金锄头文库上搜索。
1、1第七章: 二元关系q 第一节：有序对与笛卡儿积第二节：二元关系 第三节：关系的运算第四节：关系的性质第五节：关系的闭包第六节：等价关系与划分第七节：偏序关系2第七章: 二元关系q 第一节：有序对与笛卡儿积第二节：二元关系 第三节：关系的运算第四节：关系的性质第五节：关系的闭包第六节：等价关系与划分第七节：偏序关系37.3 关系的运算q二元关系的定义域和值域 v定义域： v值域： q例 vX=1,2,3,4,5,6,Y=a,b,c,d,e,f vR=, vdomR=1,2,3,4 vranR=a,b,c,d47.3 关系的运算q二元关系的逆 v q例： vR=， ， vR-1=， ， 1 0
2、0 1 1 0 1 00 0 0 1 0 0 1 0 MR= 1 1 0 0 MR-1=MRT= 0 0 0 1 0 0 1 0 1 1 0 0 57.3 关系的运算q 关系的右复合q 例 vA=1,2,3,4,5,B=3,4,5,C=1,2,3 vR=|x+y=6=, vS=y-z=2 =, vRS=,67.3 关系的运算q 例 vR=, vS=, vRS=, vSR=, vRR=, vSS= q 注意：RSSR。 77.3 关系的运算q 定理：设F是任意的关系，则 v (F-1)-1=F vdomF-1 =ranF, ranF-1 =domFq 定理：设F，G，H是任意的关系 v (FG)
3、H = F(GH) v (FG)-1 =G-1F-187.3 关系的运算q 例 vR=, vS=, vR-1=, vS-1=, vS-1R-1=, , qS-1R-1=(RS)-197.3 关系的运算q 定理: 设R为A上关系，则RIAIARRq 定理: vR(ST)=RSRT vR(ST)RSRT v (ST)X=SXTX v (ST)XSXTX107.3 关系的运算q 证明 R(ST)=RSRT R(ST) y(RST) y(R(ST) y(RS) (RT) y(RS) y(RT) RS RT RSRT117.3 关系的运算qR的n次幂 v 记为Rn vR0 =A vRn+1=RnR q
4、定理: 设R是集合A上的关系，m,nN vRm Rn=Rm+n v (Rm)n=Rmn127.3 关系的运算q 例R=, vR0= , vR1=R vR2=, vR3=R2R=, vR4=R3R1=, vR5=R4R1=,137.3 关系的运算从关系图来看关系的n次幂 R： 1 2 3 4 5 R2就是所有在R中通过二条弧连接的点则在R2这 两点间直接有条弧。1 2 3 4 5 R3,R4147.3 关系的运算q 定理：R是A上的二元关系，若存在自然数i 和j，且iR，则R为A上的自反关系 q反自反性 vaA，有 R，R为A上的反自反关系 q例 A=a,b,c vR1=, vR2=, vR3=
5、,177.4 关系的性质q例：R是I+上的整除关系，则R具有自反性。 v证明：xI+，x能整除x， vR，R具有自反性。 q例：R是I上的同余关系，则R具有自反性， v证明：xI，(x-x)/k=0I, vx与x同余RR具有自反性 q其它，关系，均是自反关系。187.4 关系的性质q例：N上的互质关系是反自反关系。 v证明：xN，x与x是不互质的， v R，R具有反自反关系。q实数上的,关系,均是反自反关系。197.4 关系的性质q关系矩阵的特点 v自反关系的关系矩阵的对角元素均为1， v反自反关系的关系矩阵的对角元素均为0。 q关系图的特点?q定理：R是A上的关系，则： vR是自反关系的充要
6、条件是IAR vR是反自反关系的充要条件是RIA=。207.4 关系的性质q对称性 va,bA,如果R,则必有R,R 为A上的对称关系。 q例 vR1, vR1是对称的 vR2, vR2是对称的 vR3, vR3不是对称的 217.4 关系的性质q例：R是N上的互质关系,R具有对称性。q关系矩阵特点 v对称关系的关系矩阵是对称矩阵 q关系图特点？q定理： R在A上对称当且仅当R=R-1227.4 关系的性质q反对称性 va,bR,如果R且R,则必有 ab, R是A上的反对称关系 va,bA,如ab,R,则必有 R。 q例: Aa,b,c vR, vS, vT, vR,S是反对称的,T不是反对称
7、的237.4 关系的性质q例: 实数集合上关系是反对称关系 vx,y实数集,如xy,且xy,则yx不成立 q例,关系,均是反对称关系。q反对称关系矩阵和关系图特点？q定理： R在A上反对称当且仅当RR-1 IA247.4 关系的性质q传递性 va,b,cA,如果R,R, 必有 R, 称R为A上的传递关系 q例 vR1, v是传递关系 vR2, v是传递关系 vR3, v不是传递关系257.4 关系的性质q例:整除关系DI是I上的传递关系。 vx,y,zI,如DI,DI,即 x能整除y,且y能整除z,则必有x能整除z, DI q例:P(A)上的包含关系具有传递性。 v若uv,vw,则必有uw q
8、例:实数集上的关系具有传递性。 v若xy,yz必有xz267.4 关系的性质q传递关系关系图特点 v如果结点a能通过有向弧组成的有向路径通向结 点x,则a必须有有向弧直接指向x,否则R就不是传 递的 q例R=,q定理：R在A上传递当且仅当RR Rdcba277.4 关系的性质自 反： 反自反： 对 称： 反对称： 传 递： 287.4 关系的性质q例 X=1,2,3 vR1=,n R2=, n反对称n反自 反n反对 称n可传 递297.4 关系的性质qR3=,qR4= Ex 自反，对称，可传递的 n自反，对称，反对称，可传递的307.4 关系的性质qX=1,2,3, R5= v反自反的，对称的
9、，反对称的，可传递的q若X= ，X上的空关系v自反的，反自反的，对称的，反对称的，可传递 的31第七章: 二元关系q 第一节：有序对与笛卡儿积第二节：二元关系 第三节：关系的运算第四节：关系的性质第五节：关系的闭包第六节：等价关系与划分第七节：偏序关系327.5 关系的闭包q定义 R是非空集合A上的关系，若A上另外有 一个关系R满足如下三条， vR是自反的（对称的，传递的） vRR vA上任何一个满足以上两条的关系R”，均有 RR”，称关系R为R的自反（对称,传递）闭包, 记作r(R),（s(R),t(R)）337.5 关系的闭包q解释 vR是在R的基础上添加有序对 v添加元素的目的是使R具有
10、自反性(对称性,传递 性) v添加后使之具有自反性(对称性,传递性)的所有关 系中R是最小的一个347.5 关系的闭包q例A=a,b,cR=,v自反闭包r(R) v,v对称闭包s(R) v,v传递闭包t(R) v,r(R)a b ccbaacbcbabac357.5 关系的闭包q例R=,，求R的 传递闭包a b c d e367.5 关系的闭包q定理 R是非空集合A上的关系,则r(R)=RA 证明: vRRA vRA是自反的. v设R”满足RR”,R”是自反的,RA则R或A 如R,由RR”知R”如A,由R”的自反性知R”。均有R”RAR” 377.5 关系的闭包q定理: 设R是非空集A的关系,
11、则s(R)=RR-1 q证明: vRRR-1满足定义第2条 vRR-1 RR-1 R-1R RR-1 RR-1是对称的387.5 关系的闭包v如RR”,且R”是对称的 RR-1 R或R-1 如R,由RR”,则R” 如R-1,则R,则R” 因R”对称 R”,RR-1R” 满足定义第3条397.5 关系的闭包q例:设A=1,2,3,A上的关系R如图,求 r(R),s(R)解:R=, r(R)= RA =, s(R)= RR-1 =,1 2 3407.5 关系的闭包定理: 设R是非空集合A上的关系,则t(R)= Ri=RR2 推论: 设A是非空有限集，|A|=n，R是集合A上的二 元关系，则t(R）
12、= Ri=RR2Rn417.5 关系的闭包q例 A=a,b,c,d vR=, vS=,求t(R),t(S)q解:R2=,R3= t(R)=R, S2=,S3=,S4= t(S)=S,a b c dRa b c d S427.5 关系的闭包q定理：设X是一集合，R是X上的二元关系，则 有： vR是自反的当且仅当r(R)R； v若R是对称的当且仅当s(R)R； v若R是可传递的当且仅当t(R)R。437.5 关系的闭包q定理：设X是集合，R1和R2是X上的二元关系 ， R1R2，则有： vr(R1)r(R2) vs(R1)s(R2) vt(R1)t(R2)447.5 关系的闭包q定理：设X是一集合，R是X上的二元关系，则 有： v若R是自反的，则s(R),t(R)也自反 v若R是对称的，则r(R),t(R)也对称 v若R是可传递的，则r(R)也可传递457.5 关系的闭包q若R是传递的，s(R)不一定是传递的。 反例:R=,，R是传递的 s(R)=,， s(R)不是传递的467.5 关系的闭包常用下列符号表示一些闭包： “R加”： 传递闭包，“R星”： 自反传递闭包，
