电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

离散数学-12参考答案

4页
  • 卖家[上传人]:豆浆
  • 文档编号:794586
  • 上传时间:2017-05-14
  • 文档格式:DOC
  • 文档大小:57.50KB
  • / 4 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、计算机学院 2004-2005 学年第一学期离散数学试题参考答案一、 选择题(每小题 1 分,共 10 分)1 下面哪个命题是命题“张三今天迟到或李四明天请假”的否定?(C )A. 张三今天迟到或李四明天不请假 B. 张三今天不迟到或李四明天不请假C. 张三今天不迟到且李四明天不请假 D. 不是张三今天不迟到就是李四明天不请假2 PQ 的逆反式是(D ) 。A.QP B. PQ C. QP D. Q P 3 下列各式中不是永真式的是(D ) )()()(. )()()( xxPxPABACcB4 设 A,B 是集合,且 A-B=,则有(B) BDCB.5 幂集( () = ( C )。A. , B. ,C. , D. ,6 设 R,S 是非空集合 A 上的等价关系,则 R S 的对称性(A)A.一定成立 B. 一定不成立 C. 不一定成立 D. 取决于 R 是否包含 S7 若 f:AB, g:BC 是两个函数,且复合函数 f g 是满射的,则( C ) 。A. f 必是满射 B. f 必是单射 C. g 必是满射 D. g 必是单射8 对于自然数集 N,下列哪种运算不是可结合的?( A

      2、 )A. a*b = a+2b B. a*b=a+b+3 C. a*b=min(a,b) D. a*b=ab (mod 4)9 群 G1=与群 G2=之间的关系是( D )A.同态 B.同构 C.G2 是 G1 的子群 D. A,B,C 都不对10 任何无向图中结点间的连通关系是一个( D ) 。A. 偏序关系 B. 相容关系 C. 拟序关系 D.等价关系第一题答题表题号 1 2 3 4 5 6 7 8 9 10A B C D 二、 判断题(每小题 1 分,共 10 分)1 命题“十减四等于五”是一个原子命题。 (Y)2 联结词“” (或非)是可结合的。 (N)3 同一个谓词公式在不同的论域上的真值不一定相同 。 (Y)4 A,B 是集合,则命题 可能同时成立。 (Y)BA,5 若 R,S 是集合 A 上的二元关系,则 t(R S)=t(R) t(S) (N)6 A 是有限集 , f: A A 是单射函数,则 f 是双射的。 (Y)7 设*是 S 上可结合的二元运算,a S,且 a 是可逆的,则 a 亦是可约的。 (Y)8 任何一个 Abel 群不一定是循环群 (Y)9 f 是群 G

      3、到群 H 的同态映射,若 G 是交换群,则 H 也是交换群 (N )10 若有向图 G 是个欧拉图,则 G 是一个强连通图 (Y)第二题答题表题号 1 2 3 4 5 6 7 8 9 10Y N 三、 演算题(共 40 分,以下第 1.、2.、3.小题每题 6 分,考生可任选答其中两题,若三题均做,则按每题 4 分计分;第 4.-7.题是必答题,每题 7 分)1 (6 分)设 A=a,b,c,c,a,b,B=a,b,b,计算 (1)AB; (2)AB; (3)(B)。2 (6 分)设集合 A = 1,2,3, A 上的关系 R = (1, 1), (1, 2), (2, 2), (2, 3), (3, 3),a) 写出 R 的关系矩阵;b) R 具有关系的哪些特性(自反、反自反、对称、反对称、传递)?(参考答案:a) .10b) R 具有反对称性和自反性 )3 (6 分)求公式 (P Q)( P Q) 的主析取范式和主合取范式。(答案:主析:( P Q) (P Q) 主合 :( P Q) (P Q)4 (7 分)设 A=1,2,3,4,6,12,R A2,且 R=| a 整除 b。a)

      4、 证明 R 是偏序的; (自反、反对称、可传递)b) 画出 R 的哈斯图;c) 给出集合2,3,4,6 的极小元、极大元、最小上界、最大下界。(答:小: 2, 3;大 4, 6;上: 12;下 1)5 (7 分)设 N 是自然数集合, f,g,h 是从 N 到 N 的函数,其中:是 奇 数是 偶 数nhngnf 0)(,)(,1)(给出 ff, fg, gf, hf, gh, hg, (fg) h。 (注: 是函数的复合运算)(答案: ff(n)=n+2, ( fg)(n)=2(n+1), gf(n)=2n+1: gh(n)=0, hg(n)=0(n 为偶数 )及2( n 为奇数) ; (fg) h( n) =0。 )6(7 分)设 Zn 为模 n 加群,f:Z 12Z 3, f(x)=(x mod 3),则 f 为同态映射。a) 验证 f 是否为单同态和满同态。b) 令 K=x|f(x)=0,计算 K。答:a)是满同态,因为 Z3 中每个元素 x 至少都有一个像源 x。该映射是保持运算的。即 Z12 中的任何 a, b,有:f(a+12b)=(a+12b )mod 3=a mod3

      5、+3 b mod3=f(a)+3 f(b)。b)K=0,3,6,97 (7 分)已知无向图 G 有 12 条边,1 度顶点有 2 个,2 度、3 度、5 度顶点各 1 个,其余顶点度数均为 4,求 4 度顶点的个数。.(答案: 3)四、 证明题(共 40 分。以下六小题每题 8 分,考生可以任选做其中五题。若六题全做,按前五题计分)1(8 分)用形式演绎法证明: P Q, P R, Q S, R (P Q)蕴涵 S .参考证明:证 : (1) P Q P(2) R (P Q) P(3) R (P Q) Q(2)(4) (P Q) R Q(3)(5) R Q(1)(4)(6) P R P(7) R P Q (6)(8) P Q(5)(7)(9) Q Q(1)(8)(10) Q S P(11) S Q(9)(10)所以 P Q, P R, Q S, R (P Q)蕴涵 S 2 (8 分)用数学归纳法证明:若 R 是集合 A 上的自反和传递关系,则对任意的n, Rn=R。(证明: n=1 时, R1=R。设 n=k 时, Rk=R。 Rk+1=Rk R=ROR=R2.设 R2,则存在c,式

      6、aRc,cRb,由于 R 是传递的,有 aRb。所以, R2R. 设 aRb,由于 R 是自反的, bRb,从而 aRORb,即 aR2b。所以 RR2。综合有 R2=R。进一步有 Rk+1=R。 )3 (8 分)设 ( A,*) 是一个半群,且对于 A 中的每个 a 和 b,若 a b,则 a*b b*a。证明: aA,有 a*a=a。( 证明:假设 a*a=b a, 由于 a 是半群,则可结合。从而, a*b=a*(a*a)=(a*a)*a=b*a,矛盾,所以, a*a=a) .4 (8 分)设 H 是群 G 的子群,证明:H 是 G 的正规子群的充要条件是: aG , aHa-1H.(证明 :“”设 H 是正规子群 ,则 aH=Ha.设 b aHa-1 ,h H, b=aha-1ba=ah aH=Ha,h H: ba=ah=ha (利用消去律 )b=h H aHa-1H. “”:设 a: aHa-1H, baH, hH, b=ah ba-1=aha-1 =h ( aHa-1H) b=haHa aHHa; bHa, hH, b=ha a-1b=a-1ha a-1b=h( a-1Ha

      7、H) b=ah aH HaaH; Ha=aH.即 H 是正规子群) 5 (8 分)设 G 是一个群, H, K 是群 G 的子群,证明:G 上的二元关系 R=| hH,kK,b=hak是一个等价关系。( 证明: H,K 均是子群, e 是 H,K 中元素。对于任意的 G 中元素 a,有: a=eae,即aRa. R 是自反的 。 设 aRb,由定义, hH, k K, b=hak, H,K 是子群,则 h-1H,k-1K, a=eae =h-1hakk-1= h-1(hak)k-1=h-1bk-1,从而, aRb。 R 也是对称的 。设 aRb,bRc 成立,则有 b=h1ak1,c=h2bk2,从而有 c=h2h1ak1k2, H,K 是子群,封闭性满足,存在h3=h2h1,H, k3=k1k2, K, 从而 c=h3ak3,即 aRc。 R 是传递的 。综合上述, R 是等价关系。 )6 (8 分)设 G=是简单无向连通图,但不是完全图,证明 G 中必存在三个结点u,v,wV,使得(u,v) E,(v,w) E,但(u,w) E。( 证明:因为 G 不是完全图,存在 u, wV, (u,w) E,由 G 是连通的,在 u, w 之间必有基本通路 L。设为 uv1v2vnw,n 1,若 n=1, v2=w,这样的话, u,v2,w 即是所求。若 n1,则 (u,v2) E,否则 L 就不是基本路径,令 v1=v,v2=w,这时, u,v,w 即为所求。 )

      《离散数学-12参考答案》由会员豆浆分享,可在线阅读,更多相关《离散数学-12参考答案》请在金锄头文库上搜索。

      点击阅读更多内容
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.