離散數(shù)學(xué)復(fù)習(xí)題題庫(kù)證明題

1、編號(hào)題目答案題型分值大綱難度區(qū)分度1用先求主范式的方法證明（Pf答:先求出左右兩個(gè)公式的主合取范式證明10；2.433Q)(PfR)o(Pf(QR)(PfQ)(PfR)o(,PvQ)(,PvR)題o(iPvQv(RiR)(iPv(QiQ)vR)o(iPvQvR)(iPvQv-1R)(iPvQvR)(，Pv,QvR)(,PvQv，R)(,PvQvR)(,Pv，QvR)(Pf(QR)o(,Pv(QR)o(,PvQ)(,PvR)o(,PvQv(R,R)(,Pv(Q,Q)vR)o(iPvQvR)(iPvQv-1R)(iPvQvR)(，Pv,QvR)(,PvQv，R)(,PvQvR)(,Pv，QvR)它

2、們有一樣的主合取范式，所以它們等價(jià)。2給定連通簡(jiǎn)單平面圖G=,且|V|=6,|E|=12,則對(duì)于任意fF,d(f)=3。答:因?yàn)閨V|=63,且G二V,E,F是一個(gè)連通簡(jiǎn)單無(wú)向平面圖,所以對(duì)任一fF,deg(f)3。由歐拉公式|V|-|E|+|F|=2可得|F|=8。再由公式,deg(f)=2|E|,deg(f)=24。fFfF因?yàn)閷?duì)任一fF,deg(f)3,故要使上述等式成立,對(duì)任一fF,deg(f)=3。證明題106.4333證明對(duì)于連通無(wú)向簡(jiǎn)單平面圖，當(dāng)邊數(shù)e30時(shí)，必存在度數(shù)S4的頂點(diǎn)。答:若結(jié)點(diǎn)個(gè)數(shù)小于等于3時(shí)，結(jié)論顯然成立。當(dāng)結(jié)點(diǎn)多于3個(gè)時(shí)，用反證法證明。記|V|二n,|E|二m,

3、|F|二k假設(shè)圖中所有結(jié)點(diǎn)的度數(shù)都大于等于5。由歐拉握手定理得,deg(v)_2|E|得5n3。證明題106.433由公式deg(f)=2|E冋得,2m,3kof話再由歐拉公式|V|-|E|+|F|=2可得22m-m+2m=1m5315從而30m,這與已知矛盾。4在個(gè)連通簡(jiǎn)單無(wú)向平面圖G=V,E,F中若|V|,3,則|E|3|V|-6O答：|V|，3，且G二V,E,F是一個(gè)連通簡(jiǎn)單無(wú)向平面圖,d(f)，3,feFo由公式deg(f)=2|E|可得，2|E|,3|F|ofeF再由歐拉公式|V|-|E|+|F|=2可得|V|-|E|+2|E|,2o3|E|3|V|-6o證明題106.4335設(shè)G=

4、是連通的簡(jiǎn)單平面圖，|V|=n,3，面數(shù)為k,則k是連通的簡(jiǎn)單平面圖,故每個(gè)面的度數(shù)都不小于3。從而由公式deg(f)=2|E|feF可得3k2m再由歐拉公式|V|-|E|+|F|=2有m=n+k-2證明題106.433及故3kn+k-22k2n-4。6在半群G,*中，若對(duì)即證108.344答:任意取定a,G,記方程a*x_a的惟解為eR。明va,b,G,方程a*x=b和a*eR_a。題y*a_b都有惟解貝9G,*下證eR為關(guān)于運(yùn)算*的右單位兀。是一個(gè)群。對(duì)vb,G,記方程y*a_b的惟解為y。G,*是半群，.運(yùn)算*滿足結(jié)合律。b*eR_(y*a)*eR_y*(a*eR)_y*a_bo類似地,

5、記方程y*a_a的唯一解為eL。即eL*a_a下證eL為關(guān)于運(yùn)算的左單位兀。對(duì)vb,G,記方程a*x_b的惟解為x。G*是半群，.運(yùn)算*滿足結(jié)合律。.eL*b二eL*(a*x)_(eL*a)*x二a*x二b。從而在半群G*中，關(guān)于運(yùn)算*存在單位兀，記為eo現(xiàn)證G中每個(gè)兀素關(guān)于運(yùn)算*存在逆兀。對(duì)beG,記c為方程b*x=e的惟一解。下證c為b關(guān)于運(yùn)算的逆元。記d=c*b。則b*d=(b*c)*b=e*b=bob*e=b,且方程b*x=b有惟解，,d_e。,b*c=c*b=eo從而c為b關(guān)于運(yùn)算的逆兀。綜上所述，G*是一個(gè)群。7設(shè)G*是一個(gè)群，H、K是其子群。定義G上的關(guān)系R對(duì)任意a,beG,aR

6、bo存在heH,keK,使得b=h*a*k則R是G上的等價(jià)關(guān)系。答：aeG,因?yàn)镠、K是G的子群，所以eeH且eeK。令h=k=e,則a=e*a*a=h*e*k,從而aRa。即R是自反的。a,beG，若aRb/則存在heH,keK,使得b=h*a*k。因?yàn)镠、K是G的子群，所以h-ieH且k-ieK。故a=h-i*a*k-i,從而bRa。即R是對(duì)稱的。a,b,ceG,若aRb,bRc,則存在h,geH,k,leK,使得b=h*a*k,c=g*b*l。所以證明題104.433c二g*b*l二g*(h*a*k)*l=(g*h)*a*(k*l)。因?yàn)镠、K是G的子群，所以g*heH且k*leKo從而

