第三章关系习题课(学生)(共18页).doc

精选优质文档-----倾情为你奉上习 题 课例1 设是一个集合，＝n，求：1.上的二元关系有多少？2. 上的自反的二元关系有多少？3. 上的反自反的二元关系有多少？解：因为把所有的反自反的二元关系的每个都加上对角线上的序对，就变成了自反的关系，因此，自反的与反自反的个数一样多即4. 上的对称的二元关系有多少？，故共有个对称的关系5. 上的反对称的二元关系有多少？6. 上既是自反的也是反自反的二元关系的个数；7.上既不是自反的也不是反自反的二元关系有多少？解：解：可用容斥原理来计算设B表示所有自反关系构成的集合，C表示所有反自反关系构成的集合，则而，故，从而于是，既不是自反的，也不是反自反关系共有个8.自反的且对称的关系有多少？[此结果与“反自反的且对称的关系有多少？”是一样多]即有（对角线上全去掉）9.自反的或对称的关系有多少？解：设B表示自反关系的集合，C表示对称关系的集合，则自反或对称关系的集合为：10.上既是反自反的也是反对称的二元关系的个数为：；11.上既是对称的也是反对称的关系个数；解：上既是对称的也是反对称的关系，故有12.上既不是对称的也不是反对称的关系个数；解：设A表示对称、B表示反对称，则既不是对称的也不是反对称的二元关系为：例2设有集合A，，求A上具有反自反且反对称性的二元关系的数目，并写出计算过程。

解：不妨设，将，看作一个抽屉，，看作一个抽屉，，看作一个抽屉若要获得具有反对称性且反自反性的关系，其中的元素只能在三个抽屉中取且每个抽屉中至多取一个元素，分几种情况：（1）一个也不取，有种取法2）只取一个元素，有种取法3）取二个元素，有种取法4）取三个元素，有种取法故具有反自反性且反对称性的二元关系数目共有1＋6＋12＋8＝27个若，结果又为多少？抽屉数：，每个抽屉有3种选择，故共有个例3 设，是A的幂集上的二元关系且，则不满足下列哪些性质？为什么？（1）自反性；（2）反自反性；（3）对称性；（4）反对称性；（5）传递性解：(1)自反性因为，但，所以，故不是自反的2）反自反性因为，，故，故不是反自反的3）对称性若，则，所以，故，从而是对称的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 举例说明与确实不相等解：设，在上定义小于关系“”，则“不等关系≠”；而“全关系”因此的确不相等例7（）是否存在（）上的一个二元关系R，使得两两不相等解：存在令，即可例8 证明：如果R是对称的，则R＋也是对称的证：证1 ，则，使得于是存在m－1个元素，使得由R的对称性有：于是，从而，即是对称的习 题 课例1 设是整数集上的关系，定义为，则（1）证明：是等价关系；（2）确定的等价类证：（1）因为，有，故，即R是自反的若，即，则，因此，即R是对称的若，，即且，故，即，所以R是传递的由此可知：是上的等价关系2）因为，，所以R的等价类有：例2设是上的一个自反关系，证明：是等价关系若且，则[书上习题]证：是上的等价关系若且，由的对称性有：且，再由的传递性有：R是自反的，故有若，由，有，所以是对称的若且，由的对称性有：且，故由题意得，所以是传递因此，是上的等价关系例3.令，上的两个关系如图3所示，它们是否是等价关系？不是等价关系（因为不传递）是等价关系图3例4 设，是上的等价关系，则也是上的等价关系吗？解：不一定是的等价关系。

因为不一定具有传递性举例：设，，，则因为且，但，故不满足传递性，即不一定是上的等价关系例5设是上如下的二元关系：，当且仅当证明：(1) 等价关系；(2)求等价类数证：(1)等价关系显然；(2)等价类数为：只能取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设是上的一个二元关系，设，使得且证明：若是上的等价关系，则也是上的等价关系；证： 证明若是等价关系，则也是等价关系1）自反性因为是自反的，所以，有根据的定义，有，所以是自反的；（2）对称性：若，则，使得且因为是对称的，所以且，根据的定义有，所以是对称的；(3) 传递性：若，，则，使得且。

因为是传递的，所以且，使得且因为是传递的，所以根据的定义有所以是传递的由（1），（2），（3）可知：是等价关系例9 设是集合A的划分，若，1≤i≤n，证明：是集合的划分证：因为是集合A的划分，故，，i≠j但，当i≠j时，当i＝j时，所以是的划分例10设和是集合上的等价关系，和是由和所诱导产生的划分，证明：当且仅当的每个划分块都包含在的某个划分块中， 分析：只要理解等价关系和划分的概念以及它们之间的一一对应关系，就很容易证明证：令划分, 若，则的每个划分块都包含在的某个划分块中于是，即为中任一划分块，所以在中任取一个元素因为是的划分且，所以存在，使得于是，有，又因为，所以根据划分的定义有，所以由的任意性知，的每一划分块都包含在的某一划分块中必要性若的每个划分块都包含在的某个划分块中，则则在的同一划分块中根据题设，必有在的同一划分块中，故例11设是S上的二元关系，若，证明：是上的等价关系；求等价类证：因为，所以到的映射共有8个，如图2所示图2（1）等价关系显然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）自反性：，有，；因为和分别为和上的自反关系，所以，，故，因此是自反性的；（2）对称性：，若，则，；因为和分别为和上的对称关系，所以有，，从而，因此是对称性的；(3) 传递性：，若且，则有 ，，，；因为和分别为和上的传递关系，所以有，，从而，因此是传递性的综上可知：是上的等价关系例14设是自然数集合，定义上的二元关系：，则 （1）证明是一个等价关系；（2）求关系的等价类；证：（1）自反性：，是偶数，所以有因此是自反的；对称性：若，即是偶数，则是偶数，所以有因此是对称的；传递性：若，，即是偶数，是偶数，则是偶数，所以有因此是传递的 综上可知：是等价关系2）关系的等价类有：3）设， 则所诱导的等价关系就是。

例15 设，A上的二元关系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 在A＝{1,2,3,4,6,8,12,24｝和B＝{2,3,4,8,9,10,11｝上定义的整除关系“|”，画出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)设B＝{b,c｝，求B的上界集合C和上确界；下界集合D和下确界。

a) (b)图2解：1. 的Hasse图如图8(b)所示1. 设B＝{b,c｝，则A中无任意元素“大于”b，也同时“大于”c，故C＝，此时，无上确界，而D＝｛d｝，下确界：d例4 设集合上的偏序关系如图9所示则1.求出A的最大（小）元，极大（小）元2.求出的上界、下界、上确界和下确界x5x4x3x2x1图2解：1.最大元：最小元：无极大元：极小元：，2.令，则上界：下界； 上确界：下确界：令，则上界：，下界：无； 上确界：，下确界：无；令，则上界：，下界：； 上确界：，下确界：例5设集合，上的关系定义如下：则 （1）写出的关系矩阵；（2）验证是偏序集；（3）并画出Hasse图4）若上的关系如下：，则又如何？cebad解：（1）所对应的关系矩阵为为：（2）由关系矩阵可知：对角线上的所有元素全为1，故是自反的； 图10，故是反对称的； 对应的关系矩阵为： 。