集合论II关系的概念、性质与运算资料.ppt

* * * * * * * 必要性证明用了集合相等的定义，也可以先用自反闭包的定义。 * * * 或者用直接证法： R1? R2 ? r(R2)，也就是说R1? r(R2) ，又知r(R2)是自反的，由自反闭包的定义可知r(R1) ? r(R2) * * * * * * * * * * * * IA ?R ? s(R)，故s(R)自反 ///// IA ?R ? t(R) ，故t(R)自反 任取 (a, b)? r(R)，由于r(R)=R ? IA，故 (a, b)? R 或者(a, b)? IA ，无论哪种情况均可推出(b, a)? r(R) ///// 任取(a, b)? t(R)，必存在某个m, (a, b)? Rm,只要证Rm是对称的，可用数学归纳法证明 r(R)=R ? IA ，任取(a, b)， (b, c) ? r(R)，有四种情况，无论哪种情况均可推出(a, c) ? r(R) s(R)不一定是传递的，因为s(R) )=R ? R--1， R 和 R -1各自是传递的，但是简单求并以后不一定是传递的 例如R={(a, b)， (b, c) , (a, c)} * 因为s(R) ? R，由定理2.6， rs(R) ? r(R) ， 由于s(R) 对称，由定理2.11， rs(R) 对称， 再由对称闭包的定义， rs(R) ? sr(R) 类似可证rs(R) ? sr(R) ，从而rs(R) = sr(R) * * * 证明： （公式法：等式推导） （3）由于s(R)=R?R-1?R, 根据定理2.6，有ts(R)?t(R)， sts(R)?st(R)。而由定理 2.11可知，ts(R)是对称的，所以sts(R)=ts(R)。因此ts(R)?st(R)。 第2次作业 1. 举出A={1, 2, 3}上关系R的例子，使其具有下述性质： a) 既是对称的，又是反对称的； b) 既不是对称的，又不是反对称的； c) 是传递的。 2. 设R和S是A上的二元关系，确定下列命题是真还是假。如果命题为真，则证明之；如果命题为假，则给出一个反例。 （1）若R和S是传递的，则R?S是传递的。 （2）若R和S是传递的，则R?S是传递的。 （3）若R和S是传递的，则RoS是传递的。 （4）若R是传递的，则R-1是传递的。 （5）若R和S是自反的，则R?S是自反的。 第2次作业 3. 给定X={a,b,c,d}，在X上定义关系R={a,db,cd,cc,b}求RoR的自反闭包、对称闭包及可传递闭包。 * * * * * * * * * * * * 对于R，“如果aRb且bRc，那么aRc” 或者成立，或者不成立，成立就是传递关系，不成立就不是传递关系，二者必居其一。 对于R2，如果你不能肯定它是传递的，可以从反面考虑问题，看它是否不是传递的， * * * * * * * * * * * * * * * * * 2 .3 关系的运算 定理2.1 （1）(R-1)-1=R; （2）(R1?R2)-1= R1-1? R2-1; （3）(R1?R2)-1= R1-1 ?R2-1; （4） (A?B)-1= B-1?A-1； （5）? -1=?； （6）(?)-1= ; （7） (R1-R2)-1= R1-1-R2-1； （8）若R1?R2，则R1-1? R2-1 。 证明方法 （1）证明两个关系相等，因为关系是集合，可采用证明集合相等的方法（基本法或公式法）证明关系相等。例如用基本法：任取a,b ?A a, b?左式?a, b?右式; 则左式?右式； a, b?右式?a, b?左式; 则右式?左式； 则左式=右式。 （2）证明关系满足某一性质 根据该性质的定义进行求证。 例如，要证明集合A上的二元关系R是自反的，就是证明对于任意的a?A，a, a?R。 证明两个关系相等 (3) 基本法证明： a, b?(R1?R2)-1 ? b, a? (R1?R2) ? b, a?R1且 b, a?R2 ? a, b?R1-1且a, b?R2-1? a, b ? R1-1 ?R2-1 所以，(R1?R2)-1= R1-1 ?R2-1。 (1), (2)类似, 证明见教材或参考书。 (4)类似。 (5)反证法。 设?-1??，则存在a, b??-1, 那么b, a??. 导致矛盾。 (6), (7), (8)基本法或公式法证明。 2 .3 关系的运算 定理2.2 R是A上的二元关系，则R是对称的?R=R-1。 证明： R是对称的 ? R=R-1：（证明两个关系相等） a, b?R, 因为R是对称的，所以b, a?R, 则a, b?R-1; 所以