离散数学课件第三章集合与关系—2.pptVIP

3-7 复合关系和逆关系 二元关系是以序偶为元素的集合，所以可以对它进行集合运算。 此外还有一种新的运算：关系的复合 定义3-7.1 设R是从集合A到集合B上的二元关系，S是从集合B到集合C上的二元关系，则R?S称为R和S的复合关系，表示为 R?S={ x，z ? x∈A∧z∈C ∧ ?y(y∈B∧x，y∈R∧y，z∈S) } 复合关系举例 例：A={1，2，3，4}，B={3，5，7}，C={1，2，3} R={2,7，3,5，4,3}，S={3,3，7,2} 则 R?S={2，2，4，3} 如图所示： 复合关系的结合律 定理：设R1? A1 ? A2, R2 ? A2 ? A3, R3 ? A3 ? A4, 则 (R1?R2)?R3 = R1?(R2?R3)。 复合关系的矩阵表示（自学） 两个关系的复合可通过相应矩阵相乘获得。 复合关系练习 练习：R是A上的二元关系，试证R是传递的充要条件是R?R?R 逆关系 定义3-7.2 设R是A到B的二元关系，则R的逆是B到A的二元关系，记为Rc，其中Rc ={y,x|x,y?R}。 注 ：（1）xRy?yRcx （2）互换R的关系矩阵的行和列，即得Rc的关系矩阵。 即 MRc＝MRT （3）颠倒R的关系图中每条弧线的箭头方向，即得Rc的关系图。 逆关系举例 例1 整数集上的 ‘’ 关系的逆是 ‘’ 关系 集合族上的 ‘?’ 关系的逆是 ‘?’ 空关系的逆是空关系 A?B的全域关系的逆是B?A的全域关系 例2 A={0,1,2,3}，R={0,0,0,3,3,2,1,3} 则 Rc = { 0,0,3,0,2,3,3,1 } 定理 定理：设R,R2,R1是A到B的关系，则 a） (Rc)c=R b） (R1∪R2)c = R1c∪R2c c） (R1∩R2)c = R1c∩R2 d） (~R)c = ~(Rc), ~R=A?B-R 即R的补的逆等于逆的补 e） (R1-R2)c =R1c -R2c f) (A?B)c = B?A 定理 定理3-7.2 设R、S分别是A到B、B到C的关系， 则(R?S)c=Sc ? Rc 定理 定理3-7.3 R是A上的二元关系 (a) R是对称的 ? R=Rc (b) R是反对称的 ? R∩Rc?IA 3-8 关系的闭包运算 设R是A上的关系，我们希望R具有某些有用的性质，比如说自反性。如果R不具有自反性，我们通过在R中添加一部分有序对来改造R，得到新的关系R’，使得R’具有自反性。但又不希望R’与R相差太多，换句话说，添加的有序对要尽可能的少。满足这些要求的R’就称为R的自反闭包。通过添加有序对来构造的闭包除自反闭包外还有对称闭包和传递闭包。 各种闭包的定义 定义3-8.1 设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R’，使得R’满足以下条件：　　（1）R’是自反的（对称的或传递的）　　（2）R ? R’ 　　（3）对A上任何包含R的自反（对称或传递）关系R”，有 R’ ? R”。　　 一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。 注： R的自反闭包记为r(R),若R是自反的，则R=r(R),反之也成立。 R的对称闭包记为s(R),若R是对称的，则R=s(R),反之也成立。 R的传递闭包记为t(R),若R是传递的，则R=t(R),反之也成立。 构造闭包的方法 下面的定理给出了构造闭包的方法： ① 自反闭包 r(R)=R∪IA 用关系图解释 ② 对称闭包 s(R)=R∪Rc ③ 传递闭包 t(R)= = R∪R2∪R3∪… 证明 r(R)=R∪IA 证：设R’ = R∪IA ∵ ① ?x?A,x,x?R’ ∴R’具有自反性 ② R?R’ ③ 设R”是自反的，且R?R” ∵R’’是自反的，∴IA?R” 又∵R?R” ∴R’=IA∪R?R” 综上所述，R’满足自反闭包定义的三个条件， ∴ r(R)= R’= R∪IA 证明 s(R)=R∪Rc 证明：设 R’= R∪Rc ① R’c=(R∪Rc)c=Rc∪(Rc)c= Rc∪R=R’ ， 所以R’是对称的 ② R’=R∪Rc?R ③ 设R”是对称的，且R?R” ，要证 R’?R” 任取a,b∈R∪Rc?a,b∈R∨a,b∈Rc ? a,b∈R”∨b,a∈R