[离散数学讲义第3章.ppt

关系是序偶的集合，由于序偶的有序，可以得到关系的一些特殊运算。 3-7 复合关系和逆关系（续） 定义：R为X到Y的二元关系，将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系，记作Rc Rc = {〈y,x〉| 〈x,y〉?R} 例如：集合I上的关系的逆关系为，集合X={1,2,3,4}到Y={a,b,c}上的关系R={〈1,a〉,〈2,b〉,〈3,c〉},则逆关系为 Rc={〈a,1〉,〈b,2〉,〈c,3〉} 注：显然(Rc)c =R 证明：〈x,y〉?R ?〈y,x〉?Rc ?〈x,y〉?(Rc)c Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 3-7 复合关系和逆关系（续） 定理：设R，R1，R2都是从A到B的二元关系，则： (R1 ∪ R2)c = R1c ∪ R2c (R1 ∩ R2)c = R1c ∩ R2c (A ? B)c = B ? A (R)c = Rc 其中R= A ? B-R (R1 - R2)c = R1c - R2c Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. d) 〈x,y〉? (R)c 3-7 复合关系和逆关系（续） 证明： a) 〈x,y〉? (R1 ∪ R2)c ? 〈y,x〉? R1 ∪ R2 ? 〈y,x〉? R1 ?〈y,x〉? R2 ? 〈x,y〉? R1c ?〈x,y〉? R2c ? 〈x,y〉? R1c ∪ R2c ? 〈y,x〉? R ?〈y,x〉? R ? 〈x,y〉? Rc ?〈x,y〉? Rc e) R1 - R2 = R1 ∩ R2 因此(R1 - R2)c = (R1 ∩ R2)c = R1c ∩ (R2)c = R1c ∩ R2c = R1c - R2c Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 3-7 复合关系和逆关系（续） 定理：设T为从集合X到集合Y的关系，S为从集合Y到集合Z的关系，则(T ? S)c = Sc ? Tc。 证明：〈z,x〉? (T ? S)c ? 〈x,z〉? T ? S 定理：设R为X上的二元关系，则 R是对称当且仅当R=Rc R是反对称的当且仅当R ∩ Rc ? IX 证明：R对称，则〈x,y〉?R ?〈y,x〉?R ?〈x,y〉? Rc得证R=Rc；反之，若R=Rc ，则〈x,y〉? R ?〈y,x〉? Rc ? 〈y,x〉? R，因此可得R是对称的。 ? (?y)(y?Y ?〈x,y〉?T ?〈y,z〉?S) ? (?y)(y?Y ?〈y,x〉?Tc ?〈z,y〉?Sc) ? 〈z,x〉? Sc ? Tc Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 3-7 复合关系和逆关系（续） 例4：集合X={a,b,c}，R是X上的二元关系，R的关系矩阵如下，求Rc和R ? Rc的关系矩阵。 解： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 3-8 关系的闭包运算 定义：设R是X上的二元关系，若另有一个关系R’满足： a) R’是自反的（对称的，可传递的） b) R’ ? R c) 对于任何自反的（对称的，可传递的）关系R’’，如果有R’’ ? R，则有R’’ ? R’。 则称关系R’为R的自反（对称，传递）闭包。记作r(R)，（s(R)，t(R)）。 注：自反（对称，传递）闭包是包含R的最小自反（对称，传递）关系。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspo