2020电大-离散数学-形考综合练习-答案

离散数学形成性考核作业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．请将语句“所有人都努力学习．”翻译成谓词公式．

答：

1

设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

(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的哈斯图为：

abcgdhef

(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）G的图形为：

V1V2V5V2（2）邻接矩阵为： （4）补图为：

V1V5V3V4V3V4

（3）v1结点度数为1，v2结点度数为2，

v3结点度数为3，v4结点度数为2，v5结点度数为2：

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权最小的生成树及其权值．

3

解：

（1）G的图形： （2）邻接矩阵： （3）最小生成树及权值

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

解：二叉树如下（方形为已给定权）：

61303117171075523 权：2*5+3*5+5*4+7*3+17*2+31=131

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

解：

P?Q?R ??R?Q?R 取范式、合取范式、主合取范式都为：?R?Q?R 主析取范式为：（?P??Q??R)?(?P??Q?R)?(?P?Q??R) ?(?P?Q?R)?(P??Q?R)?(P?Q??R)?(P?Q?R)

4

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,z)

（2）P(x,y)中的x是约束变元，y是自由变元

Q(y,x,z)中的x和z是约束变元，y是自由变元R(y,z)中的z是自由变元，y是约束变元

9．设个体域为D={a1, a2}，求谓词公式(?y)(?x)P(x,y)消去量词后的等值式；

答：

(?y)(?x)P(x,y) =?xP(x, a1)??xP(x, a2) = (P(a1,a1)?P(a2,a1))?(P(a1,a2)?P(a2,a2))

三、证明题

1．对任意三个集合A, B和C，试证明：若A?B = A?C，且A??，则B = C．

证明：

(1)对于任意∈A×B,其中a∈A,b∈B,因为A×B= A×C,必有∈A×C,其中b∈C因此B?C

(2)同理,对于任意∈A×C,其中,a∈A,c∈C,因为A×B= A×C，必有∈A×B,其中c∈B,因此C?B 由(1)(2)，得B=C。

2．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自

5