1、第 3-3讲 复合 关系、逆关系与闭包运算1. 复合关系2. 逆关系3. 闭包 的概念4. 构造闭包5. 课堂练习6. 第 3-3讲 作业11、 复合关系定义 1 设 R是 X到 Y的关系， S是 Y到 Z的关系，则 RS称为 R和 S的 复合关系 ，定 义为 ：RS= y(RS） 例 1 设 R=,S=,求 RS， SR， RR， RRR。解 ： RS=,SR=,RR =,RRR=( RR) R=,n RR和 RRR分别记作 R(2)、 R(3)， 进而有 R(n)。21、 复合关系 （续）n 关系的复合运算可以利用关系矩阵求出：设关系矩阵 A=(aij)nn， B=(bij)nn， C=(
2、cij)nn， AB =C其中如例 1可用矩阵运算求解如下：式中： 表示逻辑析取 表示逻辑合取32、 逆关系定义 2 二元关系 R的 逆关系 定义为：RC=|R。设 R=,，则RC=,。定理 1 设 R、 S都是集合 A到 B的二元关系，则（ 1） (RC)C=R（ 2） (RS)C= RCSC（ 3） (RS)C= RCSC（ 4） (AB)C=B A（ 5） (R)C= (RC) （ 这里 R= AB-R,即 R的绝对补 ）（ 6） (R-S)C= RC-SC42、 逆关系 （续 2）定理 2 设 T是 X到 Y的关系， S是 Y到 Z的关系，证明 (TS)C=SCTC证： (TS)C T
3、Sy( T S)y( TC SC) SCTC 定理 3 设 R为 A上的关系，则（ 1） R在 A上自反当且仅当 IA R（ 2） R在 A上反自反当且仅当 RIA=（ 3） R在 A上对称当且仅当 R RC（ 4） R在 A上反对称当且仅当 RRCIA（ 5） R在 A上传递当且仅当 RRR52、 逆关系 （续 3）（定理 3的证明） 证： (1)R在 A上自反当且仅当 IA R。必要性。 任取 IA， 如果 R在 A上自反 ,必有IA x A R从而证明了 IA R。充分性。 当 IA R时，任取 xA IA R，因此 R在 A上是自反的。（ 2） R在 A上反自反当且仅当 RIA=。必要
4、性 。用反证法。假设 R在 A上反自反但 RIA， 必存在 RIA， 由于 IA是 A上的恒等关系，从而推出x=y， xA且 R ， 这与 R在 A上是反自反的相矛盾。充分性。 设 RIA=， 任取 xAIA R。从而证明了 R在 A上是反自反的。62、 逆关系 （续 4）（定理 3的证明） (5) R在 A上传递当且仅当 RRR 。必要性。 如果 R在 A上是传递的，任取 RR， 有RRt(RR)R, 所以 RRR充分性。 若 RRR， 如果 、 R， 因R R RR R, 所以 R是传递的。证： (4) R在 A上反对称当且仅当 RRCIA必要性。 任取 RRCRRCRR x=y（ 因为
5、R在 A上是反对称的） IA。 这就证明了 RRCIA充分性 若 RRCIA， 任取 R， 如果同时有 R，由于 R R RRC RRCIA x=y 所以， R在 A上是反对称的73、 闭包的概念定义 3 设 R是非空集合 A上的关系，如果(1) R 是自反的 (对称的、传递的 )； (2) RR ；(3)若 R” 是 A上自反 (对称 .传递 )关系 ,如果 R” R，则R” R 。则称 R 是 R的 自反闭包 (对称闭包 、 传递闭包 )。 记作r(R),s(R),t(R)。关系可以具有自反、对称、传递等性质。然而，不是所有的关系都具有这些性质。但通过对给定的关系添加新的元素（有序对），所
6、得的关系将具有这些性质。当然，在对给定的关系进行扩充时，一方面要使扩充后的关系具有某些性质；另一方面，又不想添加过多的元素，做到恰到好处，即添加的元素要最少。对给定的关系用扩充元素的方法得出具有某些性质的新关系叫闭包运算。83、 闭包的概念 （续 1）定理 4 设 R是非空集合 A上的关系， R是自反的 (对称的、传递的 )，当且仅当 r(R)=R（ s(R)=R,t(R)=R）。从闭包的定义可知， R的自反闭包 (对称闭包、传递闭包 )是包含 R且具有自反 (对称、传递 )性质的 “ 最小 ” 关系。同时，如果 R本身已经具备这些性质，那么它们就是具备这些性质且包含 R的 “ 最小 ” 关系。于是，有下面的定理：93、 闭包的概念 （续 2）例 2 设 A=1,2,3,4， R=,，求 r(R)， s(R)， t(R)。解： r(R)=RIA=,s(R)=RRC=,t(R)=,也可从 R的关系图来求关系闭包。10
