离散数学复习题题库证明题

1、编号题目答案题型分值大纲难度区分度1用先求主范式的方法证明（Pf答:先求出左右两个公式的主合取范式证明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、们有一样的主合取范式，所以它们等价。2给定连通简单平面图G=,且|V|=6,|E|=12,则对于任意fF,d(f)=3。答:因为|V|=63,且G二V,E,F是一个连通简单无向平面图,所以对任一fF,deg(f)3。由欧拉公式|V|-|E|+|F|=2可得|F|=8。再由公式,deg(f)=2|E|,deg(f)=24。fFfF因为对任一fF,deg(f)3,故要使上述等式成立,对任一fF,deg(f)=3。证明题106.4333证明对于连通无向简单平面图，当边数e30时，必存在度数S4的顶点。答:若结点个数小于等于3时，结论显然成立。当结点多于3个时，用反证法证明。记|V|二n,|E|二m,

3、|F|二k假设图中所有结点的度数都大于等于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=V,E,F中若|V|,3,则|E|3|V|-6O答：|V|，3，且G二V,E,F是一个连通简单无向平面图,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设G=

4、是连通的简单平面图，|V|=n,3，面数为k,则k是连通的简单平面图,故每个面的度数都不小于3。从而由公式deg(f)=2|E|feF可得3k2m再由欧拉公式|V|-|E|+|F|=2有m=n+k-2证明题106.433及故3kn+k-22k2n-4。6在半群G,*中，若对即证108.344答:任意取定a,G,记方程a*x_a的惟解为eR。明va,b,G,方程a*x=b和a*eR_a。题y*a_b都有惟解贝9G,*下证eR为关于运算*的右单位兀。是一个群。对vb,G,记方程y*a_b的惟解为y。G,*是半群，.运算*满足结合律。b*eR_(y*a)*eR_y*(a*eR)_y*a_bo类似地,

5、记方程y*a_a的唯一解为eL。即eL*a_a下证eL为关于运算的左单位兀。对vb,G,记方程a*x_b的惟解为x。G*是半群，.运算*满足结合律。.eL*b二eL*(a*x)_(eL*a)*x二a*x二b。从而在半群G*中，关于运算*存在单位兀，记为eo现证G中每个兀素关于运算*存在逆兀。对beG,记c为方程b*x=e的惟一解。下证c为b关于运算的逆元。记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关于运算的逆兀。综上所述，G*是一个群。7设G*是一个群，H、K是其子群。定义G上的关系R对任意a,beG,aR

6、bo存在heH,keK,使得b=h*a*k则R是G上的等价关系。答：aeG,因为H、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。因为H、K是G的子群，所以h-ieH且k-ieK。故a=h-i*a*k-i,从而bRa。即R是对称的。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)。因为H、K是G的子群，所以g*heH且k*leKo从而

7、aRc。即R是传递的。综上所述，R是G上的等价关系。8设h是从群G,到G2,的群答:(1)因为h(e1)h(e1)=h(e1ei)=h(e1)=证明108.2；8.355同态，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)。因为HG,所以a*b丘(4)若h为单一同态，则,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。设|h(a)|=m,则h(am)=(h(a)m=MeJ-e?。因为h是单同态，所以am=eTo即|a|m。故|h(a)|=|a|o若a的阶是无限的，则类似于上述证明过程可以得出，h(a)的阶也是无限的。故结论成立。9设*是集合A上可结合的二兀运算，答：(1)va,A,

9、记b=a*a。因为*是可结合的,故有证明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,因为由(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上的二兀运算*定义为：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)，从而*满足结合律。(2)记e=2。对ael，a*2=a+2-2=a=2+a-2=2*a.o故e=2是I关于运算*的单位元。(3)对aeI，因为a*(4-a)二a+4-a-2=2二e=4-a+a-2=(4-a)*a古攵4-a是a关于运算啲逆元。综上所述，I,*为群。证明题108.34411R是集合X上的一个自反关系，求证：R是对答“”,a,b,ceX若va,b,va,ceR由r证104.322称和传递的，当且仅当a,b和a,c在R中明有v.b,c在R中。对称性知vb,a,vc,aeR，由r传递性得vb,ceR题

12、“”若va,beR,va,ceR有vb,ceR任意a,beX，因va,aeR若va,beR.vb,aeR所以R是对称的。若va,beR，vb,ceR则vb,aeRaeR.va,ceR即r是传递的。12f和g都是群vG,到G2*的同态映射，证1、答：证，a,beC，有f(a)=g(a),f(b)=g(b)，又证108.2；44明C,是vG的一个子群。其中明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设R是A上一个二兀关系，答：证104.433(1)S自反的明S=1(a,beA)a(对于某一个ceA,有a,aeA,且由Rb自反，)(eR)a(eR)，题试证明若R是A上一个等价关系，则S也是A上的一个等价关系。,.a,aeS(2)S对称的Va,beAeS(eR)(eR)S定一义(eR)(eR)R对称KeSR传递S传递的Va,b,ceAeSeS(eR)(eR)(eR)(eR)(eR)(eR)R传递eSS定义由（1）、（2）、（3）得；S是等价关系。141）用反证法证明答：1证明：证明102.455(PVQ)(PTR)(QTS)SvR。1(SvR)P（附加前提）题2）

14、用CP规则证明(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设,是半群，e是左幺元且VxA,XA,使得f*x二e,贝y是群。答：(1)Va,b,cA,若a*b=a*c贝Ub=c证明题108.1；8.344事实上:a*ba*c,a使a*(a*b)=a*(a*c)(a*a)*b*a)*c,.e*b=e*c即：bce是

15、vA,*之幺元。事实上：由于e是左幺元，现证e是右幺元。xeA,x*eeA,x使X*(x*e)二(x*x)*e二e*e二e二x*x由即x*ex,e为右幺元(3)xeA,则x-ieA事实上：xeA(x*x)*xx*(x*x)二x*e二x二e*xx*xe故有x*xx*xe/.x有逆元x由(2),(3)知：为群。16设A1,2,3,，9,在AxA上定义关系R:,eR当且仅当a+db+c,证明R是AxA上的等价关系，并求出?R答：证明：1)：eAxA,va+b=b+a,.,eR即R自反。2)：,eR,贝Ua+d=b+c，d+a=c+b,即c+bd+a,从而,eR,即r对称。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是等价关系。且，RAxA,a+5，b+2，AxA,a，b-3，,17试证明若G,*是群，H匸G,且任意的答：证明：（1）设群G,*的幺元为e，则VxG有证明io8.i；8.355aH，对每一个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