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

2、V|=63，且 G=V,E,F是一个连通简单无向平面图，所以对任一 fF，deg(f)3。由欧拉公式|V|-|E|+|F|=2 可得|F|=8。证明题106.433再由公式deg(f)=2|E|，deg(f)=24。 Ff Ff因为对任一 fF，deg(f)3，故要使上述等式成立，对任一 fF，deg(f)=3。 3证明对于连通无向简单平面图，当边数 e30 时，必存在度数4 的顶点。答：若结点个数小于等于 3 时，结论显然成立。当结点多于 3 个时，用反证法证明。记|V|=n,|E|=m,|F|=k。假设图中所有结点的度数都大于等于 5。由欧拉握手定理得deg(v)=2|E|得 5n2

3、m。 Vv又因为 G=V,E,F是一个连通简单无向平面图，所以对每个面 f,deg(f)3。由公式deg(f)=2|E|可得，2m3k。 Ff再由欧拉公式|V|-|E|+|F|=2 可得 2m-m+m=52 32m151从而 30m,这与已知矛盾。证明题106.4334在一个连通简单无向平面图答：|V|3，且 G=V，E，F是一个连通简单无Q证明题106.433G=V，E，F中若|V| 3，则 |E| 3|V|6。向平面图，d(f) 3，fF。由公式deg (f)=2|E|可得，2|E|3|F|。 Ff再由欧拉公式|V|-|E|+|F|=2 可得|V|-|E|+|E|2。32|E|3|

4、V|6。 5设 G=是连通的简单平面图，|V|=n 3，面数为 k,则 k 2n-4。答：记|E|=m。因为 G=是连通的简单平面图，故每个面的度数都不小于 3。从而由公式deg(f)=2|E| Ff可得 3k2m再由欧拉公式|V|-|E|+|F|=2 有m=n+k-2及 kn+k-223故 k2n-4。证明题106.4336在半群中，若对a,b G，方程 a*x=b 和y*a=b 都有惟一解，则是一个群。答：任意取定 aG，记方程 a*x=a 的惟一解为 eR。即a*eR=a。下证 eR为关于运算*的右单位元。对bG，记方程 y*a=b 的惟一解为 y。是半群，运算*满足结合律。Q证明

5、题108.344b*eR=(y*a)*eR=y*(a*eR)=y*a=b。类似地，记方程 y*a=a 的唯一解为 eL。即eL*a=a。下证 eL为关于运算*的左单位元。对bG，记方程 a*x=b 的惟一解为 x。是半群，运算*满足结合律。QeL*b=eL*(a*x)=(eL*a)*x=a*x=b。从而在半群中, 关于运算*存在单位元，记为 e。现证 G 中每个元素关于运算*存在逆元。对bG，记 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。Qb*c=c*b=e。

6、从而 c 为 b 关于运算的逆元。综上所述，是一个群。7设是一个群，H、K 是其子群。答：aG，因为 H、K 是 G 的子群，所以 eH 且 eK。证明题104.433定义 G 上的关系 R：对任意a,bG，aRb 存在 hH,kK, 使得 b=h*a*k，则 R 是 G 上的等价关系。令 h=k=e,则 a=e*a*a=h*e*k,从而 aRa。即 R 是自反的。a,bG，若 aRb，则存在 hH，kK, 使得 b=h*a*k。因为 H、K 是 G 的子群，所以 h-1H 且 k-1K。故 a=h-1*a*k-1,从而 bRa。即 R 是对称的。a,b,cG，若 aRb,bRc,则存在

