离散数学证明题(共18页).doc
精选优质文档-倾情为你奉上编号题目答案题型分值大纲难度区分度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,E,F>，且|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。因为对任一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是一个连通简单无向平面图，所以对每个面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,E>是连通的简单平面图，|V|=n3，面数为k,则k2n-4。答：记|E|=m。因为G=<V,E>是连通的简单平面图，故每个面的度数都不小于3。从而由公式deg(f)=2|E|可得3k2m再由欧拉公式|V|-|E|+|F|=2有 m=n+k-2及 kn+k-2故 k2n-4。证明题106.4336在半群<G,*>中，若对a,bG，方程a*x=b 和y*a=b都有惟一解，则<G,*>是一个群。答：任意取定aG，记方程a*x=a的惟一解为eR。即a*eR=a。下证eR为关于运算*的右单位元。对bG，记方程y*a=b的惟一解为y。<G,*>是半群，运算*满足结合律。b*eR=(y*a)*eR=y*(a*eR)=y*a=b。类似地，记方程y*a=a的唯一解为eL。即eL*a=a。下证eL为关于运算*的左单位元。对bG，记方程a*x=b的惟一解为x。<G,*>是半群，运算*满足结合律。eL*b=eL*(a*x)=(eL*a)*x=a*x=b。 从而在半群<G,*>中, 关于运算*存在单位元，记为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关于运算的逆元。 综上所述，<G,*>是一个群。证明题108.3447设<G,*>是一个群，H、K是其子群。定义G上的关系R：对任意a,bG，aRb ó存在 hH,kK, 使得b=h*a*k，则R是G上的等价关系。答：aG，因为H、K是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是从群<G1,>到<G2,>的群同态，G和G2的单位元分别为e1和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)-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*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）可知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。试证：<I,*>为群。答：（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=e=4-a+a-2=(4-a)*a。故4-a是a关于运算*的逆元。 综上所述，<I,*>为群。证明题108.34411R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当< a, b> 和<a , c>在R中有<.b , c>在R中。答：“” 若 由R对称性知，由R传递性得 “” 若， 有 任意 ，因 若 所以R是对称的。若， 则 即R是传递的。证明题104.32212f和g都是群<G1 ,>到< G2, *>的同态映射，证明<C , >是<G1, >的一个子群。其中C=1、 答：证，有 ，又 < C , > 是 < G1 , >的子群。证明题108.2；8.34413设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设<A,*>，是半群，e是左幺元且，使得，则<A , *>是群。答：（1）(2) e 是<A，*>之幺元。事实上：由于e是左幺元，现证e是右幺元。（3）由（2），（3）知：<A,*>为群。证明题108.1；8.34416设，在上定义关系当且仅当，证明是上的等价关系，并求出答：证明：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) 前提 (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），（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专心-专注-专业
