2022年电大离散数学作业答案--合集.docx

《2022年电大离散数学作业答案--合集.docx》由会员分享，可在线阅读，更多相关《2022年电大离散数学作业答案--合集.docx（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 电大离散数学作业答案3-7 合集姓名：离散数学作业3 学号：得分：老师签名：离散数学集合论部分形成性考核书面作业本课程形成性考核书面作业共3 次,内容主要分别是集合论部分、 图论部分、数理规律部分的综合练习,基本上是依据考试的题型（除单项挑选题外）支配练习题目, 目的是通过综合性书面作业,使同学自己检验学习成果, 找出把握的薄弱学问点,重点复习,争取尽快把握；本次形考书面作业是第一次作业,大家要仔细准时地完成集合论部分的综合练习作业；要求： 将此作业用 A4 纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求 2022 年 11 月

2、7 日前完成并上交任课老师（不收电子稿）；并在03 任务界面下方点击“ 储存” 和“ 交卷” 按钮,完成并上交任课老师；一、填空题1设集合 A 1, 2, 3, B 1, 2,就 PA- PB = 3 ,1,3 ,2,3 ,1,2,3 ,A B= , 2设集合 A 有 10 个元素,那么 A 的幂集合 PA的元素个数为 10243设集合 A=0, 1, 2, 3 ,B=2, 3, 4, 5 ,R 是 A 到 B 的二元关系,就 R 的有序对集合为Rx ,yxA 且yB 且x,yAB , , 4设集合 A=1, 2, 3, 4 ,B=6, 8, 12 , A 到 B 的二元关系Rx,yy2x,x

3、A,yB那么 R1 , 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 中至少包名师归纳总结 含, 等元素第 1 页,共 14 页-

4、 - - - - - -精选学习资料 - - - - - - - - - 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 上的自反关系,判定结论：“是自反的”是否成立？并说明理由- 1 R 1、R1R2、R1R2解 ：成立R2；a c g 由于 R1和 R2 是 A 上的

5、自反关系,即I AR1,IA由逆关系定义和 I AR1,得 IA R1- 1；b 由 IAR1,IAR2,得 IA R1R2,IA R1 R2；所以, R1-1、R1R2、R1R2是自反的；d f h 3如偏序集 的哈斯图如图一所示,e 就集合 A 的最大元为 a,最小元不存在解 ：错误图一集合 A 的最大元不存在, a 是极大元4设集合 A=1, 2, 3, 4 ,B=2, 4, 6, 8 ,判定以下关系 f 是否构成函数 f：AB,并说明理由1 f=, , , ；3 f=, , , 2f=, , ；（1）不构成函数；由于对于 3 属于 A,在 B 中没有元素与之对应；（2）不构成函数；由于

6、对于4 属于 A,在 B 中没有元素与之对应；（3）构成函数；由于A 中任意一个元素都有A 中唯独的元素相对应；三、运算题1设E,12 ,3,4 ,5 ,A,14 ,B,12,5 ,C,24 ,求：4 AB1 ABC；2 AB- BA 3 PAPC；解：（ 1）ABC=1,15,3 3,1 ,5 （3）PAPC,1 ,4 ,14 ,2 ,4 ,2,4 1 ,14 （4）AB =AB（ AB）=,124,5, 1,24 ,5 （2）=1 ,2,4,5-1=2,4,5 名师归纳总结 - - - - - - -第 2 页,共 14 页精选学习资料 - - - - - - - - - 2设 A=1,2

7、,1,2,B=1,2,1,2 ,试运算（1）（A B）；（2）（ AB）；（3）A B解：（ 1）A B =1,2 （2）AB =1,2 （3）A B= , , , , , , , y3设 A=1 ,2,3,4,5 ,R=|x A,y A 且 x+y 4 ,S=|x A,A 且 x+y0 ,试求 R,S,R S,S R,R-1,S-1,rS,sR解： R=, S=空集R*S=空集S*R=空集R-1=,S-1 =空集rS= sR= 4设 A=1, 2, 3, 4, 5, 6, 7, 8,R 是 A 上的整除关系, B=2, 4, 6 1 写出关系 R 的表示式；2 画出关系 R 的哈斯图；3 求

8、出集合 B 的最大元、最小元1R= 3集合 B 没有最大元,最小元是 2 四、证明题1试证明集合等式： A BC=AB AC1证明 ：设,如 xA BC,就 xA 或 xBC,即 xA 或 x B 且 xA 或 xC即 xAB 且 xAC ,B 且 xAC,即 xT=AB AC,所以 A BC AB AC反之,如 xAB AC,就 xA即 xA 或 xB 且 xA 或 xC,名师归纳总结 即 xA 或 xBC,第 3 页,共 14 页即 xA BC,- - - - - - -精选学习资料 - - - - - - - - - 所以AB AC A BC因此 A BC=AB AC AC2试证明集合等

