2022年2022年离散数学形考任务-试题及答案完整版 .pdf

2017 年 11 月上交的离散数学形考任务一本课程的教学内容分为三个单元，其中第三单元的名称是（A ）选择一项：A. 数理逻辑B. 集合论C. 图论D. 谓词逻辑题目2答案已保存满分 10.00 标记题目题干本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第 2 章关系与函数中的第3 个知识点的名称是（D ）选择一项：A. 函数B. 关系的概念及其运算C. 关系的性质与闭包运算D. 几个重要关系题目3答案已保存满分 10.00 标记题目题干本课程所有教学内容的电视视频讲解集中在VOD 点播版块中， VOD 点播版块中共有 （B）讲选择一项：A. 18 B. 20 C. 19 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 29 页 - - - - - - - - - D. 17 题目4答案已保存满分 10.00 标记题目题干本课程安排了7 次形成性考核作业，第3 次形成性考核作业的名称是（ C）选择一项：A. 集合恒等式与等价关系的判定B. 图论部分书面作业C. 集合论部分书面作业D. 网上学习问答题目5答案已保存满分 10.00 标记题目题干课程学习平台左侧第1 个版块名称是：（C）选择一项：A. 课程导学B. 课程公告C. 课程信息D. 使用帮助题目6答案已保存满分 10.00 标记题目题干课程学习平台右侧第5 个版块名称是：（D）选择一项：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 29 页 - - - - - - - - - A. 典型例题B. 视频课堂C. VOD 点播D. 常见问题题目7答案已保存满分 10.00 标记题目题干 教学活动资料 版块是课程学习平台右侧的第（A）个版块选择一项：A. 6 B. 7 C. 8 D. 9 题目8答案已保存满分 10.00 标记题目题干课程学习平台中 课程复习 版块下，放有本课程历年考试试卷的栏目名称是：（D ）选择一项：A. 复习指导B. 视频C. 课件D. 自测请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排 ，字数要求在100500 字完成后在下列文本框中提交解答：学习计划学习离散数学任务目标：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 29 页 - - - - - - - - - 其一是通过学习离散数学，使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理，掌握计算机中常用的科学论证方法，为后续课程的学习奠定一个良好的数学基础；其二是在离散数学的学习过程中，培养自学能力、抽象思维能力和逻辑推理能力，解决实际问题的能力，以提高专业理论水平。其三是初步掌握处理离散结构所必须的描述工具和方法离散数学的主要内容：第一章节：主要介绍集合及其运算第二章节：主要介绍关系与函数第三章节：主要介绍图的基本概念及性质第四章节：主要介绍几种特殊图第五章节：主要介绍树及其应用第六章节：主要介绍命题逻辑第七章节：主要介绍谓词逻辑离散数学的考核方式分为：了解、理解和掌握。了解是能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。离散数学形考任务二若集合 Aa,a,1,2Aa,a,1,2 ，则下列表述正确的是( C )选择一项：A.a,a Aa,aAB.1，2?A 1，2?AC.a ? Aa? AD. ?A ?A题目2答案已保存满分 10.00 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 29 页 - - - - - - - - - 标记题目题干设集合 A=1, 2, 3 ，B=3, 4, 5 ，C=5, 6, 7 ，则 AB C =( A)选择一项：A. 1, 2, 3, 4 B. 1, 2, 3, 5 C. 2, 3, 4, 5D. 4, 5, 6, 7题目3答案已保存满分 10.00 标记题目题干设集合 A = 1,aa，则 P(A) = ( D )选择一项：A. 1, aaB. ? ,1, aaC. 1,a,1,a1,a,1,a D. ? ,1,a,1,a?,1,a,1,a 题目4答案已保存满分 10.00 标记题目题干集合 A=1, 2, 3, 4, 5, 6, 7, 8 上的关系 R=|x+y=10 且 x, yA，则 R 的性质为（ B）选择一项：A. 自反的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 29 页 - - - - - - - - - B. 对称的C. 传递且对称的D. 反自反且传递的题目5答案已保存满分 10.00 标记题目题干如果 R1和 R2是 A 上的自反关系，则 R1R2， R1 R2， R1-R2中自反关系有（ B ）个选择一项：A. 0 B. 2 C. 1 D. 3 题目6答案已保存满分 10.00 标记题目题干设 A=1, 2, 3, 4, 5, 6, 7, 8 ，R 是 A 上的整除关系， B=2, 4, 6 ，则集合 B 的最大元、最小元、上界、下界依次为 ( D )选择一项：A. 8、2、8、2B. 8、1、6、1C. 6、2、6、2D. 无、2、无、 2题目7答案已保存满分 10.00 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 29 页 - - - - - - - - - 标记题目题干设集合 A=2, 4, 6, 8 ，B=1, 3, 5, 7 ，A 到 B 的关系 R=| y = x +1 ，则 R= ( A )选择一项：A. , , B. , , C. , , D. , , 题目8答案已保存满分 10.00 标记题目题干设集合 A =1 , 2, 3 上的函数分别为： ?= ， ， g = ， ， ，h = ， ， ，则 h =（ A ）选择一项：A. ?gB. g?C. ?D. g?g题目9答案已保存满分 10.00 标记题目题干设 A、B 是两个任意集合，侧A-B = ? ? ? ( B)选择一项：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 29 页 - - - - - - - - - A. A = B B. A ? B C. A ? B D. B = ? ?题目10答案已保存满分 10.00 标记题目题干设集合 A=1， 2，3，4，5，偏序关系 是 A 上的整除关系，则偏序集上的元素5是集合 A 的（C）选择一项：A. 最大元B. 最小元C. 极大元D. 极小元离散数学作业3离散数学集合论部分形成性考核书面作业一、填空题1 设集合1, 2, 3,1, 2AB， 则 P(A)- P(B )=3 ， 1,3 ， 2,3 ， 1,2,3 ，A B=, 2设集合 A 有 10 个元素，那么 A 的幂集合 P(A)的元素个数为 1024 3设集合 A=0, 1, 2, 3，B=2, 3, 4, 5 ，R是 A 到 B 的二元关系，则 R的有序对集合为 ，4设集合 A=1, 2, 3, 4 ，B=6, 8, 12 ，A 到 B 的二元关系R,2,ByAxxyyx那么 R1, ,BAyxByAxyxR且且名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 29 页 - - - - - - - - - 5设集合 A=a,b,c,d，A 上的二元关系 R=, , , ，则R 具有的性质是没有任何性质6 设集合 A= a,b,c,d ， A 上的二元关系 R=, , , ，若在 R中再增加两个元素,，则新得到的关系就具有对称性7如果 R1和 R2是 A 上的自反关系，则 R1R2，R1R2，R1- R2中自反关系有2 个8设 A=1,2 上的二元关系为 R=|x A，y A,x+y=10，则 R 的自反闭包为, 9设 R是集合 A 上的等价关系，且1 , 2 , 3是 A 中的元素，则 R 中至少包含,等元素10设集合 A=1, 2 ，B=a, b ，那么集合 A 到 B 的双射函数是 , 或, 二、判断说明题 （判断下列各题，并说明理由）1若集合 A = 1，2，3上的二元关系 R=，则(1) R是自反的关系；(2) R是对称的关系解：（ 1）错误。 R 不具有自反的关系，因为不属于 R。（2）错误。 R 不具有对称的关系，因为不属于 R。2如果 R1和 R2是 A 上的自反关系，判断结论：“R-11、R1R2、R1 R2是自反的”是否成立？并说明理由解：成立因为 R1和 R2是 A 上的自反关系，即IAR1，IAR2。由逆关系定义和IAR1，得 IA R1-1；由 IAR1，IAR2，得 IA R1R2，IA R1R2。所以， R1-1、R1R2、R1R2是自反的。3若偏序集 的哈斯图如图一所示，则集合 A 的最大元为 a，最小元不存在解：错误集合 A 的最大元不存在， a 是极大元4 设集合 A=1,2,3,4 ， B=2, 4, 6, 8 ， ， 判断下列关系 f 是否构成函数 f：BA，并说明理由(1) f=, ；(2)f=, ；(3) f=, 解：（1）不构成函数。因为对于3 属于 A，在 B 中没有元素与之对应。（2）不构成函数。因为对于4 属于 A，在 B 中没有元素与之对应。a b c d 图一g e f h 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 29 页 - - - - - - - - - （3）构成函数。因为A 中任意一个元素都有A 中唯一的元素相对应。三、计算题1设4,2,5,2, 1,4, 1,5,4,3,2,1CBAE，求：(1) (AB)C；(2) (A B)- (BA) (3) P(A)P(C)；(4) AB解：(1) (AB)C=1 1,3,5=1,3,5 (2) (AB)- (BA)=1,2,4,5-1=2,4,5 (3) P(A) = ,1,4,1,4 P(C)= ,2,4,2,4 P(A)P(C)=1,1,4 (4) AB= (AB)- (BA)= 2,4,5 2设 A=1,2,1,2，B=1,2,1,2 ，试计算（1）（A B）；（ 2）（AB）；（ 3）AB解：（1）A B =1,2 （2）AB =1,2 （3）AB= ， ， ， ， ， ， ，, 3设 A=1，2，3，4，5，R=|x A，y A 且 x+y 4，S=|x A，y A 且 x+y0，试求 R，S，R S，S R，R-1，S-1，r(S)，s(R)解：R=, S=空集R*S=空集S*R=空集R-1=,S-1 =空集r(S)= s(R)= 4设 A=1,2,3,4,5,6,7,8，R是 A 上的整除关系， B=2,4, 6 (1) 写出关系 R的表示式；(2 )画出关系 R的哈斯图；(3) 求出集合 B 的最大元、最小元解：(1)R= (3)集合 B 没有最大元，最小元是2 (2)关系 R 的唯斯图四、证明题1 2 5 6 4 10 7 3 8 9 11 12 关系 R的哈斯图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 29 页 - - - - - - - - - 1试证明集合等式： A (BC)=(A B) (AC)证明 ：设，若 xA (BC)，则 xA 或 xBC，即 xA 或 xB 且 xA 或 xC即 xAB 且 xAC ，即 xT=(AB) (AC)，所以 A (BC) (AB) (AC)反之，若 x(AB) (AC)，则 xAB 且 xAC，即 xA 或 xB 且 xA 或 xC，即 xA 或 xBC，即 xA (BC)，所以(AB) (AC) A (BC)因此 A (BC)=(AB) (AC)2试证明集合等式A (BC)=(AB) (A C)证明：设 S=A(BC)，T=(AB)(AC)，若 xS，则 xA 且 xBC，即 xA 且 xB 或 xA 且 xC，也即 xAB 或 xAC ，即 xT，所以 S T反之，若 xT，则 xAB 或 xAC，即 xA 且 xB 或 xA 且 xC 也即 xA 且 xBC，即 xS，所以 TS因此 T=S3对任意三个集合 A, B 和 C，试证明： 若 AB = AC，且 A，则 B = C证明：（1） 对于任意 AB，其中 aA，bB,因为 AB= AC ，必有AC,其中 b C因此 B C （2）同理，对于任意 AC,其中， aA，cC，因为 AB= AC必有AB，其中 cB，因此 C B有（1）（2）得 B=C 4试证明：若 R与 S是集合 A 上的自反关系，则R S也是集合 A 上的自反关系证明：若 R 与 S 是集合 A 上的自反关系，则任意xA,x,x R, x,x S, 从而 x,x R S,注意 x 是 A的任意元素，所以R S 也是集合 A上的自反关系名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 29 页 - - - - - - - - - 离散数学形考任务四设无向图 G 的邻接矩阵为，则 G 的边数为 ( B )选择一项：A. 6 B. 5 C. 4 D. 3 题目2答案已保存满分 10.00 标记题目题干如图一所示，以下说法正确的是( D) 选择一项：A. ( a,ea,e) 是割边B. ( a,ea,e) 是边割集C. (a,e),(b,c)(a,e),(b,c) 是边割集D. ( d,ed,e) 是边割集题目3答案已保存满分 10.00 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 29 页 - - - - - - - - - 标记题目题干如图三所示，以下说法正确的是( C) 选择一项：A. ( a,da,d) 是割边B. ( a,da,d) 是边割集C. (a,d),(b,d) (a,d),(b,d) 是边割集D. ( b,db,d) 是边割集题目4答案已保存满分 10.00 标记题目题干无向图 G存在欧拉回路，当且仅当（C ）.选择一项：A. G 中所有结点的度数全为偶数B. G 中至多有两个奇数度结点C. G 连通且所有结点的度数全为偶数D. G 连通且至多有两个奇数度结点题目5答案已保存满分 10.00 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 29 页 - - - - - - - - - 标记题目题干若 G 是一个欧拉图，则G 一定是 ( C )选择一项：A. 平面图B. 汉密尔顿图C. 连通图D. 对偶图题目6答案已保存满分 10.00 标记题目题干无向树 T 有 8 个结点，则T 的边数为 ( B )选择一项：A. 6 B. 7 C. 8 D. 9 题目7答案已保存满分 10.00标记题目题干已知一棵无向树T 中有 8 个顶点， 4 度、 3 度、 2 度的分支点各一个，T 的树叶数为 ( A)选择一项：A. 5 B. 8 C. 3 D. 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 29 页 - - - - - - - - - 题目8答案已保存满分 10.00 标记题目题干设无向图G 的邻接矩阵为，则 G 的边数为 ( C )选择一项：A. 1 B. 6 C. 7 D. 14 题目9答案已保存满分 10.00 标记题目题干设有向图（ a）、（ b）、（ c）与（ d）如图所示，则下列结论成立的是( D )选择一项：A. （a）只是弱连通的B. （b）只是弱连通的C. （c）只是弱连通的D. （d）只是弱连通的题目10答案已保存满分 10.00 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 29 页 - - - - - - - - - 标记题目题干以下结论正确的是( D )选择一项：A. 无向完全图都是欧拉图B. 有 n 个结点 n1 条边的无向图都是树C. 无向完全图都是平面图D. 树的每条边都是割边离散数学作业5 离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3 次， 内容主要分别是集合论部分、 图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果， 找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。要求：将此作业用 A4 纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求 2010 年 12 月 5 日前完成并上交任课教师（不收电子稿）。并在05 任务界面下方点击“保存”和“交卷”按钮，以便教师评分。一、填空题1已知图 G 中有 1 个 1 度结点，2 个 2 度结点， 3 个 3 度结点， 4 个 4 度结点，则 G 的边数是 152设给定图 G(如右由图所示 )，则图 G 的点割集是fce,3设 G 是一个图，结点集合为V，边集合为 E，则G 的结点度数之和等于边数的两倍4无向图 G 存在欧拉回路，当且仅当G 连通且不含奇数度结点5设 G=是具有 n 个结点的简单图，若在G 中每一对结点度数之和大于等于 V，则在 G 中存在一条汉密尔顿回路6 若图 G=中具有一条汉密尔顿回路， 则对于结点集 V的每个非空子集 S，在 G 中删除 S中的所有结点得到的连通分支数为W，则 S中结点数 |S|与 W满足名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 29 页 - - - - - - - - - 的关系式为SW7设完全图 Kn有 n 个结点 (n 2)，m 条边，当 n 为奇数时， Kn中存在欧拉回路8结点数 v 与边数 e满足 e=v1关系的无向连通图就是树9设图 G 是有 6 个结点的连通图，结点的总度数为18，则可从 G 中删去条边后使之变成树10设正则 5 叉树的树叶数为 17，则分支数为 i = 4 二、判断说明题 （判断下列各题，并说明理由）1 如果图 G 是无向图，且其结点度数均为偶数， 则图 G存在一条欧拉回路答：错误。应叙述为： “如果图 G 是无向连通图，且其结点度数均为偶数，则图 G 存在一条欧拉回路。”2如下图所示的图G 存在一条欧拉回路答：错误。因为图中存在奇数度结点，所以不存在欧拉回路。3如下图所示的图G 不是欧拉图而是汉密尔顿图答：正确。因为有 4个结点的度数为奇数，所以不是欧拉图；而对于图中任意点集V中的非空子集1V ， 都有)(1VGPV1。 其中)(1VGP是从图中删除1V结点及其关联的边。4设 G 是一个有 7 个结点 16条边的连通图，则G 为平面图答：错误。若 G 是连通平面图，那么若63, 3vev就有，而 16376，所以不满足定理条件，叙述错误。5设 G 是一个连通平面图，且有6个结点 11条边，则 G 有 7 个面答：正确。因为连通平面图满足欧拉公式。即：2rev。由此题条件知6-11+7=2 成立。G名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 29 页 - - - - - - - - - 三、计算题1设 G=，V= v1，v2，v3，v4，v5 ，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，试(1) 给出 G 的图形表示；(2) 写出其邻接矩阵；(3) 求出每个结点的度数；(4) 画出其补图的图形答：（ 1）1v 2v3v4v 5v（2）0110010110110110110000100)(DA（3）)deg(1v1、)deg(2v2、)deg(3v4、)deg(4v3、)deg(5v2 （4）1v2v 3v4v 5v2 图 G=， 其中 V= a, b, c,d,e ， E= (a, b), (a, c), (a, e), (b, d),(b, e), (c, e), (c, d), (d, e) ，对应边的权值依次为2、1、2、3、6、1、4 及 5，试（1）画出 G 的图形； （2）写出 G 的邻接矩阵；（3）求出 G 权最小的生成树及其权值b c 解：（ 1） 。 2 1 a。 6 4 2 1 3 。e 5d 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 29 页 - - - - - - - - - （2）0111110110110011100110110)(DA（3）b。c2 1 a。 1 e。3 。d其权值为： 7 3已知带权图 G 如右图所示(1) 求图 G 的最小生成树；(2)计算该生成树的权值答：(1) 1 2 7 5 3 (2) 权值为 18。4设有一组权为 2,3,5,7,17,31 ，试画出相应的最优二叉树， 计算该最优二叉树的权解：65 17 48 5 1217 31 2 3 5 7 权值为 65。四、证明题1设 G 是一个 n 阶无向简单图， n 是大于等于 3 的奇数证明图 G 与它的补图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 29 页 - - - - - - - - - G中的奇数度顶点个数相等证明：设 a 为 G 中任意一个奇数度顶点，由定义，a仍为顶点，为区分起见，记为 a, 则 deg(a)+deg(a )=n-1, 而 n 为奇数，则 a 必为奇数度顶点。由a的任意性，容易得知结论成立。2设连通图 G 有 k 个奇数度的结点， 证明在图 G 中至少要添加2k条边才能使其成为欧拉图证明：由定理推论知：在任何图中，度数为奇数的结点必是偶数个， 则 k 是偶数。又由欧拉图的充要条件是图G 中不含奇数度结点。因此，只要在每对奇数度结点间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图。故最少要加条边才能使其成为欧拉图。形考任务六设 P：我将去打球， Q：我有时间命题 我将去打球，仅当我有时间 时符号化为 ( B)选择一项：A. B. C. D. 题目2还未回答满分 10.00 标记题目题干命题公式(P Q)的析取范式是( D ) 选择一项：A. (P Q) RB. (P Q) RC. (P Q) R名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 29 页 - - - - - - - - - D. ( PQ) R题目3还未回答满分 10.00 标记题目题干命题公式(PQ)析取范式是 ( A )选择一项：A. PQB. C. D. 题目4答案已保存满分 10.00 标记题目题干下列公式成立的为( D)选择一项：A. PQ P QB. PQPQC. QP PD. P (P Q)Q题目5答案已保存名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 29 页 - - - - - - - - - 满分 10.00 标记题目题干下列公式( C )为重言式选择一项：A. PQP QB. (Q(P Q) ( Q (P Q)C. (P( QP)( P(PQ)D. ( P (P Q) Q题目6答案已保存满分 10.00 标记题目题干设 A （x） ： x 是人， B （x） ： x 是教师，则命题 “有人是教师”可符号化为（D ） 选择一项：A.?( x)(A(x) ?B(x) ?( x)(A(x) ?B(x)B.(?x)(A(x) B(x) (?x)(A(x) B(x)C.?(?x)(A(x ) B(x) ?(?x)(A(x)B(x)D.( x)(A(x) B(x) ( x)(A(x) B(x)题目7还未回答满分 10.00 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 29 页 - - - - - - - - - 标记题目题干表达式 ( x)(P(x,y) Q(z)y(R(x,y)z Q(z)中(x)中辖域是 ( B )选择一项：A. P(x, y) B. P(x, y)Q(z)C. R(x, y) D. 题目8答案已保存满分 10.00 标记题目题干 A 设个体域 D= a, b, c ，那么谓词公式去量词后的等值式为A 选择一项：A. (A(a) A(b) A(c) (B(a) B(b) B(b)B. (A(a) A(b) A(c) (B(a) B(b) B(b)C. (A(a) A(b) A(c) (B(a) B(b) B(b)D. (A(a) A(b) A(c) (B(a) B(b) B(b)题目9还未回答满分 10.00 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 29 页 - - - - - - - - - 标记题目题干A 下列等价公式成立的为( A)选择一项：A. P PQ QB. C. D. 题目10还未回答满分 10.00 标记题目题干A 设个体域 D 是整数集合，则命题? x y (xy = y) 的真值是（A ）选择一项：A. T B. F C. 不确定D. 以上说法都不是名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 29 页 - - - - - - - - - 离散数学作业7离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3 次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习， 基本上是按照考试的题型 （除单项选择题外） 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果， 找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。要求：将此作业用 A4 纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17 周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。一、填空题1命题公式()PQP的真值是1 或 T 2设 P：他生病了， Q：他出差了 R：我同意他不参加学习 . 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为（PQ）R 3含有三个命题变项P，Q，R 的命题公式 P Q 的主析取范式是 (PQR)(PQR) 4设 P(x)：x 是人， Q(x)：x 去上课，则命题“有人去上课”可符号化为x(P(x)Q(x) 5 设个体域 D a, b,那么谓词公式)()(yyBxxA消去量词后的等值式为(A(a)A(b)(B(a)B(b) 6 设个体域 D1, 2, 3 ， A(x)为 “x大于 3” ， 则谓词公式 ( x)A(x)的真值为 0(F) 7谓词命题公式 ( x)(A(x) B(x) C(y)中的自由变元为y 8谓词命题公式 ( x)(P(x)Q(x) R(x，y)中的约束变元为x 三、公式翻译题1请将语句“今天是天晴”翻译成命题公式设 P：今天是晴天。则P。2请将语句“小王去旅游，小李也去旅游”翻译成命题公式设 P：小王去旅游。Q：小李去旅游。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 29 页 - - - - - - - - - 则 P Q3请将语句“他去旅游，仅当他有时间”翻译成命题公式设 P：他去旅游。Q：他有时间。则 PQ 4请将语句“ 41次列车下午五点开或六点开”翻译成命题公式设 P：41 次列车下午五点。Q：41次列车下午六点开。则 P 或 Q5请将语句“有人不去工作”翻译成谓词公式设 A（x）：x 是人B（x）：去工作x(A(x)B(x) 6请将语句“所有人都努力工作”翻译成谓词公式设 A（x）：x 是人B（x）：努力工作x(A(x)B(x) 四、判断说明题（ 判断下列各题，并说明理由）1命题公式P P 的真值是 1。答：错误。因为P 和 P 的否不能同时为真。2命题公式）（)z()()(RyQxPx中的约束变元为 y。答：错误。该式中的约束元为x。3谓词公式),()()y(zyxQzxPx，）（中x 量词的辖域为P(x,y)( z)Q(x,y,z)。答： 错误。 谓词公式),()()y(zyxQzxPx，）（中x 量词的辖域为 P(x,y)。若谓词公式),()()y(zyxQzxPx，）（变为),()()y(zyxQzxPx，）（），x 量词的辖域为 P(x,y)( z)Q(x,y,z)。4下面的推理是否正确，请给予说明(1) ( x)A(x) B(x) 前提引入(2) A(y) B(y) US (1) 答：错误。因为 B(x)不受全称量词x的约束，不能使用全称指定规则。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 29 页 - - - - - - - - - （2）应为 A(y) B(x)，换名时，约束元与自由变元不能混淆。四计算题1求 PQ R的析取范式，合取范式、主析取范式，主合取范式PQ RP Q R（析取范式）（P Q R）（合取范式）真值表：P Q R P 原式极小项极大项0 0 0 1 1 PPP 0 0 1 1 1 PQR 0 1 0 1 1 PQR 0 1 1 1 1 PQR 1 0 0 0 0 P Q R 1 0 1 0 1 PQR 1 1 0 0 1 PQR 1 1 1 0 1 PQR 主析取范式（PPP） （PQR） （PQR） （PQR） （PQR） （PQR） （PQR）主合取范式（P Q R）2求命题公式 (P Q)(R Q)的主析取范式、主合取范式真值表：P Q R （P Q） R Q 原式极小项极大项0 0 0 1 0 1 PPP 0 0 1 1 1 1 PQR 0 1 0 0 1 1 PQR 0 1 1 0 1 1 PQR 1 0 0 0 0 0 P Q R 1 0 1 0 1 1 PQR 1 1 0 0 1 1 PQR 1 1 1 0 1 1 PQR 主析取范式（PPP） （PQR） （PQR） （PQR） （PQR） （PQR） （PQR）主合取范式（P Q R）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 27 页，共 29 页 - - - - - - - - - 3设谓词公式()( , )()( , , )()( , )xP x yz Q y x zy R y z（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元答： （1）x 的辖域为P（x,y）zQ(x,y,z)z的辖域为Q(x,y,z) y的辖域为 R(y,z) (2) 约束变元为P（x,y）zQ(x,y,z)中的 xQ(x,y,z) 中的 z R(y,z)中的 y 自由变元为P（x,y）zQ(x,y,z)中的 y R(y,z)中的 z 4设个体域为 D=a1, a2 ，求谓词公式y xP(x,y)消去量词后的等值式；答：谓词公式y xP(x,y)消去量词后的等值式为= xP（x,a1）xP（x,a2）=P (a1, a2）P (a1, a2）(P(a1, a2）P (a1, a2) 五、证明 题1试证明 (P(QR)P Q 与 (PQ)等价证明： (P(QR)P QP (QR)P QP Q（PQ）2试证明(AB) (B C)CA证明：(AB) (B C)C (A B) (B C)C ( A B) (BC) (CC) ( A B) (BC)0) ( A B) (BC) ( A ( BC) (B ( BC) ( A ( BC) 0 A ( BC) (A B C) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 28 页，共 29 页 - - - - - - - - - 故由左边不可推出右边A名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 29 页，共 29 页 - - - - - - - - -