【正文】 n163。B且C205。D且A199。(BA)=198。d) A – (B 200。(A – C)；f) A – (A – B) = A 199。4. 證明a) A=B當(dāng)且僅當(dāng)A197。A；c) (A197。C)；d) A199。(A199。A)197。a) 若A199。~C205。B=A199。B=A200。C，則B=C。f) 若A205。C；g) 若B199。A。b) (AB)200。d) (AB)199。f) (AB)197。B。B=A；k) 195。(A200。195。B)。(B)=195。195。為：a) {{198。9. 設(shè)且，且。 用歸納法證明：a) ；b) 2+22+23+…+2n=2n+12；c) 2n=2n；d) 3|n3+2n。3證明：若n206。I+，則。規(guī)定每人每次可扳倒1至根，且扳倒最后一根直立的大頭針者為獲勝者。假定對(duì)任意自然數(shù)i≥i0及j≥j0，皆有一個(gè)命題P(i, j)滿足： i) P(i0, j0)真； ii)對(duì)任意自然數(shù)k≥i0及l(fā)≥j0，若P(k, l)真，則P(k+1, l)和P(k, l+1)皆真。n。 m。 m+。證明：若n206。試確定下列集合：a) A{1}Bb) A2Bc) (BA )2 證明或用反例推翻下列命題：a) (A∪B)(C∪D)= (AC)∪(BD) b) (A∩B)(C∩D)= (AC)∩(BD)c) (A－B)(C－D)= (AC)－(BD) d) (A197。這個(gè)命題對(duì)嗎？如果對(duì)，則給予證明；如果不對(duì)，則舉出反例。195?！萢, b且b206。B={198。a) A={0, 1, 2}，B={0, 2, 4}，R={x, y| x, y 206。設(shè)和都是從集合到集合的二元關(guān)系。試判斷下面的論斷正確與否。S也是自反的(反自反的，對(duì)稱的，反對(duì)稱的，或傳遞的)。R，4整除|x－y|且|x－y|＜10}；c) S={x, y|x, y206。I+。x}； b) ran(∪x)=∪{ranR|R206。∩{ranR|R206。1若R為集合上的一個(gè)二元關(guān)系，則也是∪(∪R)上的二元關(guān)系。D，畫出它們的關(guān)系圖，并寫出它們的關(guān)系矩陣。R1的關(guān)系矩陣MR199。3. 設(shè)IA為集合A上的恒等關(guān)系，即IA={x, x|x206。R1必是自反的和對(duì)稱的。 設(shè)集合{a, b, c, d}上的二元關(guān)系R1和R2為R1={a, a,a, b,b, d}；R2={a, d,b, c,b, d,c, b}。 (R1oR2)∩(R1oR3), (R2∩R3)o R4204。設(shè)R為集合A上的二元關(guān)系，s，tN，st且Rs=Rt。N，則Rk{R0,R1,…,Rt1}。R；b) R是反自反的，當(dāng)且僅當(dāng)R∩IA=198。如果集合A上的二元關(guān)系R既是自反的，又是傳遞的，則R2=R。A，皆令R (X)={ y206。若X1205。R (X1)﹨R (X2)；1設(shè)R1為從集合A到集合B的二元關(guān)系，R2為從集合B到集合C的二元關(guān)系。t(R1)∪t(R2)。并分別給出使s(R1)∩s(R2)205。設(shè)R為集合A上的二元關(guān)系，試證明：a) RoR*= R+= R*oR；b) (R+)+= R+；c) (R*)*= R*；設(shè)R1和R2都是集合A上的相容關(guān)系。I且iI且i≤0 }；d) { i, j | i, j206。I且i| j }；f) { i, j | i, j206。I且有x, y206。并給出了如下的證明：如果x, y206。因此R是自反的。R。試判斷下列A上的二元關(guān)系是不是A上的等價(jià)關(guān)系，為什么？a) A2－R1；b) R1－R2；c) ；d) r(R1－R2)；e) R2oR1；f) R1∪R2；g) t(R1∪R2) ；h) t(R1∩R2) ；設(shè)∏1和∏2都是集合A的劃分。S2，就稱∏1和∏2的加細(xì)，記為∏1≤∏2且∏1≠∏2，就稱∏1為∏2的真加細(xì)，并記為∏1∏2。R2當(dāng)且僅當(dāng)A/R1＜A/R2。如果i,j206。畫出下列集合上的整除關(guān)系的哈斯圖。證明：a) 若R是A上的半序，當(dāng)且僅當(dāng)R∩R1=IA且R=R*；b) 若R是A上的擬序，當(dāng)且僅當(dāng)R∩R1=198。c) A的某些非空子集有下確界，但無最小元。設(shè)A,≤為全序結(jié)構(gòu)。R，則 x1, y1T x 2, y2當(dāng)且僅當(dāng)x 1≤x2且y1≤y2；b) 若x1, x2, y1, y2206。證明R和R1同時(shí)為S上的良序，當(dāng)且僅當(dāng)S為有限集。195。中有 Supl=∪l；infl=∩l。第三章下列關(guān)系中哪些是部分函數(shù)？對(duì)于不是部分函數(shù)的關(guān)系，說明不能構(gòu)成部分函數(shù)的原因。若對(duì)任意s1,s2206。(A)到195。(X)，則f [A－B]202。(Y)，則f1[C－D]= f1[C]－f 1[D]。{ 0,1}2中的全部序偶。R皆有f (x)= x+3,g(x)=2x +1,h(x)= x/2。對(duì)x≥0,h(x)=。證明：如果f是內(nèi)射(滿射，雙射)，則f n也是內(nèi)射(滿射，雙射)。證明dom(gof)=domf。設(shè)f,g,h都是從N到N的函數(shù)，其中f(x)=3x,g(x)=3x+1,h(x)=3x+2。如果gof是左可逆的，能否保證f和g也一定都是左可逆的？設(shè)f:A→B且n(A)≥2。a) (A－B)∪(A－C)=A；b) (AB)= 198。設(shè)n0且x1,x 2,…,xn是n個(gè)任意整數(shù)，證明存在k和i使1≤i≤k≤n且xi+xi+1+…+xk能被n整除。任給52個(gè)整數(shù)，證明其中必有兩數(shù)之和能被100整除或兩數(shù)之差能被100整除。b) 有理數(shù)集合Q；c) {x|x∈Q且0≤x≤1}。設(shè)a,b,g,d為基數(shù)，0＜a≤b且g≤d，證明a+g≤b+d，a設(shè)B={ f| f:R→R且f是連續(xù)的}，證明(A)=192。1. 畫出圖G=V, E, y的圖示，指出其中那些圖是簡(jiǎn)單圖。5. 在一次集會(huì)中，相互認(rèn)識(shí)的人會(huì)彼此握手。8. 。1. 畫出K4的所有不同構(gòu)的子圖，并說明其中哪些是生成子圖，并找出互為補(bǔ)圖的生成子圖。4. 設(shè)G是任意6階簡(jiǎn)單無向圖。6. 證明沒有子圖是3階完全無向圖的n階簡(jiǎn)單無向圖最多有[n2/4]條邊。d) 求出從A至F的距離。3. a) 對(duì)于每個(gè)節(jié)點(diǎn)n，求R(n)。 0,并且等號(hào)成立當(dāng)且僅當(dāng)n1 = n2。5. 證明有向圖的每個(gè)節(jié)點(diǎn)和每條邊恰處于一個(gè)弱分支中。判斷G是否有有向回路。11. 證明有k個(gè)弱分支的n階簡(jiǎn)單有向圖至多有(nk)(nk+1)條邊。15. ，旁邊的數(shù)字是該邊的加權(quán)長(zhǎng)度，求出從n1到n11的加權(quán)距離。這句話對(duì)嗎？如果對(duì)，給出證明，如果不對(duì)，舉出反例。 n。7. 設(shè)G是非平凡的弱連通有向圖，證明G是歐拉有向圖，當(dāng)且僅當(dāng)G是若干個(gè)邊不相交的有向回路之并。3. 設(shè)n和n′是樹T的兩個(gè)不同結(jié)點(diǎn)，從n至n′的基本路徑是T中最長(zhǎng)的基本路徑。6. 。 h 163。