国开电大2021春离散数学形考任务4 各章综合练习 答案
一、公式翻译题（每小题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}, b , {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>,<3,3>,<6,6>,<12,12>,<24,24>,<36,36>,<2,6>,<3,6>,
<2,12>,<3,12>,<6,12>,<2,24>,<3,24>,<6,24><12,24>,
<2,36><3,36>,<6,36>,<12,36>}
（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→（R∧Q）┐P∨(R∧Q) （┐P∨Q）∧（┐P∨R） （合取范式）
P→（R∧Q）
┐P∨(R∧Q)
(┐P∧(┐Q∨Q) )∨(R∧Q)
(┐P∧┐Q)∨(┐P∧Q)∨(R∧Q)
((┐P∧┐Q)∧ (┐R∨R))∨(┐P∧Q )∨(R∧Q )
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q)∨(R∧Q) (┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨((┐P∧Q)∧(┐R∨R))∨(R∧Q)
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧Q∧R)∨(R∧Q)
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨ (┐P∧Q∧R)∨((┐P∨P)∧(R∧Q))
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧Q∧R)∨ (P∧R∧Q)（主析取范式）
5．试画一棵带权为1, 2, 3, 3, 4的最优二叉树,并计算该最优二叉树的权．
最优二叉树如图：
权为13+23+32+32+42=29
6．试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．
解：用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量词的辖域为，
z量词的辖域为,
（2）自由变元为公式中的y与中的x，
约束变元为的x与中的
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论