2022年2022年离散数学复习题题库-证明题 .pdf

上传人:Che****ry 文档编号:27232152 上传时间:2022-07-23 格式:PDF 页数:15 大小:390.10KB
返回 下载 相关 举报
2022年2022年离散数学复习题题库-证明题 .pdf_第1页
第1页 / 共15页
2022年2022年离散数学复习题题库-证明题 .pdf_第2页
第2页 / 共15页
点击查看更多>>
资源描述

《2022年2022年离散数学复习题题库-证明题 .pdf》由会员分享,可在线阅读,更多相关《2022年2022年离散数学复习题题库-证明题 .pdf(15页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、编号题目答案题型分值大纲难度区分度1用 先 求 主 范 式 的 方 法 证 明 (P Q)(PR) (P (Q R)答:先求出左右两个公式的主合取范式(PQ)(PR) (PQ)(PR) (PQ (RR)(P(QQ)R) (PQ R)(PQR)(PQ R)(PQ R) (PQR)(PQ R)(PQ R) (P (QR)) (P(QR )) (PQ)(PR) (PQ (RR)(P(QQ)R) (PQ R)(PQR)(PQ R)(PQ R) (PQR)(PQ R)(PQ R) 它们有一样的主合取范式,所以它们等价。证明题10 2.3 ;2.4 3 3 2给 定 连通 简 单 平 面图G=, 且 |V

2、|=6, |E|=12, 答:因为|V|=63,且 G= V,E,F 是一个连通简单无向平面图,所以对任一 fF,deg(f)3。证明题10 6.4 3 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 15 页 - - - - - - - - - 则对于任意 fF, d(f)=3。由欧拉公式 |V|-|E|+|F|=2可得|F|=8 。再由公式Ffdeg(f)=2|E|,Ffdeg(f)=24 。因为对任一 fF,deg(f)3,故要使上述等式成立,对任一 fF,de

3、g(f)=3 。3证明对于连通无向简单平面图,当边数 e30 时, 必存在度数 4 的顶点。答:若结点个数小于等于3 时,结论显然成立。当结点多于 3 个时,用反证法证明。记|V|=n,|E|=m,|F|=k。假设图中所有结点的度数都大于等于5。由欧拉握手定理得Vvdeg(v)=2|E| 得 5n2m 。又因为 G= V,E,F是一个连通简单无向平面图,所以对每个面 f,deg(f)3。由公式Ffdeg(f)=2|E|可得, 2m 3k。再由欧拉公式|V|-|E|+|F|=2可得252m-m+32m=151m 从而 30m,这与已知矛盾。证明题10 6.4 3 3 4在一个连通简单无向平面图G

4、= V,E,F中若 |V|3,则 |E|3|V| 6。答:|V|3,且 G= V,E,F是一个连通简单无向平面图,d(f) 3,fF。由公式Ffdeg (f)=2|E|可得, 2|E|3|F| 。证明题10 6.4 3 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 15 页 - - - - - - - - - 再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+32|E|2。|E|3|V| 6。5设 G= 是连通的简单平面图,|V|=n3,面数为 k, 则 k

5、 2n-4。答:记|E|=m。因为 G= 是连通的简单平面图, 故每个面的度数都不小于3。从而由公式Ffdeg(f)=2|E|可得 3k2m 再由欧拉公式 |V|-|E|+|F|=2有 m=n+k-2 及23kn+k-2 故 k2n-4。证明题10 6.4 3 3 6在 半 群 中 , 若 对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)=

6、y*a=b 。类似地,记方程 y*a=a 的唯一解为 eL。 即 eL*a=a。下证 eL为关于运算 *的左单位元。对bG ,记方程 a*x=b 的惟一解为 x。是半群,运算*满足结合律。eL*b=eL*(a*x)=(eL*a)*x=a*x=b 。证明题10 8.3 4 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 15 页 - - - - - - - - - 从而在半群 中, 关于运算 *存在单位元,记为e。现证 G中每个元素关于运算 *存在逆元。对bG ,记 c

7、 为方程 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 关于运算的逆元。综上所述, 是一个群。7设是一个群, H、K是其子群。定义 G上的关系 R:对任意 a,bG ,aRb 存 在h H,k K, 使 得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,b G ,若 aRb ,则存在 h H

8、 ,kK, 使得 b=h*a*k。因为 H 、 K是 G的子群, 所以 h-1H且 k-1K。 故 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*hH且 k*l K。从而 aRc。即 R是传递的。综上所述, R是 G上的等价关系。证明题10 4.4 3 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

9、师精心整理 - - - - - - - 第 4 页,共 15 页 - - - - - - - - - 8设 h 是从群 到的群同态, 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|。答:(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, 故

10、h(a-1)=h(a)-1。(3) c,d h(H),a,b H,使得 c=h(a),d=h(b)。故cd=h(a)h(b)=h(ab)。因为 H G ,所以 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 的

11、阶是无限的,则类似于上述证明过程可以得出,h(a) 的阶也是无限的。故结论成立。证明题10 8.2 ;8.3 5 5 9设*是集合 A上可结合的二元运算,且a,bA,若 a*b=b*a,则 a=b。试证明:答:(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), 证明题10 8.1 2 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -

12、 - - - - 第 5 页,共 15 页 - - - - - - - - - (1)a A,a*a=a,即 a 是等幂元;(2)a,bA,a*b*a=a; (3)a,b,cA,a*b*c=a*c 。(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=

13、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,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) ,从而 *满足结合律。(2)记 e=2。对aI ,a

14、*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 关于运算 *的逆元。综上所述, 为群。证明题10 8.3 4 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 15 页 - - - - - - - - - 11R 是集合 X 上的一个自反关系,求证:R 是对称和传递的,当且仅当 和在 R 中有在 R 中。答: “”Xcba,

15、若Rc,ab,a由 R对称性知Ra,ca,bc,bb,ac,ac,ba, ab,aa,bb, acb,ab,c,a即 R 是传递的。证明题10 4.3 2 2 12f 和 g 都是群 到 的同态映射, 证明 是 的 一 个 子 群 。 其 中C=)()(|1xgxfGxx且1、 答:证Cba,,有)()(),()(bgbfagaf,又)()(,)()(1111bgbgbfbf)()()()(1111bgbgbfbfaf (agbgagbfafb()(*)()(*)()111)1baCb1 是 的子群。证明题10 8.2 ;8.3 4 4 13设 R 是 A 上一个二元关系,,(),(|,Rbc

16、RcaAcAbabaS且有对于某一个答:(1)S 自反的Aa,由R 自反,),(),(RaaRaa,证明题10 4.4 3 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 15 页 - - - - - - - - - 试证明若 R 是 A 上一个等价关系,则S 也是 A上的一个等价关系。Saa,(2)S 对称的传递对称定义RSabRRbcRcaSRbcRcaSbaAba,),(),(),(),(,S 传递的定义传递SScaRRcbRbaRceRebRbdRdaScbS

17、baAcba,),(),(),(),(),(),(,由(1) 、 (2) 、 (3)得; S 是等价关系。141)用反证法证明RSSQRPQP)()()(。2)用 CP 规则证明)()(),(SQPSQRRQP答: 1 证明:)(RSP(附加前提)RSTE QPP QPTE SQP SPTE PSTE 证明题10 2.4 5 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 15 页 - - - - - - - - - )()(RPRSTI RPTI RPP RPTE

18、)(RPTE FTI 2、证明PP(附加前提))(RQPP RQTI )(SQRP )(SQQTI SQTE )(SQPCP 15设 , 是 半 群 , e是 左 幺 元 且AxAx?,,使得exx *?,则 是群。答: (1)cbcabaAcba则若*,证明题10 8.1 ;8.3 4 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 15 页 - - - - - - - - - cbcebecaabaacaabaaacaba:*,*)*?(*)*?()*(*?)*(

19、*?*:即使事实上(2) e 是之幺元。事实上:由于e 是左幺元,现证e 是右幺元。为右幺元即由使exexxxeeeexxexxxAexAx,*)1(*?*)*?()*(*?,*,(3)AxAx1,则xxexxxxexxxexexxxxxxxAx?*?*)*?(*)?*(:有逆元故有事实上由(2) , (3)知: 为群。16设9,3,2,1A,在AA上定义关系RdcbaR,:当且仅当cbda,证明R是AA上的等价关系,并求出?5 ,2R答:证明: 1) :,RbabaabbaAAba即 R 自反。2) :,bcadcbdaRdcba则即Rbadcadbc, 从而,即 R 对称。3) :证明题1

