第三章关系习题课(学生)

1、精选优质文档-倾情为你奉上习 题 课例1 设是一个集合，n，求：1.上的二元关系有多少？2. 上的自反的二元关系有多少？3. 上的反自反的二元关系有多少？解：因为把所有的反自反的二元关系的每个都加上对角线上的序对，就变成了自反的关系，因此，自反的与反自反的个数一样多。即4. 上的对称的二元关系有多少？，故共有个对称的关系。5. 上的反对称的二元关系有多少？6. 上既是自反的也是反自反的二元关系的个数；7.上既不是自反的也不是反自反的二元关系有多少？解：解：可用容斥原理来计算设B表示所有自反关系构成的集合，C表示所有反自反关系构成的集合，则。而，故，从而于是，既不是自反的，也不是反自反关系共有个

2、。8.自反的且对称的关系有多少？此结果与“反自反的且对称的关系有多少？”是一样多即有（对角线上全去掉）9.自反的或对称的关系有多少？解：设B表示自反关系的集合，C表示对称关系的集合，则自反或对称关系的集合为：。10.上既是反自反的也是反对称的二元关系的个数为：；11.上既是对称的也是反对称的关系个数；解：上既是对称的也是反对称的关系，故有。12.上既不是对称的也不是反对称的关系个数；解：设A表示对称、B表示反对称，则既不是对称的也不是反对称的二元关系为：例2设有集合A，求A上具有反自反且反对称性的二元关系的数目，并写出计算过程。解：不妨设，将，看作一个抽屉，看作一个抽屉，看作一个抽屉。若要获得

3、具有反对称性且反自反性的关系，其中的元素只能在三个抽屉中取且每个抽屉中至多取一个元素，分几种情况：（1）一个也不取，有种取法。（2）只取一个元素，有种取法。（3）取二个元素，有种取法。（4）取三个元素，有种取法。故具有反自反性且反对称性的二元关系数目共有1612827个。若，结果又为多少？抽屉数：，每个抽屉有3种选择，故共有个。例3 设，是A的幂集上的二元关系且，则不满足下列哪些性质？为什么？（1）自反性；（2）反自反性；（3）对称性；（4）反对称性；（5）传递性。等价于。解：(1)自反性。因为，但，所以，故不是自反的。（2）反自反性。因为，故，故不是反自反的。（3）对称性。，若，则，所以，故

4、，从而是对称的。（4）反对称性。令，则，故且，但，所以，从而不是反对称的。（5）传递性。令，则有且，故且，但，故，所以不是传递的。习题课例1 证明：，其中证：；同理可证例2 书上做为定理出现设R、S是上的二元关系，则（1），是空关系。（2）证：因为是传递的，故。（3）证：因为且，故，且，从而例3 如图5所示给出下图中每个关系的自反、对称和传递闭包。· · （a） （b） （c）图5（1）自反闭包（2）对称闭包（3）传递闭包例4 设R是集合A上的反对称关系，则t(R)一定是反对称的吗？证：t(R)在A上不一定是反对称的。例：，则R的传递闭包为：t(R)是全关系，故t(R)不是

5、反对称的而是对称的。例5 举例说明与确实不相等。解：设，在上定义小于关系“”，则“不等关系”；而“全关系”。因此的确不相等。例7（）是否存在（）上的一个二元关系R，使得两两不相等。解：存在。令，即可。例8 证明：如果R是对称的，则R也是对称的。证：证1 ，则，使得。于是存在m1个元素，使得。由R的对称性有：。于是，从而，即是对称的。习 题 课例1 设是整数集上的关系，定义为，则（1）证明：是等价关系；（2）确定的等价类。证：（1）因为，有，故，即R是自反的。，若，即，则，因此，即R是对称的。，若，即且，故，即，所以R是传递的。由此可知：是上的等价关系。（2）因为，所以R的等价类有：。例2设是上

6、的一个自反关系，证明：是等价关系若且，则。书上习题证：是上的等价关系。若且，由的对称性有：且，再由的传递性有：R是自反的，故有。若，由，有，所以是对称的。若且，由的对称性有：且，故由题意得，所以是传递。因此，是上的等价关系。例3.令，上的两个关系如图3所示，它们是否是等价关系？不是等价关系（因为不传递）是等价关系图3例4 设，是上的等价关系，则也是上的等价关系吗？解：不一定是的等价关系。因为不一定具有传递性。举例：设，则因为且，但，故不满足传递性，即不一定是上的等价关系。例5设是上如下的二元关系：，当且仅当。证明：(1) 等价关系；(2)求等价类数。证：(1)等价关系显然；(2)等价类数为：。