9、式A BC=AB 2证明 ：设 S=ABC,T=ABA C, 如 xS,就 xA 且 xBC,即 xA 且 xB 或 xA 且 xC,也即 xAB 或 xAC ,即 xT,所以 S T反之,如 xT,就 xAB 或 xAC,即 xA 且 xB 或 xA 且 xC 也即 xA 且 xBC,即 xS,所以 T S因此 T=S3对任意三个集合 A, B 和 C,试证明：如 AB = AC,且 A,就 B = C（1） 对于任意 A B,其中 aA,bB, 由于 A B= A C,必有 A C,其中 b C因此 B C （2）同理,对于任意 A C,其中, aA,cC,由于 A B= A C 必有 A

10、 B,其中 cB,因此 C B 有（ 1）（2）得 B=C 4试证明：如 R 与 S 是集合 A 上的自反关系,就 反关系RS 也是集合 A 上的自如 R 与 S 是集合 A 上的自反关系,就任意 xA,x,x R,x,x S, 从而 x,x RS,留意 x 是 A的任意元素,所以 反关系RS 也是集合 A上的自离散数学作业5 姓名：学号：得分：老师签名：离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3 次,内容主要分别是集合论部分、 图论部分、数理规律部分的综合练习,基本上是依据考试的题型（除单项挑选题外）支配练习题目, 目的是通过综合性书面作业,使同学自己检验学习成果, 找出

11、把握的薄名师归纳总结 - - - - - - -第 4 页,共 14 页精选学习资料 - - - - - - - - - 弱学问点,重点复习,争取尽快把握；本次形考书面作业是其次次作业,大家要仔细准时地完成图论部分的综合练习作业；要求： 将此作业用 A4 纸打印出来,手工书写答题,字迹工整,解答题要有 解答过程,要求 2022 年 12 月 5 日前完成并上交任课老师（不收电子稿）；并在 05 任务界面下方点击“ 储存” 和“ 交卷” 按钮,以便老师评分；一、填空题1已知图 G 中有 1 个 1 度结点, 2 个 2 度结点, 3 个 3 度结点, 4 个 4 度结点,就 G 的边数是15 2

12、设给定图 G如右由图所示 ,就图 G 的点割集是 f 3设 G 是一个图,结点集合为V,边集合为 E,就G 的结点 度数之和 等于边数的两倍4无向图 G 存在欧拉回路,当且仅当 G 连通且 等于出度5设 G=是具有 n 个结点的简洁图,如在G 中每一对结点度数之和大于等于 n-1 ,就在 G 中存在一条汉密尔顿路6如图 G=中具有一条汉密尔顿回路,就对于结点集 V 的每个非空子集 S,在 G 中删除 S 中的全部结点得到的连通分支数为W,就 S中结点数 |S|与 W 满意的关系式为WG-V1V1n 为奇数时,K n 中7设完全图 K n 有 n 个结点 n 2,m 条边,当存在欧拉回路8结点数

13、 v 与边数 e满意e=v-1 关系的无向连通图就是树9设图 G 是有 6 个结点的连通图,结点的总度数为 4 条边后使之变成树18,就可从 G 中删去10设正就 5 叉树的树叶数为 17,就分支数为 i = 5 二、判定说明题 （判定以下各题,并说明理由）1假如图 G 是无向图,且其结点度数均为偶数, 就图 G 存在一条欧拉回路 1 不正确,缺了一个条件,图 图 G 是一个有孤立结点的图；G 应当是连通图,可以找出一个反例,比如2如下图所示的图 G 存在一条欧拉回路2 不正确,图中有奇数度结点,所以不存在是欧拉回路；3如下图所示的图G 不是欧拉图而是汉密尔顿图名师归纳总结 - - - - -

14、 - -第 5 页,共 14 页精选学习资料 - - - - - - - - - 解：正确G由于图中结点 a,b,d,f 的度数都为奇数,所以不是欧拉图；假如我们沿着 a,d,g,f,e,b,c,a,这样除起点和终点是 次仅一次,所以存在一条汉密尔顿回路,是汉密尔顿图a 外,我们经过每个点一4设 G 是一个有 7 个结点 16 条边的连通图,就 G 为平面图解： 1 错误假设图 G 是连通的平面图,依据定理,结点数v,边数为 e,应满意 e 小于等于 3v-6,但现在 16 小于等于 3*7-6,显示不成立；所以假设错误；5设 G 是一个连通平面图,且有 2 正确6 个结点 11 条边,就 G