7、aRc。即R是傳遞的。綜上所述，R是G上的等價(jià)關(guān)系。8設(shè)h是從群G,到G2,的群答:(1)因?yàn)閔(e1)h(e1)=h(e1ei)=h(e1)=證明108.2；8.355同態(tài)，G和g2的單位元分別為e1e2h(e1),所以hGe?。題和e2，則(2),aeG1,h(a)h(a-1)=h(aa-1)=h(e1)=e2,(1)h(e1)=e2；h(a-1)h(a)=h(a-1a)=h(e1)=e2,故h(a-1)=h(a)-1。(2),aGG1，h(a-1)=h(a)-1；(3),c,dEh(H),a,beH，使得c=h(a),d=h(b)。故(3)若HG，則h(H)G2；cd=h(a)h(b)=

8、h(a*b)。因?yàn)镠G,所以a*b丘(4)若h為單一同態(tài)，則,aGG1，H，故cdeh(H)o又c-1=(h(a)-1=h(a-1)且a-1EH,|h(a)|=|a|。故c-1Eh(H)o由定理5.3.2知h(H)g2。若|a|二n,則an二e故(h(a)n=h(an)=h(e1)=e2O從而h(a)的階也有限，且|h(a)|n。設(shè)|h(a)|=m,則h(am)=(h(a)m=MeJ-e?。因?yàn)閔是單同態(tài)，所以am=eTo即|a|m。故|h(a)|=|a|o若a的階是無(wú)限的，則類似于上述證明過(guò)程可以得出，h(a)的階也是無(wú)限的。故結(jié)論成立。9設(shè)*是集合A上可結(jié)合的二兀運(yùn)算，答：(1)va,A,

9、記b=a*a。因?yàn)?是可結(jié)合的,故有證明108.122且va,b,A,若a*b=b*a，則a二b。b*a=(a*a)*a=a*(a*a)=a*l由已知條件可得a=a*a。題試證明：(2)va,b,A,因?yàn)橛?1),(1)va,A,a*a=a，即a是等幕元；a*(a*b*a)=(a*a)*(b*a)=a*(b*a),(2)va,b,A,a*b*a=a;(a*b*a)*a=(a*b)*(a*a)=(a*b)*a=a*(b*a)(3)va,b,c,A,a*b*c=a*co故a*(a*b*a)=(a*b*a)*a從而a*b*a=a(3)va,b,c,A,(a*b*c)*(a*c)=(a*b*c)*a)

10、*c=(a*(b*c)*a)*c且(a*c)*(a*b*c)=a*(c*(a*b*c)=a*(c*(a*b)*c)。由(2)可知a*(b*c)*a二a且c*(a*b)*c二c,故(a*b*c)*(a*c)=(a*(b*c)*a)*c二a*c且(a*c)*(a*b*c)二a*(c*(a*b)*c)二a*c，即(a*b*c)*(a*c)=(a*c)*(a*b*c)。從而由已知條件知，a*b*c二a*c。10I上的二兀運(yùn)算*定義為：a,beI,a*b二a+b-2。試證:為群。答：(1)a,b,ceI，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2二a+b+c-4,a*(b*c)=a+(b

11、*c)-2=a+(b+c-2)-2=a+b+c-4o故(a*b)*c二a*(b*c)，從而*滿足結(jié)合律。(2)記e=2。對(duì)ael，a*2=a+2-2=a=2+a-2=2*a.o故e=2是I關(guān)于運(yùn)算*的單位元。(3)對(duì)aeI，因?yàn)閍*(4-a)二a+4-a-2=2二e=4-a+a-2=(4-a)*a古攵4-a是a關(guān)于運(yùn)算啲逆元。綜上所述，I,*為群。證明題108.34411R是集合X上的一個(gè)自反關(guān)系，求證：R是對(duì)答“”,a,b,ceX若va,b,va,ceR由r證104.322稱和傳遞的，當(dāng)且僅當(dāng)a,b和a,c在R中明有v.b,c在R中。對(duì)稱性知vb,a,vc,aeR，由r傳遞性得vb,ceR題

