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

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

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

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

（）．

A．{

2,3

}ÎA

B．A

Í{1,2,3,4}

C．{1,2,3,4

}ÍA

D．1ÎA

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

A．10

B．20

C．30

D．5

3．无向图G是棵树，结点数为10，则G的边数为（）．

A．

B．

C．

D．

4．设A（x）：x是人，B（x）：x是学生，则命题“有的人是学生”可符号化为（）．

A．┐(“x)(A(x)

→B(x))

B．

(x)(A(x)∧B(x))

C．(x)(A(x)∧B(x))

D．┐(x)(A(x)∧┐B(x))

5．下面的推理正确的是（）．

A．(1)

（“x）F（x）→G（x）

前提引入

(2)

F（y）→G（y）

US（1）．

B．(1)

（$x）F（x）→G（x）

前提引入

(2)

F（y）→G（y）

US（1）．

C．(1)

（$x）(F（x）→G（x））

前提引入

(2)

F（y）→G（x）

ES（1）．

D．(1)

（$x）（F（x）→G（x））

前提引入

(2)

F（y）→

G（y）

ES（1）．

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

6．设A={1，2}，B={1，2，3

}，则A到B上不同的函数个数为

．

7．有n个结点的无向完全图的边数为

．

8．若无向图G中存在欧拉路但不存在欧拉回路，则G的奇数度数的结点有

个．

9．设G是有10个结点的无向连通图，结点的度数之和为30，则从G中删去

条边后使之变成树．

10．设个体域D＝{1,2,3,4}，则谓词公式($x)A(x)消去量词后的等值式为

．

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

11．将语句“昨天下雨”翻译成命题公式．

12．将语句“小王今天上午或者去看电影或者去打球”翻译成命题公式．

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

13．存在集合A与B，使得AÎB与AÍB同时成立．

14．完全图K4是平面图．

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

15．设偏序集的哈斯图如下，B为A的子集，其中B={

b,c

}，试

（1）写出R的关系表达式；

（2）画出关系R的关系图；

（3）求出B的最大元、极大元、上界．

16．．设图G=，V={

v1，v2，v3，v4，v5}，E={

(v1,v2)，(v1,v4)，(v1,v5)，(v2,v3)，(v3,v5)

}，试

（1）画出G的图形表示；

（2）写出其邻接矩阵；

（3）求出每个结点的度数；

（4）画出图G的补图的图形．

17．求P→（Q∧R）的合取范式与主合取范式．

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

18．设A，B，C是任意集合，试证明：若A´A=B´B，则A=B．

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

(供参考)

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

1．A

2．A

3．C

4．B

5．D

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

6．9

7．n(n-1)/2

（或C2n）

8．2

9．6

10．A(1)

∨A(2)

∨

A(3)

∨

A(4)

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

11．设P：昨天下雨．

（2分）

则命题公式为：P．

（6分）

12．设P：小王今天上午去看电影

Q：小王今天上午去打球

（2分）

则命题公式为：Ø（P↔Q）．

或者（ØP∧Q）∨（P∧ØQ）

（6分）

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

13．正确．

（3分）

例：设A={a}，B={a，{a}}

（5分）

则有AÎB且AÍB．

（7分）

说明：举出符合条件的例均给分．

14．正确．

（3分）

完全图K4是平面图，（5分）

如K4可以如下图示嵌入平面．

（7分）

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

15．（1）R={<

a,a

>,<

b,b

>,<

c,c

>,<

d,d

>,<

a,b

>,<

a,c

>,<

a,d

>,<

b,d

>}．（4分）

（2）关系图

（8分）

（3）集合B无最大元，极大元为b与c、无上界

（12分）

16．解：

（1）关系图

（3分）

（2）邻接矩阵

（6分）

（3）deg(v1)=3

deg(v2)=2

deg(v3)=2

deg(v4)=1

deg(v5)=2

（9分）

（4）补图

（12分）

17．P→（Q∧R）

ÛØP∨(Q∧R)

（2分）

Û(ØP∨Q)∧(ØP∨R)

合取范式

（5分）

Û(ØP∨Q)

∨(R∧ØR)

∧

(ØP∨R)

（7分）

Û(ØP∨Q)

∨(R∧ØR)

∧

(ØP∨R)

∨(Q∧ØQ)

（9分）

Û(ØP∨Q∨R)∧(ØP∨Q∨ØR)

∧

(ØP∨R∨Q)∧(ØP∨R∨ØQ)

（11分）

Û(ØP∨Q∨R)∧(ØP∨Q∨ØR)∧(ØP∨ØQ∨R)

主合取范式

（12分）

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

18．证明：

设xÎA，则ÎA´A，（1分）

因A´A=B´B，故ÎB´B，则有xÎB，（3分）

因此AÍB．

（5分）

设xÎB，则ÎB´B，（6分）

因A´A=B´B，故ÎA´A，则有xÎA，因此BÍA．

（7分）

故得A=B．

（8分）