15、 有 7 个面依据欧拉定理, 有 v-e+r=2,边数 v=11,结点数 e=6,代入公式求出面数 r=7 三、运算题1设 G=,V= v1,v2,v3,v4,v5 ,E= v1,v3,v2,v3,v2,v4,v3,v4,v3,v5,v4,v5 ,试1 给出 G 的图形表示；3 求出每个结点的度数；解：1 v1 2 写出其邻接矩阵；4 画出其补图的图形v2 v3 v4 v5 2 邻接矩阵为名师归纳总结 - - - - - - -第 6 页,共 14 页精选学习资料 - - - - - - - - - 00100001102,v3 结点度数为3, v4 结点度数为2,v5 结点度数为2 1101

16、101101001103 v1 结点度数为1,v2 结点度数为4 补图图形为v1 v2 v3 v4 v5 2图 G=,其中 V= a, b, c, d, e ,E= a, b, a, c, a, e, b, d, b, e, c, e, c, d, d, e ,对应边的权值依次为（1）画出 G 的图形；2、1、2、3、6、1、4 及 5,试（2）写出 G 的邻接矩阵；（3）求出 G 权最小的生成树及其权值（1）G 的图形如下：（2）写出 G 的邻接矩阵名师归纳总结 - - - - - - -第 7 页,共 14 页精选学习资料 - - - - - - - - - （3）G 权最小的生成树及其权

17、值3已知带权图 G 如右图所示1 求图 G 的最小生成树；解：1 最小生成树为1 7 2 3 5 2运算该生成树的权值2 该生成树的权值为 1+2+3+5+7=18 4设有一组权为 2, 3, 5, 7, 17, 31,试画出相应的最优二叉树,运算该最优名师归纳总结 - - - - - - -第 8 页,共 14 页精选学习资料 - - - - - - - - - 二叉树的权63 31 1 17 1 7 5 5 2 3 权为 2*5+3*5+5*4+7*3+17*2+31=131 四、证明题1设 G 是一个 n 阶无向简洁图, n 是大于等于 3 的奇数证明图 G 与它的补图 G 中的奇数度顶

18、点个数相等证明：设 G V E,G V E就 E 是由 n 阶无向完全图 K 的边删去 E n所得到的 所以对于任意结点 u V ,u 在 G 和 G 中的度数之和等于 u 在 K 中的度数由于 n 是大于等于 3 的奇数,从而 K 的每个结点都是偶数度的 （n 1 2度）,于是如 u V 在 G 中是奇数度结点,就它在 G 中也是奇数度结点故图 G与它的补图 G 中的奇数度结点个数相等2设连通图 G 有 k 个奇数度的结点, 证明在图 G 中至少要添加k 条边才能 2使其成为欧拉图名师归纳总结 - - - - - - -第 9 页,共 14 页精选学习资料 - - - - - - - - -

19、 证明 ：由定理 3.1.2,任何图中度数为奇数的结点必是偶数,可知 k 是偶数又依据定理 4.1.1 的推论,图 G 是欧拉图的充分必要条件是图 G 不含奇数度结点因此只要在每对奇数度结点之间各加一条边,使图 为偶数,成为欧拉图G 的全部结点的度数变故最少要加k 条边到图 G 才能使其成为欧拉图2名：姓离散数学作业7 学号：得分：老师签名：离散数学数理规律部分形成性考核书面作业本课程形成性考核书面作业共 3 次,内容主要分别是集合论部分、 图论部分、数理规律部分的综合练习,基本上是依据考试的题型（除单项挑选题外）支配练习题目, 目的是通过综合性书面作业,使同学自己检验学习成果, 找出把握的薄

20、弱学问点,重点复习,争取尽快把握；本次形考书面作业是第三次作业,大家要 仔细准时地完成数理规律部分的综合练习作业；要求： 将此作业用 A4 纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求本学期第17 周末前完成并上交任课老师（不收电子稿）；并在07 任务界面下方点击“ 储存” 和“ 交卷” 按钮,以便老师评分；一、填空题1命题公式 P Q P 的真值是 1 或 T 2设 P：他生病了, Q：他出差了 R：我同意他不参与学习 . 就命题“ 如果他生病或出差了,我就同意他不参与学习” 符号化的结果为（P Q）R 3含有三个命题变项P,Q,R 的命题公式 P Q 的主析取范式是PQRP

