欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

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

    • 资源ID:27238827       资源大小:381.72KB        全文页数:14页
    • 资源格式: PDF        下载积分:4.3金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要4.3金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

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

    编号题目答案题型分值大纲难度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 2给 定 连通 简 单 平 面图G=, 且 |V|=6, |E|=12, 则对于任意 fF, d(f)=3。答:因为|V|=63,且 G= V,E,F 是一个连通简单无向平面图,所以对任一 fF,deg(f)3。由欧拉公式 |V|-|E|+|F|=2可得|F|=8 。证明题10 6.4 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 14 页 - - - - - - - - - 再由公式Ffdeg(f)=2|E|,Ffdeg(f)=24 。因为对任一 fF,deg(f)3,故要使上述等式成立,对任一 fF,deg(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 4在一个连通简单无向平面图G= 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| 。再由欧拉公式|V|-|E|+|F|=2可得证明题10 6.4 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 14 页 - - - - - - - - - |V|-|E|+32|E|2。|E|3|V| 6。5设 G= 是连通的简单平面图,|V|=n3,面数为 k, 则 k 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 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)=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 。从而在半群 中, 关于运算 *存在单位元,记为e。证明题10 8.3 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 14 页 - - - - - - - - - 现证 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 关于运算的逆元。综上所述, 是一个群。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,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 8设 h 是从群 到的群同答:(1) 因为 h(e1)h(e1)=h(e1e1)= h(e1)= e2h(e1),所以 h(e1)=e2。证明题10 8.2 ;8.3 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 14 页 - - - - - - - - - 态, 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|。(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,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 的阶是无限的,则类似于上述证明过程可以得出,h(a) 的阶也是无限的。故结论成立。9设*是集合 A上可结合的二元运算,且a,bA,若 a*b=b*a,则 a=b。试证明:(1)a A,a*a=a,即 a 是等幂元;答:(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。证明题10 8.1 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 14 页 - - - - - - - - - (2)a,bA,a*b*a=a; (3)a,b,cA,a*b*c=a*c 。(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 。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*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 11R 是集合 X 上的一个自反关系,求证:R 是对称和传递的,当且仅当 和在 R 中有在 R 中。答: “”Xcba,若Rc, ab,a由 R对称性知Ra, ca,bc,bb,ac,ac,ba, ab,aa,bb, acb,ab,c, a即 R 是传递的。12f 和 g 都是群 到 的同态映射, 证明 是 的 一 个 子 群 。 其 中C=)()(|1xgxfGxx且1、 答:证Cba,,有)()(),()(bgbfagaf,又)()(,)()(1111bgbgbfbf)()()()(1111bgbgbfbfaf (agbgagbfafb()(*)()(*)()111)1baCb1 是 的子群。证明题10 8.2 ;8.3 4 13设 R 是 A 上一个二元关系,,(),(|,RbcRcaAcAbabaS且有对于某一个试证明若 R 是 A 上一个等价关系,则S 也是 A上的一个等价关系。答:(1)S 自反的Aa,由R 自反,),(),(RaaRaa,Saa,(2)S 对称的证明题10 4.4 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 14 页 - - - - - - - - - 传递对称定义RSabRRbcRcaSRbcRcaSbaAba,),(),(),(),(,S 传递的定义传递SScaRRcbRbaRceRebRbdRdaScbSbaAcba,),(),(),(),(),(),(,由(1) 、 (2) 、 (3)得; S 是等价关系。141)用反证法证明RSSQRPQP)()()(。2)用 CP 规则证明)()(),(SQPSQRRQP答: 1 证明:)(RSP(附加前提)RSTE QPP QPTE SQP SPTE PSTE )()(RPRSTI RPTI 证明题10 2.4 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 14 页 - - - - - - - - - RPP RPTE )(RPTE FTI 2、证明PP(附加前提))(RQPP RQTI )(SQRP )(SQQTI SQTE )(SQPCP 15设 , 是 半 群 , e是 左 幺 元 且AxAx?,,使得exx*?,则 是群。答: (1)cbcabaAcba则若*,cbcebecaabaacaabaaacaba:*,*)*?(*)*?()*(*?)*(*?*:即使事实上(2) e 是之幺元。事实上:由于e 是左幺元,现证e 是右幺元。证明题10 8.1 ;8.3 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 14 页 - - - - - - - - - 为右幺元即由使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) :cedfedfccbdaRfedcRdcba,则从而ebcecbcedafa,,Rfeba即 R 传递。综上得出, R 是等价关系。且证明题10 4.4 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 14 页 - - - - - - - - - 9 ,6,8 ,5,7,4,6, 3,5, 2,4, 13,25,5 ,2baAAbababaAAbabaR17试证明若,G是群,GH,且任意的Ha,对每一个Gx,有axxa,则,H是,G的子群。答 : 证 明 :( 1) 设 群,G的 幺 元 为e, 则Gx有xeex,He即 H 非空。(2)Hba,,则Gx有bxxbaxxa,,从而Hbabaxbxabxbbabbxbaxba11111111,)()()()()()(故,H是,G的子群。证明题10 8.1 ;8.3 5 18证明: 1)PQ ,Q R,R,S P= S 2)A(BC),C(D E),F(DE),A=BF 答:证明1):(1) R 前提(2) Q R 前提(3) Q (1) , (2)(4) P Q 前提(5) P (3) , (4)(6) SP 前提证明题10 2.4 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页,共 14 页 - - - - - - - - - (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) 、P Q , PR, QS = RS 2) 、(PQ)(RS),(QW) (SX),(W X),PR = P 答: 证明 1) :(1) R 附加前提(2) P R 前提(3) P (1) , (2)(4) PQ 前提(5) Q (3) , (4)(6) QS 前提(7) S (5) , (6)证明题10 2.4 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页,共 14 页 - - - - - - - - - (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 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) X (8) , (11)(14) WX (12) , (13)(15)(W X) 前提(16)(W X)(W X) (14) , (15)20证明: 答:证明 1):证明10 2.4 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页,共 14 页 - - - - - - - - - 1) 、 (UV) (MN), UP, P (QS),QS =M 2) 、 B D, (EF)D, E= B(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 前提(5) (EF) (3) , (4)(6) EF (5)(7) E (6)(8) E 前提(9) EE (7) , (8)题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页,共 14 页 - - - - - - - - -

    注意事项

    本文(2022年2022年离散数学题库证明题 .pdf)为本站会员(Che****ry)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

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

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

    收起
    展开