《离散数学证明题(共18页).doc》由会员分享,可在线阅读,更多相关《离散数学证明题(共18页).doc(18页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上编号题目答案题型分值大纲难度区分度1用先求主范式的方法证明(PQ)(PR) (P(QR)答:先求出左右两个公式 的主合取范式(PQ)(PR) (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.4332给定连通简单平面图G=,且|V|=6, |E|=12, 则对于任意fF, d(f)=3。答
2、:因为|V|=63,且G=V,E,F是一个连通简单无向平面图,所以对任一fF,deg(f)3。由欧拉公式|V|-|E|+|F|=2可得|F|=8。再由公式deg(f)=2|E|,deg(f)=24。因为对任一fF,deg(f)3,故要使上述等式成立, 对任一fF,deg(f)=3。证明题106.4333证明对于连通无向简单平面图,当边数e30时,必存在度数4的顶点。答:若结点个数小于等于3时,结论显然成立。当结点多于3 个时,用反证法证明。记|V|=n,|E|=m,|F|=k。假设图中所有结点的度数都大于等于5。由欧拉握手定理得deg(v)=2|E|得 5n2m。又因为G=V,E,F是一个连通
3、简单无向平面图,所以对每个面f,deg(f)3。由公式deg(f)=2|E|可得,2m3k。再由欧拉公式|V|-|E|+|F|=2可得2m-m+m=m从而30m,这与已知矛盾。证明题106.4334在一个连通简单无向平面图G=V,E,F中若|V|3,则 |E|3|V|6。答:|V|3,且G=V,E,F是一个连通简单无向平面图,d(f) 3,fF。由公式deg (f)=2|E|可得,2|E|3|F|。再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+|E|2。|E|3|V|6。证明题106.4335设G=是连通的简单平面图,|V|=n3,面数为k,则k2n-4。答:记|E|=m。因为G=
4、是连通的简单平面图,故每个面的度数都不小于3。从而由公式deg(f)=2|E|可得3k2m再由欧拉公式|V|-|E|+|F|=2有 m=n+k-2及 kn+k-2故 k2n-4。证明题106.4336在半群中,若对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*a=a。下证eL为关于运算*的左单位元。对bG,记方程a
5、*x=b的惟一解为x。是半群,运算*满足结合律。eL*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。b*c=c*b=e。从而c为b关于运算的逆元。 综上所述,是一个群。证明题108.3447设是一个群,H、K是其子群。定义G上的关系R:对任意a,bG,aRb 存在 hH,kK, 使得b=h*a*k,则R是G上的等价关系。答:aG,因为H、K是
6、G的子群,所以eH且eK。令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,则存在 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上的等价关系。证明题104.4338设h是从群到的群同态,G和G2的单位元分别为e1和
7、e2,则(1)h(e1)=e2;(2)aG1,h(a-1)=h(a)-1;(3)若HG1,则h(H)G2;(4) 若h为单一同态,则aG1,|h(a)|=|a|。答:(1) 因为h(e1)h(e1)=h(e1e1)= h(e1)= e2h(e1),所以h(e1)=e2。(2) aG1,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,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
8、)-1=h(a-1)且a-1H,故c-1h(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)的阶也是无限的。故结论成立。证明题108.2;8.3559设*是集合A上可结合的二元运算,且a,bA,若a*b=b*a,则a=b。试证明:(1)aA,a*a=a,即a是等幂元;(2)a,bA,a*b
9、*a=a;(3)a,b,cA,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,bA,因为由(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)。由(2)可
10、知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。证明题108.12210I上的二元运算*定义为:a,bI,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),从而*满足结合律
11、。(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=e=4-a+a-2=(4-a)*a。故4-a是a关于运算*的逆元。 综上所述,为群。证明题108.34411R是集合X上的一个自反关系,求证:R是对称和传递的,当且仅当 和在R中有在R中。答:“” 若 由R对称性知,由R传递性得 “” 若, 有 任意 ,因 若 所以R是对称的。若, 则 即R是传递的。证明题104.32212f和g都是群到的同态映射,证明是的一个子群。其中C=1、 答:证,有 ,又 是 的子群。证明题108.2;8.344
12、13设R是A上一个二元关系,试证明若R是A上一个等价关系,则S也是A上的一个等价关系。答:(1) S自反的,由R自反,(2) S对称的S传递的由(1)、(2)、(3)得;S是等价关系。证明题104.433141)用反证法证明。2)用CP规则证明答:1证明:P(附加前提)TEPTEPTETETITIPTETETI2、证明P(附加前提)PTIPTITE CP证明题102.45515设,是半群,e是左幺元且,使得,则是群。答:(1)(2) e 是之幺元。事实上:由于e是左幺元,现证e是右幺元。(3)由(2),(3)知:为群。证明题108.1;8.34416设,在上定义关系当且仅当,证明是上的等价关系
13、,并求出答:证明:1):即R自反。 2): 即,即R对称。 3): 从而 , 即 R传递。综上得出,R是等价关系。且证明题104.43317试证明若是群,且任意的,对每一个,有,则是的子群。答:证明:(1)设群的幺元为,则 有 ,即H非空。 (2),则 有 ,从而 故 是的子群。证明题108.1;8.35518证明:1)PQ,QR,R,SP=S2)A(BC),C(DE),F(DE),A=BF答:证明1):(1) R 前提(2) QR 前提(3) Q (1),(2)(4) PQ 前提(5) P (3),(4)(6) SP 前提(7) S (5),(6)证明2): (1) A 前提(2) A(BC
14、) 前提 (3) BC (1),(2)(4) B 附加前提(5) C (3),(4)(6) C(DE) 前提(7) DE (5),(6)(8) F(DE) 前提(9) F (7),(8) BF CP 证明题102.44419证明:1)、PQ, PR, QS = RS2)、(PQ)(RS),(QW)(SX),(WX),PR = P答: 证明1):(1) R 附加前提(2) PR 前提(3) P (1),(2)(4) PQ 前提(5) Q (3),(4)(6) QS 前提(7) S (5),(6)(8) RS CP,(1),(8)证明2): (1) P 假设前提(2) PR 前提(3) R (1)
15、,(2)(4) (PQ)(RS) 前提(5) PQ (4)(6) RS (5)(7) Q (1),(5)(8) S (3),(6)(9) (QW)(SX) 前提(10) QW (9)(11) SX (10)(12) W (7),(10)(13) X (8),(11)(14) WX (12),(13)(15) (WX) 前提(16) (WX)(WX) (14),(15)证明题102.45520证明:1)、(UV)(MN), UP, P(QS),QS =M2)、BD,(EF)D,E=B答:证明1):(1) QS 附加前提(2) P(QS) 前提 (3) P (1),(2)(4) UP 前提(5) U (3),(4)(6) UV (5)(7) (UV)(MN) 前提 (8) MN (6),(7)(9) M (8)证明2):(1) B 附加前提(2) BD 前提 (3) D (1),(2)(4) (EF)D 前提(5) (EF) (3),(4)(6) EF (5)(7) E (6)(8) E 前提(9) EE (7),(8)证明题102.433专心-专注-专业
限制150内