东南大学离散数学.ppt

1 第七章: 二元关系 q 第一节：有序对与笛卡儿积 第二节：二元关系 第三节：关系的运算 第四节：关系的性质 第五节：关系的闭包 第六节：等价关系与划分 第七节：偏序关系 2 第七章: 二元关系 q 第一节：有序对与笛卡儿积 第二节：二元关系 第三节：关系的运算 第四节：关系的性质 第五节：关系的闭包 第六节：等价关系与划分 第七节：偏序关系 3 7.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,d 4 7.3 关系的运算 q二元关系的逆 v q例： vR=， ， vR-1=， ， 1 0 0 1 1 0 1 0 0 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 5 7.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=, 6 7.3 关系的运算 q 例 vR=, vS=, vRS=, vSR=, vRR=, vSS= q 注意：RSSR。 7 7.3 关系的运算 q 定理：设F是任意的关系，则 v (F-1)-1=F vdomF-1 =ranF, ranF-1 =domF q 定理：设F，G，H是任意的关系 v (FG)H = F(GH) v (FG)-1 =G-1F-1 8 7.3 关系的运算 q 例 vR=, vS=, vR-1=, vS-1=, vS-1R-1=, , qS-1R-1=(RS)-1 9 7.3 关系的运算 q 定理: 设R为A上关系，则 RIAIARR q 定理: vR(ST)=RSRT vR(ST)RSRT v (ST)X=SXTX v (ST)XSXTX 10 7.3 关系的运算 q 证明 R(ST)=RSRT R(ST) y(RST) y(R(ST) y(RS) (RT) y(RS) y(RT) RS RT RSRT 11 7.3 关系的运算 qR的n次幂 v 记为Rn vR0 =A vRn+1=RnR q 定理: 设R是集合A上的关系，m,nN vRm Rn=Rm+n v (Rm)n=Rmn 12 7.3 关系的运算 q 例R=, vR0= , vR1=R vR2=, vR3=R2R =, vR4=R3R1 =, vR5=R4R1 =, 13 7.3 关系的运算 从关系图来看关系的n次幂 R： 1 2 3 4 5 R2就是所有在R中通过二条弧连接的点则在R2这 两点间直接有条弧。 1 2 3 4 5 R3,R4 14 7.3 关系的运算 q 定理：R是A上的二元关系，若存在自然数i 和j，且iR，则R为A上的自反关系 q反自反性 vaA，有 R，R为A上的反自反关系 q例 A=a,b,c vR1=, vR2=, vR3=, 17 7.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其它，关系，均是自反关系。 18 7.4 关系的性质 q例：N上的互质关系是反自反关系。 v证明：xN，x与x是不互质的， v R，R具有反自反关系。 q实数上的,关系,均是反自反关系。 19 7.4 关系的性质 q关系矩阵的特点 v自反关系的关系矩阵的对角元素均为1， v反自反关系的关系矩阵的对角元素均为0。 q关系图的特点? q定理：R是A上的关系，则： vR是自反关系的充要条件是IAR vR是反自反关系的充要条件是RIA=。 20 7.4 关系的性质 q对称性 va,bA,如果R,则必有R,R 为A上的对称关系。 q例 vR1, vR1是对称的 vR2, vR2是对称的 vR3, vR3不是对称的 21 7.4 关系的性质 q例：R是N上的互质关系,R具有对称性。 q关系矩阵特点 v对称关系的关系矩阵是对称矩阵 q关系图特点？ q定理： R在A上对称当且仅当R=R-1 22 7.4 关系的性质 q反对称性 va,bR,如果R且R,则必有 ab, R是A上的反对称关系 va,bA,如ab,R,则必有 R。 q例: Aa,b,c vR, vS, vT, vR,S是反对称的,T不是反对称的 23 7.4 关系的性质 q例: 实数集合上关系是反对称关系 vx,y实数集,如xy,且xy,则yx不成立 q例,关系,均是反对称关系。 q反对称关系矩阵和关系图特点？ q定理： R在A上反对称当且仅当RR-1 IA 24 7.4 关系的性质 q传递性 va,b,cA,如果R,R, 必有 R, 称R为A上的传递关系 q例 vR1, v是传递关系 vR2, v是传递关系 vR3, v不是传递关系 25 7.4 关系的性质 q例:整除关系DI是I上的传递关系。 vx,y,zI,如DI,DI,即 x能整除y,且y能整除z,则必有x能整除z, DI q例:P(A)上的包含关系具有传递性。 v若uv,vw,则必有uw q例:实数集上的关系具有传递性。 v若xy,yz必有xz 26 7.4 关系的性质 q传递关系关系图特点 v如果结点a能通过有向弧组成的有向路径通向结 点x,则a必须有有向弧直接指向x,否则R就不是传 递的 q例R=, q定理：R在A上传递当且仅当RR R dcba 27 7.4 关系的性质 自 反： 反自反： 对 称： 反对称： 传 递： 28 7.4 关系的性质 q例 X=1,2,3 vR1=, n R2=, n反对称 n反自 反 n反对 称 n可传 递 29 7.4 关系的性质 qR3=, qR4= Ex 自反，对称，可传递的 n自反，对称，反对称，可传递的 30 7.4 关系的性质 qX=1,2,3, R5= v反自反的，对称的，反对称的，可传递的 q若X= ，X上的空关系 v自反的，反自反的，对称的，反对称的，可传递 的 31 第七章: 二元关系 q 第一节：有序对与笛卡儿积 第二节：二元关系 第三节：关系的运算 第四节：关系的性质 第五节：关系的闭包 第六节：等价关系与划分 第七节：偏序关系 32 7.5 关系的闭包 q定义 R是非空集合A上的关系，若A上另外有 一个关系R满足如下三条， vR是自反的（对称的，传递的） vRR vA上任何一个满足以上两条的关系R”，均有 RR”，称关系R为R的自反（对称,传递）闭包, 记作r(R),（s(R),t(R)） 33 7.5 关系的闭包 q解释 vR是在R的基础上添加有序对 v添加元素的目的是使R具有自反性(对称性,传递 性) v添加后使之具有自反性(对称性,传递性)的所有关 系中R是最小的一个 34 7.5 关系的闭包 q例A=a,b,c R=, v自反闭包r(R) v, v对称闭包s(R) v, v传递闭包t(R) v, r(R) a b c cba acb c b a b ac 35 7.5 关系的闭包 q例R=,，求R的 传递闭包 a b c d e 36 7.5 关系的闭包 q定理 R是非空集合A上的关系,则r(R)=RA 证明: vRRA vRA是自反的. v设R”满足RR”,R”是自反的,RA 则R或A 如R,由RR”知R” 如A,由R”的自反性知R”。 均有R” RAR” 37 7.5 关系的闭包 q定理: 设R是非空集A的关系,则s(R)=RR-1 q证明: vRRR-1满足定义第2条 vRR-1 RR-1 R-1R RR-1 RR-1是对称的 38 7.5 关系的闭包 v如RR”,且R”是对称的 RR-1 R或R-1 如R,由RR”,则R” 如R-1,则R,则R” 因R”对称 R”,RR-1R” 满足定义第3条 39 7.5 关系的闭包 q例:设A=1,2,3,A上的关系R如图,求 r(R),s(R) 解:R=, r(R)= RA =, s(R)= RR-1 =, 1 2 3 40 7.5 关系的闭包 定理: 设R是非空集合A上的关系, 则t(R)= Ri=RR2 推论: 设A是非空有限集，|A|=n，R是集合A上的二 元关系， 则t(R）= Ri=RR2Rn 41 7.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 d R a b c d S 42 7.5 关系的闭包 q定理：设X是一集合，R是X上的二元关系，则 有： vR是自反的当且仅当r(R)R； v若R是对称的当且仅当s(R)R； v若R是可传递的当且仅当t(R)R。 43 7.5 关系的闭包 q定理：设X是集合，R1和R2是X上的二元关系 ， R1R2，则有： vr(R1)r(R2) vs(R1)s(R2) vt(R1)t(R2) 44 7.5 关系的闭包 q定理：设X是