2024年秋季离散数学综合考试

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

姓 名: 严先贵 学 号1944201250206 得 分: 教师签名: 离散数学综合练习书面作业

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

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)(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＞

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

解: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〉}

4.设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 ) 关系R的哈斯图

8 4 6 3 2 7 1 5

(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) v2 ?

? v3

? v4

v1 ?

? v5

(2) 邻接矩阵为

?0??0?1??0?0?

0100??0110?1011?

?1101?0110??(3) v1结点度数为1,v2结点度数为2,v3结点度数为3,v4结点度数为2,v5结点度数为2

(4) 补图图形为

? v3

v2 ? v1 ? ? v5

? v4

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)G的图形如下:

(2)写出G的邻接矩阵