2020电大-离散数学-形考综合练习答案.docx

PAGE 5 姓 名： 姓 名： 学 号： 得 分： 教师签名： 离散数学综合练习书面作业 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档． 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、公式翻译题 1．请将语句“小王去上课，小李也去上课．”翻译成命题公式． 答： 设P：小王去上课。Q：小李去上课。 则命题公式为：P∧Q 2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 答： 设P：他去旅游。Q：他有时间。 则命题公式为：P→Q 3．请将语句 “有人不去工作”翻译成谓词公式． 答： 设A(x)：x是人 B(x)：去工作 则谓词公式为：?x(A(x)∧B(x)) 4．请将语句“所有人都努力学习．”翻译成谓词公式． 答： 设A(x)：x是人 B(x)：努力学习 则谓词公式为：?x(A(x)∧B(x)) 二、计算题 1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算 （1）(A?B)； （2）(A∩B)； （3）A×B． 解：(1)A -B ={{1},{2}} (2)A∩B ={1,2} (3)A×B= {{1},1,{1},2,{1},{1,2},{2},1,{2},2,{2}, {1,2},1,1,1,2,1, {1,2},2,1,2,2,2, {1,2}} 2．设A={1，2，3，4，5}，R={x，y|x?A，y?A且x+y?4}，S={x，y|x?A，y?A且x+y0}，试求R，S，R?S，S?R，R-1，S-1，r(S)，s(R)． 解： R={1,1,1,2,1,32,12,23,1} S=空集 R?S=空集 S?R=空集 R-1={1,1,2,13,11,22,21,3} S-1=空集 r(S)={1,12,23,34,45,5} s(R)={1,11,21,32,12,23,1} 3．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}． (1) 写出关系R的表示式； (2) 画出关系R的哈斯图； (3) 求出集合B的最大元、最小元． 解： R={1,11,21,31,41,51,61,71,82,22,42,62,83,33,64,44,85,56,67,78,8} R的哈斯图为： 集合B没有最大元，最小元是2 4．设G=V，E，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）G的图形为： （2）邻接矩阵为： 补图为： v1结点度数为1，v2结点度数为2， v3结点度数为3，v4结点度数为2，v5结点度数为2： 5．图G=V, E，其中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权最小的生成树及其权值． 解： （1）G的图形： （2）邻接矩阵： （3）最小生成树及权值 设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权． 解：二叉树如下（方形为给定权）： 权：2*5+3*5+5*4+7*3+17*2+31=131 7． 求P?Q?R的析取范式，合取范式、主析取范式，主合取范式． 解： P?Q?R ??R?Q?R 取范式、合取范式、主合取范式都为：?R?Q?R 主析取范式为：（?P??Q??R)?(?P??Q?R)?(?P?Q??R) ?(?P?Q?R)?(P??Q?R)?(P?Q??R)?(P?Q?R) 8．设谓词公式． （1）试写出量词的辖域； （2）指出该公式的自由变元和约束变元． 答： （1）量词x的辖域为：P(x,y)→(?z)Q(y,x,z) 量词z的辖域为：Q(y,x,z) 量词y的辖域为：R(y,z) （2）P(x,y)中的x是约束变元，y是自由变元 Q