收藏 分销(赏)

离散数学课件第四章(第3讲).ppt

上传人:人****来 文档编号:10251819 上传时间:2025-04-30 格式:PPT 页数:25 大小:625KB
下载 相关 举报
离散数学课件第四章(第3讲).ppt_第1页
第1页 / 共25页
离散数学课件第四章(第3讲).ppt_第2页
第2页 / 共25页
离散数学课件第四章(第3讲).ppt_第3页
第3页 / 共25页
离散数学课件第四章(第3讲).ppt_第4页
第4页 / 共25页
离散数学课件第四章(第3讲).ppt_第5页
第5页 / 共25页
点击查看更多>>
资源描述

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,4,关系的运算,关系的复合,定义,:设,(,R,关系),,(,S,关系),,于是可获得:,(,R,S,),的关系,称,R,S,为,R,和,S,的复合关系,并规定为:,例:设,A=1,2,3,4,5,,,R,S,均为,AA,的关系,且,R=S=,则,R,S=,S,R=,讨论:,(,1,),R,S,S,R,,,因此,“,”,是不可交换的。,(,2,),R,S,为新的二元关系,且,R,S,为,X,Z,上的二元关系。,定理,:设,则有:,即,:,关系的复合运算满足结合律,.,定义,给定集合,X,,,R,是,X,中的二元

2、关系,设,于是,R,的,n,次幂,可以定义成:,例:,多个相同的二元关系,R,复合,复合运算的矩阵表示:,设有三个集合:,而,|X|=m,|Y|=n,|Z|=p,,则关系矩阵:,例:设,X=1,2,3,R,S,均是,X,中的二元关系,,R=,S=,0 1 0,0 1 0,1 0 0,M,R,=,0,1 1,0,0 1,1,0 0,M,S,=,(,0,0,),(,1,0,),(,0,1,),=0,0,0,1,0 0 1,0 1 1,M,RS,=,2,逆关系,定义,:,设,X,Y,是二个集合,若,R,是,XY,的关系,从,YX,的关系,称为,R,的逆关系,用,表示,或用,表示。,例:,X=0,1,

3、2,,,R=,=,2,逆关系,讨论定义:,(,1,)只要将,R,中每一个序偶中的元素全部调换位置,就可得到,R,的逆关系。,(,2,),的关系矩阵为,的转置矩阵;,(,3,)在,R,的关系图中,只要把所有箭头改换方向就可得到,的关系图。(自回路箭头改变与否无关),定理,设,,则可有:,同样,证明:对于任一,来讲,若有,同理可证,R,一定是对称的,定理,:,设,R,是集合,X,中的二元关系,当且仅当,则,R,才是对称的。,证明:充分性:,R,是对称的,对于任一,必要性:,R,是对称的,,对任一,定理:给定集合,X,Y,,于是可有:,3.,闭包运算,定义,:给定集合,X,,,R,是,X,中的二元关

4、系,若有另一关系,R,满足下列条件:,(,1,),R,是自反的(对称,可传递的);,(,2,),则称,R,是,R,的自反(对称,传递的)闭包,,并依次用,r(R),s(R),t(R),来表示。,4,关系的运算,,则,(,3,)对于任一自反(对称,传递的)关系 ,若,例:设,A=1,2,3,,,R,为,AA,的关系,且,R=,R=,具有自反性质,R=,具有自反性质,R,是包含,R,的具有自反性质的,最小,的二元关系,讨论定义:,(,1,)已知一个集合中的二元关系,R,,则,r(R),s(R),t(R),是包含,R,的具有自反(对称,传递)性质的,最小,的二元关系,它们是,唯一,的;,(,2,)若

5、R,不是自反(对称,传递)的,则我们可以补上,最少,序偶,使之变为自反、对称、传递关系,从而得到,r(R),s(R),t(R),;,定理,:给定集合,X,,,R,是,X,中的二元关系,于是可有:,(,1,)当且仅当,r(R)=R,,则,R,是自反的;,(,2,)当且仅当,s(R)=R,,则,R,是对称的;,(,3,)当且仅当,t(R)=R,,则,R,是可传递的。,该定理说明:若,R,是自反(对称,传递)的,则,r(R),s(R),t(R),就是,R,本身。,定理,:,R,是,X,中的二元关系,是,X,中的恒等关系,,则有,证明:按定义证:,(,1,),设,,则,R,是自反的,,(,3,)设有

6、任一包含,R,的二元关系,R,也是自反的,即,则,例:设,X=a,b,c,R=,,求,r(R),解:,r(R)=,定理,:给定集合,X,,,R,是,X,中的二元关系,则有,例:设,X=a,b,c,R=,,求,s(R),s(R)=,定理,:设,X,是一集合,,R,是,X,中的二元关系,则:,例:,X=a,b,c,R=,,,|X|=3,计算,t(R),例:,X=a,b,c,d,R=,计算,t(R),定理,:设,|X|=n,,,R,是,X,中的二元关系,则,例:设,X=a,b,R=,,求,r(R),s(R),t(R),r(R)=,s(R)=,t(R)=R,定理,:设,X,是一集合,,R,是,X,中的二元关系,则有:,r(S(R)=S(r(R),r(t(R)=t(r(R),S(t(R),t(S(R),证明:,r(s(R),r(S(R)=S(r(R),例:设,X=a,b,c,R=,(,1,),rs(R)=r=,sr(R)=s=,(,2,),rt(R)=r=,tr(R)=t=,(,3,),ts(R)=t=,st(R)=S=,

展开阅读全文

开通  VIP会员、SVIP会员  优惠大
下载10份以上建议开通VIP会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传
相似文档                                   自信AI助手自信AI助手
搜索标签

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        抽奖活动

©2010-2025 宁波自信网络信息技术有限公司  版权所有

客服电话:4009-655-100  投诉/维权电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :gzh.png    weibo.png    LOFTER.png 

客服