7、只能取2，3，2n，故等价类数有个。例6 设R是A上的对称和传递的关系。若对A中每个a，使得，证明：R是A上的等价关系。证：，使得。由R的对称性有：。再由R的传递性有：。由a的任意性可知，R是A上的自反关系，故R是A上的等价关系。例7 设R是集合A上的一个自反的和传递的关系；T是A上的一个关系，使得且。证明：T是A上的等价关系。证：（1）因为R是上的自反关系，所以，有，故由T的定义有：，即T是上的自反关系。（2）若，由题设：且。显然，即T是上的对称关系。（3）若且，由题设可知：，且，。由R传递性得：且，故，所以T是上的传递关系。由（1），（2），（3）即得T是上的等价关系。例8设是上的一个二元

8、关系，设，使得且。证明：若是上的等价关系，则也是上的等价关系；证： 证明若是等价关系，则也是等价关系。（1）自反性因为是自反的，所以，有。根据的定义，有，所以是自反的；（2）对称性：若，则，使得且。因为是对称的，所以且，根据的定义有，所以是对称的；(3) 传递性：若，则，使得且。因为是传递的，所以。且，使得且。因为是传递的，所以。根据的定义有。所以是传递的。由（1），（2），（3）可知：是等价关系。例9 设是集合A的划分，若，1in，证明：是集合的划分。证：因为是集合A的划分，故，ij。但，当ij时，。当ij时，。所以是的划分。例10设和是集合上的等价关系，和是由和所诱导产生的划分，证明：当且

9、仅当的每个划分块都包含在的某个划分块中，。 分析：只要理解等价关系和划分的概念以及它们之间的一一对应关系，就很容易证明。证：令划分, 。充分性。若，则的每个划分块都包含在的某个划分块中。于是，即为中任一划分块，所以。在中任取一个元素。因为是的划分且，所以存在，使得。于是，有，又因为，所以。根据划分的定义有，所以。由的任意性知，的每一划分块都包含在的某一划分块中。必要性若的每个划分块都包含在的某个划分块中，则。，则在的同一划分块中。根据题设，必有在的同一划分块中，故。因此。例11设。是S上的二元关系，若，证明：是上的等价关系；求等价类。证：因为，所以到的映射共有8个，如图2所示。图2（1）等价关

10、系显然。（2），故，。所以等价类集合为。例12 设，并设，在上定义关系为：。证明：(1)R是等价关系；(2)计算出A/R。证：I(1)自反性。，有，所以，即R是A上的自反关系。(2)对称性。，若，则，故，所以，即R是A上的对称关系。(3)传递性。，若且，则且，即，所以，故R是A上的传递关系。由(1)，(2)，(3)可知，R是A上的等价关系。II首先求出A=S×S的全部元素，然后找出所有元素对应的等价类即可。在求等价类时，记住以下几条性质：(1)；(2)若，则。因为所以，例13设是上的等价关系，是上的等价关系。关系满足：证明：是上的等价关系。解：（1）自反性：，有，；因为和分别为和上的

11、自反关系，所以，故，因此是自反性的；（2）对称性：，若，则，；因为和分别为和上的对称关系，所以有，从而，因此是对称性的；(3) 传递性：，若且，则有 ，；因为和分别为和上的传递关系，所以有，从而，因此是传递性的。综上可知：是上的等价关系。例14设是自然数集合，定义上的二元关系：，则 （1）证明是一个等价关系；（2）求关系的等价类；证：（1）自反性：，是偶数，所以有。因此是自反的；对称性：若，即是偶数，则是偶数，所以有。因此是对称的；传递性：若，即是偶数，是偶数，则是偶数，所以有。因此是传递的。 综上可知：是等价关系。（2）关系的等价类有：。（3）设， 则所诱导的等价关系就是。例15 设，A上的

