东南大学离散数学课件.ppt

第七章: 二元关系,第一节：有序对与笛卡儿积 第二节：二元关系 第三节：关系的运算 第四节：关系的性质 第五节：关系的闭包 第六节：等价关系与划分 第七节：偏序关系,第七章: 二元关系,第一节：有序对与笛卡儿积 第二节：二元关系 第三节：关系的运算 第四节：关系的性质 第五节：关系的闭包 第六节：等价关系与划分 第七节：偏序关系,7.3 关系的运算,二元关系的定义域和值域 定义域： 值域： 例 X=1,2,3,4,5,6,Y=a,b,c,d,e,f R=, domR=1,2,3,4 ranR=a,b,c,d,7.3 关系的运算,二元关系的逆 例： R=， R-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,7.3 关系的运算,关系的右复合 例 A=1,2,3,4,5,B=3,4,5,C=1,2,3 R=|x+y=6 =, S=y-z=2 =, RS=,7.3 关系的运算,例 R=, S=, RS=, SR=, RR=, SS= 注意：RSSR。,7.3 关系的运算,定理：设F是任意的关系，则 (F-1)-1=F domF-1 =ranF, ranF-1 =domF 定理：设F，G，H是任意的关系 (FG)H = F(GH) (FG)-1 =G-1F-1,7.3 关系的运算,例 R=, S=, R-1=, S-1=, S-1R-1=, , S-1R-1=(RS)-1,7.3 关系的运算,定理: 设R为A上关系，则 RIAIARR 定理: R(ST)=RSRT R(ST)RSRT (ST)X=SXTX (ST)XSXTX,7.3 关系的运算,证明 R(ST)=RSRT R(ST) y(RST) y(R(ST) y(RS) (RT) y(RS) y(RT) RS RT RSRT,7.3 关系的运算,R的n次幂 记为Rn R0 =A Rn+1=RnR 定理: 设R是集合A上的关系，m,nN Rm· Rn=Rm+n (Rm)n=Rmn,7.3 关系的运算,例R=, R0= , R1=R R2=, R3=R2·R =, R4=R3·R1 =, R5=R4·R1 =,7.3 关系的运算,从关系图来看关系的n次幂 R： 1 2 3 4 5 R2就是所有在R中通过二条弧连接的点则在R2这两点间直接有条弧。 1 2 3 4 5 R3,R4,7.3 关系的运算,定理：R是A上的二元关系，若存在自然数i和j，且ij，使Ri=Rj 对所有的k0，则Ri+k=Rj+k 对所有的k,m0 ，则有Ri+md+k=Ri+k 设S=R0,R1,R2,Rj-1，则R的每一次幂是S的元素，即对nN, RnS,第七章: 二元关系,第一节：有序对与笛卡儿积 第二节：二元关系 第三节：关系的运算 第四节：关系的性质 第五节：关系的闭包 第六节：等价关系与划分 第七节：偏序关系,7.4 关系的性质,自反性 aA，有R，则R为A上的自反关系 反自反性 aA，有 R，R为A上的反自反关系 例 A=a,b,c R1=, R2=, R3=,7.4 关系的性质,例：R是I+上的整除关系，则R具有自反性。 证明：xI+，x能整除x， R，R具有自反性。 例：R是I上的同余关系，则R具有自反性， 证明：xI，(x-x)/k=0I, x与x同余RR具有自反性 其它，关系，均是自反关系。,7.4 关系的性质,例：N上的互质关系是反自反关系。 证明：xN，x与x是不互质的， R，R具有反自反关系。 实数上的,关系,均是反自反关系。,7.4 关系的性质,关系矩阵的特点 自反关系的关系矩阵的对角元素均为1， 反自反关系的关系矩阵的对角元素均为0。 关系图的特点? 定理：R是A上的关系，则： R是自反关系的充要条件是IAR R是反自反关系的充要条件是RIA=。,7.4 关系的性质,对称性 a,bA,如果R,则必有R,R为A上的对称关系。 例 R1, R1是对称的 R2, R2是对称的 R3, R3不是对称的,7.4 关系的性质,例：R是N上的互质关系,R具有对称性。 关系矩阵特点 对称关系的关系矩阵是对称矩阵 关系图特点？ 定理： R在A上对称当且仅当R=R-1,7.4 关系的性质,反对称性 a,bR,如果R且R,则必有ab, R是A上的反对称关系 a,bA,如ab,R,则必有R。 例: Aa,b,c R, S, T, R,S是反对称的,T不是反对称的,7.4 关系的性质,例: 实数集合上关系是反对称关系 x,y实数集,如xy,且xy,则yx不成立 例,关系,均是反对称关系。 反对称关系矩阵和关系图特点？ 定理： R在A上反对称当且仅当RR-1 IA,7.4 关系的性质,传递性 a,b,cA,如果R,R, 必有R, 称R为A上的传递关系 例 R1, 是传递关系 R2, 是传递关系 R3, 不是传递关系,7.4 关系的性质,例:整除关系DI是I上的传递关系。 x,y,zI,如DI,DI,即x能整除y,且y能整除z,则必有x能整除z, DI 例:P(A)上的包含关系具有传递性。 若uv,vw,则必有uw 例:实数集上的关系具有传递性。 若xy,yz必有xz,7.4 关系的性质,传递关系关系图特点 如果结点a能通过有向弧组成的有向路径通向结点x,则a必须有有向弧直接指向x,否则R就不是传递的 例R=, 定理：R在A上传递当且仅当R·R R,7.4 关系的性质,自 反： 反自反： 对 称： 反对称： 传 递：,7.4 关系的性质,例 X=1,2,3 R1=,R2=, 反对称,反自反 反对称 可传递,7.4 关系的性质,R3=, R4= Ex 自反，对称，可传递的,自反，对称，反对称，可传递的,7.4 关系的性质,X=1,2,3, R5= 反自反的，对称的，反对称的，可传递的 若X= ，X上的空关系 自反的，反自反的，对称的，反对称的，可传递的,第七章: 二元关系,第一节：有序对与笛卡儿积 第二节：二元关系 第三节：关系的运算 第四节：关系的性质 第五节：关系的闭包 第六节：等价关系与划分 第七节：偏序关系,7.5 关系的闭包,定义 R是非空集合A上的关系，若A上另外有一个关系R满足如下三条， R是自反的（对称的，传递的） RR A上任何一个满足以上两条的关系R”，均有RR”，称关系R为R的自反（对称,传递）闭包,记作r(R),（s(R),t(R)）,7.5 关系的闭包,解释 R是在R的基础上添加有序对 添加元素的目的是使R具有自反性(对称性,传递性) 添加后使之具有自反性(对称性,传递性)的所有关系中R是最小的一个,7.5 关系的闭包,例A=a,b,c R=, 自反闭包r(R) , 对称闭包s(R) , 传递闭包t(R) ,7.5 关系的闭包,例R=,，求R的传递闭包,7.5 关系的闭包,定理 R是非空集合A上的关系,则r(R)=RA 证明: RRA RA是自反的. 设R”满足RR”,R”是自反的,RA 则R或A 如R,由RR”知R” 如A,由R”的自反性知R”。 均有R” RAR”,7.5 关系的闭包,定理: 设R是非空集A的关系,则s(R)=RR-1 证明: RRR-1满足定义第2条 RR-1 RR-1 R-1R RR-1 RR-1是对称的,7.5 关系的闭包,如RR”,且R”是对称的 RR-1 R或R-1 如R,由RR”,则R” 如R-1,则R,则R” 因R”对称 R”,RR-1R” 满足定义第3条,7.5 关系的闭包,例:设A=1,2,3,A上的关系R如图,求r(R),s(R) 解:R=, r(R)= RA =, s(R)= RR-1 =,7.5 关系的闭包,定理: 设R是非空集合A上的关系, 则t(R)= Ri=RR2 推论: 设A是非空有限集，|A|=n，R是集合A上的二元关系， 则t(R）= Ri=RR2Rn,7.5 关系的闭包,例 A=a,b,c,d R=, S=,求t(R),t(S) 解:R2=,R3= t(R)=R, S2=,S3=,S4= t(S)=S,7.5 关系的闭包,定理：设X是一集合，R是X上的二元关系，则有： R是自反的当且仅当r(R)R； 若R是对称的当且仅当s(R)R； 若R是可传递的当且仅当t(R)R。,7.5 关系的闭包,定理：设X是集合，R1和R2是X上的二元关系， R1R2，则有： r(R1)r(R2) s(R1)s(R2) t(R1)t(R2),7.5 关系的闭包,定理：设X是一集合，R是X上的二元关系，则有： 若R是自反的，则s(R),t(R)也自反 若R是对称的，则r(R),t(R)也对称 若R是可传递的，则r(R)也可传递,7.5 关系的闭包,若R是传递的，s(R)不一定是传递的。 反例:R=,，R是传递的 s(R)=,，s(R)不是传递的,7.5 关系的闭包,常用下列符号表示一些闭包： “R加”： 传递闭包， “R星”： 自反传递闭包，,