集合与二元关系

集合与关系部分习题参考答案习题三(1)假(2)真(3)真(4)真(5)假(6)假(7)假(8)真(9)假(10)真(1)AUg={1,2,3,5,7,9,11}AHC={3}(AUB)CC={1,5,7,9,11}A—B={1,9}C—D ={3,6,12}B©D={3,4,5,7,8,11}(1)AUB={1,2,3,5,7,9,11} (2)ACC={3} (3)(AUB)CC={1,5,7,9,11}(4)A—B={1,9} (5)C—D={3,6,12} (6)B®D={3,4,5,7,8,11}3.4⑴如下图AA(2)cc(4)3.5P(A)=(0,{°}}p(a)={0,{{1}},{1},{{1},1}}p(a)={0,{0},{{1}},{{2}},{{1,2}},{0,{1}},{0,{2}},{0,{1,2}},{{1},{2}},{{1},{1,2}},{{2},{1,2}},{0,{1},{2}},{0,{1},{1,2}},{0,{2},{1,2}},{{1},{2},{1,2}},A}(4)P(a)={0,{{1,1}},{{2,1}},{1,2,1},{{1,1},{2,1}},{{1,1},{1,2,1}},{{2,1},{1,2,1}},A}3.6 原式=((AU(B-C))nA)U(B-(B~A))=AU(AnB)=A3.7假。例如，A={1,2},B={1,3},C={2,3}不成立假。例如，A=0,B={1},C={2}不成立3.8证明(AUC)-(BUC)=A-B-C。(原题有误，右式少了C)证明：(auc)-(buc)=(auc)nB—C=(auc)n时c=(“uc)nc)nb=ancnb—A-B-C3.9(AnB)-C=AA(B-C),左式=anbnc=an(bnc)=an(b-c)=右式AU(B-A)=AUB,左式=au(bna)=(aub)n(aua)=(aub)nE)=AuB=右式A-(A-B)=AnB,左式=an(anb)=(an(aub)=(ana)u(anb)=anb=右式A-(B-C)=(A-B)U(AnC),左式=an(bnc)=(an(buc)=(anb)u(anc)=右式(AUB)-C=(A-C)U(B-C),左式=(AuB)nC)=(AnC)u(BuC)=(A-C)u(B-C)=右式AUB=AU(BU(AnB))。右式=Bu(Au(anB))=BuA=右式 (吸收律)3.10设|A1=3,1P(B)1=64,1P(AuB)1=256。求IB1,1AnBI,IA—B1,1A㊉BI。解.IBI=6,IAnBI=1,IA-BI=2,IA㊉BI=7。3.11解：假设会英、日、德和法语的人分别为A,B,C,D,则IAI=13,IBI=5,ICI=10,IDI=9,ianBi=2,Anc\=IAnD\=IcnD\=4,ibnc\=IBnD\=0,因b只与a相交，所以集合关系图如下，可知：只会日语的为IBI-IAnBI=5-2=3，根据图可计算:IAUCUD1=24-3=21,根据容斥原理：IAUCUDI=IAI+IDI+ICI-IAnC\-AnD\-ICCD\+IAnCnD\可知会三种语言的有：IAncnD\=21-32+4+4+4=1人只会英语的：|A|-|AnB|-\AnC\-\AnD\+IAncnD|=13-2-4-4+1=4人只会德语的：|c|-|Dnc|-|Anc|+|AncnD|=i0-4-4+i=3人只会法语的：|D|-|Dnc|-|AnD|+|AnCnD|=9-4-4+1=2人只会日语的：IBI-IAnBI=5-2=3人。习题四设A={a,b}，求P(A)xA={<中,a>,<中，b>,<{a},a>,<{a},b>,<{b},a>,<{b},b>,<{a,b},a>,<{a,b},b>}设AB为集合，IAI=〃,IBI=m。问A到B的二元关系共多少个？2nm问A上二元关系共多少个？2n4.3列出下列二元关系R的所有元素：A={0,1,2},B={0,2,4},R={vx,y>Ix,y^AAB}；R={<0,0>,<0,2>,<2,0>,<2,2>}A={1,2,3,4,5},B={1,2},R={<x,y>\2<x+y<4且x次且yEB}；R={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>}A={1,2,3},B={-3,-2,-1,0,1},R={<x,y>Ix^A,y^B且IxI=IyI}；R={<1,1>,<1,-1>,<2,2>,<2,-2>,<3,3>,<3,-3>}4.4列出所有从X={a,b,c}到丫={d}的关系。XXY={<a,d>,<b,d>,<c,d>},XXY的所有子集为X到Y的关系，有8个，分别是:R1=中,R2={<a,d>},R3={<b,d>},R4={<c,d>},R5={<a,d>,<b,d>},R6={<a,d>,<c,d>},R7={<b,d>,<c,d>},R8={va,d>,vb,d>,vc,d>}。4.5设A={0,1,2,3,4,5},B={1,2,3}，用列举法描述下列关系，并作出它们的关系图及关系矩阵：R1={<x,y>\x^A^B且y^AAB}人］={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}R2={<x,y>\x^A,y油且x=y2}R2={<1,1>,<4,2>}R3={<x,y>Lx^A,y次且x+y=5}R3={<0,5>,<1,4>,<2,3>,<3,2>,<4,1>,<5,0>}R4={<x,y>Lx^A,y次且x=ky,kWN,k<2}R4={<0,0>,<0,1>,<0,2>,<0,3>,<0,4>,<0,5>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}4.6设P={<1,2>,<2,4>,<3,3>}和Q={<1,3>,<2,4>,<4,2>},计算PUQ,PAQ,domP,domQ,ranP,ranQ,dom(PAQ),ran(PAQ)。解：PUQ={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>},PAQ={<2,4>},domP={1,2,3},domQ={1,2,4},ranP={2,3,4},ranQ={2,3,4},dom(PAQ)={2},ran(PAQ)={4}。4.7设P={1,2,3},图4-10给出了P上的5个关系R］、R2、R3、R4、R5,判断它们具有哪些性质?R1：自反性； R2：反对称；R3：反自反，对称；R4：反对称，传递；日5：自反,对称，反对称，传递。4.8设A为一集合，A\=n，试计算A上有多少种不同的自反的(反自反的)二元关系？自反和反自反都是22，，2-n种A上有多少种不同的对称的二元关系？22nA上有多少种不同的反对称的二元关系？2n-3n4.9设A={Q,b,c,d}，A上二元关系鸟，R2分别为R={<b，b>，<b，c>，<c，a>}S={<b，a>，<c，a>，<c，d>，<d，c>}计算R。S，S。R，R2，S2。解：R。S={<d，a>}，S。R={<b,a>，<b,d>}，R2={<b，a>，<b，b>，<b，c>}，S2={vc，c>，vd，d>，vd，a>}4.10设R]和R2是A上任意关系，判断以下命题的真假并说明理由。若R1和R2是自反的，则R]°R2也是自反的；真；若R1和R2是反自反的，则R1°R2也是反自反的；假；例如：R1={<1，2>}，R2={<2，1>}，则R1。R2={<2,2>}，不是反自反。若R1和R2是对称的，则R1°R2也是对称的；假；例如：R1={<1,2>，<2,1>}，R2={<1,3>,<3,1>}，则R1。R2={<3,2>},不是对称。若R1和R2是传递的，则R1oR2也是传递的。假；设集合A={a,b,c}，当R]={(a,b),(b,c),(a,c)}，R2={(b,c),(c,a),(b,a)}，R1和R2都是传递的.但是，由R。R={(a,a), (a, c), (b,a)}得(b, a)E R。R, (a, c)ER。R1，且(b,c)wR。R1，故R。R1不是传递的。4.11设A={1,2,3,4,5}，A上关系R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>，<1,3>}。试求R。S的关系矩阵。M=MXMR。SSR一00100--01000--00010000010100000000=10000X00010=010000100000000010000000000000000004.12设R是集合A={a,b,c,d}上的二兀关系，已知R={<a,b>,<b,c>,<c,d>,<d,a>}，求R2,R-1。R2={<a,c>,<b,d>,<c,a>,<d,b>}RT={<b,a>,<c,b>,<d,c>,<a,d>}求r(R)，s(R)，t(R)。r(R)={<a,a>,<b,b>,<c,c>,<d,d>,<a,b>,<b,c>,<c,d>,<d,a>}s(R)={<a,b>,<b,c>,<c,d>,<d,a>,<b,a>,<c,b>,<d,c>,<a,d>}，t(R)=AXA(因为R的关系图为回路a-b-c-d-a,所以每个点都可以到达任意点,所以其传递关系为全域关系)4.13设R是集合X上的二元关系，对任意x，x，x以，每当</,x>ER,<x,x>ER时，ijk ij jk必有<xk，x?6，则称R是循环的。试证：R是等价关系，当且仅当R是自反和循环的。证：必要性：设R为等价关系，故R是自反，对称，传递的。若xRy，yRz，由R传递有xRz，由R对称有zRx，所以R是循环的。故R为等价关系时R是自反的和循环的；充分性：设R是自反的和循环的，若xRy,由R自反有yRy,从而由R循环有yRx,故R是对称的。若xRy,yRz，由R循环有zRx，从而由R对称有xRz，因此R是传递的。故R是自反的和循环的时R为等价关系。命题得证.4.14设集合A={1，2，3，4，5，6}，A有划分n1={{1，2，3}，{4，5，6}}n2={{1，2}，{3,4}，{5,6}}求n1，n2所对应的等价关系。解：n1对应的等价关系R={<1,2>,<2,1>,<2,3>,<3,2>,<1,3>,<3,1>,<4,5>,<5,4>,<4,6>,<6,4>,<5,6>,<6,5>}UIA,n2对应的等价关系R={<1,2>,<2,1>,<3,4>,<4,3>,<5,6>,<6,5>}UIA4.15图4-11为一偏序集<A,A>的哈斯图。下列命题哪些为真？aRb,dRa,cRd,cRb,bRe,aRa,eRa；假，真，假，假，假，真，真根据哈斯图画出R的关系图；指出A的极大元，极小元，最大元，最小元；极大元：a,极小元：d,e,最大元：a,最小元：无;(4)求出子集B]={c,d,e},B2={b,c,d},B3={b,c,d,e}的上界，下界，上确界，下确界。B1上界a,c,上确界为c，无下界和下确界，B2上界a，上确界为a，下界和下确界均为d,B3上界a，上确界为a，无下界和下确界。图4-114.16画出集合S=｛1,2,3,4,5,6｝在偏序关系“整除”下的哈斯图，并:（1） 写出｛1,2,3,4,5,6｝的极大元，极小元，最大元，最小元。（2） 分别写出｛2,3,6｝及｛2,3,5｝的上界，下界，上确界，下确界。解：（1） 极大元4,5,6,极小元1，无最大元，最小元1。（2）｛2,3,6｝的上界为6,下界为1，上确界为6,下确界为1，｛2,3,5｝无上界和上确界，下界和下确界均为1。习题五5.1若R为二元关系，且xRy定义为x2+y2=1，其中x,y为实数。x,y在下面哪个取值范围内R为函数？0<x<1，0<y<1°T<x<1,T<y<1。-1<x<1,0<y<1。x任意，0<y<1。(1)是(2)否(3)是(4)否5.2对下列函数(本题不涉及集合S,删除，原本是用来求S的原象的)f:RTR，f(x)=x，S={8}；f:RtR+(正实数集)，f(x)=2x，S={1}；f:NtNxN，f(n)=<n,n+1>，S={<2,2>}；f:NtN，f(n)=2n+1，S={2,3}；f:ZtN，f(x)=\xl，S={0,1}；f:RtR，f(x)=3，S=N；⑺f:[0e]tR，f(x)=—，S={0,L}；1+x 2(8)f:(0,1)T(0,8)，f(x)=1，S={0,1}。x请作表回答如下问题：判断各函数分别是单射、满射或双射？单射：(1)(2)(3)(4)(7)(8)满射:(1)(2)(5)双射:(1)(2)求各函数的象(值域)；f(R)={8}f(S)={2}因S不包含于N(定义域)，所以S在f下没有象。f(S)={5，7}f(S)={0，1}f(S)={3}f(S)={1，2/3}因S不包含于定义域，所以S在f下没有象，⑶若f是双射，写出f-的表达式。f-1的表达式：f-1：RTR,f-1(X)=x,f-1的表达式：f-1:R+tR,f-1(x)=log2x,5.3已知f，g，h是R到R的函数：f(x)=x3-4x；g(x)=1 ；h(x)=x4。1+x2求：(1)go h。f，(2f。g。h, (3)f。f，(4)g。g, (5)g。h, (6)h。g。(1)g。h。f(x)= 1 1+(x3一4x)8(2)J。g。h(x)=( )3-1+x8 1+x8⑶J。f(x)=(x3-4x)3-4x1gog(x)= 1 1+( )21+x2g。h(x)=1+x8h。g(x)= 1 (1+x2)45.4f和g是N到N的函数，In为N上的恒等函数，「国 (n是偶数)f(n)=2n；g(n)=<、口(n是奇数)2证明：g。f=IN，但f。g用。(略)5.5设f,g,h是N到N的函数，{0(n是偶数)1(n是奇数)试确定(1)fof, (2)fo g,⑶g。f,⑷goh, (5)h。g，(6)(f。g) oh。(1)fof(n)=n+2，

(2)f。g(n)=2n+1,⑶g。f(n)=2n+(当n是偶数时)(当n是奇数时)(当n是偶数时)(当(当n是偶数时)(当n是奇数时)(当n是偶数时)(当n是奇数时)12h。g(n)=0(fog)oh=|1135.6设函数声RxRtRxR,f定义为：f(<x,y>)=<x+y,x-y>证明f是单射；证明f是满射；求逆函数f-1；求复合函数f-1。f和f。f。(1)(2)略f-i(<x,y>)=<X±^—>2 ' 2f-1of(vx,y>)=vx,y>f。f(<x,y>)=<2x,2y>5.7设R是集合A上的等价关系，在什么条件下从A到A/R存在双射？R是集合A上的恒等关系5.8令X={%,x2,...,%}，件。1%，...，引。问.有多少个不同的由X到Y的关系？,有多少个不同的由X到Y的函数？.当n,m满足什么条件时，存在单射，且有多少个不同的单射？,当n，m满足什么条件时，存在满射，且有多少个不同的满射？.当n，m满足什么条件时，存在双射，且有多少个不同的双射？解：(1)2mn(2)nm(3)m<=n时，存