《离散数学课件第四章(第3讲).ppt》由会员分享，可在线阅读，更多相关《离散数学课件第四章(第3讲).ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4 关系的运算关系的运算关系的复合关系的复合定义定义：设（R关系），关系），（S关系），关系），于是可获得：于是可获得：（RS）的关系，称的关系，称 RS为为R和和S的复合关系，并规定为：的复合关系，并规定为：例：设例：设A=1,2,3,4,5，R,S均为均为AA的关系，且的关系，且R=S=则则 RS=SR=讨论：讨论：（1）RS SR，因此因此“”是不可交换的。是不可交换的。（2）RS为新的二元关系，且为新的二元关系，且RS为X Z 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 00 1 01 0 0MR=0 1 10 0 11 0 0MS=（0 0）（1 0）（0 1）=00 0 10 0 10 1 1MRS=2逆关系逆关系 定义定义:设设X,Y是二个集合，若是二个集合，若R是是XY的关系，从的关系，从YX的关的关系，称
3、为系，称为R的逆关系，用的逆关系，用 表示，或用表示，或用 表示。表示。例：例：X=0,1,2，R=2逆关系逆关系 讨论定义：讨论定义：（1）只要将）只要将R中每一个序偶中的元素全部调换位置，就可得到中每一个序偶中的元素全部调换位置，就可得到R的的逆关系逆关系。（2）的关系矩阵为的关系矩阵为 的的转置矩置矩阵；（3）在）在R的关系的关系图中，只要把所有箭中，只要把所有箭头改改换方向就可得到方向就可得到的关系的关系图。（自回路箭。（自回路箭头改改变与否无关）与否无关）定理定理设，则可有：，则可有：同样 证明：对于任一证明：对于任一 来讲，若有来讲，若有 同理可同理可证 R一定是对称的一定是对称的
4、 定理定理:设设R是集合是集合X中的二元关系，当且仅当中的二元关系，当且仅当则则R才是对称的。才是对称的。证明：证明：充分性：充分性：R是对称的是对称的 对于任一对于任一 必要性：必要性：R是对称的，是对称的，对任一对任一 定理：给定集合定理：给定集合X,Y,，于是可有：，于是可有：3.闭包运算闭包运算定义定义：给定集合：给定集合X，R是是X中的二元关系，若有另一中的二元关系，若有另一关系关系R满足下列条件：满足下列条件：（1）R 是自反的（对称，可传递的）；是自反的（对称，可传递的）；（2）则称则称R是是R的自反（对称，传递的）闭包，的自反（对称，传递的）闭包，并依次用并依次用r(R),s(
5、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）若）若R不是自
6、反（对称，传递）的，则我们可以补上不是自反（对称，传递）的，则我们可以补上最少最少序偶，使之变为自反、对称、传递关系，从而得到序偶，使之变为自反、对称、传递关系，从而得到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)
7、就是就是R本身。本身。定理定理：R是是X中的二元关系中的二元关系,是是X中的恒等关系，中的恒等关系，则有则有 证明：按定义证：证明：按定义证：（1）设设，则，则R是自反的，是自反的，（3）设有任一包含）设有任一包含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=