离散数学（本）2017年3月份试题（含答案）

离散数学（本）2017年1月份试题

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

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

（）．

A．2ÎA

B．{1,2}ÌA

C．{1,2}ÍA

D．ÆÎA

2．设A={1,2,3｝，B

={1,2,3,4}，A到B的关系R

={

|

x大于y｝，则R

=

（）．

A．{<1,1>,<2,1>}

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

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

>}

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

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

A．20

B．10

C．21

D．19

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

A．r

+

v

e

=2

B．v

+

e

r=4

C．v

+

e

r=2

D．v

+

e

–

r

=

–

5．设个体域D是实数集合，则命题($x)(“y)(x´y

=

y)的真值是（）．

A．不确定

B．

F

C．由y的取值确定

D．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(g°

f)等于

．

8．结点数相等与边数相等是两个图同构的条件．

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

-S中的连通分支数不超过

．

10．设个体域D＝{a,b,c}，则谓词公式($x)P(x)消去量词后的等值式为

．

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

11．将语句“小李前天去工厂劳动，昨天休息．”翻译成命题公式．

12．将语句“如果他去开会，则我去开会．”翻译成命题公式．

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

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

14．($x)(P(x)→Q(y)∧R(z))中的约束变元为y．

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

15．设A={1，2，3}，R={|xÎA，yÎA且x

+y

>4}，S={|xÎA，yÎA且x

16．设图G=，其中，结点集V={a,b,c,d,e}，边集E={

(a,b),(a,c),(a,e),(b,c),(b,d),(b,e),(c,e),(d,e)

}，对应边的权值依次为1、1、3、2、3、6、1及5，请画出G的图形、写出G的邻接矩阵并求出G权最小的生成树及其权值．

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

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

18．试证明：P→Q

Þ

P→(P∧Q)

．

离散数学（本）2017年3月份试题解答

(供参考)

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

1．D

2．C

3．B

4．A

5．D

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

6．{

a,b

}

7．{2，3}

8．必要

9．4

10．P(a)

∨P(b)

∨

P(c)

三、逻辑公式翻译（每小题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))中的y是自由变元，约束变元为x．

（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分）

说明：对于每一个求解项，如果基本求出了解，可以给对应1分．

16．解：G的图形表示为：

（3分）

邻接矩阵：

（6分）

粗线表示最小的生成树：

（9分）

权为6

（12分）

17．（10分）

权为2´3+2´3+2´2+3´2+4´2=30

（12分）

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

18．证明：

（1）P→Q

P

（1分）

（2）P

P（附加前提）

（3分）

（3）Q

T（1）（2）I

（5分）

（4）P∧Q

T（2）（3）I

（7分）

（5）P→(P∧Q)

CP规则

（8分）

说明：1．因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分．

说明：2．另证如下：

设P→(P∧Q)为F，（1分）

则P为T，P∧Q为F．

（3分）

所以P为T，Q为F，（5分）

从而P→Q也为F．

（7分）

所以P→QÞP→(P∧Q)．

（8分）

说明3：可以用真值表验证．