.
离散数学形成性考核作业4
姓 名: 学 号: 得 分: 教师签名: 离散数学综合练习书面作业
要求:学生提交作业有以下三种方式可供选择:
1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有
解答过程,完成作业后交给辅导教师批阅.
2. 在线提交word文档.
3. 自备答题纸张,将答题过程手工书写,并拍照上传. 一、公式翻译题
1.请将语句“小王去上课,小李也去上课.”翻译成命题公式. 设P:小王去上课。 Q: 小李去上课。
则P^Q
2.请将语句“他去旅游,仅当他有时间.”翻译成命题公式.
设P:他去旅游。 Q: 他有时间。
则P→Q
3.请将语句 “有人不去工作”翻译成谓词公式. 设A(x): x是人 B(x):去工作
?x(A(x)^?B(x))
4.请将语句“所有人都努力学习.”翻译成谓词公式. 设A(x): x是人 B(x):努力工作 ?x(A(x)^B(x))
精选文档
.
二、计算题
1.设A={{1},{2},1,2},B={1,2,{1,2}},试计算 (1)(AB); (2)(A∩B); (3)A×B.
解:(1)(AB)={{1},{2}} (2)(A∩B)={1,2} (3) A×B
{<{1},1>,<{1},2>,<{1},{1,2 }>,<{2},1>,<{2},2>,<{2},{1,2 }>,<1,1>,<1,2>,<1,{1,2 }>,<2,1>,<2,2>,<2,{1,2 }>}
2.设A={1,2,3,4,5},R={
R={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>} S=Φ RS=Φ SR=Φ
R-1={<1,1>,<2,1>,<3,1>,<1,2>,<2,2>,<1,3>} S-1=Φ
r(S)= {<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}
s(R)= {<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}
3.设A={1, 2, 3, 4, 5, 6, 7, 8},R是A上的整除关系,B={2, 4, 6}.
(1) 写出关系R的表示式; (2) 画出关系R的哈斯图; (3) 求出集合B的最大元、最小元.
解:(1)
R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<1,8>,<2,2>,<2,4>,<2,6>,<2,8>,<3,3>,<3,6>,<4,4>,<4,8>,<5,5>,<6,6>,<7,7>,<8,8>}
(2)
8
4 6 2 3 7
5
1 关系R的哈斯图
(3) 集合B没有最大元,最小元是2
4.设G=
精选文档
.
(v3,v4),(v3,v5),(v4,v5) },试
(1) 给出G的图形表示; (2) 写出其邻接矩阵; (3) 求出每个结点的度数; (4) 画出其补图的图形.
解:(1) v1°
v2
° °v3
v4° °v5
?0?0?(2) A(D)??1??0??0
0100?0110??1011?
?1101?0110??(3) deg(v1)?1、deg(v2)?2、deg(v3)?4、deg(v4)?3、deg(v5)?2
(4) °v1
v2° °v3
v4° °v5
5.图G=
精选文档
.
(b, d), (b, e), (c, e), (c, d), (d, e) },对应边的权值依次为2、1、2、3、6、1、4及5,试
(1)画出G的图形; (2)写出G的邻接矩阵; (3)求出G权最小的生成树及其权值. b c
解:(1) 。 。
2 1 a。 6 4 2 1 3 。 。 e 5 d
?0?1?(2) A(D)??1??0??1
1101?0011??0011?
?1101?1110??(3) b c 。 。
2 1 a。 1 3 。 。 e d 其权值为:7
精选文档
.
6.设有一组权为2, 3, 5, 7, 17, 31,试画出相应的最优二叉树,计算该最优二叉树的权.
解: 65
17 48
5 12
17 31
2 3 5 7
权值为65。
7. 求PQR的析取范式,合取范式、主析取范式,主合取范式.
解:┐P(Q∨R)= ┐PQ∨R 所以合取范式和析取范式都是┐PQ∨R
所以主合取范式就是┐P
Q∨R
所以主析取范式就是(PQ R) (
PQ R) (PQ(PQ R) (PQ R) (P
Q R) (PQ R)
8.设谓词公式(?x)(P(x,y)?(?z)Q(y,x,z))?(?y)R(y,z). (1)试写出量词的辖域;
(2)指出该公式的自由变元和约束变元.
解:(1)量词x的辖域为 P(x,y) (z)Q(y,x,z) 量词z的辖域为Q(y,x,z) 量词y的辖域为R(y,x)
(2) P(x,y)中的x是约束变元,y是自由变元
Q(y,x,z)中的x和z是约束变元,y是自由变元 R(y,x)中的x是自由变元,y是约束变元
精选文档
R)
离散数学形成性考核作业4
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)