已知集合A{a.doc

第四章 关系习题4.11. 已知集合A=a, b,a,b，B=1, 2，求笛卡尔积AB，BA，B B，B3。解 AB=(a,1),(a,2),(b,1),(b,2),(a,b,1),(a,b,2)，BA=(1,a), (1,b), (1, a,b),(2, a), (2, b), (2, a,b)，B B=(1,2),(1,2),(2,1),(2,2) ，B3=(1,1,1),(1,1,2),(1,2,1),(1,2,2), (2,1,1),(2,1,2),(2,2,1),(2,2,2) 。2. 设A=x, y，求集合P(A)A。解 P(A)=, x, y, x, y，因此，P(A)A=, , , , , , , 。3. 设A、B、C、D是任意集合，判断下列命题是否正确？AB=ACB=C；(AB)C=(ACBC)；存在集合A使得AAA。解 不正确。例如令A=，B=1，2，C=x，则AB=AC=正确。因为， (A-B)Cx(A-B)yCxAxByCxAyCxByCACBC(AC-BC) 。所以，(A-B)C(AC-BC) 。又因为，(AC-BC)ACBC (xAyC)(xByC)(xByC) (xByC) xA(xByC) (xAxB)yC x(A-B)yC (A-B)C。所以，(AC-BC)(A-B)C。综上所述，(AB)C=(ACBC)。正确。例如A=，AA=，显然AAA。但是当A时，因为AA是由集合A中的两个元素的序偶组成的集合，所以AAA一般不成立。4. 设任意三个集合A、B、C，求证(1)A(BC)=(AB)(AC)； (2)(BC)A=(BA)(CA)。证明 (1)A(BC)(xAy(BC)(xA(yByC)(xAyB)(xAyC)(AB) (AC)(AB) (AC)因此A(BC)=(AB)(AC)。同理可证(2)。5.设A、B、C、D为任意集合，证明(AC)(BD)(AB)(CD)成立。若AA=BB，则A=B成立。证明 (AC)(BD)(AC)(BD)(AC)(BD)(xAyC)(xByD)(xAxB)(xAyD)(yCxB)(yCyD)(xAxB)(yCyD)x(AB)y(CD)(AB)(CD)。因此，(AC)(BD)(AB)(CD)。设xA，若AA，而AA=BB，所以，BB，即xB，因此AB；同理可证BA；故A=B。习题4.21.写出从集合A=1, 2, 3到集合B=a的所有关系。解 因为，AB=(1, a), (2, a) ,(3, a)，所以，R1=、R2=、R3=、R4=、R5=, 、R6=, 、R7=, 、R8=, , 。2.用L和D分别表示集合A=1, 2, 3, 4, 8, 9上的普通的大于等于关系和整除关系，即L=|(xy)(x, yA)，D=|(x整除y)(x, yA)，试列出L，D和LD，LD，L-D中的所有有序对。解 L=, , , , , , , , , , , , , , , , , , , , ；D=, , , , , , , , , , , , , , LD=, , , , , LD=, , , , , , , , , , , , , , , , , , , , , , , , , , , , L-D=, , , , , , , , , , , , , , 3.已知X=a, b, c，Y=a, d，求XY上的全域关系和恒等关系。解 XY=a, b, c, d，则XY上的全域关系U、恒等关系I分别为U=, , , , , , , , , , , , , , , ；I=, , , 。4.设P=, , , 和Q= , ,，求PQ，PQ，domP，ranP，domQ，ranQ，dom(PQ)，ran(PQ)。解 PQ=, ；PQ=, , , , ；domP=1, 2, 4，ranP=2, 3, 4；domQ=1, 2, 4，ranQ=2, 3；dom(PQ)=1, 2, 4，ran(PQ)=2, 3, 4。5. 设R1和R2都是从集合A到集合B的二元关系，证明：(1)dom(R1R2)=domR1domR2；(2)ran(R1R2)ranR1ranR2证明 (1)对于任意元素xA，xdom(R1R2)$y(R1R2)$y(R1R2)xdom(R1)xdom(R2)x(dom(R1)dom(R2)故dom(R1R2)=domR1domR2(2)对于任意元素yByran(R1R2)$x(R1R2)$x(R1R2)$x(R1)$x (R2) yranR1yranR2y(ranR1ranR2)。故ran(R1R2)ranR1ranR26. 设A=0, 1, 2, 4, 6, 8，B=1, 2, 3，用列举法表示下列A到B关系，并给出关系图及关系矩阵：R1=| xAByAB AB；R2=|xAyBx+y=5 AB；R3=|xAyA($k)(x=k*ykNk2) A A；R4=|xAyBx和y互素 AB。解 R1=, , , ；R2=, ；R3=, , , , , , ,；R4=, , ,，。关系图如下：012468123R1R2012468123012468R3012468012468123R4图4-1习题4.31. 设集合1, 2, 3, 4上的二元关系R1和R2为R1=, , , ，R2=, , ，试求R1R2，R2R1，R12和R22。解 从关系复合的定义来求：R1R2=, , , ；R2R1=, ；R12=R1R1=, , , ；R22=R2R2=, , 。2. 设R1为从集合A到集合B的二元关系，R2为从集合B到集合C的二元关系，试求dom(R1R2)、ran(R1R2)与集合A、B、C。解 dom(R1R2)A；ran(R1R2)C。3. 设A=1, 2, 3上的关系R1=|i-j是偶数或i=2*j或i=j-1，R2=|i=j+2，(1)利用定义求R1，R2，R1R2，R1R2R1，R1-1；(2)利用矩阵求解R1R2，R1R2R1，R1-1，给出对应的关系矩阵；(3) 给出R1，R2，R1R2，R1R2R1，R1-1的关系图。解 (1)利用定义求解，R1=, ,；R2=；R1R2=, ,；R1R2R1=, , ；R1-1=, , ；(2)利用矩阵求解， ；。关系图如图4-2：123 R2123 R1R2R1R2R1123R1 123 R1-1123图4-24.设A=1, 2, 3, 4, 5，R=, , , , ，试找出最小的正整数m和n，使mn且Rm=Rn。解 R=, , , , ，R2=, , , , ,，R3=, , , , ，R4=, , , , ，R5=, , , , ，R6=, , , , ，R7=, , , , = R1。所以，m=1、n=7可使得R1=R7。5.集合A=1, 2, 3, 4, 5上的关系R=, , , , , , , ，求，nN。解 =，因此，一般地，。6设A,B是集合，R,S是A到B的关系，证明下列各题：(R-S)-1=R-1-S-1；(AB)-1=BA；-1=；RSR-1S-1。证明 对于任意的(R-S)-1，则R-S，所以，R，但S，因此，再由逆关系的定义有，R-1，而S-1，故R-1-S-1。即(R-S)-1R-1-S-1。同理可证R-1-S-1(R-S)-1。综合可得(R-S)-1=R-1-S-1。由集合的笛卡尔积和逆关系的定义，因为，对于任意的aA,bB都有，BA，则AB，所以，(AB)-1，即BA(AB)-1，另一方面，因为，对于任意的aA,bB都有，(AB)-1，所以，则AB，所以，BA，即(AB)-1BA。综合上述有，(AB)-1=BA。用反证法证明-1=，假设存在aA,bB使得，-1，则，这与是空集矛盾。先证明RSR-1S-1。对于任意的aA,bB，若R-1，由逆关系的定义则R，而RS，所以，S，因此，S-1，即R-1S-1。再证明R-1S-1RS。若R，则R-1，而R-1S-1，所以， S-1，因此，S，即RS。习题4.41.设R1，R2，R3，R4都是整数集上的关系，且xR1yxy0,xR2y|x-y|=1，xR3yx-y=5，用Y(yes)和N(no)填写表4-1。关系自反的反自反的对称的反对称的传递的R1R2R3表4-1解 如表4-2关系自反的反自反的对称的反对称的传递的R1NNYNYR2NYYNNR3NY表4-2NYN2.设整数集I中，任意两个元素x、y之间有关系R，xRyx(x-1)=y(y-1)，问R是否具有自反性、反自反性、对称性、反对称性和传递性？解 R具有自反性，因为对于任意的xI，x(x-1)=x(x-1)，即R，所以R具有自反性；因为R具有自反性，所以R不具有反自反性；R具有对称性，因为对于任意的x, yI ，若R，则x(x-1)=y(y-1)，所以y(y-1)=x(x-1)，即R，因此R具有对称性；显然R不具有反对称性；R具有传递性，设R，R，即x(x-1)=y(y-1)，y(y-1)=z(z-1)，显然有x(x-1) =z(z-1)，即R，所以R具有传递性。3.设集合A=0, 1, 2, 4的关系R=xyA ，画出R的关系图；R是否具有自反性、反自反性、对称性、反对称性和传递性？解 (1)R=, , , , , 102004图4-3, , , , , , , ，关系图如图4-3。R具有对称性。4.设R为非空有限集合A上的二元关系，如果R是反对称的，则RR-1的关系矩阵MRR-1中最多能有几个元素为1？解 若A上关系R是反对称的，则RR-1关系矩阵MRR-1中最多只有主对角线上有非零值，即最多只有|A|个非零值。5.设集合A=1, 2, 3，求：(1)在其上定义一个既不是自反的也不是反自反的关系；(2)在其上定义一个既不是对称的也不是反对称的关系；(3)在其上定义一个既是对称的也是反对称的关系；(4)在其上定义一个是传递的关系。解 答案可以有很多组，下面给出一组答案如下。(1)R=；(2)R=, , ；(3)R=, ；(4)R=, , 。6.设R1，R2为集合A上的自反关系，证明R1R2也是A上的自反关系。证明 因为，R1，R2为集合A上的自反关系，则对于任意的xA，有 R1，且R2，因此，R1R2，故R1R2是A上的自反关系。习题4.51.设R1=,，R2=, , , 都是集合上A=a, b, c的二元关系，求出各自的自反闭包，对称闭包和传递闭包（用有序对形式给出），并给出各闭包的关系矩阵和关系图。解 r(R1)=R1IA=, , , ,；s(R1)=R1=, , , ；t(R1)=, , ；r(R2)=R2IA=, , , s(R2)=R2=, , , , t(R2)=, , , 关系矩阵如下：，。关系图如图4-4：a cR1R2r(R1)s(R1)t(R1)r(R2)s(R2)t(R2)图4-4b a cb a cb a cb a cb a cb a cb a cb 2.已知集合1, 2, 3上的关系R，R=, , , , 求下列关系的关系矩阵, (1)r(R), (2)s(R), (3)t(R), (4)rs(R), (5)sr(R)。解 ，则；，；。3.设R1，R2为A上关系，R1R2，求证：r(R1)r(R2)；s(R1)s(R2)；t(R1)t(R2)。证明 因为，R1R2，所以，IAR1IAR2，即r(R1)r(R2)。因为，R1R2，由习题4.3第6题可得，所以，即s(R1)s(R2)。因为，R1R2，所以，则，即t(R1)t(R2)。4.设R1，R2为集合A上的关系，证明r(R1R2)=r(R1)r(R2)；s(R1R2)=s(R1)s(R2)；t(R1)t(R2)t(R1R2)。证明 由自反闭包的定义又r(R1)= IAR1IAR1R2= r(R1R2)，同理有r(R2)= IAR2IAR1R2= r(R1R2)，所以有r(R1)r(R2) r(R1R2)；另一方面，下面分两种情况来证明。如果a=b，则IA，所以；如果ab，则，因此，若，则，所以，同理，若，则，所以，。故r(R1R2) r(R1)r(R2)。综上所述，r(R1R2)=r(R1)r(R2)。因为R1R1R2，且R2R1R2，所以由第3题有s(R1)s(R1R2) ，且s(R2)s(R1R2)，因此，s(R1)s(R2)s(R1R2)；另一方面，则或，若，则或，所以，或，因此，；若，则，所以，或，因此，或，所以，或，因此，。故s(R1R2) s(R1)s(R2)。综上所述，s(R1R2)=s(R1)s(R2)。对于任取的 t(R1)t(R2)，则 t(R1)或t(R2)。若 t(R1)，则存在正整数m使得，因此，所以， t(R1R2)；同理若t(R2)，可证 t(R1R2)。综上所述，t(R1)t(R2)t(R1R2)。5.给出一个二元关系R使st(R)ts(R)。解 R=是集合A=x, y上的二元关系，则st(R)=, ，而ts(R)=, , , 。因此st(R)ts(R)。6.证明定理4的(2)（设R为集合A上的二元关系，则rt(R)=tr(R)）。证明 rt(R)=r(RR2Rn)= IARR2Rn=( IAR)(IAR2)(IARn)( IAR)(IAR)2(IAR)n=tr(R)。反之，对于任意的tr(R)，则存在正整数n，使得(IAR)n，即IARR2Rn，亦即 rt(R)，所以，tr(R)rt(R)。综上所述，tr(R)=rt(R)。习题4.61.设A=1, 2, 3, 4，问A上共有多少个等价关系?解 A上共有15个等价关系。由等价关系和划分是一一对应关系，而A共有如下的15个划分：p1=1,2,3,4，p2=1,1,2,3,4，p3=2,1,3,4，p4=3,1,2,4，p5=4,1,2,3，p6=1,2,3,4，p7=1,3,2, 4，p8=1,4, 2,3，p9=1,2,3,4，p10=1,3,2,4，p11=1,4,2,3，p12=2,3,1, 4，p13=2, 4,1,3，p14=3,4,1,2，p15=1,2,3,4。与每个划分对应的等价关系由读者自行给出。2. 设R是集合A上的对称关系和传递关系，求证：若对每个元素aA，存在一个元素bA，使R，则R是等价关系。证明 要证明R是A上的等价关系，只需证明R是A上的自反关系。事实上，因为，aA，总存在一个元素bA，使R，而R是集合A中的对称关系，所以R，又因为R是A上的传递关系，有R且R时，可得R，即R是集合A中的自反关系。故R是等价关系。3. 集合A=a, b, c, d, e上的划分为S，S=a, d, e, b, c，写出由划分S导出的A上的等价关系R。画出R的关系图，并求MR。解 R=a, d, ea, d, eb, cb, c=, , , , , , , , , 关系图如图4-5abdec图4-5。4. R1和R2都是集合A上的等价关系，试判断下列A上的二元关系是不是A上的等价关系。若不是，请给出反例。A2-R1；R1-R2；r(R1-R2)； R1R2；R1R2。解 不是等价关系。例如设A=1,2,3，R1=,，而显然A2-R1=,不是等价关系；不是等价关系。例如A=1,2,3，R1=,，R2=,，而显然R1-R2=,不是等价关系；不是等价关系，令A=1, 2, 3，R1=, , , , , , , , ，R2=, , , , R1-R2=, , , ，r(R1-R2)=(R1-R2)IA=, , , , , , ，因为R1-R2，R1-R2，但R1-R2，显然R1-R2不具有传递性，所以R1-R2不是等价关系。(4)不是等价关系，令A=1, 2, 3，R1=, , , , ，R2=, , , , ，R1R2=, , , , , , , ，因为R1R2，但R1R2，所以R1R2不是等价关系。(5)不是等价关系，令A=1, 2, 3，R1=, , , , ，R2=, , , , R1R2=, , , , , , ，因为R1，R2，但R1R2，显然R1R2不具有传递性，所以R1R2不是等价关系。5. 设p1和p2都是集合A的划分，试判断下列集合是不是A的划分，为什么？(1)p1p2；(2)p1p2；(3)p1-p2；(4)(p1(p2p1)p1。解 若p1=p2，则p1p2是集合A的划分，其它情况p1p2不是集合A的划分；例如设A=1,2,3，p1=1,2,3,p2=1,2,3，而p1p2=1,1,2,2,3,3不是划分。若p1=p2，则p1p2是集合A的划分，其它情况p1p2不是集合A的划分，例如设A=1,2,3，p1=1,2,3,p2=1,2,3，而p1p2=1不是集合A的划分；若p1p2=，则p1-p2是集合A的划分，其它情况p1-p2不是集合A的划分，例如设A=1,2,3，p1=1,2,3,p2=1,2,3，而p1-p2=2,3不是集合A的划分； 因为(p1(p2p1)p1=p1，所以(p1(p2p1)p1是集合A的划分。6. R是整数集合I上的关系，R=|x2=y2(1)证明R是等价关系；(2)确定R的等价类。证明 (1)对任意的xI，x2=x2，即R，所以R是自反的；对任意的R，即x2=y2，则y2=x2，即R，所以R是对称的；对任意的R，R,即x2=y2，y2=z2，显然x2=z2，亦即R，所以R是传递的；综合、可知R是等价关系。(2)R的等价类可以分为0, 1, 2, ,其中 0=0，1=-1=1, -1，2=-2=2, -2，n=-n=n, -n，。习题4.71.设R是X上的二元关系，试证明R=IXRR-1是X上的相容关系。证明 (1)自反性。因为对任意的xX，IX，所以IXRR-1=R，即R是自反的；(2)对称性。对于任意的IXRR-1，且xy，显然RR-1，则R，或R-1，因此，R-1，或R，从而有RR-1，所以IXRR-1=R，即R是对称的；综上所述，R是X上的相容关系。2.设集合A=1,2,3,4,5,6，R=, , , , , , , , , , , , , , , , , , , ，证明R是A上的相容关系，给出R的关系矩阵和简化关系图，求R的最大相容类。证明 (1)对任意的xA，有R，所以R是自反的；(2) 设任意的R，且xy，都有R，即R是对称的；综上所述，R是A上的相容关系。R的关系矩阵如下，关系图如图4-6：，1 2 34 5 6图4-6最大相容类为：1,2,3,2,3,4,2,4,5,6。习题4.81.设集合X=1, 2, 3, 4, 5上的二元关系为：R=, , , , , , , ，, , , , ，验证是偏序集，并画出哈斯图。解 从R的定义中，显见R具有自反性、反对称性、传递性，所以R是A上的偏序关系，即是偏序集。COVA=, , , , 2.如图4-8所示，为一偏序集的哈斯图，(1)下列命题哪些为真?aRb，dRa，cRd，cRb，bRc， aRa，eRa；(2)给出R的关系图；(3)指出A的最大元，最小元(如果有的话)，极大元，极小元；(4)求出集合A及其子集B1=c, d, e，B2=b, c, d，B3=a, c, d, e的上界，下界，上确界，下确界(如果有的话)。解 (1)从哈斯图可以看出，dRa，aRa，eRa(2)R的关系图如图4-9：(3)A的最大元为a，无最小元，极大元为a，极小元为d，e；(4)出集合A及其子集B1=c, d, e，B2=b, c,d，B3=a, c, d, e的上界，下界，上确界，下确界如表1。24513图4-7abecd图4-8abcde图4-9上界下界上确界下确界A=a, b, c, d, ea无a无B1=c, d, ec, a无c无B2=b, c, dadadB3=a, c, d, ea无a无表13.填写表2，区分偏序集的子集B上的最大(小)元，极大(小)元，上(下)界，上(下)确界。b是B的定 义bB否存在性唯一性最大元素bB且b大于B中其它每个元素是不一定存在存在则唯一最小元素bB且b小于B中其它每个元素是不一定存在存在则唯一极大元素bB且b不小于B中其它每个元素是不一定存在不一定唯一极小元素bB且b不大于B中其它每个元素是不一定存在不一定唯一上界bA且b大于B中每个元素不一定不一定存在不一定唯一下界bA且b小于B中每个元素不一定不一定存在不一定唯一上确界B的上界中的最小者不一定不一定存在存在则唯一下确界B的下界中的最大者不一定不一定存在存在则唯一表24.下列集合中哪些是偏序集、拟序集、全序集、良序集？ ；。解 是偏序集，不是其它集合；是拟序集，不是其它集合；是偏序集、全序集、良序集，不是拟序集；是偏序集、全序集、良序集，不是拟序集；复习题四1.设A、B、C是非空集合，证明：AB=ACB=C。证明 对于任意的bB，因为A非空，所以存在aA，且AB，因为AB=AC，所以AC，从而bC，因此BC。同理可证CB。故B=C。2.设A、B、C是集合，IA是A上的恒等关系。证明：若RAB，则IAR=R。证明 利用集合相等的定义去证，即分别证明IARR，RIAR；对于任意的IAR，必存在z，满足IA，R，而IAx=z，所以R，即IARR；对于任意的R，因为IA，所以IAR，即RIAR；综上所述，IAR=R。*3.设A是含有n个元素的有限集。分别求A上不相同的自反关系、反自反关系、既对称又反对称关系的总个数。解 (1)共有2n(n-1)个A上的不相同的自反关系；(2)共有2n(n-1)个A上的不相同的反自反关系；(3)共有2n(n+1)/2个A上的不相同的对称关系；(4)共有2n2n(n-1)/2个A上的不相同的反对称关系；(5)共有2n个A上不相同的既是对称又反对称的关系。4.设A=1, 2, 3，R是P(A)上的二元关系，且R=|ab。则R不满足下列哪些性质，为什么？自反性；反自反性；对称性；反对称性；传递性。解 R不具有自反性，因为 (A)，但=，所以R，故R不具有自反性。R不具有反自反性，因为1P(A)且11=1，所以R，故R不具有反自反性。R具有对称性，x,yP (A)，若R，则xy，所以yx，因此R，故R具有对称性。R不具有反对称性，设x=1, 2，y=1, 3，则xy=yx=1，由R的定义易知，R且R，但xy，故R不具有反对称性。R不具有传递性，设x=1，y=1, 2，z=2，则有xy=1且yz=2，所以R且R，但xz=，所以R，故R不具有传递性。5.设R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当，和在R之中，并有R。证明 设R是集合X上的一个自反关系，如果R是X上对称和传递的，则对于任意a,b,cX，若有RR，则RR，故得 R反之，若R，R，必有R，则对任意a,bX，若R，而因为R是自反关系，所以R)，故R，即R是对称的。若RR，则RR，所以R，即R是可传递的。6. 证明：设R是集合A上的一个任意关系，证明下列各式：(1)(R+)+=R+；(2)RR*=R+=R*R；(3)(R*)*=R*；其中，R+=t(R)，R*=rt(R)证明 (1)因为R+=t(R)是传递的，所以，(R+)+=t(R+)=t(t(R)=t(R)=R+(2)因为R*=IAR+=IA(RR2R3)RR*=R(IA(RR2R3)=RIARRRR2=RR2R3=R+同理可证，R*R=R+。(3)(R*)*=(R*)+IA=t(R*)IA=R*IA(因为R*是传递的)=R*7.设A和B均为非空集合，R1和R2分别为A和B上的等价关系，设