《电大1009-离散数学2015年10月份试题-开放本科期末考试试卷》

一、单项选择题（每小题3分，本题共15分）

1．若集合A＝{1,2,3}，则下列表述正确的是()．

A．{1}AB．{1}A

C．{1,2,3}AD．A

2．设A={1,2,3｝，B={1,2,3,4}，A到B的关系R={<x,y>|x大于y｝，则R=()．

A．{<2,1>,<3,1>,<3,2>}B．{<1,1>,<1,2>,<1,3>,<1,4>,<1,5>}

C．{<1,1>,<2,1>}D．{<1,2>,<2,3>}

3．无向图G的结点的度数之和是10，则图G的边数为（）．

A．10B．15

C．20D．5

4．设连通平面图G有v个结点，e条边，r个面，则（）．

A．v+e-r=2B．v+e-r=4

C．r+v-e=2D．v+e–r=–4

5．设个体域D是整数集合，则命题xy(xy=y)的真值是（）．

A．不确定B．由y的取值确定

C．FD．T

二、填空题（每小题3分，本题共15分）

6．设集合A={a,b,c}，B={b,c}，C={c,d}，则A∩(B∪C)等于．

7．设A={2，3}，B={1，2}，C={3，4}，从A到B的函数f={<2,2>,<3,1>}，从B到C

的函数g={<1，3>,<2，4>}，则Dom(gf)等于．

8．若图G=<V,E>，其中V={a,b,c,d}，E={(a,b),(b,c),(b,d)}，则该图中的割点

为．

9．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为4，则在G-S中

的连通分支数不超过．

10．设个体域D＝{1,2,3,4}，A(x)为“x大于5”，则谓词公式(x)A(x)的真值

为．

三、逻辑公式翻译（每小题6分，本题共12分）

11．将语句“雪是白色的，但天是蓝色的．”翻译成命题公式．

12．将语句“如果下雨，则活动取消．”翻译成命题公式．

四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）

13．集合的元素可以是集合．

14．(x)(P(x)→Q(y)∧R(z))中的自由变元为x．

五．计算题（每小题12分，本题共36分）

15．设A={1，2，3}，R={<x，y>|xA，yA且x+y>4}，S={<x，y>|xA，yA且x<y}，

试求R，S，R-1，s(S)．

1

16．图G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)}，对

应边的权值依次为2、3、4、5、6及7，试

（1）画出G的图形；

（2）写出G的邻接矩阵；

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

17．试画一棵带权为1,1,3,4,4的最优二叉树,并计算该最优二叉树的权．

六、证明题（本题共8分）

18．试证明：P∨QP→（(P∨Q)）．

2

离散数学（本）2015年10月份试题

参考解答

一、单项选择题（每小题3分，本题共15分）

1．B2．A3．D4．C5．D

二、填空题（每小题3分，本题共15分）

6．{b，c}

7．{2，3}（或A）

8．b

9．4

10．假（或F，或0）

三、逻辑公式翻译（每小题6分，本题共12分）

11．设P：雪是白色的，Q：天是蓝色的．（2分）

则命题公式为：P∧Q．（6分）

12．设P：下雨，Q：活动取消．（2分）

则命题公式为：P→Q．（6分）

四、判断说明题（每小题7分，本题共14分）

13．正确．（3分）

例：集合{{1}}中的元素{1}是集合．（7分）

14．错误．（3分）

(x)(P(x)→Q(y)∧R(z))中的约束变元为x，自由变元为y与z．（7分）

五．计算题（每小题12分，本题共36分）

15．

R={<2,3>,<3,2>,<3,3>}（3分）

S={<1,2>,<1,3>,<2,3>}（6分）

R-1={<2,3>,<3,2>,<3,3>}（9分）

s(S)={<1,2>,<1,3>,<2,3>,<2,1>,<3,1>,<3,2>}（12分）

16．（1）G的图形表示为：

a4d

3

27（3分）

6

bc

5

3

0111

1011

（2）邻接矩阵：（6分）

1101

1110

（3）粗线与结点表示的是最小生成树，

a4d

3

27（10分）

6

bc

5

权值为9（12分）

17．13

5

8

2

344

（10分）

11

权为13+13+32+42+42=28（12分）

六、证明题（本题共8分）

18．证明：

（1）P∨QP（1分）

（2）PP（附加前提）（3分）

（3）QT（1）（2）I（5分）

（4）P∧QT（2）（3）I（6分）

（5）(P∨Q)T（4）E