离散数学题库证明题

编号题目答案题型分值大纲难度1用先求主范式的方法证明(P→Q)(P→R)(P→（QR）答：先求出左右两个公式的主合取范式(P→Q)(P→R)(PQ)(PR)(PQ(RR)))(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(P→（QR）)(P（QR）)(PQ)(PR)(PQ(RR))(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)它们有一样的主合取范式，所以它们等价。证明题102.3；2.432给定连通简单平面图G=V,E,F，且|V|=6,|E|=12,则对于任意fF,d(f)=3。答：因为|V|=63，且G=〈V,E,F〉是一个连通简单无向平面图，所以对任一fF，deg(f)3。由欧拉公式|V|-|E|+|F|=2可得|F|=8。证明题106.43再由公式Ffdeg(f)=2|E|，Ffdeg(f)=24。因为对任一fF，deg(f)3，故要使上述等式成立，对任一fF，deg(f)=3。3证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点。答：若结点个数小于等于3时，结论显然成立。当结点多于3个时，用反证法证明。记|V|=n,|E|=m,|F|=k。假设图中所有结点的度数都大于等于5。由欧拉握手定理得Vvdeg(v)=2|E|得5n2m。又因为G=〈V,E,F〉是一个连通简单无向平面图，所以对每个面f,deg(f)3。由公式Ffdeg(f)=2|E|可得，2m3k。再由欧拉公式|V|-|E|+|F|=2可得252m-m+32m=151m从而30m,这与已知矛盾。证明题106.434在一个连通简单无向平面图G=〈V，E，F〉中若|V|3，则|E|3|V|－6。答：|V|3，且G=〈V，E，F〉是一个连通简单无向平面图，d(f)3，fF。由公式Ffdeg(f)=2|E|可得，2|E|3|F|。再由欧拉公式|V|-|E|+|F|=2可得证明题106.43|V|-|E|+32|E|2。|E|3|V|－6。5设G=V,E是连通的简单平面图，|V|=n3，面数为k,则k2n-4。答：记|E|=m。因为G=V,E是连通的简单平面图，故每个面的度数都不小于3。从而由公式Ffdeg(f)=2|E|可得3k2m再由欧拉公式|V|-|E|+|F|=2有m=n+k-2及23kn+k-2故k2n-4。证明题106.436在半群G,*中，若对a,bG，方程a*x=b和y*a=b都有惟一解，则G,*是一个群。答：任意取定aG，记方程a*x=a的惟一解为eR。即a*eR=a。下证eR为关于运算*的右单位元。对bG，记方程y*a=b的惟一解为y。G,*是半群，运算*满足结合律。b*eR=(y*a)*eR=y*(a*eR)=y*a=b。类似地，记方程y*a=a的唯一解为eL。即eL*a=a。下证eL为关于运算*的左单位元。对bG，记方程a*x=b的惟一解为x。G,*是半群，运算*满足结合律。eL*b=eL*(a*x)=(eL*a)*x=a*x=b。从而在半群G,*中,关于运算*存在单位元，记为e。证明题108.34现证G中每个元素关于运算*存在逆元。对bG，记c为方程b*x=e的惟一解。下证c为b关于运算的逆元。记d=c*b。则b*d=(b*c)*b=e*b=b。b*e=b,且方程b*x=b有惟一解，d=e。b*c=c*b=e。从而c为b关于运算的逆元。综上所述，G,*是一个群。7设G,*是一个群，H、K是其子群。定义G上的关系R：对任意a,b∈G，aRb存在h∈H,k∈K,使得b=h*a*k，则R是G上的等价关系。答：a∈G，因为H、K是G的子群，所以e∈H且e∈K。令h=k=e,则a=e*a*a=h*e*k,从而aRa。即R是自反的。a,b∈G，若aRb，则存在h∈H，k∈K,使得b=h*a*k。因为H、K是G的子群，所以h-1∈H且k-1∈K。故a=h-1*a*k-1,从而bRa。即R是对称的。a,b,c∈G，若aRb,bRc,则存在h,g∈H，k,l∈K,使得b=h*a*k，c=g*b*l。所以c=g*b*l=g*(h*a*k)*l=(g*h)*a*(k*l)。因为H、K是G的子群，所以g*h∈H且k*l∈K。从而aRc。即R是传递的。综上所述，R是G上的等价关系。证明题104.438设h是从群G1,到G2,的群同答：(1)因为h(e1)h(e1)=h(e1e1)=h(e1)=e2h(e1),所以h(e1)=e2。证明题108.2；8.35态，G1和G2的单位元分别为e1和e2，则（1）h(e1)=e2；（2）aG1，h(a-1)=h(a)-1；（3）若HG1，则h(H)G2；（4）若h为单一同态，则aG1，|h(a)|=|a|。(2)a∈G1，h(a)h(a-1)=h(aa-1)=h(e1)=e2,h(a-1)h(a)=h(a-1a)=h(e1)=e2,故h(a-1)=h(a)-1。(3)c,d∈h(H),a,b∈H，使得c=h(a),d=h(b)。故cd=h(a)h(b)=h(ab)。因为HG，所以ab∈H，故cd∈h(H)。又c-1=(h(a))-1=h(a-1)且a-1∈H，故c-1∈h(H)。由定理5.3.2知h(H)G2。(4)若|a|=n,则an=e1。故(h(a))n=h(an)=h(e1)=e2。从而h(a)的阶也有限，且|h(a)|n。设|h(a)|=m,则h(am)=(h(a))m=h(e1)=e2。因为h是单一同态，所以am=e1。即|a|m。故|h(a)|=|a|。若a的阶是无限的，则类似于上述证明过程可以得出，h(a)的阶也是无限的。故结论成立。9设*是集合A上可结合的二元运算，且a,bA,若a*b=b*a，则a=b。试证明：（1）aA,a*a=a，即a是等幂元；答：（1）aA,记b=a*a。因为*是可结合的，故有b*a=(a*a)*a=a*(a*a)=a*b。由已知条件可得a=a*a。（2）a,bA,因为由（1），a*(a*b*a)=(a*a)*(b*a)=a*(b*a),(a*b*a)*a=(a*b)*(a*a)=(a*b)*a=a*(b*a)。故a*(a*b*a)=(a*b*a)*a，从而a*b*a=a。证明题108.12（2）a,bA,a*b*a=a;（3）a,b,cA,a*b*c=a*c。（3）a,b,cA,（a*b*c）*（a*c）=（（a*b*c）*a）*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,bI，a*b=a+b-2。试证：I,*为群。答：（1）a,b,cI，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4,a*(b*c)=a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。故(a*b)*c=a*(b*c)，从而*满足结合律。（2）记e=2。对aI，a*2=a+2-2=a=2+a-2=2*a.。故e=2是I关于运算*的单位元。（3）对aI，因为a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。故4-a是a关于运算*的逆元。综上所述，I,*为群。证明题108.3411R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当a,b和a,c在R中有.b,c在R中。答：“”Xcba,,若Rc,a,b,a由R对称性知Ra,c,a,b，由R传递性得Rc,b证明题104.32“”若Rb,a，Rc,a有Rc,b任意Xba,，因Ra,a若Rb,aRa,b所以R是对称的。若Rb,a，Rcb,则Rcb,Rab,Rc,a即R是传递的。12f和g都是群G1,★到G2,*的同态映射，证明C,★是G1,★的一个子群。其中C=)}()(|{1xgxfGxx且1、答：证Cba,，有)()(),()(bgbfagaf，又)()(,)()(1111bgbgbfbf)()()()(1111bgbgbfbfaf(★agbgagbfafb()(*)()(*)()111★)1ba★Cb1C,★是G1,★的子群。证明题108.2；8.3413设R是A上一个二元关系，)},,,(),(|,{RbcRcaAcAbabaS且有对于某一个试证明若R是A上一个等价关系，则S也是A上的一个等价关系。答：（1）S自反的Aa，由R自反，),(),(RaaRaa，Saa,（2）S对称的证明题104.43传递对称定义RSabRRbcRcaSRbcRcaSbaAba,),(),(),(),(,,S传递的定义传递SScaRRcbRbaRceRebRbdRdaScbSbaAcba,),(),(),(),(),(),(,,,,由（1）、（2）、（3）得；S是等价关系。141）用反证法证明RSSQRPQP)()()(。2）用CP规则证明)()(),(SQPSQRRQP答：1证明：⑴)(RSP（附加前提）⑵RST⑴E⑶QPP⑷QPT⑶E⑸SQP⑹SPT⑷⑸E⑺PST⑹E⑻)()(RPRST⑺I⑼RPT⑵⑻I证明题102.45⑽RPP⑾RPT⑽E⑿)(RPT⑾E⒀FT⑼⑿I2、证明①PP（附加前提）②)(RQPP③RQT①②I④)(SQRP⑤)(SQQT③④I⑥SQT⑤E⑦)(SQPCP15设A,*，是半群，e是左幺元且AxAxˆ,，使得exx*ˆ，则A,*是群。答：（1）cbcabaAcba则若**,,,cbcebecaabaacaabaaacaba:**,*)*ˆ(*)*ˆ()*(*ˆ)*(*ˆˆ**:即使事实上(2)e是A，*之幺元。事实上：由于e是左幺元，现证e是右幺元。证明题108.1；8.34为右幺元即由使exexxxeeeexxexxxAexAx,*)1(*ˆ**)*ˆ()*(*ˆˆ,*,（3）AxAx1,则xxexxxxexxxexexxxxxxxAxˆˆ**ˆˆ***)*ˆ(**)ˆ*(:有逆元故有事实上由（2），（3）知：A,*为群。16设}9,,3,2,1{A，在AA上定义关系RdcbaR,,,:当且仅当cbda，证明R是AA上的等价关系，并求出?]5,2[R答：证明：1）：,,,,,,,RbabaabbaAAba即R自反。2）：,,,,,,bcadcbdaRdcba