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

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

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

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

（）．

A．{1,2}ÎA

B．{1,2,3

}

Í

A

C．{1,2,3

}A

D．{1,2,3}ÎA

2．已知无向图G的结点度数之和为10，则G的边数为（）．

A．10

B．20

C．30

D．5

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

A.5

B.10

C.9

D.12

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）

ES（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（y）

US（1）．

D．(1)

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

前提引入

(2)

F（y）→G（x）

ES（1）．

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

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

a,b,c

}，则A´B的元素个数为

．

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

．

8．设无向图G中存在欧拉路，则G的奇数度数的结点数为

．

9．设G是有10个结点的连通图，边数为20，则可从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分）

b

c

d

a

15．设关系R的关系图如下，试

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

（2）判断R是否为等价关系，并说明理由．

16．设图G=，V={

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

(v1,v2)，(v1,v4)，(v2,v4)}，试

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

（2）写出其邻接矩阵；

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

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

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

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

18．对任意集合A，B和C，试证明A´

（BÈC)

=（A´

B)

È

（A´

C)．

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

参考解答

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

1．B

2．D

3．C

4．C

5．A

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

6．6

7．n(n-1)/2

8．两个或零个

（注：答“两个”也给3分）

9．11

10．A(1)

∧A(2)

∧

A(3)

∧

A(4)

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

11．设P：小明是个学生．

（2分）

则命题公式为：P．

（6分）

12．设P：他上午去教室上课，Q：他下午去体育馆参加比赛．

（2分）

则命题公式为：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,b

>,<

b,a

>,<

a,c

>,<

c,a

>,<

c,d

>,<

d,c

>}．

（4分）

（2）不是等价关系

（8分）

因为该关系不满足自反性（或答：不满足传递性）

（12分）

16．解：（1）关系图

（3分）

（2）邻接矩阵

（6分）

（3）deg(v1)=2

deg(v2)=2

deg(v3)=0

deg(v4)=2

（9分）

（4）补图

（12分）

17．解：ØP∨(Q∧R)

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

合取范式

（2分）

Û(ØP∨Q)

∨(R∧ØR)

∧

(ØP∨R)

（5分）

Û(ØP∨Q)

∨(R∧ØR)

∧

(ØP∨R)

∨(Q∧ØQ)

（7分）

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

∧

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

（10分）

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

主合取范式

（12分）

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

18．证明：设S=

A´

（BÈC)，T=（A´

B)

È

（A´

C)，若∈S，则有x∈A且y∈（BÈC)，即x∈A且y∈B或y∈C，（1分）

即有

x∈A且y∈B，或x∈A且y∈C，（2分）

可得∈（A´

B)，或∈（A´

C)，（3分）

则有∈（A´

B)

È

（A´

C)，即

∈T，（4分）

所以SÍT．

（5分）

反之，若∈T，则有∈（A´

B)，或∈（A´

C)，则有x∈A且y∈B，或x∈A且y∈C，即有x∈A且y∈B或y∈C，（6分）

则有x∈A且y∈（BÈC)，即有∈S，所以TÍS．

（7分）

得证

A´

（BÈC)=（A´

B)

È

（A´

C)．

（8分）