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

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上的二元关系。定理：设 则有： 即:关系的复合运算满足结合律. 定义给定集合X，R是X中的二元关系，设 于是R的n次幂 可以定义成：例：多个相同的二元关系R 复合复合运算的矩阵表示： 设有三个集合： 而|X|=m,|Y|=n,|Z|=p，则关系矩阵：例：设X=1,2,3,R,S均是X中的二元关系，

2、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的关系，称为R的逆关系，用 表示，或用 表示。例：X=0,1,2，R= =2逆关系 讨论定义：（1）只要将R中每一个序偶中的元素全部调换位置，就可得到R的逆关系 。（2 ） 的关系矩阵为 的转置矩阵； （3）在R的关系图中，只要把所有箭头改换方向就可得到的关系图。（自回路箭头改变与否无关） 定理设 ，则可有： 同样 证明：对于任一 来讲，若有 同理可证R一定是对称的 定理:设R是

3、集合X中的二元关系，当且仅当则R才是对称的。证明：充分性：R是对称的 对于任一 必要性： R是对称的， 对任一 定理：给定集合X,Y, ，于是可有： 3.闭包运算定义：给定集合X，R是X中的二元关系，若有另一关系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，则

4、r(R), s(R), t(R)是包含R的具有自反（对称，传递）性质的最小的二元关系,它们是唯一的； （2）若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是自反的， （

5、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) =