集合論離散數(shù)學(xué)課本習(xí)題

510206512100Ev10Ev4A={x|xx2為奇數(shù)}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、設(shè)A、B和C為集合。證明或用反例以下的各個(gè)命題7A、BABAB{,{{x,y,10、設(shè)AB)A=B設(shè)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表達(dá)下列集合：{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

設(shè)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)。這個(gè)命題對(duì)嗎？如果對(duì)，則給予證 4xCyC，則<xy>(C))。5、證明：a∪<a,b>b∪<a,b>。6、把三元偶<abc>定義為aababc}}b>={{a,A},{b,B}}。證明這個(gè)定義的合理性。1 列出從A到B的關(guān)系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的二元關(guān)系。證明dom(R1∪R2)=ran(R1∩R2)4LD分別表示集合{1,2,3,6}L,DL∩D中的所有序偶。的，或傳遞的)，則R∩S，R∪S，R－S，RS也是自反的(反自反的，對(duì)稱(chēng)的，稱(chēng)的，7RSS={<xy>|xyRx·yS={<xy>|xyR，4整除|x－y|且S={<xy>|xyR，x2=1yS={<xy>|xyR，4|x|≤1|y|≥1}8n,mI+AnAm元關(guān)系？證明你的9、設(shè)和AB的二元關(guān)系構(gòu)成的集類(lèi)，并且11RA上的一個(gè)二元關(guān)系，若令fldR=domR∪ranR則fldR=∪(∪R習(xí)題試畫(huà)出R的關(guān)系圖GR，求出R的關(guān)系矩陣MR,并R所具有的性質(zhì)2.2.3A={1,2,3}上的十二個(gè)二元關(guān)系的關(guān)系圖，寫(xiě)出相應(yīng)的關(guān)系矩陣，2.14L,DLD，畫(huà)出它們的關(guān)系圖，并寫(xiě)出它們的An共有多少個(gè)A共有多少個(gè)A共有多少個(gè)A共有多少個(gè)A上的不相同的稱(chēng)關(guān)系共有多少個(gè)A上的不相同的既是對(duì)稱(chēng)又稱(chēng)的關(guān)系設(shè)R為非空有限集A上的二元關(guān)系。如果R是稱(chēng)的，則RR-1的關(guān)系矩陣R為集合ARR-1A上包含R的最小對(duì)稱(chēng)關(guān)系，RR-1為A上R中的最大對(duì)稱(chēng)關(guān)系。IA為集合A上的恒等關(guān)系，即IA={<x,x>|xA}AR，A上的二元關(guān)系IARR-1必是自反的和對(duì)稱(chēng)的。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上的二元關(guān)系，s，tN，s<tRs=Rt,9IAA上的恒等關(guān)系，RARRRR=R-R是稱(chēng)的，當(dāng)且僅當(dāng)RR-1=11R1AB的二元關(guān)系，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上的二元關(guān)系是不是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是自反的。請(qǐng)你想，他的看法和證明對(duì)嗎？為什么？R,4AR滿足：若<xy>,<y,z>R，則<z,x>RR為循環(huán)的。ARAR是自反的和循環(huán)的。5R1R2AAA上的等價(jià)1R21t(R1∪R2)t(R1∩R2)7R1R2AR1=R2A/R1=A/R28、設(shè)∏1和∏2AS1∈∏1S2∏2S1S2，就稱(chēng)∏12的加細(xì)，記為∏1≤∏2若∏1≠∏2，就稱(chēng)∏1為∏2的真加細(xì)，并記為∏1<∏2。R1R2A上的等價(jià)關(guān)系，證明：{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 當(dāng)且僅 f(n)<f(m),或f(n)=f(m)且f(nn的不同素因子的個(gè)數(shù)。I+,R>為良序結(jié)構(gòu)。14、設(shè)A的所有劃分組成的集合，并在R2，則∏1R∏2當(dāng)且僅當(dāng)∏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、設(shè)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階簡(jiǎn)單無(wú)向圖。證明G或者G344除1。習(xí)題AF6AFAFAFAF設(shè)1,2,3是任意無(wú)向圖（有向圖）G的三個(gè)任意節(jié)點(diǎn)，以下三是否成立？如果成d(120,并且等號(hào)成立當(dāng)且僅當(dāng)12d(12d(2,1)d(12d(2,3)d(13)證明無(wú)向圖是連通的當(dāng)且僅當(dāng)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是弱連通有向圖。如果對(duì)于G的任意節(jié)點(diǎn)皆有dv1GGk個(gè)弱分支的n階簡(jiǎn)單有向圖至多有(n-k)(n-k+1)GnG的任意節(jié)點(diǎn)，dG(vn12Gn的任意正整數(shù)k，nk習(xí)題確定圖7.4.6的六個(gè)圖哪個(gè)是圖，有向圖，圖，有向圖，找出其如果G1和G2是可運(yùn)算的有向圖，則G1G2仍是有向圖。這句話對(duì)嗎？如果設(shè)n是大于2的奇數(shù)，證明n階完全無(wú)向圖有(n-1)/2個(gè)邊不相交的回路+dG(′)n。試證明G是圖設(shè)G是非平凡的連通無(wú)向圖，證