离散数学形成性考核作业4离散数学综合练习书面作业

离散数学形成性考核作业4

姓 名： 学 号： 得 分： 教师签名： 离散数学综合练习书面作业

要求：学生提交作业有以下三种方式可供选择：

1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有

解答过程，完成作业后交给辅导教师批阅．

2. 在线提交word文档．

3. 自备答题纸张，将答题过程手工书写，并拍照上传．

一、公式翻译题

1．请将语句“小王去上课，小李也去上课．”翻译成命题公式．

设Ｐ：小王去上课 Ｑ:小李去上课 则：命题公式Ｐ∧Ｑ

2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．

设Ｐ：他去旅游

Ｑ：他有时间

则命题公式为Ｐ→Ｑ

3．请将语句 “有人不去工作”翻译成谓词公式．

设Ａ（x）:x是人 Ｂ（x）：去工作

则谓词公式为 ?x（A(x)∧－B（x）)

1

4．请将语句“所有人都努力学习．”翻译成谓词公式． 设A（x）: x是人 B（x）:努力学习

则谓词公式为 ?x（A（x）∧B（x））

二、计算题

1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算 （1）(A?B)； （2）(A∩B)； （3）A×B．

解：

（1） （A-B）＝{{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={|x?A，y?A且x+y?4}，S={|x?A，y?A且x+y<0}，试求R，S，R?S，S?R，R-1，S-1，r(S)，s(R)．

解：

R＝{<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>} S=空集 R?S=空集 S?R =空集

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的最大元、最小元．

2

4．设G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试

(1) 给出G的图形表示； (2) 写出其邻接矩阵； (3) 求出每个结点的度数； (4) 画出其补图的图形．

答：（1）

（2）

（3）

deg(v1)=1, deg(v2)=2 ,deg(v3)=4 ,deg(v4)=3,deg(v5)=2

(4)

3

5．图G=，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试

（1）画出G的图形； （2）写出G的邻接矩阵； （3）求出G权最小的生成树及其权值．

解： （1）

（2）

（3）

其中权值是：7

6．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．

解：

4

权值：65

7． 求P?Q?R的析取范式，合取范式、主析取范式，主合取范式． 解：

5