理工大学离散数学检测题答案24083.pdf

《理工大学离散数学检测题答案24083.pdf》由会员分享，可在线阅读，更多相关《理工大学离散数学检测题答案24083.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、-.z.*理工大学离散数学第一章检测题答案 一、填空题每空 2 分，共 30 分 1PQ2PQ 3，c。4()()()PQRPQRPQR，5()()PQPRS6QP 7()()PQQP 二、单项选择题每题 2 分，共 20 分 1 2 3 4 5 6 7 8 9 10 得分 D B C B C D A A C B 三、简答题每题 6 分，共 12 分 1构造命题公式)(RQP的真值表 P Q R QR()PQR 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 2求命题公式()PQRP

2、的主析取*式和主合取*式。3判断命题公式()()PQPR与 ()PQR是否等价。解：()()()()APQPRPQPR 等价 四证明题共 32 分 -.z.10 分用 CP 规则证明SQPSRQRQP),(),(；1.P P 6.)(SR T(4,5)I 2分 2.()PQR P 7.R T(3,4)I2分 3.QR T(1,2)I 2 分 8.S T(6,7)I2分 4.Q P(附加前提)9.)(SQ CP 2 分 5.)(SRQ P 10 分用归谬法证明 ,(),ABCB CSA 证:1 (AP 附加前提)1 分 2 ABP 3 1,2BT I 2 分 4 CBP 5 3,4CT I 2

3、分 6 CSP 7 6CT I 2 分 8 5,7CCTI 2 分 由 8 得出了矛盾，根据归谬法说明原推理正确1 分 3 12 分公安人员审理*珠宝商店的钻石项链的失窃案，侦察结果如下：1营业员A或B盗窃了钻石项链 2假设B作案，则作案时间不在营业时间 3假设A提供的证词正确，则货柜未上锁 4假设A提供的证词不正确，则作案发生在营业时间 5货柜上了锁 试问：作案者是谁？要求写出推理过程。-.z.解：令A表示“营业员A盗窃了钻石项链；B表示“营业员B盗窃了钻石项链；P表示“作案时间在营业时间；Q表示“A提供的证词正确；R表示“货柜上了锁。则侦察结果如下：AB，BP，QR，QP，R由此可推出作案

4、者是A 4 分 推理过程如下：(1)R P (6)BPP(2)QR P (7)BT(5)，(6)I2 分(3)QT(1)，(2)I2 分(8)ABP(4)QPP (9)A T(7)，(8)I2 分(5)P T(3)，(4)I2 分*理工大学离散数学第二章检测题答案 一、填空题每空 3 分，共 30 分 1()()()()()()x G xF xx F xG x 或()()()()()()x G xF xy F yG y 2()()()()(,)(,)(,)xzwP xR x wQ z yR x w 3()()()()()()P aP bP cQ aQ bQ c 4)()()()()()(cPb

5、PaPcPbPaP5(),()()(,)P xxyP x y 6,x y；y 7()(,)P xyR x y8()()()xF xG x 二、单项选择题每题 2 分，共 20 分 1 2 3 4 5 6 7 8 9 10 得分-.z.A A B D C A C C B D 三、简答题每题 6 分，共 12 分 1求謂词公式),()()()(),()()(zyQzyPyyxQxPx的前束析取*式 2证明：()()()()x P xQ xxP xxQ x 证：四证明题共 38 分 1 12 分用谓词演算的推理规则证明:)()(xQxPx，)()()(xSxRxQx，)(aP)(aR)(aS 1)(

6、)(xQxPxP 2)()(aQaP)1(US 2 分 3)(aP)(aRP 4)(aQ)3)(2(TI 2 分 5)()()(xSxRxQxP 6)()()(aSaRaQ)5(US 2 分 7)(aR)3(T I 2 分 8)()(aRaQ)7)(4(TI 2 分 9)(aS)8)(6(TI 2 分 2(10分)指出下面推理证明过程中的错误，并给出正确的证明 用谓词演算的推理规则证明：证:：(1)()(xRxQx P (6)(aZ T(4)I (2)()(aRaQ US(1)(7)(aR T(2),(5)I (3)()(xZxQx P (8)()(aZaR T(6),(7)I-.z.(4)(

7、)(aZaQ ES(3)(9)()(xZxRx EG(8)(5)(aQ T(4)I 该证明的错误在于:(1)、(2)与(3)、(4)的顺序颠倒了，应该先指定存在后指定全称。2 分正确的证明是：4 分(1)()(xZxQx P (6)(aZ T(2)I 1 分 (2)()(aZaQ ES(1)2 分(7)(aR T(4),(5)I 1分(3)()(xRxQx P (8)()(aZaR T(6),(7)I 1分(4)()(aRaQ US(3)2 分(9)()(xZxRx EG(8)1 分 (5)(aQ T(2)I 3 16 分符号化以下命题并推证其结论 任何人如果他喜欢音乐,他就不喜欢体育每个人或

8、者喜欢体育，或者喜欢美术有的人不喜欢美术因而有的人不喜欢音乐 设 M(*)：*喜欢音乐，S(*)：*喜欢体育，(*)：喜欢美术 该推理符号化为：()()()()()()x M xS xx S xA xx A xx M x 或 前提：()(),()(),()x M xS xx S xA xx A x 结论：()x M x 4 分证：1()x A x P 2()A a ES1 2 分 3()()x S xA x P 4()()S aA a US3 2 分 5()S a T2 4I2 分 6()()x M xS x P-.z.7()()M aS a US6 2 分 8()()S aM a T7E 1

9、 分 9()M a T5 8I2 分 10()x M x EG9 1 分*理工大学离散数学第三、四章检测题答案 一、填空题每空 2 分，共 40 分 1 2nn ,3,a b c 4反对称，传递。51RR；1iiR6AI，100010001或单位矩阵 7 4,6 ，2,3 ，无 ，无 ，12 ，1 。8 1f,0,1,2f,1,0。9单射，满射；既是单射又是满射；BI；AI 二、单项选择题每题 2 分，共 20 分 1 2 3 4 5 6 7 8 9 10 得分(1)(2)(1)(3)2 2(1)(3)(3)(1)三、简答题共 30 分 1 6 分设A=1,2,3,5,6,10,15,30，“

10、为集合A上的整除关系。A，是否为偏序集 假设是，画出其哈斯图；解：A，是偏序集。其哈斯图为：2 12 分对以下图所给的偏序集,A，求下表所列集合的上下界，上下确界，并将结果填入表中。子 集 上 界 下 界 上 确 界 下 确 界 ,a b c a d a d ,c d e,a c 无 c 无 A a 无 a 无 3 6 分设 A=1,2,3,4,5,6，集合A上的关系 R=1,3,1,5,2,5,4,4,4,5,5,4,6,3,6,6。1画出R的关系图，并求它的关系矩阵；-.z.2求(),()r R S R及()t R。解：1R的关系图为 R的关系矩阵为 1001000010000110000

11、00000010000010100RM 2 分 2()1,1,2,2,3,3,5,5r RR，1 分()3,1,5,1,5,2,3,6S RR 1 分()1,4,2,4,5,5t RR 2 分 4设Z是整数集，R是Z上的模 3 同余关系，即,(mod3)Rx y x yZ xy，试根据等价关系R决定Z的一个划分。答案：由R决定的Z的划分为：2,1,0RRR，其中：四证明题共 10 分 设,baRba 定义 1,0,:baf为 abaxxf)(，证明：f是双射，并求出其逆映射。证：1先证明f是入射2 分 对任意的),()(,2121xfxfbaxx若则有abaxabax21，从而有21xx，故f

12、是入射。2)再证明f是满射2 分 对任意的,)(,)(,1,0yxfbaayabxy使得都存在从而f是满射。综合1、2知f是双射。,1,0:1baf为 axabxf)()(1，对任意 1,0 x。1 分*理工大学离散数学第五章检测题答案-.z.一、填空题每空 2 分，共 30 分 1.11ba 2a3,S S 4a；1 5S关于运算不封闭 6 2，14aa7 循环群，生成元 8 12 12 11 12 9B关于封闭 二、单项选择题每题 2 分，共 20 分 1 2 3 4 5 6 7 8 9 10 得分 B C A A B D D C B D 三、简答题共 30 分 1设是实数集R上的二元运算

13、，其定义如下：1求 23，3(-5)和 71/2。2,R 是半群吗？可交换吗？3求R中关于的单位元。4R中哪些元素有逆元素，其逆元素是什么？答案：117，-32，14.5。2,R 是半群，可交换。30。4当,1/2aR a 时，a有逆元素，1/(1 2)aaa。2设,Aa b c d，,A 是交换群，a是,A 的单位元。的运算表如下：abcd abcd abcd 12baxx 43cxax 56dxxa 求123456,x xx xx x，并说明道理。答案：123456,xd xc xb xd xc xb。因为有限群的运算表中的每行、每列都是群中元素的一个置换。3设集合1,3,4,5,9G，是

14、定义在G上的模 11 乘法即任意a,bG，有-.z.a*b=(ab)(mod11)，是普通乘法，问,G 是循环群吗？假设是，试找出它的生成元。答：,G 的运算表如下表所示。1 3 4 5 9 1 3 4 5 9 1 3 4 5 9 3 9 1 4 5 4 1 5 9 3 5 4 9 3 1 9 5 3 1 4 从运算表可知，在G上封闭、有幺元 1，且5143213,33,43,53,93，再由是可结合的得,G 是循环群，3，4，5 和 9 均为其生成元。四证明题共20 分 4 分设,G 是独异点，e为其幺元，且对aG，有a ae，证明,G 是一个交换群。证明：对aG，由于a ae，则 1aa，

15、即G中的每一个元素a都有逆元素,故,G 是一个群。又对,a bG，有 111()a babb ab a，所以,G 是一个 Abel 群。6 分设,G 是一个群，aG，:f GG，xG，有 试证明f是,G 一个自同构 证：首先证明f是入射。3 分 其次证明f是满射。对1,(),yGxay aGyf xf 都存在使得因此 是满射.-.z.综合以上两点，知f是双射。3 分*理工大学离散数学第六章检测题答案 一、填空题每空 2 分，共 40 分 1.上确界 和下确界，a，b 2至少有一个补元素，不一定30，1；1，0 41,0aaaa5ab；ab 6 nAA，2nA 二、单项选择题每题 2 分，共 2

16、0 分 1 2 3 4 5 6 7 8 9 10 得分 D C B C A D A B D D 三、简答题共 30 分 1下面哈斯图表示的格中哪个元素无补元？对有补元的元素求出它们的补元 解：c 无补元1 分，a 的补元为 e1 分，b 的补元为 d1 分，d 的补元为 b、e1 分，e 的补元为 a、d1 分，0 与 1 互为补元。1 分 2设,0,1B 是一个布尔代数且0,1Ba b，求布尔表达式 的析取*式和合取*式并计算(1)f ba,的值。解：123()f x xx,的析取*式为：123123123123()()()()xxxxxxxxxbxxx4分 123()f x xx,的合取*

17、式为：123123123123123()()()()()xxxxxxxxxxxxbxxx4分(1)f bab,2 分 3设A=1,2,3,5,6,10,15,30，“为集合A上的整除关系。(1)A，是否为偏序集 假设是，画出其哈斯图；(2)A，是否构成格？为什么？(3)A，是否构成布尔代数？为什么？解：(1)A，是偏序集。其哈斯图为：(2)A，构成格。因为其任意两个元素都有上确界和下确界。(3)A，构成布尔代数。因为它是有界分配格，且其任意 元素都有唯一补元素。-.z.四证明题共 10 分 4 分设,G 是独异点，e为其幺元，且对aG，有a ae，证明,G 是一个交换群。证明：对aG，由于a

18、ae，则 1aa，即G中的每一个元素a都有逆元素,故,G 是一个群。又对,a bG，有 111()a babb ab a，所以,G 是一个 Abel 群。6 分设,G 是一个群，aG，:f GG，xG，有 试证明f是,G 一个自同构 证：首先证明f是入射。3 分 其次证明f是满射。对1,(),yGxay aGyf xf 都存在使得因此 是满射.综合以上两点，知f是双射。3 分 离散数学第七章检测题答案 一、单项选择题每题 2 分，共 20 分 1 2 3 4 5 6 7 8 9 10 得分 2 4 2 4 3 2 4 2 1 3 二、填空题每空 3 分，共 45 分 1 4 ，3 。2 _0_

19、，_1_。_0_，_0_。3(2121,VV VV 4 2 E ，偶数 。5_5_；_9_。6 3 ，1 。77。三、简答题每题 5 分，共 25 分-.z.1对有向图,GV E求解以下问题：1写出邻接矩阵A；2,GV E中长度为 3 的不同的路有几条？其中不同的回路有几条？解：1邻接矩阵为：0100100100000011100000010A，22300110110010000100010,000101100001101001111100001101AA 则，,GV E中长度为 3 的不同的路有 10 条，其中有 1 条不同的回路。2设有盏灯，拟公用一个电源，求至少需要插头的接线板的数目。解

20、：设至少需要 4 插头的接线板 i 个，则有 4-1i=28-1 3 分 故 i=9 即至少需要 9 个 4 插头的接线板。2 分 3设有 6 个城市 V1，V2，V6，它们之间有输油管连通，其布置如以下图,Si(数字)中 Si为边的编号，括号内数字为边的权，它是两城市间的距离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供给最少需多少连士兵看守输油管道总长度越短，士兵越好防守。求他们看守的最短管道的长度。(要求写出求解过程)解：为保证每个城市石油的正常供给最少需 5 连士兵看守.求看守的最短管道相当于求图 的最小生成树问题，此图的最小生成树为：因此看守的最短管道

21、的长度为：1222 4以给定权 1,4,9,16,25,36,49,64,81,100 构造一棵最优二叉树。5一次学术会议的理事会共有 20 个人参加，他们之间有的相互认识，但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于 20，说明能否把这 20 个人排在圆桌旁，使得任意一个人认识其旁边的两个人？根据是什么？解：可以把这 20 个人排在圆桌旁，使得任意一个人认识其旁边的两个人。1 分 根据是：分别用 20 个结点代表这 20 个人，将相互认识的人之间连一条线，便得到一个 无向简单图,GV E，每个结点ivV的度数是与iv认识的人的数目，由题意知-.z.,ijv vV，有deg()deg()20ijvv，于 是,GV E中 存 在 哈 密 尔 顿 回 路，设12201iiiiCv vv v是,GV E中的一条哈密尔顿回路，按此回路安排园桌座位即符合要求。4 分 四证明与应用题10 分 1*次聚会的成员到会后相互握手，试用图论的知识说明与奇数个人握手的人数一定是一个偶数。证:用结点代表成员,握手的成员之间连一条线,则所有聚会的成员之间的握手情况可以用一个图来表示，其中每个结点的度数就是该结点所代表的成员握手的人数,由于任一图中奇数度结点的个数为偶数,所以与奇数个人握手的人数一定是一个偶数。