东南大学离散数学课件.ppt
《东南大学离散数学课件.ppt》由会员分享,可在线阅读,更多相关《东南大学离散数学课件.ppt(46页珍藏版)》请在三一文库上搜索。
1、第七章: 二元关系,第一节:有序对与笛卡儿积 第二节:二元关系 第三节:关系的运算 第四节:关系的性质 第五节:关系的闭包 第六节:等价关系与划分 第七节:偏序关系,第七章: 二元关系,第一节:有序对与笛卡儿积 第二节:二元关系 第三节:关系的运算 第四节:关系的性质 第五节:关系的闭包 第六节:等价关系与划分 第七节:偏序关系,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
2、 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 关系的
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=, R
4、0= , R1=R R2=, R3=R2R =, R4=R3R1 =, R5=R4R1 =,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,第七章: 二元关系,第一节:有序对与笛卡儿积 第二节:二元关系 第三节:关系的运算
5、第四节:关系的性质 第五节:关系的闭包 第六节:等价关系与划分 第七节:偏序关系,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具有反自反关系。 实数上的
6、,关系,均是反自反关系。,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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 东南大学 离散数学 课件
链接地址:https://www.31doc.com/p-2045034.html