离散数学下载作业
教师沟通后选择：
1.将此次作业用A4纸打印出来，手工书
写答题，字迹工整，解答题要有解答过程，完
成作业后交给辅导教师批阅.
2.在线提交word文档.
3.自备答题纸张，将答题过程手工书写，并拍照上传.
一、公式翻译题(每小题4分，共16分)
1.将语句“我会英语，并且会徳语.”翻译成命题公式.
答：设P：我会英语Q：我会徳语
则命题公式为PAQ
2.将语句“如果今天是周二，则昨天是周二.”翻译成命题公式. 答：设P：今天是周三
Q：昨天是周二
则命题公式为：PQ
3.将语句“C3次列车每天上午9点发车或者10点发车”翻译成命题公式.
答：设P： C3次列车每天上午9点发车
Q： C3次列车每天上午10点发车
则命题公式为：「(P—Q)
4.将语句“小王是个学生，小李是个职员，而小张是个军人.”翻译成命题公式. 答：
设：P：小王是个学生Q：小李是个职员R：小张是个军人
则命题公式为：PAQAR
二、计算题(每小题12分，共84分)
1.设集合A={{a],a,h ). B={a, {Z?})，试计算
(1)ACB：(2)AUB；(3) A-(AC8)
答：(l)Ac8 ={a}
(2)AuB=({a).a.b{b)|
<3) A-(Anfi)=({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)求出8的最大元、极大元、最小上界.
答：（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>, r=(v b %, %, E=((vi,%), , (Vi,%), (%,%), (%,%)}»
试
(】)给出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)其补图的图形
v1 ,4
v2 v3
4.求的合取范式与主析取范式.
答：P-(QAR)
=1 PV(QAR)
=(1 PVQ) A (-1 PVR)合取范式
=(-1 PVQ) V (RAn R) A (-1 PVR)
=(-1 PVQ) V (RA-i R) A <-i PVR) V (QAq Q)
=(-1 PVQVR) A (-1 PVQVn R) A(i PVn QVR)主合取范式
=<-i PA-i QAn R) V (-1 PA-i QAR) V(i PAn QAq R)(i PAQAR) V (PAn
QAR) V (PAQA-i R) V (PAQAR)主析取范式
5.试画一棵带权为1,2, 3, 3,4的最优二叉树，并计算该最优二叉树的权.
最优二义树的权为 1 X 3+2 X 3+3 X 2+3 X 2+4 X 2=29
6.试利用Kruskal算法求出如下所示賦权图中的最小生成树(要求写出求解步骤)，并求此最小生成树的权.
答：W(v2, v6)=l，选(v2,v6)
W(v4, v5)=l，选(v4, v5)
二叉树公式W(vl, v6)=2，选(vl,v6)
W(v3, v5)=2，选(v3, v5)
W(v2, v3)=4，选(v2, v3) 最小生成树，如图
生成树的权 W(T) =1+1+2+2+4=10
7.设谓词公式(女)胎,y)一(Vz)2U, y, z)，试
(1)写出量词的辖域； (2)指出该公式的自由变元和约束变元. 答：(1) 3x 的辖域为
P(x,y)f VzQ(x, y, z)
▼z的辖域为Q(x, y, z)
<2)自由变元
P(x, y)-VzQ(x, y, z)中的 y 约束变元
P(x,y)-VzQ(x, y, z)中的 x

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