离散数学与3.7-8 .pptVIP

3－7复合关系和逆关系 一、复合关系 定义 设R是一个从集合A到集合B的二元关系，S是从集合B到集合C的二元关系(也可简单的描述为R：A→B，S：B→C)，则R与S的复合关系R?S是从A到C的关系，并且： R?S＝ 运算“?”称为复合运算。 复合关系和逆关系 例例1)、设R1是关系“是…的兄弟”，R2是关系“是…的母亲”，则R1?R2是什么关系？ 2）如果R1是关系“是…的母亲” ，则R1?R1是什么关系？ 复合关系和逆关系 例：设 R＝{1,2,3,4,2,2} S＝{4,2,2,3,3,1}， 分别是定义为从A→B和从B→C的关系，其中A＝B＝C＝{1,2,3,4}。 1)用集合方法求R?S，S?R，R?R，S?S。则： R?S＝{1,3,3,2,2,3}； S?R＝{4,2,2,4,3,2}； R?R＝{1,2,2,2}； S?S＝{4,3,2,1}。 复合关系和逆关系 R本身的复合关系 R?R R?????R R(m)? R(n) (R(m))(n) 复合关系和逆关系 设I是整数集合，R，S是I到I的两个关系： R＝{x,3x|x∈I}； S＝{x,5x|x∈I}。 则： R?S＝ S?R＝ R?R＝ S?S＝ (R?R)?R＝ (R?S)?R＝ 复合关系和逆关系 复合关系也可以用矩阵来表示 复合关系和逆关系 复合关系和逆关系 例：设A＝{a,b,c),B＝{1,2,3},R是从A到B的一个关系，R＝{a,1,c,2,b,3}， 则：　 Rc＝关系图和关系矩阵如下： 复合关系和逆关系 三、几种运算之间的若干重要性质 定理　设R，S，T分别是从集合A到集合B，集合B到集合C，集合C到集合D的二元关系，则： 1)(R?S)?T＝R?(S?T) 2)(R?S)c＝Sc?Rc定理3-7.2 复合关系和逆关系 复合关系和逆关系 2).任取c,a∈(R?S)c，则a,c∈R?S,由“?”的定义知：则至少存一个b∈B,使得：a,b∈R，b,c∈S， 即：b,a∈Rc,c,b∈Sc。由c,b∈Sc和b,a∈Rc,有：c,a∈Sc?Rc，所以，(R?S)c?Sc?Rc。 反之，任取c,a∈Sc?Rc，由“?”的定义知：则至少存一个b∈B,使得：c,b∈Sc和b,a∈Rc，所以：　a,b∈R，b,c∈S。由“?”知：a,c∈R?S。即有：c,a∈(R?S)c。所以，Sc?Rc?(R?S)c。 由集合的定义知：(R?S)c＝Sc?Rc。■ 复合关系和逆关系 定理 设R，S是从集合A到集合B的二元关系，则有： (R∪S)c＝Rc∪Sc； (R∩S)c＝Rc∩Sc； (R-S)c＝Rc-Sc； (R)c＝Rc； R=A×B-R (A×B)c＝(B×A)；　 定理3-7.3 设R为上的二元关系，则 a) R是对称的，当且仅当R=Rc b) R是反对称的，当且仅当R∩Rc ? Ix 例题 复合关系和逆关系 例：设A＝{a,b,c,d,e,f},定义在A上的关系 R＝{a,a,a,b,b,c,c,d,d,e,e,f}， S＝{a,b,b,c,c,d,d,e,e,f},求Rn和Sn。 复合关系和逆关系 　S1＝S, 　S2＝S?S＝{a,c,b,d,c,e,d,f}， 　S3＝S?S?S＝S2?S＝{a,d,b,e,c,f}， 　S4＝S3?S＝{a,e,b,f}， 　S5＝S4?S＝{a,f}， 　S6＝S5?S＝Φ， 　S7＝Φ，…， 　Sn＝Φ　(n5)。 3-8关系的闭包运算 对一些给定的关系用扩充一些序偶得办法可得到具 有某些特殊性质的新关系。这就是闭包运算。　 定义 设R是X上的二元关系，如果另一个关系R’是 满足： 1. R’是自反的； 2. R ? R’； 3.对于X上的任意自反的关系R”，若R?R”，则R’?R”。 则称R’为R的自反闭包。 换句话说，R的自反闭包（对称闭包、传递闭包）是包含R的最小的自反的（对称的、传递的）关系。 通常分别用r(R)、s(R)和t(R)表示R的自反闭包、对称闭包和传递闭包。 关系的闭包运算 　【定理】设R 是 X 上的二元关系，则： 1. R是自反的当且仅当r(R) = R； 2. R是对称的当且仅当s(R) = R； 3. R是传递的当且仅当t(R) = R； 关系的闭包运算 下面介绍由给定关系R,求其各种闭包的方法。 定理 设R是集合A上的二元关系，则： r(R)＝R∪IA。 s(R)＝R∪RC。 t(R)＝t(R) = R ? R2 ? R3 ? ...