12、“”若va,beR,va,ceR有vb,ceR任意a,beX，因va,aeR若va,beR.vb,aeR所以R是對(duì)稱的。若va,beR，vb,ceR則vb,aeRaeR.va,ceR即r是傳遞的。12f和g都是群vG,到G2*的同態(tài)映射，證1、答：證，a,beC，有f(a)=g(a),f(b)=g(b)，又證108.2；44明C,是vG的一個(gè)子群。其中明8.3C=x1xeG且f(x)=g(x)f(b-1)二f-1(b),g(b-1)二g-1(b)題f(b-1)二f-1(b)二g-1(b)二g(b-1)f(ab-1)二f(a)*f-1(b)二g(a)*g(b-1)二g(ab-1).ab-1eC.

13、vC,是vG1,的子群。13設(shè)R是A上一個(gè)二兀關(guān)系，答：證104.433(1)S自反的明S=1(a,beA)a(對(duì)于某一個(gè)ceA,有a,aeA,且由Rb自反，)(eR)a(eR)，題試證明若R是A上一個(gè)等價(jià)關(guān)系，則S也是A上的一個(gè)等價(jià)關(guān)系。,.a,aeS(2)S對(duì)稱的Va,beAeS(eR)(eR)S定一義(eR)(eR)R對(duì)稱KeSR傳遞S傳遞的Va,b,ceAeSeS(eR)(eR)(eR)(eR)(eR)(eR)R傳遞eSS定義由（1）、（2）、（3）得；S是等價(jià)關(guān)系。141）用反證法證明答：1證明：證明102.455(PVQ)(PTR)(QTS)SvR。1(SvR)P（附加前提）題2）

14、用CP規(guī)則證明(2)S一iRMEPT(QTR),RT(QTS)PT(QTS)PVQPPTQTEQTSP一PTSTESTPTE(8)(-SAR),(PaR)TIPARTIP,RPPvRT(10)E(PaR)T(11)EFT(12)12、證明PP(附加前提)P，(Q，R)pQ，RtIRT(QTS)PQ，(Q，S)tIQ，STEp，(Q，S)cp15設(shè),是半群，e是左幺元且VxA,XA,使得f*x二e,貝y是群。答：(1)Va,b,cA,若a*b=a*c貝Ub=c證明題108.1；8.344事實(shí)上:a*ba*c,a使a*(a*b)=a*(a*c)(a*a)*b*a)*c,.e*b=e*c即：bce是

15、vA,*之幺元。事實(shí)上：由于e是左幺元，現(xiàn)證e是右幺元。xeA,x*eeA,x使X*(x*e)二(x*x)*e二e*e二e二x*x由即x*ex,e為右幺元(3)xeA,則x-ieA事實(shí)上：xeA(x*x)*xx*(x*x)二x*e二x二e*xx*xe故有x*xx*xe/.x有逆元x由(2),(3)知：為群。16設(shè)A1,2,3,，9,在AxA上定義關(guān)系R:,eR當(dāng)且僅當(dāng)a+db+c,證明R是AxA上的等價(jià)關(guān)系，并求出?R答：證明：1)：eAxA,va+b=b+a,.,eR即R自反。2)：,eR,貝Ua+d=b+c，d+a=c+b,即c+bd+a,從而,eR,即r對(duì)稱。3)：證明,題104.433V,c,dR,e,fR,貝Ua+d，b+c,c+f，d+ef，d+e一c從而a+f，a+d+e-c，b+c+e-c，b+e，,R,即R傳遞。綜上得出，R是等價(jià)關(guān)系。且，RAxA,a+5，b+2，AxA,a，b-3，,17試證明若G,*是群，H匸G,且任意的答：證明：（1）設(shè)群G,*的幺元為e，則VxG有證明io8.i；8.355aH，對(duì)每一個(gè)xG，有a*x，x*a,x*e，e*x,.eH即h日非空。題則H,*是G,*的子群。(2)Va,bH，貝yVxG有a*x，x*a,b*x，x*b，從而(a*b-i)*x，(a*b-i)*x*(b*b-i)，a*(b-i*b)*x*b-i，(a*x)*b