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

离散数学形成性考核作业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))

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>}

2

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)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）

v1 ?

v2 ?

? v3

3

? v5

? v4

(2) 邻接矩阵为

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

0011011011011010??0?1? ?1?0??(3) v1结点度数为1，v2结点度数为2，v3结点度数为3，v4结点度数为2，v5结点度数为2

(4) 补图图形为

v1 ? v2 ? ? v3

4

? 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的邻接矩阵

（3）G权最小的生成树及其权值

5