7、h,gH，k,lK, 使得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*hH 且 k*lK。从而 aRc。即 R 是传递的。综上所述，R 是 G 上的等价关系。8设 h 是从群到的群同态，G 和 G2的单位元分别为 e11和 e2，则（1）h(e1)=e2；（2）a G1，h(a-1)=h(a)-1；（3）若 H G1，则 h(H) G2；答：(1) 因为 h(e1)h(e1)=h(e1e1)= h(e1)= e2h(e1),所以 h(e1)=e2。(2) aG1，h(a)h(a-1)=h(aa

8、-1)= h(e1)= e2,h(a-1)h(a)=h(a-1a)= h(e1)= e2,故 h(a-1)=h(a)-1。(3) c,dh(H),a,bH，使得 c=h(a),d=h(b)。故cd=h(a)h(b)=h(ab)。因为 HG，所以 ab H ，故cdh(H)。又 c-1=(h(a)-1=h(a-1)且 a-1H，故 c-1h(H)。由证明题108.2； 8.355（4）若 h 为单一同态，则a G1，|h(a)|=|a|。定理 5.3.2 知 h(H)G2。(4) 若|a|=n,则 an=e1。故(h(a)n=h(an)=h(e1)=e2。从而 h(a)的阶也有限，且|h(

9、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 是等幂元；（2）a,b A,a*b*a=a;（3）a,b,c A,a*b*c=a*c。答：（1）aA,记 b=a*a。因为*是可结合的，故有b*a=(a*a)*a=a*(a*a)=a*b。由已知条件可得 a=a*a。（2）a,b

10、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。（3） a,b,cA,（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)。证明题108.122由（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

11、*(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。试证：为群。答：（1）a,b,cI，(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。对aI，a*2=a+2-2=a=2+a-2=2*a.。故 e=2是 I 关于运算*的单位元。（3）对aI，因为 a*（4-a）=a+4-a-2=2=

12、e=4-a+a-2=(4-a)*a。故 4-a 是 a 关于运算*的逆元。综上所述，为群。证明题108.34411R 是集合 X 上的一个自反关系，求证：R 是对称和传递的，当且仅当和在 R 中有在 R 中。答：“” 若 Xcba,R c, ab, aa, bc, bb, ac, ac, ba, ab, aa, bb, acb,ab,c, a到的同态映射，证明是的一个子群。其中 C=)()(|1xgxfGxx且1、答：证，有，又Cba ,)()(),()(bgbfagaf)()(, )()(1111bgbgbfbf)()()()(1111bgbgbfbfaf (agbgagbf

13、afb()(*)()(*)()111)1b 是的子群。aCb1证明题108.2； 8.34413设 R 是 A 上一个二元关系，),(),( |,RbcRcaAcAbabaS且有对于某一个试证明若 R 是 A 上一个等价关系，则 S 也是 A 上的一个等价关系。答：（1）S 自反的，由 R 自反，Aa),(),(RaaRaaSaa ,（2）S 对称的证明题104.433传递对称定义RSabRRbcRcaSRbcRcaSbaAbaLLL,),(),(),(),(,S 传递的定义传递SScaRRcbRbaRceRebRbdRdaScbSbaAcbaLL,),(),(),(),(),()

14、,(,由（1）、（2）、（3）得；S 是等价关系。141）用反证法证明。RSSQRPQP)()()(2）用 CP 规则证明)()(),(SQPSQRRQP答：1 证明：P（附加前提）)(RS TERSPQP TEQP PSQ TESP TEPS TI)()(RPRSTIRP证明题102.455PRP TERP TE)(RPTIF2、证明P（附加前提）PP)(RQPTIRQ P)(SQRTI)(SQQTESQ CP)(SQP15设，是半群，e 是左幺元且，使得，则AxAx,exx*是群。答：（1）cbcabaAcba则若*,cbcebecaabaacaabaaacaba:*,*)*(*)*()*(*)*(*:即使事实上 Q(2) e 是之幺元。事实上：由于 e 是左幺元，现证 e 是右幺元。证明题108.1； 8.344为右幺元即由使exexxxeeeexxexxxAexAx,*) 1 (*)*()*(*,*,（3）AxAx1,则xxexxxxexxxexexxxxxxxAx *)*(*) *(:有逆元故有事实上由（2），（3）知：为群。16设，在上定义关系

展开阅读全文