集合论离散数学课本习题

510206512100Ev10Ev4A={x|xx2为奇数}B={x|y∈Ix=2y}{a,b}{a,b,c,{a,b,{a,b}{a,b,c,{a,b,{a,b}{a,b,{a,{a,b}{a,b,{a,6、设A、B和C为集合。证明或用反例以下的各个命题7A、BABAB{,{{x,y,10、设AB)A=B设A(AB)~(A~A(A–B)–A–(B–(AB)(AB)(BA={n|nI+n<12},Bn|nI+n8},C={2n|nI+},D={3n|nI+}E2n-1|nI+}试A，B，C，DE表达下列集合：{n|n{n|nn10nn9}ABCDACBD且A–(BC)=(A–B)(A–A–(BC)=(A–B)(A–A–(A–B)=AA=BAB=(AB)C=A(BA(B(BCA=(BA)(CA)ACBC且ACBC，则ABC，则AB(A-B)(A-C)=A- R{a|aR且a1}R{a|aRa(11)}iI

RiRiAn{x|xRxn}nN

Ax{y|yR且0yxxR

Ax

设A ，Am0

m0

1

n(n

；n

4111211n+2+122n 1112

1 nnn

5

5证明：若nI+，则

Fn 1至m根，且扳倒最后一根直立的大头针者为获胜者。试证明：如果甲先扳且(m+n)n，则甲总能获胜。,,P(i0j0)i≥i0j≥j0，P(i,j)皆真。7nmNnmnm8nmNnmn+m+9nmNn＜mxNm=nx+1 3B∪CA，则(A×B)－(C×D(A－C)×(B－D)。这个命题对吗？如果对，则给予证 4xCyC，则<xy>(C))。5、证明：a∪<a,b>b∪<a,b>。6、把三元偶<abc>定义为aababc}}b>={{a,A},{b,B}}。证明这个定义的合理性。1 列出从A到B的关系R中的所有序偶A={0,1,2}，B={0,2,4}，R={<x,y>|x,yA∩BA={1,2,3,4,5}，B={1,2,3}，R={<xy>|xAyBx2R1R2都是从{1,2,3,4}到2,3,4}R1={<1,2>,<2,4>,<3,3>R2={<1,3>,<2,4>,<4,2>R1∪R2R1∩R2domR1,domR2ranR1ranR2,dom(R1∪R2)和ran(R1∪R2)。3R1R2AB的二元关系。证明dom(R1∪R2)=ran(R1∩R2)4LD分别表示集合{1,2,3,6}L,DL∩D中的所有序偶。的，或传递的)，则R∩S，R∪S，R－S，RS也是自反的(反自反的，对称的，称的，7RSS={<xy>|xyRx·yS={<xy>|xyR，4整除|x－y|且S={<xy>|xyR，x2=1yS={<xy>|xyR，4|x|≤1|y|≥1}8n,mI+AnAm元关系？证明你的9、设和AB的二元关系构成的集类，并且11RA上的一个二元关系，若令fldR=domR∪ranR则fldR=∪(∪R习题试画出R的关系图GR，求出R的关系矩阵MR,并R所具有的性质2.2.3A={1,2,3}上的十二个二元关系的关系图，写出相应的关系矩阵，2.14L,DLD，画出它们的关系图，并写出它们的An共有多少个A共有多少个A共有多少个A共有多少个A上的不相同的称关系共有多少个A上的不相同的既是对称又称的关系设R为非空有限集A上的二元关系。如果R是称的，则RR-1的关系矩阵R为集合ARR-1A上包含R的最小对称关系，RR-1为A上R中的最大对称关系。IA为集合A上的恒等关系，即IA={<x,x>|xA}AR，A上的二元关系IARR-1必是自反的和对称的。R1{a,b,c,d}R1R2R1={<a,a>,<a,b>,<b,d>}；R2={<a,d>,<b,c>,<b,d>,<c,b>}R2oR1，R1oR2R2R2。 4R1o(R2∩R3)R1oR2)∩(R1oR3R2∩R3)oR4R1R2R1oR2R1R2R1oR2R1R2R1oR21MR1MR2MR1R2MR1R2R1MR3。18RA上的二元关系，s，tN，s<tRs=Rt,9IAA上的恒等关系，RARRRR=R-R是称的，当且仅当RR-1=11R1AB的二元关系，R2BC12RABXAR(X)={yB|xXR(X1∪X2)=R(X1)∪RR(X1∩X2)R(X1)∩RR(X1﹨X2)R(X1)﹨R则(R1oR2)(X)=R2(R1(X))。2R1R2A4R1R2A6Rst(R)≠ts(R)7RARoR*=R+=(R+)+=(R*)*=R1∩R2AR1∪R2AR1－R2AR1R2AR1oR2A1R2A13AnA1I上的二元关系是不是Iij>|ijIi·jij>|ijIi·j≥0ijij>|ijIi≤0ij>|ijIi·j≥0ij>|ijIi|jij>|ijIxI10x≤i≤j≤10(xij>|ijI且|i－j|≤10ij>|ijIxyI10x≤i≤10(x+1)10y≤j≤10(yij>|ijIxI10xi<10(x和<y,y>R。因此R是自反的。请你想，他的看法和证明对吗？为什么？R,4AR满足：若<xy>,<y,z>R，则<z,x>RR为循环的。ARAR是自反的和循环的。5R1R2AAA上的等价1R21t(R1∪R2)t(R1∩R2)7R1R2AR1=R2A/R1=A/R28、设∏1和∏2AS1∈∏1S2∏2S1S2，就称∏12的加细，记为∏1≤∏2若∏1≠∏2，就称∏1为∏2的真加细，并记为∏1<∏2。R1R2A上的等价关系，证明：{A∩B的划分。11AnA2{i|iI{i|iIRAR|sSRAR|sSRAR|sSRAR|sS4RARAR∩R-1=IARAR∩R-1=5x1x2y1y2R，则x1y1>T<x2y2>x1≤x2x1x2y1y2R，则x1y1>T<x2y2>x1≤xx1x2y1y2R，则x1y1>T<x2y2>x1＜x2x1=x2x1x2y1y2∈R，则x1y1>T<x2y2>x1＜x211RSRR-1SS12、I+R 当且仅 f(n)<f(m),或f(n)=f(m)且f(nn的不同素因子的个数。I+,R>为良序结构。14、设A的所有划分组成的集合，并在R2，则∏1R∏2当且仅当∏1为∏2Rxy>|xy∈Nxxy>|xy∈Ryxxy>|xy∈Ry2x3As1,s2(A)f(s1,s2s1∩s2f是从(A)×(A)到(A)上f(x,y)xf

若y若xy{fg:A2→I?7AB为有限集，n(A)=mn(B)=n。AB1-1ABffxffx

若x若x1f,g,hRRxRf(x)=x+3,g(x)=2x+1,h(x)=x/2gof,fog,fof,gog,foh,hog,hof,gohfohog。2f,g,hRRx≠0,f(x)=1/xx∈R,g(x)=x20,h(x)=xfofhoggohf是否为、满射和双射ff(x)=2xf(x)=1/(1+f(x)=xa4、设n∈I+，f:A→A。证明：如果f是(满射，双射)，则fn也是(满射，双射)5fAAfofffIA7A={1,2,3}AAff(1)=3?fofof=若gof为满射，g为，则f为满若gof为，f为满射，则gn整除。)=V={1,2,3,4,={<e1,{2}>},<e2,{2,4}>,<e3,{1,2}>,<e4,{1,3}>,<e5,{1,3}>,<e6,4}>,<e7,{4,V={1,2,3,4,E={={<e1,{1,3}>},<e2,{1,4}>,<e3,{4,1}>,<e4,{1,2}>,<e5,{2,2}>,<e6,{4}>,<e7,{5,4}>,<e8,{5,3}>,<e9,{5,3}>,<e10,{5,V={1,2,3,4,5,6,7,E={={<e1,{2,1}>},<e2,{1,2}>,<e3,{1,3}>,<e4,{2,4}>,<e5,{3,4}>,<5}>,<e7,{5,3}>,<e8,{3,5}>,<e9,{6,7}>,<e10,{7,8}>,<e11,{8,7.1.87.1.9nGmnkkk+1，证明G6阶简单无向图。证明G或者G344除1。习题AF6AFAFAFAF设1,2,3是任意无向图（有向图）G的三个任意节点，以下三是否成立？如果成d(120,并且等号成立当且仅当12d(12d(2,1)d(12d(2,3)d(13)证明无向图是连通的当且仅当GG=<V,E,>V={1,2,3,4,5,67,8}，E={ab,cd,efg,h,ijk,lmn,,<i,<5,8j,<4,5>>,<k,<5,3>l<4,3m,<4,2>n,<5,2>>p,<3,2>>}GG是弱连通有向图。如果对于G的任意节点皆有dv1GGk个弱分支的n阶简单有向图至多有(n-k)(n-k+1)GnG的任意节点，dG(vn12Gn的任意正整数k，nk习题确定图7.4.6的六个图哪个是图，有向图，图，有向图，找出其如果G1和G2是可运算的有向图，则G1G2仍是有向图。这句话对吗？如果设n是大于2的奇数，证明n阶完全无向图有(n-1)/2个边不相交的回路+dG(′)n。试证明G是图设G是非平凡的连通无向图，证