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

#国家开放大学《离散数学(本)》下载作业参考答案一、公式翻译题(每小题4分，共16分)1．将语句“我会英语，并且会德语．”翻译成命题公式．参考答案：设p.我学英语Q：我学法语则命题公式为:pAQ2．将语句“如果今天是周三，则昨天是周二．”翻译成命题公式．参考答案：设P：今天是周三Q：昨天是周二则命题公式为：PfQ.将语句“C3次列车每天上午9点发车或者10点发车”翻译成命题公式.参考答案：设P：C3次列车每天上午9点发车Q：C3次列车每天上午10点发车则命题公式为：1(P-Q).将语句“小王是个学生，小李是个职员，而小张是个军人．”翻译成命题公式．参考答案：设P：小王是个学生Q：小李是个职员R：而小张是个军人则命题公式为：PAQAR二、计算题(每小题12分，共84分).设集合A={{a},a,b},B={a,{b}}试计算：(1)AcB； (2)AuB； (3)A-(AcB)参考答案：AcB={a}AuB={{a},a,b{b}}(3)A-(AcB)={{a},a,b}-{a}={a,b}.设集合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最小上届：12.设G=<卜，E>，V={v1,v2,v3,v4}，E={(v1,v2)，(v1,v3)，(v1,v4)，(v2,vJ，(v3,9,试(1)给出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数;(4)画出其补图的图形。参考答案：G的图形表示

(2)邻接矩阵(2)邻接矩阵01111010(3)每个结点的度数Deg(v1)=3Deg(v2)=2Deg(v3)=3Deg(v4)=2(4)其补图的图形vl剑.求P一(Q八R)的合取范式与主析取范式.参考答案：P-(QaR)二口Pv(QaR)二([PvQ)a([PvR)合取范式二([PvQ)v(RaiR)a([PvR)=(口PvQ)v(RaiR)a(]PvR)v(QaiQ)=(qPvQvR)A(]PvQVqR)A(qPVqQvR)主合取范式=(qPa[Qa[R)v(qPa[QaR)v(qPa[Qa[R)(qPaQaR)V(PA]QaR)v(PaQa]R)v(PaQaR)主析取范式.试画一棵带权为1,2,3,3,4的最优二叉树,并计算该最优二叉树的权.

参考答案:最优二叉树的权为1X3+2X3+3X2+3X2+4X2=29.试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权.参考答案：W(v2,v6)=l,i£(v2,v6)W(v4,v5)=l,选(v4,v5)W(v1,v6)=2,选(vl,v6)W(v3,v5)=2,选(v3,v5)W(v2,v3尸4,选(v2,v3)生成树的权W（T）=1+1+2+2+4=10.设谓词公式（土）尸（羽y）T（Vz）Q（x,y,z）,试（1）写出量词的辖域;（2）指出该公式的自由变元和约束变元。参考答案：(1)3x的辖域为P(x,y)fVzQ(x,