21、QR 名师归纳总结 4设 Px：x 是人, Qx：x 去上课,就命题“ 有人去上课”可符号化为第 10 页,共 14 页xPx Qx 5设个体域 Da, b ,那么谓词公式xA x yB y消去量词后的等值式为AaAbBaBb - - - - - - -精选学习资料 - - - - - - - - - 6设个体域 D1, 2, 3 ,Ax为“ x 大于 3” ,就谓词公式 xAx 的真值为0F y x 7谓词命题公式 xAx Bx Cy中的自由变元为8谓词命题公式 xPx Qx Rx,y中的约束变元为三、公式翻译题1请将语句“ 今日是天晴” 翻译成命题公式设 P：今日是晴天；就 P 2请将语句

22、“ 小王去旅行,小李也去旅行” 翻译成命题公式设 P：小王去旅行；Q：小李去旅行；就 P Q3请将语句“ 假如明每天下雪,那么我就去滑雪” 翻译成命题公式设 P：明天下雪；Q：我去滑雪；就 PQ 4请将语句“ 他去旅行,仅当他有时间” 翻译成命题公式设 P：他去旅行；Q：他有时间；就 PQ“ 有人不去工作” 翻译成谓词公式5请将语句设 A（x）： x 是人B（x）：去工作xAx Bx 6请将语句“ 全部人都努力工作” 翻译成谓词公式设 A（x）： x 是人B（x）：努力工作xAx Bx 四、判定说明题（ 判定以下各题,并说明理由）1命题公式 P P 的真值是 1答：错；由于 P 和 P 的否不

23、能同时为真；名师归纳总结 2命题公式P PQ P 为永真式x是永真式P （Q P）第 11 页,共 14 页答：对；P （P Q） PP P1 3谓词公式xPxyGx,y xP答：对；它同 P（QP）是等价形式 P（QP）- - - - - - -精选学习资料 - - - - - - - - - P Q P 1 Q 4下面的推理是否正确,请赐予说明1 xAx Bx 前提引入 US 1 2 Ay By 答：对；四运算题1 求 P Q R 的析取范式,合取范式、主析取范式,主合取范式P Q R P Q R （析取范式）（P Q R）（合取范式）真值表：P Q R P 原式微小项及大项1 PPP P

24、 Q R 0 0 0 1 0 0 1 1 1 PQR 0 1 0 1 1 PQR 0 1 1 1 1 PQR 1 0 0 0 0 1 0 1 0 1 PQR R）1 1 0 0 1 PQR 1 1 1 0 1 PQR 主析取范式 （PPP） （PQR） （PQ（PQR） （PQR） （PQR） （PQR）主合取范式（P Q R）2求命题公式 P Q 真值表：R Q 的主析取范式、主合取范式名师归纳总结 P Q R P（P Q） R Q P原式微小项及大项第 12 页,共 14 页1 PPP P Q R 0 0 0 1 0 0 0 1 1 1 1 PQR 0 1 0 0 1 1 PQR 0 1

25、1 0 1 1 PQR 1 0 0 0 0 0 1 0 1 0 1 1 PQR R）1 1 0 0 1 1 PQR 1 1 1 0 1 1 PQR 主析取范式 （PP） （QR） （PQ- - - - - - -精选学习资料 - - - - - - - - - （PQR） （PQR） （PQR） （PQR）主合取范式（P Q R）z Q y x z , , y R y z 3设谓词公式 x P x y , （1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元答：（1）x 的辖域为 P（x,y）zQx,y,zz 的辖域为 Qx,y,z y 的辖域为 Ry,z 2 约束变元为P（x,y）z

26、Qx,y,z中的 xQx,y,z 中的 z Ry,z 中的 y 自由变元为P（x,y）zQx,y,z中的 y Ry,z中的 z 4设个体域为 D= a1, a2 ,求谓词公式y xPx,y消去量词后的等值式；答：谓词公式（R（a,a）y xPx,y消去量词后的等值式为R（a,b） R（b,a）R（b,b） 五、证明 题1试证明 PQRP Q 与 PQ等价证明： PQRP QP QRP QP Q名师归纳总结 （PQ） xPx xRx第 13 页,共 14 页2试证明 xPx Rx证明：（ 1） xAx Bx P （2）A（c） Bc ES1 公式 ABA （3）Ac ABB T2 4 xAx EG3 5 Bc T2 公式 ABA 6 xBx ABB EG5 - - - - - - -精选学习资料 - - - - - - - - - 7 xAx xBx T46 公式 ABA 名师归纳总结 ABB 第 14 页,共 14 页- - - - - - -