12、二元关系R定义为：，证明：1.R是A上的等价关系；2.确定由R对集合A的划分。证：1.首先证明R是A上的等价关系。(1)自反性。，因为，故，即R是自反的。(2)，若，有，则，从而，即R是对称的。(3)，若即，得，从而，故R是传递的。由(1)、(2)、(3)可知，R是A上的等价关系。2.由定理知，由R的等价类可确定对集合A的划分。划分中的元素分别为元素的等价类，它们是：即集合A的划分。习 题 课例1 非空集合A上存在二元关系R，使得R既是A上的等价关系又是A上的偏序关系吗？解：存在。A上的恒等关系就满足。例2 在A1,2,3,4,6,8,12,24和B2,3,4,8,9,10,11上定义的整除关

13、系“|”，画出Hasse图，指出最大（小）元，极大（小）元。(a) (b)图1解：如图1(a)所示最大元：24 最小元：1；极大元：24 极小元：1；如图1(b)所示最大元：无 极大元：8，9，10，11；最小元：无 极大元：2，3，11（元素11既是极大元又是极小元）。例3 设偏序集的关系图如图2(a)所示。(1)画出的Hasse图。(2)设Bb,c，求B的上界集合C和上确界；下界集合D和下确界。(a) (b)图2解：1. 的Hasse图如图8(b)所示。1. 设Bb,c，则A中无任意元素“大于”b，也同时“大于”c，故C，此时，无上确界，而Dd，下确界：d。例4 设集合上的偏序关系如图9所

14、示。则1.求出A的最大（小）元，极大（小）元。2.求出的上界、下界、上确界和下确界。x5x4x3x2x1图2解：1.最大元：最小元：无极大元：极小元：，2.令，则上界：下界； 上确界：下确界：令，则上界：，下界：无； 上确界：，下确界：无；令，则上界：，下界：； 上确界：，下确界：。例5设集合，上的关系定义如下：。则 （1）写出的关系矩阵；（2）验证是偏序集；（3）并画出Hasse图。（4）若上的关系如下：，则又如何？cebad解：（1）所对应的关系矩阵为为：（2）由关系矩阵可知：对角线上的所有元素全为1，故是自反的； 图10，故是反对称的； 对应的关系矩阵为： 。因此是传递的。综上可知：故是

15、上的偏序关系，从而是偏序集。（3）对应的Hasse图如图10所示。（4）的关系矩阵为：因为，但，故不是传递的。因此，不是上的偏序关系。实际上，也可通过计算的关系矩阵来说明：，故不是传递的。因此不是上的偏序关系。例6 证明：每个由个实数组成的数列中必有一个长至少为的不减子序列，或有一个长至少为的不增子序列。证：不妨设个数是互不相同的。于是，这个数构成的集合A，且。在A上定义二元关系“”如下：当且仅当且。其中是实数间的通常的小于或等于关系。显然，二元关系是自反的，传递的。设且，则，且，从而，。所以，是反对称的。因此是A上的偏序关系，是偏序集。由推论可知，A中或有长至少为的链或有长至少为的反链。A中

16、长至少为的链，就是序列的长至少为的不减（在下）的子序列。而A的长至少为的反链，实际上就构成了的不增子序列。设反链中元素按下标递增顺序排列成因1，而，所以，故，。于是便有：。例7设是实数集，令为到的所有映射所构成的集合。若，定义：，证明：（1）是偏序关系；（2）是全序关系吗?分析：证明是偏序关系，首先搞清是定义在什么集合上，中的元素是什么形式；然后再按偏序关系的定义分别证明的自反性，反对称性，传递性；证明这三个性质，可以直接采用按定义方法证明。显然是定义在以映射作为元素的集合上，因此，中的序对是以映射作为元素的。证明：（1）证明是偏序关系。自反性：，则， ，都有， 即，故，所以是自反的。反对称性：，若且，则，有， ，即，故，即，从而是反对称的。传递性：，若且，则，有，即，所以，即，因此有，从而是传递的。综上可知：是偏序关系。（2）不是全序关系。例如：设，则，故与是不可比较的，即不是全序关系。例8设是偏序集，,，证明：是一个单射，且当时，有。证：由的定义，因，有。，若，则有，即；同理可证。由于偏序关系是反对称的，所以有，于是是单射。当时，有，由于偏序关系是传递的，有，即。于是。例9 已知集合A和B，其中A，（B，）是偏序集，定义上的二元关系如下：，1证明：R为上的偏序关系。2给出存在最大元的必要条件和最大元的一般形式。证：1（1）及有，因为是偏序集，所以“”是偏序关系，