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

1习题课例1设X是一个集合，X＝n，求：1.X上的二元关系有多少？22n2.X上的自反的二元关系有多少？3.X上的反自反的二元关系有多少？解：因为把所有的反自反的二元关系的每个都加上对角线上的序对，就变成了自反的关系，因此，自反的与反自反的个数一样多。即22nn4.X上的对称的二元关系有多少？2222nnnnn，故共有222nn个对称的关系。5.X上的反对称的二元关系有多少？22(32)nnn6.X上既是自反的也是反自反的二元关系的个数；(0)个7.X上既不是自反的也不是反自反的二元关系有多少？2(2(22))nnn解：解：可用容斥原理来计算设B表示所有自反关系构成的集合，C表示所有反自反关系构成的集合，则22nnBC。而BC，故BCBC，从而CCBCSBCSBC2222222222222(22)nnnnnnnnnnn于是，既不是自反的，也不是反自反关系共有22(22)nnn个。8.自反的且对称的关系有多少？[此结果与“反自反的且对称的关系有多少？”是一样多]即有222nn（对角线上全去掉）9.自反的或对称的关系有多少？解：设B表示自反关系的集合，C表示对称关系的集合，则自反或对称关系的集合为：22222222nnnnnnBCBCBC。10.X上既是反自反的也是反对称的二元关系的个数为：223nn；211.X上既是对称的也是反对称的关系个数；解：X上既是对称的也是反对称的关系XRI，故有2n。12.X上既不是对称的也不是反对称的关系个数；22222(22232)nnnnnnn解：设A表示对称、B表示反对称，则既不是对称的也不是反对称的二元关系为：||||||||||||||CCABSABSABAB2222222232nnnnnnn例2设有集合A，3A，求A上具有反自反且反对称性的二元关系的数目，并写出计算过程。解：不妨设{,,}Aabc，将(,)ab，(,)ba看作一个抽屉，(,)bc，(,)cb看作一个抽屉，(,)ac，(,)ca看作一个抽屉。若要获得具有反对称性且反自反性的关系，其中的元素只能在三个抽屉中取且每个抽屉中至多取一个元素，分几种情况：（1）一个也不取，有031C种取法。（2）只取一个元素，有1326C种取法。（3）取二个元素，有232212C种取法。（4）取三个元素，有332228C种取法。故具有反自反性且反对称性的二元关系数目共有1＋6＋12＋8＝27个。若An，结果又为多少？抽屉数：22nnA，每个抽屉有3种选择，故共有223nn个。例3设{1,2,3}A，R是A的幂集2,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}A上的二元关系且{(,)|}Rabab，则R不满足下列哪些性质？为什么？（1）自反性；（2）反自反性；（3）对称性；（4）反对称性；（5）传递性。{(,)|}Rabab等价于aRbab(,)abRab。解：(1)自反性。因为2A，但，所以(,)R，故R不是自反的。3（2）反自反性。因为{1}2A，{1}{1}{1}，故({1},{1})R，故R不是反自反的。（3）对称性。,2Axy，若(,)xyR，则xy，所以yx，故(,)yxR，从而R是对称的。（4）反对称性。令{1,2}x，{1,3}y，则{1}xyyx，故(,)xyR且(,)yxR，但xy，所以(,)(,)xyyx，从而R不是反对称的。（5）传递性。令{1}x，{1,2}y，{2}z，则有{1}xy且{2}yz，故(,)xyR且(,)yzR，但xz，故(,)xzR，所以R不是传递的。习题课例1证明：RRRRR，其中0120iiRRRRR证：01223()()RRRRRRRRRtRR；同理可证RRR例2[书上做为定理出现]设R、S是X上的二元关系，则（1），是空关系。（2）()RR证：因为R是传递的，故()RR。（3）()RSRS证：因为RSR且RSS，故()RSR，且()RSS，从而()RSRS例3如图5所示给出下图中每个关系的自反、对称和传递闭包。4··（a）（b）（c）图5（1）自反闭包（2）对称闭包（3）传递闭包例4设R是集合A上的反对称关系，则t(R)一定是反对称的吗？证：t(R)在A上不一定是反对称的。例：{,,,}Aabcd，{(,),(,),(,),(,)}Rabbccdda则R的传递闭包为：(){(,),(,),(,),(,),(,),tRabbccddaac(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),(,)}addcddcabddbbacbaabbcct(R)是全关系，故t(R)不是反对称的而是对称的。例5举例说明(())stR与(())tsR确实不相等。解：设{1,2,3,}N，在N上定义小于关系“”，则(())()sts“不等关系≠”；5而(())()tst“全关系”。因此的确不相等。例7（898P）是否存在X（Xn）上的一个二元关系R，使得2,,,nRRR两两不相等。解：存在。令{1,2,3,,}Xn，{(1,2),(2,3),,(1,)}Rnn即可。例8证明：如果R是对称的，则R＋也是对称的。证：证11(,)iixyRR，则mN，使得(,)mxyR。于是存在m－1个元素121,,,myyy，使得1112211(,),(,),,(,),(,)mmmxyRyyRyyRyyR。由R的对称性有：112211(,),(,),,(,),(,)mmmyyRyyRyyRyxR。于是(,)myxR，从而1(,)iiyxRR，即1iiRR是对称的。习题课例1设R是整数集I上的关系，mRn定义为22mn，则（1）证明：R是等价关系；（2）确定R的等价类。证：（1）因为mI，有22mm，故mRm，即R是自反的。,mnI，若mRn，即22mn，则22nm，因此nRm，即R是对称的。,,mnkI，若mRn，nRk，即22mn且22nk，故22mk，即mRk，所以R是传递的。由此可知：R是I上的等价关系。（2）因为iI，[]{,}Riii，所以R的等价类有：{[0],[1],[2],}RRR。例2设R是A上的一个自反关系，证明：R是等价关系若(,)abR且(,)acR，则(,)bcR。[书上习题]证：R是A上的等价关系。6是等价关系不是等价关系（因为不传递）若(,)abR且(,)acR，由R的对称性有：(,)baR且(,)acR，再由R的传递性有：(,)bcRR是自反的，故aA有(,)aaR。若(,)abR，由(,)aaR，有(,)baR，所以R是对称的。若(,)abR且(,)bcR，由R的对称性有：(,)baR且(,)bcR，故由题意得(,)acR，所以R是传递。因此，R是A上的等价关系。例3.令{1,2,3}A，A上的两个关系如图3所示，它们是否是等价关系？132231图3例4设1R，2R是A上的等价关系，则12RR也是A上的等价关系吗？解：12RR不一定是A的等价关系。因为12RR不一定具有传递性。举例：设{,,}Aabc，1{(,),(,),(,),(,),(,)}Raabbccabba，2{(,),(,),(,),(,),(,)}Raabbccbccb，则12{(,),(,),(,),(,),(,),(,),(,)}RRaabbccabbabccb因为12(,)abRR且12(,)bcRR，但12(,)acRR，故12RR不满足传递性，即12RR不一定是A上的等价关系。例5设{1,2,,},XnSXX。“”是S上如下的二元关系：(,),(,)ijklS，(,)(,)ijkl当且仅当ijkl。证明：(1)等价关系；(2)求等价类数。证：(1)等价关系显然；7(2)等价类数为：21n。ij只能取2，3，…，2n，故等价类数有21n个。例6设R是A上的对称和传递的关系。若对A中每个a，bA，使得(,)abR，证明：R是A上的等价关系。证：aA，bA，使得(,)abR。由R的对称性有：(,)baR。再由R的传递性有：(,)aaR。由a的任意性可知，R是A上的自反关系，故R是A上的等价关系。例7设R是集合A上的一个自反的和传递的关系；T是A上的一个关系，使得(,)(,)abTabR且(,)baR。证明：T是A上的等价关系。证：（1）因为R是A上的自反关系，所以aA，有(,)aaR，故由T的定义有：(,)aaT，即T是A上的自反关系。（2）若(,)abT，由题设：(,)abR且(,)baR。显然，(,)baT，即T是A上的对称关系。（3）若(,)abT且(,)bcT，由题设可知：(,)abR，(,)baR且(,)bcR，(,)cbR。由R传递性得：(,)acR且(,)caR，故(,)acT，所以T是A上的传递关系。由（1），（2），（3）即得T是A上的等价关系。例8设R是A上的一个二元关系，设{(,)|SabcA，使得(,)acR且(,)cb}R。证明：若R是A上的等价关系，则S也是A上的等价关系；证：证明若R是等价关系，则S也是等价关系。（1）自反性因为R是自反的，所以aA，有(,)aaR。根据S的定义，有(,)aaS，所以S是自反的；（2）对称性：若(,)abS，则cA，使得,acR且,cbR。因为R是对称的，所以,bcR且,caR，根据S的定义有,baS，所以S是对称的；8(3)传递性：若,abS，,bcS，则dA，使得,adR且,dbR。因为R是传递的，所以,abR。且eA，使得,beR且,ecR。因为R是传递的，所以,bcR。根据S的定义有,acS。所以S是传递的。由（1），（2），（3）可知：S是等价关系。例9设12{,,,}nAAA是集合A的划分，若iAB，1≤i≤n，证明：12{,,,}nABABAB是集合AB的划分。证：因为12{,,,}nAAA是集合A的划分，故1niiAA，ijAA，i≠j。但11()nniiiiABABAB，当i≠j时，()()ijABAB。当i＝j时，()()ijiABABAB。所以12{,,,}nABABAB是AB的划分。例10设1R和2R是集合X上的等价关系，1C和2C是由1R和2R所诱导产生的划分，证明：当且仅当1C的每个划分块都包含在2C的某个划分块中，12RR。分析：只要理解等价关系和划分的概念以及它们之间的一一对应关系，就很容易证明。证：令划分112,,,,kCAAA,212,,,,eCBBB。充分性。若12RR，则1C的每个划分块都包含在2C的某个划分块中。于是1kAC，即kA为1C中任一划分块，所以kA。在kA中任取一个元素kaA。因为2C是X的划分且aX，所以存在2eBC，使得eaB。于是kbA，有1(,)abR，又因为12RR，所以2(,)abR。9根据划分的定义有bBe，所以kABe。由kA的任意性知，1C的每一划分块都包含在2C的某一划分块中。必要性若1C的每个划分块都包含在2C的某个划分块中，则12RR。1(,)abR，则,ab在1C的同一划分块中。根据题设，必有,ab在2C的同一划分块中，故2(,)abR。因此12RR。例111,