国家开放大学电大《离散数学(本)》形考作业参考答案

国家开放大学《离散数学（本）》形考作业参考答案一、公式翻译题（每小题4分，共16分）1.将语句“我会英语，并且会德语.”翻译成命题公式.参考答案：设p.我学英语Q:我学法语则命题公式为:p/\Q2.将语句“如果今天是周三，则昨天是周二.”翻译成命题公式.参考答案：设P：今天是周三Q：昨天是周二则命题公式为：P-Q3.将语句“C3次列车每天上午9点发车或者10点发车”翻译成命题公式.参考答案：设P：C3次列车每天上午9点发车Q：C3次列车每天上午10点发车则命题公式为：I（PJQ）4.将语句“小王是个学生，小李是个职员，而小张是个军人.”翻译成命题公式.参考答案：设P：小王是个学生Q：小李是个职员R:而小张是个军人则命题公式为：PAQAR二、计算题(每小题12分，共84分)1.设集合厶={同，a,b},B={a,{b})试计算：(1)AQB；(2)AEB；(3)A-(AQB)参考答案：(1)4QB={a}(2)AE8=({a},a,b{b}}(3)A(/lQB)=({a},a,b}-{a}={a,b}2.设集合厶={2,3,6,12,24,36},B^A的子集，其中8={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的哈斯图VA(3)B的最大元素：12极大元素：12最小上届：123.设G=<V,E>,V={vv2,v3,v4）»（吃吃）},试（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画岀其补图的图形。参考答案：（1）G的图形表示v2

v3(2)邻接矩阵0111101011011010(3)每个结点的度数Deg(v1)=3Deg(v2)=2Deg(v3)=3Deg(v4)=2(4)其补图的图形5.v2‘v34.求P^（Q/\R）的合取范式与主析取范式.参考答案：PT（Q/\R）=-]PV(QAR)hh=(-|PVQ)A合取范式=(-]PVQ)V(RA-]R)A(-]PVH)=(-1PVQ)V(RA-i/?)A(-1PVR)V(QAQ)q=(-|PVQVR)A(-|PVQV-]R)A(〔P0QWR)主合取范式=(-]PAQA-]R)V(iPA-]QAR)V(-|PAQA-]R)(-]PAQAR)nnV15.试画一棵带权为1,2,3,3,4的最优二叉树，并计算该最优二叉树的权.参考答案：最优二叉树的权为1x3+2x3+3x2+3x2+4x2=296.试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权.参考答案: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)(PAQAR)V(PAQAR)V(PAQAqR)V(PAQAR)主析取范式最小生成树，如图生成树的权W(T)=1+1+2+2+4=107.设谓词公式($x)F(x,y)T%)O(x,y,z),试(1)写出量词的辖域；(2)指出该公式的自由变元和约束变元。参考答案：(1)$x的辖域为P(x,y)-