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

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

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

1．若集合A={1，2}，B={1，{1，2}}，则下列表述正确的是（）．

A．AÌB

B．AÎB

C．AÏB

D．BÌA

2．设A＝｛1,3,5｝，B={2,4,6}，A到B的关系R＝｛〈x,y〉|

x+1=y｝，则R=

（）．

A．

Æ

B．

{<2,1

>,<4,3>,<6,5>}

C．

{<1,2>,<3,4>,<5,6>}

D．

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

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

A．

B．

C．

D．

4．命题“4是偶数或-3是负数”的否定是（）。

A.4不是偶数或-3不是负数

B.4不是偶数且-3不是负数

C.4不是偶数或-3是负数

D.4是偶数且-3不是负数

5．设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))

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

6．设集合A={1,2}，B={2,3}，C={3,4,5}，则A–（B∪C）等于

．

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

f)等于

．

8．若图G=，其中V={

a,b,c,d

}，E={

(a,b),(a,d),(b,c),(b,d)}，则该图中的割点为

．

9．设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v，e和r满足的关系式

．

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

．

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

11．将语句“小明去学校了，而且小亮也去学校了．”翻译成命题公式．

12．将语句“如果天晴，我们就去比赛．”翻译成命题公式．

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

13．若图G是一个欧拉图，则图G中存在欧拉路．

14．若无向图G的结点数比边数多1，则G是树．

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

15．设集合A={1,2,3,4}，R={<1，2>,<3，4>}，S={<1，1>,<2，2>}，试计算

（1）R·S；

（2）R

-1；

（3）s（R）．

16．图G=，其中V={

a,b,c,d,e

}，E={

(a,b),(a,c),(a,d),(b,c),(b,d),(c,d),(c,e),(d,e)}，对应边的权值依次为2、3、4、5、6、7，3及2，试画出G的图形，写出G的邻接矩阵，并求出G权最小的生成树及其权值．

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

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

18．试证明集合等式AÇ

(BÈC)=(AÇB)

È

(AÇC)．

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

参考解答

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

1．B

2．C

3．D

4．B

5．A

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

6．{1}

7．{3，4}

8．b

9．v-e+r=2

10．真（或T，或1）

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

11．设P：小明去学校了，Q：小亮去学校了．

（2分）

则命题公式为：P∧Q．

（6分）

12．设P：天晴，Q：我们去比赛．

（2分）

则命题公式为：P→Q．

（6分）

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

13．正确．

（3分）

理由：按定义知道，若图G是一个欧拉图，则G中存在欧拉回路，（5分）

又因为，欧拉回路也是欧拉路，所以，满足题中条件的图G存在欧拉路．

（7分）

14．错误．

（3分）

反例：如图G的结点数比边数多1，但不是树．

（7分）

说明：按定义有：无向图G是树当且仅当无向图G是连通图且结点数比边数多1．

或举出符合条件的反例均给分．

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

15．（1）R·S

=={<1，2>}；

（4分）

（2）R

-1={<2，1>,<4，3>

}；

（8分）

（3）s（R）={<1，2>,<3，4>,<2，1>,<4，3>

}

（12分）

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

（3分）

（2）邻接矩阵：

（6分）

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

权值为10

（12分）

17．（P∨Q）→R

ÛØ（P∨Q）∨R

（2分）

Û(ØP∧ØQ)∨R

析取范式

（5分）

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

（7分）

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

∧

(ØQ∨R)

（9分）

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

∧

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

（10分）

Û(ØP∨R

∨Q)

∧

(ØP∨R

∨ØQ)

∧

(ØQ∨R∨P)

∧

(ØQ∨R∨ØP)

（11分）

Û

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

主合取范式

（12分）

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

18．证明：

设S=A∩(B∪C)，T=(A∩B)∪(A∩C)，若x∈S，则x∈A且x∈B∪C，(1分)

即

x∈A且x∈B

或

x∈A且x∈C，(2分)

也即x∈A∩B

或

x∈A∩C，（3分）

即

x∈T，所以SÍT．

（4分）

反之，若x∈T，则x∈A∩B

或

x∈A∩C，（5分）

即x∈A且x∈B

或

x∈A且x∈C

（6分）

也即x∈A且x∈B∪C，即x∈S，所以TÍS．

（7分）

因此T=S．

（8分）

另，可以用恒等式替换的方法证明．