《东南大学离散数学.ppt》由会员分享，可在线阅读，更多相关《东南大学离散数学.ppt（46页珍藏版）》请在金锄头文库上搜索。
1、1第七章第七章: 二元关系二元关系q 第一节：有序对与笛卡儿积第一节：有序对与笛卡儿积 第二节：二元关系第二节：二元关系 第三节：关系的运算第三节：关系的运算 第四节：关系的性质第四节：关系的性质 第五节：关系的闭包第五节：关系的闭包 第六节：等价关系与划分第六节：等价关系与划分 第七节：偏序关系第七节：偏序关系2第七章第七章: 二元关系二元关系q 第一节：有序对与笛卡儿积第一节：有序对与笛卡儿积 第二节：二元关系第二节：二元关系 第三节：关系的运算第三节：关系的运算 第四节：关系的性质第四节：关系的性质 第五节：关系的闭包第五节：关系的闭包 第六节：等价关系与划分第六节：等价关系与划分 第七
2、节：偏序关系第七节：偏序关系37.3 关系的运算关系的运算q二元关系的定义域和值域二元关系的定义域和值域v定义域：定义域：v值域：值域：q例例vX=1,2,3,4,5,6,Y=a,b,c,d,e,fvR=,vdomR=1,2,3,4vranR=a,b,c,d47.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 57.3 关系的运算关系的运算q关系的右复合关系的右复合q例例vA=1,2,3,4,5,B=3
3、,4,5,C=1,2,3vR=|x+y=6 =,vS= y-z=2 =,vRS=,67.3 关系的运算关系的运算q例例vR=,vS=,vRS=,vSR=,vRR=,vSS=q注意：注意：RS SR。 77.3 关系的运算关系的运算q定理：设定理：设F是任意的关系，则是任意的关系，则v(F-1)-1=FvdomF-1 =ranF, ranF-1 =domFq定理：设定理：设F，G，H是任意的关系是任意的关系v(FG)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
4、.3 关系的运算关系的运算q定理定理: 设设R为为A上关系，则上关系，则 RIAIARRq定理定理:vR(S T)=RS RTvR(ST) RSRTv(S T)X=SX TXv(ST)X SXTX107.3 关系的运算关系的运算q证明证明 R(S T)=RS RT R(S T) y( R S T) y( R ( S T) y( R S) ( R T) y( R S) y( R T) RS RT RS RT117.3 关系的运算关系的运算qR的的n次幂次幂v记为记为RnvR0 = AvRn+1=RnRq定理定理: 设设R是集合是集合A上的关系，上的关系，m,n NvRm Rn=Rm+nv(Rm)
5、n=Rmn127.3 关系的运算关系的运算q例例R=,vR0= ,vR1=RvR2=,vR3=R2R =,vR4=R3R1 =,vR5=R4R1 =,137.3 关系的运算关系的运算从关系图来看关系的从关系图来看关系的n次幂次幂 R： 1 2 3 4 5R2就是所有在就是所有在R中通过中通过二条弧二条弧连接的点则在连接的点则在R2这这两点间直接有条弧。两点间直接有条弧。 1 2 3 4 5R3,R4147.3 关系的运算关系的运算q定定理理：R是是A上上的的二二元元关关系系，若若存存在在自自然然数数i和和j，且，且ij，使，使Ri=Rjv对所有的对所有的k0，则，则Ri+k=Rj+kv对所有的
6、对所有的k,m0 ，则有，则有Ri+md+k=Ri+kv设设S=R0,R1,R2,Rj-1，则则R的的每每一一次次幂幂是是S的元素，即对的元素，即对n N, Rn S 15第七章第七章: 二元关系二元关系q 第一节：有序对与笛卡儿积第一节：有序对与笛卡儿积 第二节：二元关系第二节：二元关系 第三节：关系的运算第三节：关系的运算 第四节：关系的性质第四节：关系的性质 第五节：关系的闭包第五节：关系的闭包 第六节：等价关系与划分第六节：等价关系与划分 第七节：偏序关系第七节：偏序关系167.4 关系的性质关系的性质q自反性自反性v a A，有，有 R，则，则R为为A上的自反关系上的自反关系q反自反
7、性反自反性v a A，有，有 R，R为为A上的反自反关系上的反自反关系q例例 A=a,b,cvR1=,vR2=,vR3=,177.4 关系的性质关系的性质q例：例：R是是I+上的整除关系，则上的整除关系，则R具有自反性。具有自反性。v证明：证明： x I+，x能整除能整除x，v R，R具有自反性。具有自反性。q例：例：R是是I上的同余关系，则上的同余关系，则R具有自反性，具有自反性，v证明：证明： x I，(x-x)/k=0 I, v x与与x同余同余 RR具有自反性具有自反性q其它其它，关系，均是自反关系。关系，均是自反关系。187.4 关系的性质关系的性质q例：例：N上的互质关系是反自反关
8、系。上的互质关系是反自反关系。v证明：证明： x N，x与与x是不互质的，是不互质的，v R，R具有反自反关系。具有反自反关系。q实数上的实数上的,关系关系,均是反自反关系。均是反自反关系。197.4 关系的性质关系的性质q关系矩阵的特点关系矩阵的特点v自反关系的关系矩阵的对角元素均为自反关系的关系矩阵的对角元素均为1，v反自反关系的关系矩阵的对角元素均为反自反关系的关系矩阵的对角元素均为0。q关系图的特点关系图的特点?q定理：定理：R是是A上的关系，则：上的关系，则：vR是自反关系的充要条件是是自反关系的充要条件是IA RvR是反自反关系的充要条件是是反自反关系的充要条件是RIA=。207.
9、4 关系的性质关系的性质q对称性对称性v a,b A,如果如果 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反对称性反对称性v a,b R,如果如果 R且且 R,则必有则必有
10、ab, R是是A上的反对称关系上的反对称关系v a,b A,如如ab, R,则必有则必有 R。q例例: Aa,b,cvR,vS,vT,vR,S是反对称的是反对称的,T不是反对称的不是反对称的237.4 关系的性质关系的性质q例例: 实数集合上实数集合上关系是反对称关系关系是反对称关系v x,y 实数集实数集,如如xy,且且xy,则则yx不成立不成立q例例,关系关系,均是反对称关系。均是反对称关系。q反对称关系矩阵和关系图特点？反对称关系矩阵和关系图特点？q定理：定理： R在在A上反对称当且仅当上反对称当且仅当RR-1 IA247.4 关系的性质关系的性质q传递性传递性v a,b,c A,如果如
11、果 R, R, 必有必有 R, 称称R为为A上的传递关系上的传递关系q例例vR1,v是传递关系是传递关系vR2,v是传递关系是传递关系vR3,v不是传递关系不是传递关系257.4 关系的性质关系的性质q例例:整除关系整除关系DI是是I上的传递关系。上的传递关系。v x,y,z I,如如 DI, DI,即即x能整除能整除y,且且y能整除能整除z,则必有则必有x能整除能整除z, DIq例例:P(A)上的包含关系上的包含关系 具有传递性。具有传递性。v若若u v,v w,则必有则必有u wq例例:实数集上的实数集上的关系具有传递性。关系具有传递性。v若若xy,yz必有必有xz267.4 关系的性质关
12、系的性质q传递关系关系图特点传递关系关系图特点v如果结点如果结点a能通过有向弧组成的有向路径通向结能通过有向弧组成的有向路径通向结点点x,则则a必须有有向弧直接指向必须有有向弧直接指向x,否则否则R就不是传就不是传递的递的q例例R=,q定理：定理：R在在A上传递当且仅当上传递当且仅当RR Rdcba277.4 关系的性质关系的性质自自 反：反：反自反：反自反： 对对 称：称：反对称：反对称：传传 递：递： 287.4 关系的性质关系的性质q例例 X=1,2,3vR1=,n R2=, n反对称反对称n反自反反自反n反对称反对称n可传递可传递297.4 关系的性质关系的性质qR3=,qR4= Ex
13、 自反，对称，可传递的自反，对称，可传递的 n自反，对称，反对称，可传递的自反，对称，反对称，可传递的307.4 关系的性质关系的性质qX=1,2,3, R5= v反自反的，对称的，反对称的，可传递的反自反的，对称的，反对称的，可传递的q若若X= ，X上的空关系上的空关系v自反的，反自反的，对称的，反对称的，可传递自反的，反自反的，对称的，反对称的，可传递的的31第七章第七章: 二元关系二元关系q 第一节：有序对与笛卡儿积第一节：有序对与笛卡儿积 第二节：二元关系第二节：二元关系 第三节：关系的运算第三节：关系的运算 第四节：关系的性质第四节：关系的性质 第五节：关系的闭包第五节：关系的闭包
14、第六节：等价关系与划分第六节：等价关系与划分 第七节：偏序关系第七节：偏序关系327.5 关系的闭包关系的闭包q定定义义 R是是非非空空集集合合A上上的的关关系系，若若A上上另另外外有有一个关系一个关系R满足如下三条，满足如下三条，vR是是自反的自反的（对称的对称的，传递的传递的）vR RvA上上任任何何一一个个满满足足以以上上两两条条的的关关系系R”，均均有有R R”，称称关关系系R为为R的的自自反反（对对称称,传传递递）闭闭包包,记作记作r(R),（s(R),t(R)）337.5 关系的闭包关系的闭包q解释解释vR是在是在R的基础上添加有序对的基础上添加有序对v添加元素的目的是使添加元素的
15、目的是使R具有自反性具有自反性(对称性对称性,传递传递性性)v添加后使之具有自反性添加后使之具有自反性(对称性对称性,传递性传递性)的所有关的所有关系中系中R是最小的一个是最小的一个347.5 关系的闭包关系的闭包q例例A=a,b,c R=,v自反闭包自反闭包r(R)v,v对称闭包对称闭包s(R)v,v传递闭包传递闭包t(R)v,r(R)r(R)a b ccbaacbcbabac357.5 关系的闭包关系的闭包q例例R=,，求，求R的的传递闭包传递闭包 a b c d e367.5 关系的闭包关系的闭包q定理定理 R是非空集合是非空集合A上的关系上的关系,则则r(R)=RA证明证明: vR R
16、AvRA是自反的是自反的. v设设R”满足满足R R”,R”是自反的是自反的, RA 则则 R或或A 如如 R,由由R R”知知 R” 如如A,由由R”的自反性知的自反性知 R”。 均有均有 R” RA R” 377.5 关系的闭包关系的闭包q定理定理: 设设R是非空集是非空集A的关系的关系,则则s(R)=R R-1 q证明证明:vR R R-1满足定义第满足定义第2条条v R R-1 R R-1 R-1 R R R-1 R R-1是对称的是对称的387.5 关系的闭包关系的闭包v如如R R”,且且R”是对称的是对称的 R R-1 R或或 R-1如如 R,由由R R”,则则 R”如如 R-1,
17、则则 R,则则 R”因因R”对称对称 R”,R R-1 R”满足定义第满足定义第3条条397.5 关系的闭包关系的闭包q例例:设设A=1,2,3,A上的关系上的关系R如图如图,求求r(R),s(R)解解:R=,r(R)= RA =,s(R)= R R-1 =, 1 2 3407.5 关系的闭包关系的闭包定理定理: 设设R是非空集合是非空集合A上的关系上的关系,则则t(R)= Ri=R R2 推论推论: 设设A是非空有限集，是非空有限集，|A|=n，R是集合是集合A上的二上的二元关系，元关系， 则则t(R）= Ri=R R2 Rn417.5 关系的闭包关系的闭包q例例 A=a,b,c,dvR=,
18、vS=,求求t(R),t(S)q解解:R2=,R3=t(R)=R ,S2=,S3=,S4=t(S)=S , a b c dR a 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上的二元关系，上的二元关系， R1 R2，则有：，则有：vr(R1) r(R2)vs(R1)
19、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星星”： 自反传递闭包，自反传递闭包，
