离散数学下载作业
在线提交word文档．
一、公式翻译题（每小题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的关系表达式；
1
2  （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 ={v 1, v 2, v 3, v 4}，E ={(v 1,v 2) , (v 1,v 3) , (v 1,v 4) , (v 2,v 3) , (v 3,v 4)}，
试
（1）给出G 的图形表示；            （2）写出其邻接矩阵；
（3）求出每个结点的度数；          （4）画出其补图的图形．
（1）G 的图形表示如图所示：
（2）邻接矩阵：
（3） deg(v 1)=3，
deg(v 2)=2，
deg(v 3)=3，
deg(v 4)=2
（4）补图如图所示：
v 1 v 2 v 3
v 4
ο ο ο ο v 3 ο  ο ο v 4
v 1 24 ο ο ο ο ο ο 12 6 36 24\ 3 v 2
3
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的最优二叉树，并计算该最优二叉树的权．
最优二叉树如图所示：
权为1⨯3+2⨯3+3⨯2+3⨯2+4⨯2=29
6．试利用Kruskal 算法求出如下所示赋权图中的最小生成树（要求写出求
解步骤），并求此最小生成树的权．
解：用Kruskal 算法求产生的最小生成树。步骤为：
w (v 2,v 6) =1，选(v 2,v 6)
w (v 4,v 5) =1，选(v 4,v 5)
w (v 1,v 6) =2，选(v 1,v 6)
w (v 3,v 5) =2，选(v 3,v 5)  w (v 2,v 3) =4，选(v 2,v 3)                                                最小生成树如图所示：
ο ο ο ο ο v 6 v 1 v 2 v 5 v 3 ο v 4
1 6
2 4 5
7 9 3 1 5 2 ο ο ο ο ο ο ο ο ο 1    2    3    3 3    4 7    6
13 5 2 ο ο ο ο ο v 6 v 1 v 2 v 5 v 3 ο v 4
1 6
2 4 5 7 9
3 1 ο
4
最小生成树的权w (T )=1+1+2+2+4=10．
7.设谓词公式(∃x )P (x , y )→(∀z )Q (x , y , z )，试
（1）写出量词的辖域；    （2）指出该公式的自由变元和约束变元．
（1）∃x 量词的辖域为),(y x P ，
∀z 量词的辖域为),,(z y x Q ,
（2）自由变元为公式中的y 与),,(z y x Q 中的x ，
约束变元为),(y x P 的x 与),,(z y x Q 中的

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