国家开放大学《离散数学(本)》形考任务4参考答案.pdf

国家开放大学《离散数学(本)》下载作业参考答案一、公式翻译题（每小题4分，共16分）1．将语句“我会英语，并且会德语．”翻译成命题公式．参考答案：设p.我学英语Q:我学法语则命题公式为:pΛQ2．将语句“如果今天是周三，则昨天是周二．”翻译成命题公式．参考答案：设P：今天是周三Q：昨天是周二则命题公式为：P→Q3.将语句“C3次列车每天上午9点发车或者10点发车”翻译成命题公式．参考答案：设P：C3次列车每天上午9点发车Q：C3次列车每天上午10点发车则命题公式为：┐(P↔Q)4.将语句“小王是个学生，小李是个职员，而小张是个军人．”翻译成命题公式．参考答案：设P：小王是个学生Q：小李是个职员R:而小张是个军人则命题公式为：P∧Q∧R二、计算题（每小题12分，共84分）1．设集合A={{a},a,b}，B={a,{b}}试计算：（1）AB；（2）AB；（3）A-(AB)参考答案：1（1）AB={a}（2）AB={{a},a,b{b}}（3）A-(AB)={{a},a,b}-{a}={a,b}2.设集合A={2,3,6,12,24,36}，B为A的子集，其中B={6,12}，R是A上的整除关系，试（1）写出R的关系表达式；（2）画出关系R的哈斯图；（3）求出B的最大元、极大元、最小上界．参考答案：（1）R={<2,2>,<2,6>,<2,12>,<2,24>,<3,3>,<3,6>,<3,12>,<3,24>,<6,6>,<6,12>,<6,24>,<12,12>,<12,24>,<24,24>}（2）关系R的哈斯图（3）B的最大元素：12极大元素：12最小上届：123．设G=<V，E>，V={v,v,v,v}，E={(v,v),(v,v),(v,v),(v,v),(v,v)}，12341213142334试（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形。参考答案：（1）G的图形表示2（2）邻接矩阵01111010||11011010（3）每个结点的度数Deg(v1)=3Deg(v2)=2Deg(v3)=3Deg(v4)=2（4）其补图的图形4.求P→(Q∧R)的合取范式与主析取范式.参考答案：P→(Q∧R)=┐P∨(Q∧R)=（┐P∨Q）∧（┐P∨R）合取范式=（┐P∨Q）∨（R∧┐R）∧（┐P∨R）=（┐P∨Q）∨（R∧┐R）∧（┐P∨R）∨（Q∧┐Q）=（┐P∨Q∨R）∧（┐P∨Q∨┐R）∧（┐P∨┐Q∨R）主合取范式=（┐P∧┐Q∧┐R）∨（┐P∧┐Q∧R）∨（┐P∧┐Q∧┐R）（┐P∧Q∧R）∨（P∧┐Q∧R）∨（P∧Q∧┐R）∨（P∧Q∧R）主析取范式5．试画一棵带权为1,2,3,3,4的最优二叉树,并计算该最优二叉树的权．3参考答案：最优二叉树的权为1×3+2×3+3×2+3×2+4×2=296．试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．v16v221459vv635237vv514参考答案：W(v2,v6)=1,选(v2,v6)W(v4,v5)=1,选(v4,v5)W(v1,v6)=2,选(v1,v6)W(v3,v5)=2,选(v3,v5)W(v2,v3)=4,选(v2,v3)最小生成树，如图6v1v225419v6v352371vv54生成树的权W(T)=1+1+2+2+4=107.设谓词公式(x)P(x,y)→(z)Q(x,y,z)，试（1）写出量词的辖域；4（2）指出该公式的自由变元和约束变元。参考答案：（1）x的辖域为P(x,y)→zQ(x,y,z)z的辖域为Q(x,y,z)（2）自由变元P(x,y)→zQ(x,y,z)中的y约束变元P(x,y)→zQ(x,y,z)中的x5