离散数学 ( 第1次 )

第1次作业

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

1.

图G所示平面图deg(R3)为

A.

4

B.

5

C.

6

D.

3

2. 在完全m叉树中，若树叶数为t，分枝点数为i，则有（）。

A.

(m-1)i

B.

(m-1)i>t-1

C.

(m-1)i=t-1

D.

(m-1)i≤t-1

3.

命题a）：如果天下雨，我不去。写出命题a）的逆换式。

A.

如果我不去，天下雨。

B.

如果我去，天下雨。

C.

如果天下雨，我去。

D.

如果天不下雨，我去。

4. 设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点（）

A.

5

B.

4

C.

2

D.

6

5. 假设A={a,b,c,d},考虑子集S={{a,b},{b,c},{d}}，则下列选项正确的是（）。

A.

S是A的覆盖

B.

S是A的划分

C.

S既不是划分也不是覆盖

D.

以上选项都不正确

6. 没有不犯错误的人。M(x)：x为人。F（x）：x犯错误。则命题可表示为（）。

A.

(?x)(M(x)→F(x)

B.

(?x)(M(x)?F(x)

C.

（?x）(M(x)?F(x))

D.

(?x)(M(x)→F(x)

7. 命题逻辑演绎的CP规则为（）

A.

在推演过程中可随便使用前提

B.

在推演过程中可随便使用前面演绎出的某些公式的逻辑结果

C.

如果要演绎出的公式为B→C形式，那么将B作为前提，演绎出C D.

设?(A)是含公式A的命题公式，B<=>A，则可以用B替换?(A)中的A

8. 设G是有6个结点的完全图，从G中删去（）条边，则得到树。

A.

6

B.

9

C.

10

D.

9. 设A、B两个集合，当（）时A-B=B。

A.

A=B

B.

A?B

C.

B?A

D.

A=B=?

10. 设U={1，2，3，4，5}，A={2，4}，B={4，3，5}，C={2，5，3}，确定集合(A-C)-B = （）。

A.

{1,4}

B.

{2,3,4,5}

C.

{4}

D.

?

11. 下图的最小生成树的权为（）。

A.

40

B.

44

C.

48

D.

52

12.

对偶式为P↑Q表达式是。

A.

P∧Q

B.

P↓Q

C.

P∨Q

D.

P→Q

13. 下列语句是命题，并且真值为0的是（）

A. 雪式白的。

B.

1+2>4。

C.

天气真好啊！

D.

我正在说谎。

14. 如果有限个数的乘积为零，那么至少有一个因子等于零。N(x)：x是有限个数的乘积。Z(y)：y为0。P（x）：x的乘积为0 。F（y）：y为乘积中的一个因子则命题可表示为（）。

A.

(?x)(N(x)→P(x)∧(?y)(F(y)?(Z(y)))

B.

(?x)(N(x)?P(x))→(?y)(F(y)?(Z(y)))

C.

(?x)(N(x)→P(x)∧(?y)(F(y)→(Z(y)))

D.

(?x)(N(x)→P(x)∧(?y)(F(y)?(Z(y)))

15. 设A、B、C是任意集合，判断下述论断是否正确，并将正确的题号填入括号内（）。

A.

若A∪B=A∪C，则 B=C

B.

若A∩B=A∩C ，则 B=C

C.

若A-B=A-C，则 B=C

D.

若～A=～B，则 A=B

二、多项选择题（本大题共20分，共 5 小题，每小题 4 分）

1.

两个命题变元P和Q生成的4个小项为：。

A.

P∧Q

B.

┐P∧Q

C.

P∧┐Q

D.

┐P∧┐Q

2.

下图是（）。

A.

是强连通的

B.

是弱连通的

C.

是单侧连通的

D.

是不连通的

3.

下列说法正确的是（）

A.

设是整数加法群，令f: n→-n,? n∈Z，则f是Z的一个自同构映射。

B.

设G是一个Abel群，令 f: a〖→a〗^(-1) (? a∈G)，则f是G的一个自同构映射。

C.

设是实数乘法群，是实数加法群，令f: x→5x，则f是R的一个满同态映射

D.

A、B、C都是正确的。

4.

函数f：R×R→R×R,f()=是( )函数。

A.

入射

B.

满射

C.

双射

D.

以上答案都不对

5.

设A={1,2,3}，则集合A上的关系R={<1,1>,<1,3>,<2,1>,<2,3>}是（）关系；

A.

自反

B.

反自反

C.

不是自反

D.

不是反自反

三、判断题（本大题共20分，共 10 小题，每小题 2 分）

1. 判断对错：集合{2,3,4，???}是无限集（）。

2. 设G是一个联结词的集合，若任意一个命题公式都可用G中联结词构成的公式来表示，则称G为最小联结词组。

3. 公式?xP(x)→?yQ(x,y)的前束范式是?x?y(P(x)→Q(x,y)。

4. 判断对错。一个谓词公式wff A,如果在一种赋值下为假，则称该wff A为不可满足的。

5. 下图中（c）和（d）是根树

6. 设f∶{x,y}→{1,3,5} 定义为f(x)=1,f(y)=5，则这个函数是入射函数。

7. 设集合A={216，243，357，648}.定义A上的关系 R={〈x,y〉|x,y∈A，且x与y中至少有一个相同数字}。则R是A上的一个相容关系，R不是等价关系。

8. 自反（对称、传递）闭包是包含R的最小自反（对称、传递）关系。（）

9. 设X={1,2,3,4},Y={1,2,3,4,5},Z={1,2,3}, f:X→Y,f={,,,},

g:Y→Z,g={,,,,}，则g°f={,,,}。

10. 设R是由A={1,2,3,4} 到B={2,3,4} 的关系，S是由B到C={3,5,6}的关系，分别定义为：R={│a+b=6}={,,} S={│b整除c}={,,} 于是复合关系R°S={,,}。

四、计算题（本大题共20分，共 4 小题，每小题 5 分）

1.

设f,g均为实函数，f(x)=2x+1 , g(x)=x^2+1。求

f°g , g°f , f°f , g°g 。

2.

设集合A={1,2,3,4}，A上的二元关系R={(x,y)|x,y∈A,且x≥y},求R的关系图与关系矩阵

3.

试将公式P∧（P→Q）化为析取范式和合取范式：

4.

设全集合E={a，b，c，d，e}，A={a，d}，B={a，b，e}，C={b，d}，求下列集合：

(1)A∩～B；（2）（A∩B）∪～C；

（3）～A∪（B－C）；（4）ρ(A)∩ρ(B)

五、证明题（本大题共10分，共 2 小题，每小题 5 分）

1.

符号化下列命题并推证其结论：

科学家都是勤奋的。每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以存在着事业获得成功的人或事业半途而废的人。

2.

设整数集Z上的二元关系R定义如下：R={|x,y∈Z,(x-y)/2是整数，证明R在Z上是自反的。