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

国家开放大学《离散数学（本）》形考作业参考答案 一、公式翻译题（每小题 4 分，共 16 分） 1. 将语句“我会英语，并且会德语.”翻译成命题公式. 参考答案： 设 p.我学英语 Q:我学法语 则命题公式为:p/\Q 2. 将语句“如果今天是周三，则昨天是周二.”翻译成命题公式. 参考答案： 设 P：今天是周三 Q：昨天是周二 则命题公式为：P-Q 3. 将语句“C3次列车每天上午 9 点发车或者 10 点发车”翻译成命题公式. 参 考答案： 设 P： C3 次列车每天上午 9 点发车 Q： C3 次列车每天上午 10 点发车 则命题公式为： （P Q ） I J 4. 将语句“小王是个学生，小李是个职员，而小张是个军人.”翻译成命题公 式. 参考答案： 设 P：小王是个学生 Q：小李是个职员 R:而小张是个军人 则命题公式为：PAQAR 二、计算题(每小题 12 分，共 84 分) 1. 设集合厶={同，a,b}, B={a, {b}) 试计算： (1) AQB； (2) AEB； (3) A-(AQB) 参考答案： (1) 4QB={a} (2) A E 8=({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 的哈斯图 V A (3) B 的最大元素：12 极大元素：12 最小上届：12 3. 设 G=V, E, V={v v , v , v ）» h 2 3 4 （吃吃）},试（1）给出G 的图形表示；（2）写出其邻接矩阵；（3）求出每个 结点的度数；（4）画岀其补图的图形。 参考答案： （1）G 的图形表示 v2 v3 (2) 邻接矩阵 0 111 10 10 110 1 10 10 (3)每个结点的度数 Deg(v1)=3 Deg(v2)=2 Deg(v3)=3 Deg(v4)=2 (4)其补图的图形 5 . v2‘ v3 4.求 P^ （Q/\R）的合取范式与主析取范式. 参考答案： （ ） PT Q/\R =-]PV(QAR) =(-|PVQ) A 合取范式 =(-]PVQ) V (RA-] R) A(-]PVH) =(-1 PVQ) V (RA-i /?) A (-1 PVR) V (QA Q) q =(-|PVQVR) A (-|PVQV-] R) A ( 〔 P0 QWR)主合取范式 =(-]PA QA-] R) V(i PA-] QAR) V (-| PA QA-] R) (-] PAQAR) n n V (PA QAR) V (PAQAqR) V (PAQAR)主析取范式 1 5.试画一棵带权为 1,2, 3, 3, 4 的最优二叉树，并计算该最优二叉树的权. 参考答案： 最优二叉树的权为 1x3+2x3+3x2+3x2+4x2=29 6.试利用 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) 最小生成树，如图 生成树的权 W(T)=1 +1 +2+2+4=10 7.设谓词公式($x)F(x,y)T%)O(x,y,z),试 (1) 写出量词的辖域； (2) 指出该公式的自由变元和约束变元。 参考答案： (1) $x 的辖