资源描述：
《离散数学题库证明题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、编号题目答案题型分值大纲难度1用先求主范式的方法证明(P→Q)(P→R)(P→（QR）答：先求出左右两个公式的主合取范式(P→Q)(P→R)(PQ)(PR)(PQ(RR)))(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(P→（QR）)(P（QR）)(PQ)(PR)(PQ(RR))(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)它们有一样的主合取范式，所以它们等价。证明题102.3；2.432给定连通简单平面图G=，且
2、V
3、=6,
4、E
5、=12,则对于任意fF,d(f)=3。答：因为
6、V
7、=63
8、，且G=〈V,E,F〉是一个连通简单无向平面图，所以对任一fF，deg(f)3。由欧拉公式
9、V
10、-
11、E
12、+
13、F
14、=2可得
15、F
16、=8。再由公式deg(f)=2
17、E
18、，deg(f)=24。因为对任一fF，deg(f)3，故要使上述等式成立，证明题106.43对任一fF，deg(f)=3。1证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点。答：若结点个数小于等于3时，结论显然成立。当结点多于3个时，用反证法证明。记
19、V
20、=n,
21、E
22、=m,
23、F
24、=k。假设图中所有结点的度数都大于等于5。由欧拉握手定理得deg(v)=2
25、E
26、得5n2m。又因为G=〈V,E,F〉是一个连通简单
27、无向平面图，所以对每个面f,deg(f)3。由公式deg(f)=2
28、E
29、可得，2m3k。再由欧拉公式
30、V
31、-
32、E
33、+
34、F
35、=2可得2m-m+m=m从而30m,这与已知矛盾。证明题106.432在一个连通简单无向平面图G=〈V，E，F〉中若
36、V
37、3，则
38、E
39、3
40、V
41、－6。答：
42、V
43、3，且G=〈V，E，F〉是一个连通简单无向平面图，d(f)3，fF。由公式deg(f)=2
44、E
45、可得，2
46、E
47、3
48、F
49、。再由欧拉公式
50、V
51、-
52、E
53、+
54、F
55、=2可得
56、V
57、-
58、E
59、+
60、E
61、2。
62、E
63、3
64、V
65、－6。证明题106.431设G=是连通的简单平面图，
66、V
67、=n3，面数为k,则k2n-4。答：记
68、
69、E
70、=m。因为G=是连通的简单平面图，故每个面的度数都不小于3。从而由公式deg(f)=2
71、E
72、可得3k2m再由欧拉公式
73、V
74、-
75、E
76、+
77、F
78、=2有m=n+k-2及kn+k-2故k2n-4。证明题106.432在半群中，若对a,bG，方程a*x=b和y*a=b都有惟一解，则是一个群。答：任意取定aG，记方程a*x=a的惟一解为eR。即a*eR=a。下证eR为关于运算*的右单位元。对bG，记方程y*a=b的惟一解为y。是半群，运算*满足结合律。b*eR=(y*a)*eR=y*(a*eR)=y*a=b。类似地，记方程y*a=a的唯一解为eL。即eL
79、*a=a。下证eL为关于运算*的左单位元。对bG，记方程a*x=b的惟一解为x。是半群，运算*满足结合律。eL*b=eL*(a*x)=(eL*a)*x=a*x=b。从而在半群中,关于运算*存在单位元，记为e。现证G中每个元素关于运算*存在逆元。对b证明题108.34G，记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关于运算的逆元。综上所述，是一个群。1设是一个群，H、K是其子群。定义G上的关系R：对任意a,b
80、∈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。从
81、而aRc。即R是传递的。综上所述，R是G上的等价关系。证明题104.432设h是从群到的群同态，G和G2的单位元分别为e1和e2，则答：(1)因为h(e1)h(e1)=h(e1e1)=h(e1)=e2h(e1),所以h(e1)=e2。(2)a∈G1，h(a)h(a-1)=h(aa-1)=h(e1)=e2,h(a-1)h(a)=h(a-1a)=h(e1)=e2,故h(a-1)=h(a)-1。(3)c,d∈h(H),a,b∈证明题108.2
