国家开放大学《离散数学(本)》下载作业参考答案
 
一、公式翻译题（每小题4分，共16分）
1．将语句“我会英语，并且会德语．”翻译成命题公式．
参考答案：
设p.我学英语
Q:我学法语
则命题公式为:pΛQ
2．将语句“如果今天是周三，则昨天是周二．”翻译成命题公式．
参考答案：
设P：今天是周三
Q：昨天是周二
则命题公式为：P→Q
3.将语句“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）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
        最小上届：12
3．设G=<V，E>，V={v1, v2, v3, v4}，E={(v1,v2) , (v1,v3) , (v1,v4) , (v2,v3) , (v3,v4)}，试（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形。
参考答案：
（1）G的图形表示
（2）邻接矩阵
（3）每个结点的度数
Deg(v1)=3
Deg(v2)=2
Deg(v3)=3
Deg(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的最优二叉树,并计算该最优二叉树的权．
参考答案：
最优二叉树的权为1×3+2×3+3×2+3×2+4×2=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)P(x, y)→( z)Q(x, y, z)，试
（1）写出量词的辖域；
（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)中的x

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。