20、0 4.4 3 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 15 页 - - - - - - - - - cedfedfccbdaRfedcRdcba,则从而ebcecbcedafa,,Rfeba即 R 传递。综上得出, R 是等价关系。且9 ,6,8 , 5,7,4,6, 3,5, 2,4, 13,25,5 ,2baAAbababaAAbabaR17试证明若,G是群,GH,且任意的Ha,对每一个Gx,有axxa,则,H是,G的子群。答 : 证 明 :( 1)

21、设 群,G的 幺 元 为e, 则Gx有xeex,He即 H 非空。(2)Hba,,则Gx有bxxbaxxa,,从而Hbabaxbxabxbbabbxbaxba11111111,)()()()()()(故,H是,G的子群。证明题10 8.1 ;8.3 5 5 18证明: 答:证明1):证明10 2.4 4 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页,共 15 页 - - - - - - - - - 1)PQ ,Q R,R,S P= S 2)A(BC),C(D E),F

22、(DE),A=BF (1) R 前提(2) Q R 前提(3) Q (1) , (2)(4) P Q 前提(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(D E) 前提(7) D E (5) , (6)(8) F(DE) 前提(9) F (7) , (8) B F CP 题19证明: 答: 证明 1) :(1) R 附加前提证明题10 2.4 5 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - -

23、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页,共 15 页 - - - - - - - - - 1) 、P Q , PR, QS = RS 2) 、(PQ)(RS),(QW) (SX),(W X),PR = P (2) P R 前提(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) P R 前提(3) R (1) , (2)(4) (P Q)(RS) 前提(5) P Q (4)(6) R

24、 S (5)(7) Q (1) , (5)(8) S (3) , (6)(9) (Q W)(SX) 前提(10) QW (9)(11) SX (10)(12) W (7) , (10)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页,共 15 页 - - - - - - - - - (13) X (8) , (11)(14) WX (12) , (13)(15)(W X) 前提(16)(W X)(W X) (14) , (15)20证明: 1) 、 (UV) (MN), UP

25、, P (QS),QS =M 2) 、 B D, (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) B D 前提(3) D (1) , (2)(4) (EF)D 前提证明题10 2.4 3 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页,共 15 页 - - - - - - - - - (5) (EF) (3) , (4)(6) EF (5)(7) E (6)(8) E 前提(9) EE (7) , (8)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页,共 15 页 - - - - - - - - -

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 高考资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